蚁群算法求解TSP问题(DOC)

广东工业大学课程作业2015年2月15日课程题目基于ACO算法求解城市tsp学生姓名朱美霞学生学号2111405091专业班级计算机技术1.AOC算法的数学模型（1）、基本参数、信息素浓度公式、择路概率设蚂蚁的数量为m，城市的数量为n，城市i与城市j之间的距离为dij，t时刻城市i与城市j之间的信息素浓度为tij(t)，初始时刻，各个城市间连接路径上的信息素浓度相同，不妨记为tij(0)=t0。蚂蚁k(k=1,2,..,m)根据各城市间连接路径上的信息素浓度，决定其下一个要访问的城市，设Pijk(t)表示t时刻，蚂蚁k从城市i到城市j的概率，其计算公式为如下：ij[()][()][()][()]P0ijijkkijijsallowktttsallowtttsallow其中：ij(t)为启发式函数，ij(t)=1/dij，表示蚂蚁从城市i转移到城市j的期望程序；allowk(k=1,2,…,m)表示蚂蚁k待访问的城市的集合，开始时allowk为其他n-1城市，随着时间推进，其中的元素不断减少，直至为空，表示所有城市访问完，即遍历所有城市。为信息素的重要程度因子，其值越大，转移中起的作用越大为启发函数的重要程度因子，其值越大，表示启发函数在转移中的作用越大，即蚂蚁以较大的概率转移到距离短的城市。蚂蚁释放的信息素会随时间的推进而减少，设参数(01)表示信息素的挥发度，当所有蚂蚁完成一次循环后，各个城市间连接路径上的信息素浓度，需要实时更新。tij(t+1)=(1-)tij(t)+tij，tij=1nkijkt其中：tijk表示蚂蚁k在城市i与城市j的连接路径上，释放的信息素浓度tij表示所有蚂蚁在城市i与城市j的连接路径上，释放的信息素浓度。（2）、tijk的计算方法tijk=/0kQLk第只蚂蚁从城市i访问城市j其他其中：Q为常数，表示蚂蚁循环一次释放的信息素的总量；dij为第k只蚂蚁经过路径的长度，Length；4.相关程序1、访问每个城市一次也仅一次的最短路径，共有30个2、城市的坐标citys，这是直角坐标，根据二个城市的坐标值，可以用D=22(12)(12)xxyy可计算出任意二个城市间的距离。citys=1304231236391315417722443712139934881535332615563238122941961004431279043865703007197025621756278814912381167613326953715167839182179406123703780221236762578402928384263293134291908350723673394264334393201293532403140355025452357277828263、代码clearallclcloadcitys_data.mat%计算城市间相互距离n=size(citys,1);%城市的个数D=zeros(n,n);%n行n列的矩阵，即任意二个城市之间的距离fori=1:nforj=1:nifi~=jD(i,j)=sqrt(sum((citys(i,:)-citys(j,:)).^2));elseD(i,j)=1e-4;endendend%%初始化参数m=50;%蚂蚁数量alpha=1;%信息素重要程度因子beta=5;%启发函数重要程度因子rho=0.1;%信息素挥发因子Q=1;%常系数Eta=1./D;%启发函数Tau=ones(n,n);%信息素矩阵,全1矩阵Table=zeros(m,n);%路径记录表，全0矩阵，每只蚂蚁依次走过的城市iter=1;%迭代次数初值iter_max=200;%最大迭代次数Route_best=zeros(iter_max,n);%各代最佳路径Length_best=zeros(iter_max,1);%各代最佳路径的长度Length_ave=zeros(iter_max,1);%各代路径的平均长度%%迭代寻找最佳路径whileiter=iter_max%随机产生各个蚂蚁的起点城市start=zeros(m,1);%m是蚂蚁的个数,m行1列的矩阵，记录每个蚂蚁的城市编号fori=1:mtemp=randperm(n);start(i)=temp(1);endTable(:,1)=start;%路径记录表的1列，为每个蚂蚁的起点城市%构建解空间citys_index=1:n;%逐个蚂蚁路径选择fori=1:m%逐个城市路径选择forj=2:ntabu=Table(i,1:(j-1));%已访问的城市集合(禁忌表)allow_index=~ismember(citys_index,tabu);%不是tabu的城市就是要访问的城市allow=citys_index(allow_index);%待访问的城市集合P=allow;fork=1:length(allow)%计算城市间转移概率P(k)=Tau(tabu(end),allow(k))^alpha*Eta(tabu(end),allow(k))^beta;endP=P/sum(P);%规一化%轮盘赌法选择下一个访问城市Pc=cumsum(P);%依次累加，是实现轮盘赌法选择的方法target_index=find(Pc=rand);target=allow(target_index(1));Table(i,j)=target;endend%%结果显示[Shortest_Length,index]=min(Length_best);Shortest_Route=Route_best(index,:);disp(['最短距离:'num2str(Shortest_Length)]);disp(['最短路径:'num2str([Shortest_RouteShortest_Route(1)])]);%%绘图figure(1)plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...[citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');gridonfori=1:size(citys,1)text(citys(i,1),citys(i,2),[''num2str(i)]);endtext(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),'起点');text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),'终点');xlabel('城市位置横坐标')ylabel('城市位置纵坐标')title(['蚁群算法优化路径(最短距离:'num2str(Shortest_Length)')'])figure(2)plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:')legend('最短距离','平均距离')xlabel('迭代次数')ylabel('距离')title('各代最短距离与平均距离对比')end5.结果与分析使用不同的蚁群数量和迭代次数后求得的最短距离和最短路径如下所示：1.蚁群数50，迭代次数200最短距离:15601.9195最短路径:14121311231656724891031817192425202122262827303129115142.蚁群数50，迭代次数100最短距离:15972.7648最短路径:1151312142911231656724891031817192425202122262827303113.蚁群数100，迭代次数100最短距离:15601.9195最短路径:14121311231656724891031817192425202122262827303129115144.蚁群数50，迭代次数300最短距离:15601.9195最短路径:1151412131123165672489103181719242520212226282730312915.蚁群数100，迭代次数200最短距离:15601.9195最短路径:14121311231656724891031817192425202122262827303129115146.蚁群数100，迭代次数300最短距离:15553.0468最短路径:10984256713121415129313027282621221831719242025112316107.蚁群数150，迭代次数300最短距离:15601.9195最短路径:115141213112316567248910318171924252021222628273031291从以上的实验结果可看出，蚁群数量和迭代次数对算法的实验结果有一定影响，当蚁群数确定时，随着迭代次数的增加，最短距离会有所减小，但增加到一定的程度，最短距离将不再变化；当迭代次数不变，随着蚁群数量的增加，最短距离也有一定的改进。但增加到一定程度，最短距离还可能有所增加。6.总结通过matlab编程来实现蚁群优化算法，通过实验结果发现，虽然找到了问题的最优解，但是最优解的收敛性并不乐观，并不能求得问题的精确解，并且随着参数的调节运行结果有随机性。另外，在蚁群算法求解过程中，蚂蚁的数量和城市的数量差距对结果也是具有一定影响的。当城市规模较大的时候，问题的复杂度呈指数增长，仅仅靠这样一个基础单一的信息素更新机制引导搜索偏向，搜索效率有瓶颈。