课程作广东工业大学课程题目基于ACO算法求解城市tsp学生姓名朱美霞学生学号2111405091专业班级计算机技术2015年2月15日sGallowks笑allowPk1.AOC算法的数学模型1)、基本参数、信息素浓度公式、择路概率设蚂蚁的数量为m,城市的数量为n,城市i与城市j之间的距离为dij,t时刻城市i与城市j之间的信息素浓度为匕⑴，初始时刻，各个城市间连接路径上的信息素浓度相同，不妨记为占(0)=10。蚂蚁k(k=l,2,..,m)根据各城市间连接路径上的信息素浓度，决定其下一个要访问的城市，设Pijk(t)表示t时刻，蚂蚁k从城市i到城市j的概率，其计算公式为如下：[t(t)]«•m(t)]PJ[t(t)]a•[n(t)]PijijsGallow0其中：nij(t)为启发式函数，nij(t)=1/dij，表示蚂蚁从城市i转移到城市j的期望程序；allowk(k=1,2,...,m)表示蚂蚁k待访问的城市的集合，开始时allowk为其他n-1城市，随着时间推进，其中的元素不断减少，直至为空，表示所有城市访问完，即遍历所有城市。a为信息素的重要程度因子，其值越大，转移中起的作用越大P为启发函数的重要程度因子，其值越大，表示启发函数在转移中的作用越大,即蚂蚁以较大的概率转移到距离短的城市。蚂蚁释放的信息素会随时间的推进而减少，设参数p(Ovpvl)表示信息素的挥发度，当所有蚂蚁完成一次循环后，各个城市间连接路径上的信息素浓度需要实时更新。tij(t+1)=(1-P)tij(t)+Atij，Atij=艺皿ijk=1其中：Aqk表示蚂蚁k在城市i与城市j的连接路径上，释放的信息素浓度ijAtj.表示所有蚂蚁在城市i与城市j的连接路径上，释放的信息素浓度。ij(2)、Atijk的计算方法citys=130436394l7737l23488332632384l9643l24386300725622788238ll33237l539l8406l3780367640294263342923l2l3l52244l399l535l556l229l004790570l970l756l49ll676695l6782l79237022l225782838293ll90823672643320l3240355023572826\Q/L第k只蚂蚁从城市i访问城市jAtijk=I汇其他其中：Q为常数，表示蚂蚁循环一次释放的信息素的总量；djj为第k只蚂蚁经过路径的长度，Length；4.相关程序1、访问每个城市一次也仅一次的最短路径，共有30个2、城市的坐标citys这是直角坐标，根据二个城市的坐标值，可以用D=$(xl-x2)2+(yl—y2)2可计算出任意二个城市间的距离。%n行n列的矩阵，即任意二个城市之间的距离=jD(i,j)=sqrt(sum((citys(i,:)-citys(j,:)).人2));%蚂蚁数量%信息素重要程度因子%启发函数重要程度因子%信息素挥发因子%常系数%启发函数%信息素矩阵,全1矩阵%路径记录表，全0矩阵，每只蚂蚁%迭代次数初值%最大迭代次数%各代最佳路径%各代最佳路径的长度3、代码clearallclcloadcitys_data.mat%计算城市间相互距离n=size(citys,1);%城市的个数D=zeros(n,n);fori=1:nforj=1:nifi~elseD(i,j)=1e-4;endendend%%初始化参数m=50;alpha=1;beta=5;rho=0.1;Q=1;Eta=1./D;Tau=ones(n,n);Table=zeros(m,n);依次走过的城市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,l);%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);%依次累加，是实现轮盘赌法选择的方法Pc=cumsum(P);%依次累加，是实现轮盘赌法选择的方法xlabel(迭代次数')ylabel(距离')title（'各代最短距离与平均距离对比'）end5.结果与分析使用不同的蚁群数量和迭代次数后求得的最短距离和最短路径如下所示：1.蚁群数50，迭代次数200最短距离:15...
