蚁群算法及MATLAB程序(详细)

1、蚁群算法介绍:(1寻找最短路径的蚁群算法来源于蚂蚁寻食的行为。蚁群寻找食物时会派出一些 蚂蚁分头在四周游荡 , 如果一只蚂蚁找到食物 , 它就返回巢中通知同伴并沿途留下 “ 信 息素” (外激素 pheromone 作为蚁群前往食物所在地的标记。信息素会逐渐挥发 , 如果两 只蚂蚁同时找到同一食物 , 又采取不同路线回到巢中 , 那么比较绕弯的一条路上信息素 的气味会比较淡 , 蚁群将倾向于沿另一条更近的路线前往食物所在地。蚁群算法设计虚 拟的“蚂蚁” , 让它们摸索不同路线 , 并留下会随时间逐渐消失的虚拟“信息素” , 根 据“信息素较浓的路线更近”的原则 , 即可选择出最佳路线 .(2

2、为了模拟实际蚂蚁的行为 , 首先引进如下记号 : 设 m 是蚁群中蚂蚁的数 , ij d (i,j=1,2,.,n表示城市 i 和城市 j 之间的距离 , ( i b t 表示 t 时刻位于城市 i 的蚂蚁的个数 , 则有 ( 1ni i m b t =å( ij t t 表示 t 时刻在城市 , i j 连线上残留的信息素。 初始时刻, 各条路径上的信息素相等, 设 ( ( 0ij c c t =为常数 。 蚂蚁 ( 1,2, , k k m =在运动过程中, 根据各条路径上的信息素决定转移方向。 ( k ij P t 表示在 t 时刻蚂蚁 k 由城市 i 转移到城市 j 的概率:

3、( ( ( , 0, k ij ij k ik ik ij k k tabu kt t t P j tabu j tabu a b a b t h t h Ïìïïïï轾 ï= 臌 íïïïïÎïîå (1其中:ij n 为先验知识或称为能见度,在 TSP 问题中为城市 i 转移到城市 j 的启发信息, 一般地取 ij ij n =, a 为在路径上残留信息的重要程度; b 为启发信息的重要程度; 与实际蚁群不同,人工蚁群系统具有记忆能

4、力, ( 1,2, , k tabu k m =用以记录蚂 蚁 K 当前所走过的城市,称为禁忌表(下一步不充许选择的城市 ,集合 k tabu 随着进 化过程进行动态调整。经过 n 个时刻,所有蚂蚁完成了一次周游,此时应清空禁忌表,将当前蚂蚁所在的 城市置入 k tabu 中准备下一次周游,这时计算每一只蚂蚁走过的路程 k L ,并保存最短路径 ( min min min , 1, , k L L L k m =。随着时间推移, 以前的信息素会逐渐消失, 用参数 1r -表示信息消失程度, 蚂蚁完 成一次循环后,各路径上信息素要根据(2式作调整:( ( ( 111ij ij ijm k ij

5、ij k t t t r t r t t t =+=-+D D =D å(2 其中, k ij t D 表示第 k 只蚂蚁在本次循环过程中留在路径 ij 上的信息素, ij t D 表示本次循环中各路径 ij 上信息素的增量。(, 1 kij t t t D +=/, 0, k Q L K ij K ijìïïíïïî如果蚂蚁 在巡回中经过 如果蚂蚁 在巡回中不经过 式中 Q 是常量, L k 表示第 k 只蚂蚁的循环路线,即如果蚂蚁经过 ij 则信息素增量 为一个常量除以蚂蚁 k 的巡回路线长, 这里信息素增量只

6、与蚂蚁巡回路线和 Q 有关系而 和具体的 d ij 无关。最后,设置周游次数计数器 NC ,当达到设定值时结束,最短路径为;( min min min 1,2, , k L L l l NC = 其蚁群算法的具体过程为 :附录functionR_best,L_best,L_ave,Shortest_Route,Shortest_Length=ACATSP(C,NC_max,m, Alpha,Beta,Rho,Q% C n个村庄的距离, n ×n 的矩阵% NC_max 最大迭代次数% m 蚂蚁个数% Alpha 表征信息素重要程度的参数% Beta 表征启发式因子重要程度的参数% R

7、ho 信息素蒸发系数% Q 信息素增加强度系数% R_best 各代最佳路线% L_best 各代最佳路线的长度%=%第一步:变量初始化n=size(C,1;%n表示问题的规模(城市个数 D=zeros(n,n;%D表示完全图的赋权邻接矩阵for i=1:nfor j=1:nD(i,j=C(i,j;D(j,i=D(i,j;endendEta=1./D;%Eta为启发因子,这里设为距离的倒数Tau=ones(n,n;%Tau为信息素矩阵Tabu=zeros(m,n;%存储并记录路径的生成NC=1;%迭代计数器R_best=zeros(NC_max,n;%各代最佳路线L_best=inf.*one

8、s(NC_max,1;%各代最佳路线的长度L_ave=zeros(NC_max,1;%各代路线的平均长度while NC<=NC_max%停止条件之一:达到最大迭代次数%第二步:将 m 只蚂蚁放到 n 个城市上Randpos=;for i=1:(ceil(m/nRandpos=Randpos,randperm(n;endTabu(:,1=(Randpos(1,1:m'%第三步:m 只蚂蚁按概率函数选择下一座城市,完成各自的周游for j=2:nfor i=1:mvisited=Tabu(i,1:(j-1;%已访问的城市J=zeros(1,(n-j+1;%待访问的城市P=J;%待访

9、问城市的选择概率分布Jc=1;for k=1:nif length(find(visited=k=0J(Jc=k;Jc=Jc+1;endend%下面计算待选城市的概率分布for k=1:length(JP(k=(Tau(visited(end,J(kAlpha*(Eta(visited(end,J(kBeta; EndP=P/(sum(P;%按概率原则选取下一个城市Pcum=cumsum(P;Select=find(Pcum>=rand;to_visit=J(Select(1;Tabu(i,j=to_visit;endendif NC>=2Tabu(1,:=R_best(NC-1,

10、:;end%第四步:记录本次迭代最佳路线L=zeros(m,1;for i=1:mR=Tabu(i,:;for j=1:(n-1L(i=L(i+D(R(j,R(j+1;endL(i=L(i+D(R(1,R(n;endL_best(NC=min(L;pos=find(L=L_best(NC;R_best(NC,:=Tabu(pos(1,:;L_ave(NC=mean(L;NC=NC+1%第五步:更新信息素Delta_Tau=zeros(n,n;for i=1:mfor j=1:(n-1Delta_Tau(Tabu(i,j,Tabu(i,j+1=Delta_Tau(Tabu(i,j,Tabu(i,

11、j+1+Q/L(i; endDelta_Tau(Tabu(i,n,Tabu(i,1=Delta_Tau(Tabu(i,n,Tabu(i,1+Q/L(i; endTau=(1-Rho.*Tau+Delta_Tau;%第六步:禁忌表清零Tabu=zeros(m,n;end%第七步:输出结果Pos=find(L_best=min(L_bestShortest_Route=R_best(Pos(1,:Shortest_Length=L_best(Pos(1subplot(1,2,1DrawRoute(C,Shortest_Routesubplot(1,2,2plot(L_besthold onplot

12、(L_avefunction DrawRoute(C,R%= % DrawRoute.m% 画路线图的子函数% R Route 路线%=N=length(R;scatter(C(:,1,C(:,2;hold onplot(C(R(1,1,C(R(N,1,C(R(1,2,C(R(N,2hold onfor ii=2:Nplot(C(R(ii-1,1,C(R(ii,1,C(R(ii-1,2,C(R(ii,2hold onend附录 2A=0 6.0 11.9 16.3 27.8 36 29.2 21.1 23.7 12.9 20.8 35.7 28 22.2 10.1 20.6 28.4 44.3

13、 31.16.0 0 5.9 10.3 20.8 29 33.1 25 17.7 19.1 27 41.8 34.2 28.2 16.1 26.6 34.4 50.3 37.111.9 5.9 0 12.2 17.8 26 35 26.9 19.6 21 28.9 43.8 36.1 34.1 22 32.5 40.3 56.2 4316.3 10.3 12.2 0 11.5 19.7 22.8 14.7 7.4 8.8 16.7 31.6 23.9 32.2 26.4 36.9 39.7 58.5 47.427.8 20.8 17.8 11.5 0 8.2 22.3 26.2 18.9 20

14、.3 28.2 32.6 35.4 43.7 37.9 48.4 51.6 70.4 58.936 29 26 19.7 8.2 0 14.1 22.2 20.3 28.5 38.3 24.4 32.1 40.4 46.1 56.6 48.3 67.1 67.129.2 33.1 35 22.8 22.3 14.1 0 8.1 15.4 16.3 24.2 10.3 18 26.3 38.4 48.9 34.2 53 59.421.1 25 26.9 14.7 26.2 22.2 8.1 0 7.3 8.2 16.1 18.4 23.3 31.6 31.3 41.8 39.5 58.3 52.

15、323.7 17.7 19.6 7.4 18.9 20.3 15.4 7.3 0 15.5 23.4 25.7 30.6 38.9 33.8 44.3 46.8 65.6 54.812.9 19.1 21 8.8 20.3 28.5 16.3 8.2 15.5 0 7.9 22.8 15.1 23.4 23 33.5 31.3 40.1 4420.8 27 28.9 16.7 28.2 38.3 24.2 16.1 23.4 7.7 0 14.9 7.2 15.5 15.2 25.7 23.442.4 36.235.7 41.8 43.8 31.6 32.6 24.4 10.3 18.4 25

16、.7 22.8 14.9 0 7.7 16 28.1 31.7 23.9 42.7 42.228 34.2 36.1 23.9 35.4 32.1 18 23.3 30.6 15.1 7.2 7.7 0 8.3 20.4 24 16.2 35 34.5 22.2 28.2 34.1 32.2 43.7 40.4 26.3 31.6 38.9 23.4 15.5 16 8.3 0 12.1 15.7 7.9 26.7 26.210.1 16.1 22 26.4 37.9 46.1 38.4 31.3 33.8 23 15.2 28 20.4 12.1 0 10.5 18.3 37.1 2120.

17、6 26.6 32.5 36.9 48.4 56.6 48.9 41.8 44.3 33.5 25.7 31.7 24 15.7 10.5 0 7.8 23.7 10.528.4 34.4 40.3 39.7 51.6 48.3 34.2 39.5 46.8 31.3 23.4 23.9 16.2 7.9 18.3 7.8 0 18.8 18.344.3 50.3 56.2 58.5 70.4 67.1 53 58.3 65.6 40.1 42.2 42.7 35 26.7 37.1 23.7 18.8 0 13.231.1 37.1 43 47.4 58.9 67.1 59.4 52.3 5

18、4.8 44 36.2 42.2 34.5 26.2 21 10.5 18.3 13.2 0B=0 19.8 31.8 39.6 47.7 43.7 53.8 53.5 59.3 51.1 59.9 42.9 38.3 70.1 61.5 51.7 47.6 43.8;19.8 0 12.0 19.8 27.9 23.9 24 33.7 39.5 41.3 50.1 33.1 18.5 54.3 45.7 35.9 27.8 24;31.8 12.0 0 7.8 15.9 11.9 22 21.7 27.5 29.3 38.1 21.1 6.5 42.3 33.7 23.9 15.8 12;3

19、9.6 19.8 7.8 0 8.1 4.1 14.2 17.9 19.7 21.5 30.3 13.3 7.8 43.6 35 25.2 17.1 13.3;47.7 27.9 15.9 8.1 0 12.2 10 16.7 22.5 38.4 29.6 21.4 15.9 51.8 43.2 33.4 25.2 21.4;43.7 23.9 11.9 4.1 12.2 0 10.1 9.8 15.6 26.2 17.4 9.2 11.9 35.8 27.2 17.4 21.2 17.4;53.8 24 22 14.2 10 10.1 0 6.7 12.5 24.3 33.1 19.3 22

20、 45.9 37.3 27.5 31.3 27.5;53.5 33.7 21.7 13.9 16.7 9.8 6.7 0 5.8 17.6 26.4 19 22 42.6 34 27.2 32.7 25.5;59.3 39.5 27.5 19.7 22.5 15.6 12.5 5.8 0 11.8 20.6 20 27.5 36.6 28.2 27.6 31.7 33;51.5 41.3 29.3 21.5 38.4 26.2 24.3 17.6 11.8 0 8.8 8.2 29.3 25 16.4 15.8 23.9 31.1;59.9 50.1 38.1 30.3 29.6 17.4 3

21、3.1 26.4 20.6 8.8 0 17 38.2 15 25.6 24.6 33.3 40.5;42.9 33.1 21.1 13.3 21.4 9.2 19.3 19 20 8.2 17 0 21.1 26.6 18 8.2 17.3 24.5; 38.3 18.5 6.5 7.8 15.9 11.9 22 22 27.5 29.3 38.2 21.1 0 35.8 27.2 17.4 9.3 5.5;70.1 54.3 42.3 43.6 51.8 35.8 45.9 42.6 36.6 25 15 26.6 35.8 0 8.6 18.4 26.5 33.7;61.5 45.7 3

22、3.7 35 43.2 27.2 37.3 34 28.2 16.4 25.6 18 27.2 8.6 0 9.8 17.925.1;56.7 35.9 23.9 25.2 33.4 17.4 27.5 27.2 27.6 15.8 24.6 8.2 17.4 18.4 9.8 0 4.1 11.3;47.6 27.8 15.8 17.1 25.2 21.2 31.3 32.7 31.7 23.9 33.3 17.3 9.3 26.5 17.9 4.1 0 7.2 ;43.8 24 12 13.3 21.4 17.4 27.5 25.2 33 31.3 40.5 24.5 5.5 33.7 2

23、5.1 11.3 7.2 0C=0 8.2 13 11.5 21.2 16.5 33.9 48.7 40.7 33.5 26.2 54.9 61.7 67.3 78.5 55.1 48.5 65.18.2 0 4.8 12.6 13 8.3 25.7 40.5 32.5 25.3 18 46.7 53.5 59.1 69.9 46.9 40.3 57.7 13 4.8 0 7.8 8.2 13.1 20.9 38.5 30.5 23.3 22.8 44.7 51.5 57.1 67.9 44.9 38.3 55.711.5 12.6 7.8 0 16 20.9 28.7 46.3 38.3 3

24、1.1 30.6 52.5 59.3 60.9 75.7 52.7 46.1 63.521.2 13 8.2 16 0 13.3 12.7 30.3 22.3 15.1 21 36.5 43.3 48.9 59.7 36.7 30.1 47.516.5 8.3 13.1 20.9 11.3 0 24 32.2 24.2 17 9.7 38.4 45.2 50.8 61.6 38.6 32 49.4 33.9 25.7 24.9 28.7 12.7 24 0 24.4 28.4 27.8 35.1 42.6 49.4 55 65.8 42.8 36.2 53.648.7 40.5 38.5 46

25、.3 30.3 32.2 20.4 0 8 15.2 22.5 22.2 29 34.6 45.4 22.4 15.8 33.240.7 32.5 30.5 38.3 22.3 24.2 28.4 8 0 7.2 14.5 14.2 21 26.6 37.4 14.4 7.8 25.2 33.5 25.3 23.3 31.1 15.1 17 27.8 15.2 7.2 0 7.3 21.4 28.2 33.8 44.6 21.6 15 32.4 26.2 18 22.8 30.6 21 9.7 35.1 22.5 14.5 7.3 0 28.7 35.5 41.1 51.9 28.9 22.3

26、 39.7 54.9 46.7 44.7 52.5 36.5 38.4 42.6 22.2 14.2 21.4 28.7 0 6.8 14.6 25.4 28.6 22 39.461.7 53.5 51.5 59.3 43.3 45.2 49.4 29 21 28.2 35.5 6.8 0 7.8 18.6 20 26.6 30.8 67.3 59.1 57.1 64.9 48.9 50.8 55 34.6 26.6 33.8 41.1 14.6 7.8 0 10.8 12.2 18.8 2378.5 66.9 67.9 75.7 59.7 61.6 65.8 45.4 37.7 44.6 5

27、1.9 25.4 18.6 10.8 0 23 29.6 33.855.1 46.9 44.9 52.7 36.7 38.6 42.8 22.4 14.4 21.6 28.9 28.6 20 12.2 23 0 6.6 10.848.5 40.3 38.3 46.1 30.1 32.1 36.2 15.8 7.8 15 22.3 22 26.6 18.8 29.6 6.6 0 17.4 65.1 57.7 55.7 63.5 47.5 49.4 53.6 33.2 25.2 32.4 39.7 39.4 30.8 23 33.8 10.8 17.4 0附录 3A1=0 6 11.9 16.3

28、27.8 36 12.9 22.1 20.2 23.7 30.5 20.8 28 36.3 44.26 0 5.9 10.3 21.8 30 18.9 25 73.1 17.7 41.7 26.8 34 42.3 50.211.9 5.9 0 12.2 17.6 25.8 21 26.9 35 19.6 43.8 28.9 36.1 44.4 52.316.3 10.3 12.2 0 11.5 19.7 8.8 14.7 22.8 7.4 31.6 16.7 23.9 32.2 40.127.8 21.8 17.6 11.5 0 8.2 20.3 26.2 34.3 18.9 43.1 28.

29、2 35.4 43.7 51.636 30 25.8 19.7 8.2 0 28.5 23 14.9 20.3 25.2 36.4 32.9 41.2 48.912.9 18.9 21 8.8 20.3 28.5 0 9.2 17.3 16.2 22.8 7.9 15.1 23.4 31.322.1 25 26.9 14.7 26.2 23 9.7 0 8.1 7.3 18.4 17.1 24.3 32.6 40.520.2 33.1 35 22.8 34.3 14.9 17.3 8.1 0 15.4 10.3 25.2 18 26.3 24.223.7 17.7 19.6 7.4 18.9

30、20.3 16.2 7.3 15.4 0 25.7 24.4 31.6 39.9 47.8 30.5 41.7 43.8 31.6 43.1 25.2 22.8 18.4 10.3 25.7 0 14.9 7.7 16 23.9 20.8 26.8 28.9 16.7 28.2 36.4 7.9 17.1 25.2 24.4 14.9 0 7.2 15.5 23.4 28 34 36.1 23.9 35.4 32.9 15.1 24.3 18 31.6 7.7 7.2 0 8.3 16.226.3 42.3 44.4 32.2 43.7 41.2 23.4 32.6 26.3 39.9 16

31、15.5 8.3 0 7.9 44.2 50.2 52.3 40.1 51.6 48.9 31.3 40.5 24.2 41.8 23.9 23.4 16.2 7.9 0 B1=0 10.1 20.6 31.1 44.3 19.8 31.8 38.3 39.6 43.7 53.5 60.3 39 4910.1 0 10.5 21 34.2 29.9 29.8 36.3 37.6 41.7 45.6 52.4 28.9 38.920.6 10.5 0 10.5 19.7 24.7 19.3 25.8 27.1 31.2 35.1 41.9 18.4 28.431.1 21 10.5 0 9.2

32、14.2 8.8 15.3 16.6 20.7 24.6 31.4 7.9 17.944.3 34.2 19.7 9.2 0 27.4 22 25.9 18 22.1 25.6 32.4 8.9 18.919.8 29.9 24.7 14.2 27.4 0 12 18.5 19.8 23.9 33.7 40.5 22.1 32.131.8 29.8 19.3 8.8 22 12 0 6.5 7.8 13.9 23.7 30.5 16.7 2238.3 36.3 25.8 15.3 25.9 18.5 6.5 0 7.9 12 21.8 28.6 17 22.139.6 37.6 27.1 16

33、.6 18 19.8 7.8 7.9 0 4.1 13.9 10.7 9.1 14.243.7 41.7 31.2 20.7 22.1 23.9 13.9 12 4.1 0 9.8 16.6 13.2 10.153.5 45.6 35.1 24.6 25.6 33.7 23.7 21.8 13.9 9.8 0 6.8 16.7 6.760.3 52.4 41.9 31.4 32.4 40.5 30.5 28.6 10.7 16.6 6.8 0 23.5 13.539 28.9 18.4 7.9 8.9 22.1 16.7 17 22.1 14.2 10.1 6.7 0 104.9 32.9 2

34、8.4 17.9 18.9 32.1 22 22.1 14.2 10.1 6.7 13.5 10 0C1=0 8.8 17 15 24.9 25.1 23.6 32.2 37.8 24.6 32.7 39.9;8.8 0 8.2 23.8 33.7 32.8 16.4 25 29 15.8 23.9 31.1;17 8.2 0 26.6 38.5 34.4 18 26.6 21.4 8.2 16.3 23.5;15 23.8 26.6 0 9.9 20.1 8.6 17.2 24 18.4 26.5 33.7;24.9 33.7 38.5 9.9 0 10.2 18.5 18 24.58 28.3 36.4 43.6;25.1 32.8 34.4 20.1 10.2 0 16.4 7.8 14.6 26.2 34.3 41.5;23.6 16.4 18 8.6 18.5 16.4 0 8.6 15.4 9