蚁群算法及程序

蚁群算法介绍：(1)寻找最短路径的蚁群算法来源于蚂蚁寻食的行为。蚁群寻找食物时会派出一些蚂蚁分头在四周游荡,如果一只蚂蚁找到食物,它就返回巢中通知同伴并沿途留下“信息素”(外激素pheromone)作为蚁群前往食物所在地的标记。信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物,又采取不同路线回到巢中,那么比较绕弯的一条路上信息素的气味会比较淡,蚁群将倾向于沿另一条更近的路线前往食物所在地。蚁群算法设计虚拟的“蚂蚁”,让它们摸索不同路线,并留下会随时间逐渐消失的虚拟“信息素”,根据“信息素较浓的路线更近”的原则,即可选择出最佳路线.(2)为了模拟实际蚂蚁的行为，首先引进如下记号：设m是蚁群中蚂蚁的数，dij(i,j=1,2,…,n)表示城市i和城市j之间的距离，b(t)表示t时刻位于城市i的蚂蚁的个数，i则有m= bi(t)i=1tij(t)表示示时刻在城市i,j连线上残留的信息素。初始时刻，各条路径上的信息素相等,ij设tj(0)=C(c为常数)。蚂蚁k(k=1,2,…,m)在运动过程中，根据各条路径上的信息ij素决定转移方向。Pk(t)表示在t时刻蚂蚁k由城市i转移到城市j的概率：1ta(t)hb(t)ij ijPk」ijj"轾k(tP[hik记,j tabuk ⑴kItabukf0,jItabuk其中：nij为先验知识或称为能见度，在TSP问题中为城市i转移到城市j的启发信息,ij一般地取nij=血，a为在路径上残留信息的重要程度；b为启发信息的重要程度;与实际蚁群不同，人工蚁群系统具有记忆能力，tabuk(k=1,2,…，m)用以记录蚂蚁K当前所走过的城市，称为禁忌表(下一步不充许选择的城市)，集合tabuk随着进化过程进行动态调整。经过n个时刻，所有蚂蚁完成了一次周游，此时应清空禁忌表，将当前蚂蚁所在的城市置入tabUk中准备下一次周游，这时计算每一只蚂蚁走过的路程L,并保存最短kk路径L(L=minL,k=1,•…，m)minmin k随着时间推移，以前的信息素会逐渐消失，用参数1-r表示信息消失程度，蚂蚁完成一次循环后，各路径上信息素要根据(2)式作调整：t(t+1)=(1-r)t(t)+rDtijijijmDt=矗Dtk (2)ijijk=1其中，dtik表示第k只蚂蚁在本次循环过程中留在路径j上的信息素，Dtij表示本次循环中各路径ij上信息素的增量。Dtk(tt+1)=jQ/L,如果蚂蚁K在巡回中经过ijj' 10，如果蚂蚁K在巡回中不经过ij式中Q是常量，Lk表示第k只蚂蚁的循环路线，即如果蚂蚁经过ij则信息素增量为一个常量除以蚂蚁k的巡回路线长，这里信息素增量只与蚂蚁巡回路线和Q有关系而和具体的dij无关。最后，，设置周游次数计数器NC,当达到设定值时结束，最短路径为；L=minL l(l=l,2,…，NC)min kmin \其蚁群算法的具体过程为:

蚁群算法流程图附录function[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)%%C n个村庄的距离，nXn的矩阵%%NC_max最大迭代次数%%m蚂蚁个数%%Alpha表征信息素重要程度的参数%%Beta表征启发式因子重要程度的参数%%Rho信息素蒸发系数%%Q信息素增加强度系数%%R_best各代最佳路线%%L_best各代最佳路线的长度%%=========================================================================%%第一步：变量初始化n二size(C,l);%n表示问题的规模(城市个数)D=zeros(n,n);%D表示完全图的赋权邻接矩阵fori=1:nforj=1:nD(i,j)=C(i,j);D(j,i)=D(i,j);endendEta=l./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,l);%各代最佳路线的长度L_ave=zeros(NC_max,1);%各代路线的平均长度whileNC<=NC_max%停止条件之一：达到最大迭代次数%%第二步：将m只蚂蚁放到n个城市上Randpos=[];fori=1:(ceil(m/n))Randpos=[Randpos,randperm(n)];endTabu(:,1)=(Randpos(1,1:m))';%%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游forj=2:nfori=1:mvisited二Tabu(i,l:(j-1));%已访问的城市J=zeros(1,(n-j+1));%待访问的城市P=J;%待访问城市的选择概率分布Jc=1;fork=1:niflength(find(visited==k))==0J(Jc)=k;Jc=Jc+1;endend%下面计算待选城市的概率分布fork=1:length(J)P(k)=(Tau(visited(end),J(k)厂Alpha)*(Eta(visited(end),J(k)厂Beta);EndP=P/(sum(P));%按概率原则选取下一个城市Pcum=cumsum(P);Select=find(Pcum>=rand);to_visit=J(Select(1));Tabu(i,j)=to_visit;endendifNC>=2Tabu(1,:)=R_best(NC-1,:);end%%第四步：记录本次迭代最佳路线L=zeros(m,1);fori=1:mR=Tabu(i,:);forj=1:(n-1)L(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);fori=1:mforj=1:(n-1)Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,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_best))Shortest_Route=R_best(Pos(1),:)Shortest_Length=L_best(Pos(1))subplot(1,2,1)DrawRoute(C,Shortest_Route)subplot(1,2,2)plot(L_best)holdonplot(L_ave)functionDrawRoute(C,R)%%=========================================================================%%DrawRoute.m%%画路线图的子函数%%RRoute路线%%=========================================================================N=length(R);scatter(C(:,1),C(:,2));holdonplot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])holdonforii=2:Nplot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])holdonend附录2A=[06.011.916.327.83629.221.123.712.920.835.72822.210.120.628.431.16.005.910.320.82933.12517.719.12741.834.228.216.126.634.450.337.15.9012.217.8263526.919.62128.943.836.134.12232.540.356.24310.312.2011.519.722.814.77.48.816.731.623.932.226.436.939.747.427.820.817.811.508.222.326.218.920.328.232.635.443.737.948.451.658.936292619.78.2014.122.220.328.538.324.432.140.446.156.648.367.167.133.13522.822.314.108.115.416.324.210.31826.338.448.934.25359.42526.914.726.222.28.107.38.216.118.423.331.631.341.839.552.317.719.67.418.920.315.47.3015.523.425.730.638.933.844.346.854.819.1218.820.328.516.38.215.507.922.815.123.42333.531.340.14420.82728.916.728.238.324.216.123.47.7014.97.215.515.225.723.436.241.843.831.632.624.410.318.425.722.814.907.71628.131.723.942.22834.236.123.935.432.11823.330.615.17.27.708.320.42416.23534.528.234.132.243.740.426.331.638.923.415.5168.3012.115.77.926.216.12226.437.946.138.431.333.82315.22820.412.1010.518.337.12126.632.536.948.456.648.941.844.333.525.731.72415.710.507.810.534.440.339.751.648.334.239.546.831.323.423.916.27.918.37.8018.818.350.356.258.570.467.15358.365.640.142.242.73526.737.123.718.8013.237.14347.458.967.159.452.354.84436.242.234.526.22110.518.30]B=[019.831.839.647.743.753.853.559.351.159.942.938.370.161.551.743.8;19.8012.019.827.923.92433.739.541.350.133.118.554.345.735.27.824;31.812.007.815.911.92221.727.529.338.121.16.542.333.723.915.812;39.619.87.808.14.114.217.919.721.530.313.37.843.63525.21713.3;47.727.915.98.1012.21016.722.538.429.621.415.951.843.233.425.221.4;43.723.911.94.112.2010.19.815.626.217.49.211.935.827.217.421.217.4;53.8242214.21010.106.712.524.333.119.32245.937.327.531.327.5;53.533.721.713.916.79.86.705.817.626.4192242.63427.232.725.5;59.339.527.519.722.515.612.55.8011.820.62027.536.628.227.631.733;51.541.329.321.538.426.224.317.611.808.88.229.32516.415.831.1;50.138.130.329.617.433.126.420.68.801738.21525.624.633.340.5;33.121.113.321.49.219.319208.217021.126.6188.217.324.5;18.56.57.815.911.9222227.529.338.221.1035.827.217.49.35.5;54.342.343.651.835.845.942.636.6251526.635.808.618.426.533.7;45.733.73543.227.237.33428.216.425.61827.28.609.817.925.1;35.923.925.233.417.427.527.227.615.824.68.217.418.49.804.111.3;27.815.817.125.221.231.332.731.723.933.317.39.326.517.907.2;241213.321.417.427.525.23331.340.524.55.533.725.111.30]C=[08.21311.521.216.533.948.740.733.526.254.961.767.378.555.165.104.812.6138.325.740.532.525.31846.753.559.169.946.940.357.7134.807.88.213.120.938.530.523.322.844.751.557.167.944.938.355.712.67.801620.928.746.338.331.130.652.559.360.975.752.746.163.5138.216013.312.730.322.315.12136.543.348.959.736.730.147.516.58.313.120.911.302432.224.2179.738.445.250.861.638.63249.433.925.724.928.712.724024.428.427.835.142.649.45565.842.836.253.648.740.538.546.330.332.220.40815.222.522.22934.645.422.415.833.240.732.530.538.322.324.228.4807.214.514.22126.637.414.47.825.225.323.331.115.11727.815.27.207.321.428.233.844.621.61532.41822.830.6219.735.122.514.57.3028.735.541.151.928.922.339.754.946.744.752.536.538.442.622214.221.428.706.814.625.428.62239.461.753.551.559.343.345.249.4292128.235.56.807.818.62026.630.867.359.157.164.948.950.85534.626.633.841.114.678010.812.218.82378.566.967.975.759.761.665.845437.744.651.925.418.610.802329.633.855.146.944.952.736.738.642.822414.421.628.928.62012.22306.610.848.540.338.346.130.132.136.215.87.81522.32226.618.829.66.6017.465.157.755.763.547.549.453.633225.232.439.739.430.82333.810.817.40]附录3A1=[0611.916.327.83612.922.120.223.730.520.82836.344.2605.910.321.83018.92573.117.741.726.83442.350.25.9012.217.625.82126.93519.643.828.936.144.452.310.312.2011.519.78.814.722.87.431.616.723.932.240.121.817.611.508.220.326.234.318.943.128.235.443.751.6363025.819.78.2028.52314.920.325.236.432.941.248.918.9218.820.328.509.217.316.222.87.915.123.431.32526.914.726.2239.708.17.318.417.124.332.640.533.13522.834.314.917.38.1015.410.325.21826.324.217.719.67.418.920.316.27.315.4025.724.431.639.947.841.743.831.643.125.222.818.410.325.7014.97.71623.926.828.916.728.236.47.917.125.224.414.907.215.523.4283436.123.935.432.915.124.31831.67.77.208.316.242.344.432.243.741.223.432.626.339.91615.58.307.950.252.340.151.648.931.340.524.241.823.923.416.27.90]B1=[010.120.631.144.319.831.838.339.643.753.560.33949010.52134.229.929.836.337.641.745.652.428.938.910.5010.519.724.719.325.827.131.235.141.918.428.42110.509.214.28.815.316.620.724.631.47.917.934.219.79.2027.42225.91822.125.632.48.918.929.924.714.227.401218.519.823.933.740.522.132.129.819.38.8221206.57.813.923.730.516.72236.325.815.325.918.56.507.91221.828.61722.137.627.116.61819.87.87.904.113.910.79.114.241.731.220.722.123.913.9124.109.816.613.210.145.635.124.625.633.723.721.813.99.806.816.76.752.441.931.432.440.530.528.610.716.66.8023.513.53928.918.47.98.922.116.71722.114.210.16.701032.928.417.918.932.12222.114.210.16.713.5100]C1=[08.8171524.925.123.632.237.824.632.739.9;08.223.833.732.816.4252915.823.931.1;178.2026.638.534.41826.621.48.216.323.5;1523.826.609.920.18.617.22418.426.533.7;33.738.59.9010.218.51824.5828.336.443.6;32.834.420.110.2016.47.814.626.234.341.5;1