蚁群算法及案例分析.pptx

《蚁群算法及案例分析.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、蚁群算法及案例分析目录蚁群算法原理蚁群算法计算步骤TSP算例分析蚁群算法的特点及应用领域蚁群算法原理1、蚂蚁在路径上释放信息素。2、碰到还没走过的路口，就随机挑选一条路走。同时，释放与路径长度有关的信息素。3、信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时，就选择信息素浓度较高路径。4、最优路径上的信息素浓度越来越大．5、最终蚁群找到最优寻食路径。自然界中,蚁群的这种寻找路径的过程表现为一种正反馈的过程,与人工蚁群的寻优算法极为一致。如我们把只具备了简单功能的工作单元视为”蚂蚁”,那么上述寻找路径的过程可以用于解释人工蚁群的寻优过程。人工蚁群具有一定的记忆能力。它能够记忆已经访问过的

2、节点;另外,人工蚁群在选择下一条路径的时候并不是完全盲目的,而是按一定的算法规律有意识地寻找最短路径自然界蚁群不具有记忆的能力，它们的选路凭借外激素，或者道路的残留信息来选择，更多地体现正反馈的过程人工蚁群和自然界蚁群的相似之处在于,两者优先选择的都是含“外激素”浓度较大的路径;两者的工作单元(蚂蚁)都是通过在其所经过的路径上留下一定信息的方法进行间接的信息传递。蚁群算法原理开始初始化迭代次数Nc=Nc+1蚂蚁k=1蚂蚁k=k+1按照状态转移概率公式选择下一个元素修改禁忌表K>=蚂蚁总数m？按照公式进行信息量更新满足结束条件？输出程序计算结果结束YYNN蚁群算法计算步骤TSP算例分析给定n个

3、城市和两个两个城市之间的距离，要求确定一条经过各个城市一次当且仅当一次的最短路径。旅行商问题（TSP）第一步:初始化将m只蚂蚁随机放到n个城市，每只蚂蚁的禁忌表为蚂蚁当前所在城市，各边信息初始化为c。禁忌表体现了人工蚂蚁的记忆性，使得蚂蚁不会走重复道路，提高了效率。TSP算例分析第二步：构造路径在t时刻，蚂蚁k从城市i转移到城市j的概率为：是保存了每只蚂蚁k已经访问过的城市集合，是系统参数，分别表示信息素、距离对蚂蚁选择路径的影响程度。表示边L(i，j)上的信息素强度表示可根据由城市i到城市j的期望程度,可根据启发式算法具体确定,一般为。，算法演变成传统的随机贪婪算法最邻近城市被选中概率最大

4、，蚂蚁完全只根据信息度浓度确定路径，算法将快速收敛，这样构出的路径与实际目标有着较大的差距，实验表明在AS中设置=1~2，=2~5比较合适。TSP算例分析第三步：更新信息在所有蚂蚁找到一条合法路径后对信息进行更新。为信息素的挥发速率，为小于1的正数，一般取0.5。之所以这样做，其理由是一方面为了防止信息素的无穷累积，另一方面也是为了提高系统搜索更好可行解的能力，以避免叫早的失去探索新路径的能力。表示蚂蚁在本次运行中留在路径L(i,j)上的信息素强度.表示蚂蚁k放置在边上L(i,j)的信息素强度.表示蚂蚁所留轨迹为正常数（10,10000），表示第k只蚂蚁在本次周游中所走过的路径的长度和。TS

5、P算例分析第四步：输出结果若迭代次数小于预定的迭代次数且无退化行为（找到的都是相同的解）则转步骤二，否则，输出目前的最优解。m=31=1=5=0.5NC_max=200Q=100城市的数目为31个参数选取TSP算例分析%第一步：变量初始化n=size(C,1);%n表示问题的规模（城市个数）D=zeros(n,n);%D表示完全图的赋权邻接矩阵fori=1:nforj=1:nifi~=jD(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;%点i,j之间的距离elseD(i,j)=eps;endD(j,i)=D(i,j);endendEta=1./

6、D;%Eta为启发因子，这里设为距离的倒数Tau=ones(n,n);%Tau为信息素矩阵Tabu=zeros(m,n);%存储并记录路径的生成NC=1;%迭代计数器R_best=zeros(NC_max,n);%各代最佳路线L_best=inf.*ones(NC_max,1);%各代最佳路线的长度L_ave=zeros(NC_max,1);%各代路线的平均长度whileNC<=NC_max%停止条件之一：达到最大迭代次数%第二步：将m只蚂蚁放到n个城市上Randpos=[];fori=1:(ceil(m/n))Randpos=[Randpos,randperm(n)];endTabu(:,

7、1)=(Randpos(1,1:m))';%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游forj=2:nfori=1:mvisited=Tabu(i,1:(j-1));%已访问的城市J=zeros(1,(n-j+1));%待访问的城市P=J;%待访问城市的选择概率分布Jc=1;fork=1:nifisempty(find(visited==k,1))J(Jc)=k;Jc=Jc+1;endend%计