刘海军 蚁群算法原理及其应用

蚁群算法原理及其应用报告人：刘海军报告内容1ACO原理

2应用实例TSPMacroDorigo蚁群算法原理在自然界中，蚂蚁个体从洞穴出发寻找事物源，在找到事物之后返回蚁巢时，会在所经过的路径上留下一种称为“信息素”的物质。蚁群算法的信息交互主要是通过信息素来完成的。蚂蚁在运动的过程中，在没有“视觉”的情况下，能够感知这种物质的存在和强度。初始阶段，环境中没有信息素的遗留，蚂蚁寻找事物完全是随机选择路径，随后寻找该事物源的过程中就会受到先前蚂蚁所残留的信息素的影响，其表现为蚂蚁在选择路径时趋向于选择信息素浓度高的路径，同时信息素是一种挥发性化学物，会随着时间的推移慢慢的消逝。如果每只蚂蚁在单位距离留下的信息素相同，那对于较短路径上残留的信息素浓度就相对较高，这被后来的蚂蚁选择的概率就大，从而导致这条短路径上走的蚂蚁就越多，而经过的蚂蚁越来，该路径上残留的信息素也将更多，这样使得整个蚂蚁的集体行为构成了信息素的正反馈过程，从而找到比较短的路径。蚁群算法抽象模型蚂蚁在运动过程中根据各条路径上的信息量决定转移方向，用禁忌表来记录蚂蚁所走过的结点，其在选择过程中做动态调整。搜索过程中蚂蚁根据各条路径上的信息量和路径的启发信息来计算转移概率。为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成一次搜索循环后要对残留信息进行更新成立，因此引入信息素挥发机制，模拟人脑的记忆，会随时间的推移而逐渐淡化甚至忘记。

信息素更新机制信息素根据下式进行更新其中状态转移规则一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市s其中，S根据下列公式得到状态转移规则q是在[0,1]区间均匀分布的随机数q0的大小决定了利用先验知识与探索新路径之间的相对重要性。上述状态转移规则被称为伪随机比例规则特点：倾向于选择短的且有着大量信息素的边作为移动方向蚁群算法的应用：TSP问题TSP思路TSP思路代码（1）：数据初始化m=31;C=[13042312;36391315;41772244;37121399;34881535;33261556;32381229;41961004;4312790;4386570;30071970;25621756;27881491;23811676;1332695;37151678;39182179;40612370;37802212;36762578;40292838;42632931;34291908;35072367;33942643;34393201;29353240;31403550;25452357;27782826;23702975];Nc_max=10;alpha=1;beta=5;rho=0.5;%0<rho<1,表示路径上信息素的衰减系数Q=100;%蚂蚁释放的信息素量代码（1）：数据初始化n=size(C,1);%表示TSP问题的规模，亦即城市的数量D=ones(n,n);%记录城市之间的距离fori=1:nforj=1:nifi<jD(i,j)=sqrt((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2);endD(j,i)=D(i,j);endendeta=1./D;%启发式因子，这里设为城市之间距离的倒数pheromone=ones(n,n);%信息素矩阵,这里假设任何两个城市之间路径上的初始信息素都为1tabu_list=zeros(m,n);%禁忌表，记录蚂蚁已经走过的城市，蚂蚁在本次循环中不能再经过这些城市。%当本次循环结束后，禁忌表被用来计算蚂蚁当前所建立的解决方案，即经过的路径和路径的长度Nc=0;%循环次数计数器routh_best=zeros(Nc_max,n);%各次循环的最短路径length_best=ones(Nc_max,1);%各次循环最短路径的长度代码（2）：形成初始解whileNc<Nc_max%将m只蚂蚁放在n个城市上

rand_position=[];%[]为空矩阵

fori=1:ceil(m/n)%ceil数值函数功能为朝向无穷大方向取整

rand_position=[rand_position,randperm(n)];%p=randperm(n)返回1:n的一个随机排列

endtabu_list(:,1)=(rand_position(1:m))';%将蚂蚁放在城市上之后的禁忌表.%m只蚂蚁按概率函数选择下一座城市，在本次循环中完成各自的周游

forj=2:nfori=1:mcity_visited=tabu_list(i,1:(j-1));%已访问的城市

city_remained=zeros(1,(n-j+1));%待访问的城市

probability=city_remained;%待访问城市的访问概率

cr=1;fork=1:n%for循环用于求待访问的城市。比如如果城市个数是5，而已访问的城市city_visited=[24],则经过此for循环后city_remanied=[135]iflength(find(city_visited==k))==0%find逻辑函数功能是找出非零元素的索引号

city_remained(cr)=k;cr=cr+1;endend

代码（2）：形成初始解%状态转移规则****************************************

q0=0.5;ifrand>q0fork=1:length(city_remained)probability(k)=(pheromone(city_visited(end),city_remained(k)))^alpha*(eta(city_visited(end),city_remained(k)))^beta;%end函数终止代码块或为数组的最后一个元素的索引

position=find(probability==max(probability));to_visit=city_remained(position(1));endelsefork=1:length(city_remained)probability(k)=(pheromone(city_visited(end),city_remained(k)))^alpha*(eta(city_visited(end),city_remained(k)))^beta;endprobability=probability/sum(probability);pcum=cumsum(probability);%cumsum累积求和

select=find(pcum>=rand);to_visit=city_remained(select(1));endtabu_list(i,j)=to_visit;%**************************************************************endendifNc>0tabu_list(1,:)=routh_best(Nc,:);%将上一代的最优路径（最优解）保留下来，保证上一代中的最适应个体的信息不会丢失

end

代码（2）：形成初始解%记录本次循环的最佳路线

total_length=zeros(m,1);%m只蚂蚁在本次循环中分别所走过的路径长度

fori=1:mr=tabu_list(i,:);%取出第i只蚂蚁在本次循环中所走的路径

forj=1:(n-1)total_length(i)=total_length(i)+D(r(j),r(j+1));%第i只蚂蚁本次循环中从起点城市到终点城市所走过的路径长度

endtotal_length(i)=total_length(i)+D(r(1),r(n));%最终得到第i只蚂蚁在本次循环中所走过的路径长度

endlength_best(Nc+1)=min(total_length);%把m只蚂蚁在本次循环中所走路径长度的最小值作为本次循环中最短路径的长度

position=find(total_length==length_best(Nc+1));%找到最短路径的位置，即最短路径是第几只蚂蚁或哪几只蚂蚁走出来的

routh_best(Nc+1,:)=tabu_list(position(1),:);%把第一个走出最短路径的蚂蚁在本次循环中所走的路径作为本次循环中的最优路径

Nc=Nc+1代码（3）更新信息素delta_pheromone=zeros(n,n);fori=1:mforj=1:(n-1)delta_pheromone(tabu_list(i,j),tabu_list(i,j+1))=delta_pheromone(tabu_list(i,j),tabu_list(i,j+1))+Q/total_length(i);%total_length(i)为第i只蚂蚁在本次循环中所走过的路径长度（蚁周系统区别于蚁密系统和蚁量系统的地方）

enddelta_pheromone(tabu_list(i,n),tabu_list(i,1))=delta_pheromone(tabu_list(i,n),tabu_list(i,1))+Q/total_length(i);%至此把第i只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去

end%至此把m只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去

pheromone=(1-rho).*pheromone+delta_pheromone;%本次循环后所有路径上的信息素

tabu_list=zeros(m,n);%禁忌表清零，准备下一次循环，蚂蚁在下一次循环中又可以自由地进行选择end代码（4）输出结果position=find(length_best==min(length_best));%min找出数组中的最小元素shortest_path=routh_best(position(1),:);shortest_length=length_best(position(1));代码（5）绘制图形%绘制最短路径figure(1)%figure图形窗口控制函数功能为建立图形在句柄图形对象函数中为建立图形窗口set(gcf,'Name','AntColonyOptimization——Figureofshortest_path','Color','r')%set句柄图形对象函数功能为设置对象N=length(shortest_path);%length求向量的长度scatter(C(:,1),C(:,2),50,'filled');%绘制散点图scat