蚁群算法路径优化算法

1、以TSP为例，基本蚁群算法的具体实现步骤如下：（1）参数初始化二令时间十二0和循环複数T二山设置最大循环次数肥=0;将DL只蚂蚁置于II个元素（城市）上，令有自图上每条边（2）循环次数N十乂+1,蚂蚁的禁忌表索引号41,（4）蚂蚁数目上1女+,%】（5）蚂蚁个体根据状态转移概率公式计算的概率选择元素（城市）、i并前逬,;C-tabukDV仏仇厂*3CiXlOTAl,E否则其中，表示在t时刻蚂蚁k由元素（城市）i转移到元素（城市）j的状态转移概率。allowedk=Ctabuk表示蚂蚁k下一步允许选择的城市。a为启发式因子，表示轨迹的相对重要性,反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起

2、的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强。B为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越曲）=总大，则该状态转移概率越接近于贪心规则；nij（t）为启发函数，表达式为o式中，dij表示相邻两个城市之间的距离。（6）修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素（城市），并把该元素（城市）移动到该蚂蚁个体的禁忌表中。（7）若集合C中元素（城市）未遍历完，即km，则跳转到第（4）步，否则执行第（8）步。（8）根据公式冲=工乂更新每条路径上的信息量：ij（tn）=（1）ij（t）,J（9）若满足结

3、束条件，即如果循环次数，则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第（2）步。蚁群算法的matlab源程序1.蚁群算法主程序：main.m%functionbestroute,routelength=AntClccleartic%读入城市间距离矩阵数据文件CooCity=load（CooCity.txt）;%城市网络图坐标数据文件，txt形式给出NC=length（CooCity）;%城市个数fori=1:NC%计算各城市间的距离forj=1:NCdistance(i,j)=sqrt(CooCity(i,2)-CooCity(j,2)A2+(CooCity(i,3)-CooCity(

4、j,3)A2);endendMAXIT=10;%最大循环次数Citystart=;%起点城市编号tau=ones(NC,NC);%初始时刻各边上的信息痕迹为1rho=0.5;%挥发系数alpha=1;%残留信息相对重要度beta=5;%预见值的相对重要度Q=10;%蚁环常数NumAnt=20;%蚂蚁数量routelength=inf;%用来记录当前找到的最优路径长度forn=1:MAXITfork=1:NumAnt%考查第K只蚂蚁deltatau=zeros(NC,NC);%第K只蚂蚁移动前各边上的信息增量为零%routek,lengthk=path(distance,tau,alpha,be

5、ta,);%不靠率起始点routek,lengthk=path(distance,tau,alpha,beta,Citystart);%指定起始点iflengthkroutelength%找到一条更好的路径:routelength=lengthk;:bestroute=routek;endfori=1:NC-1%第K只蚂蚁在路径上释放的信息量deltatau(routek(i),routek(i+1)=deltatau(routek(i),routek(i+1)+Q/lengthk;%信息素更新end%deltatau(routek(NC),1)=deltatau(routek(NC),1)+

6、Q/lengthk;%endlength_n(n)=routelength;%记录路径收敛tau=(1-rho).*tau;%信息素挥发end%costtime=toc;subplot(1,2,1),plot(CooCity(bestroute,2),CooCity(bestroute,3),-*)subplot(1,2,2),plot(1:MAXIT,length_n,-*)routelength,costtime2.蚁群算法寻找路径程序：path.m%某只蚂蚁找到的某条路径routek,lengthkfunctionroutek,lengthk=path(distance,tau,alph

7、a,beta,Citystart)m,n=size(distance);ifisempty(Citystart)%如果不确定起点p=fix(m*rand)+1;%随机方式初始化起点，均匀概率elsep=Citystart;%外部给定确定起点endlengthk=0;%初始路径长度设为0routek=p;%蚂蚁路径点序列，即该蚂蚁已经过的城市集合，路径初始起点fori=1:m-1np=routek(end);%蚂蚁路径城市序号，依次经过的城市编号np_sum=0;%路由长度初始为0forj=1:mifinroute(j,routek)%判断城市节点j是否属于tabuk，即是否已经过continu

8、e;else%j为还未经过的点ada=1/distance(np,j);%预见度np_sum=np_sum+tau(np,j)Aalpha*adaAbeta;%路由表：信息痕迹、预见度endendcp=zeros(1,m);%转移概率，基于路径长度及路由表forj=1:mifinroute(j,routek)continue;elseada=1/distance(np,j);%预见度cp(j)=tau(np,j)Aalpha*adaAbeta/np_sum;%np到j的转移概率endendNextCity=nextcitychoose2(cp);%根据转移概率确定下一个城市,%直观地，取转移概率最大值方向方法