资源描述：
《蚁群算法解决tsp问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、蚁群算法解决TSP问题信管专业李鹏201101002044一、蚁群算法蚁群算法是一种用来在图中寻找优化路径的几率型算法，各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种挥发性分泌物pheromone(称为信息素，该物质随着时间的推移会逐渐挥发消失，信息素浓度的人小表征路径的远近)来实现的，吸引其他的蚂蚁过來，这样越來越多的蚂蚁会找到食物。有些蚂蚁并没有彖其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现
2、一条最短的路径被大多数蚂蚁重复着。二、问题描述旅行商问题(TravelingSalcsmanProblem)TSP是指旅行商按一定的顺序访问N个城市的每一个城市，使得每个城市都能被访问且仅能被访问一次，最后回到起点，而使路程最短，花费的代价最小。三、蚂蚁算法求解TSP问题的过程如下：(1)首先初始化，设迭代的次数为"C。初始化W>0(2)将ni个蚂蚁置于n个顶点上(3)m只蚂蚁按概率函数选择下一座城市，完成各自的周游每个蚂蚁按照状态变化规则逐步地构造一个解，即生成一条回路。蚂蚁的任务是访问所有的城市后返回到起点，牛成一条回路。设蚂蚁k当前所在的顶点为i,那么，蚂蚁k由
3、点i向点j移动要遵循规则而不断迁移，按不同概率来选择下一点。(4)记录本次迭代最佳路线(5)全局更新信息素值应用全局信息素更新规则来改变信息素值。当所有m个蚂蚁牛成了m个解，其中有一条最短路径是本代最优解，将属于这条路线上的所有弧相关联的信息素值进行更新。全局信息素更新的目的是在最短路线上注入额外的信息素，即只有屈于最短路线的弧上的信息素才能得到加强，这是一个正反馈的过程，也是一个强化学习的过程。在图中各弧上，伴随着信息素的挥发，全局最短路线上各弧的信息素值得到增加。(6)终止若终止条件满足，则结束；否则NONC+1,转入步骤(2)进行下一代进化。终止条件可指定进化的
4、代数，也可限定运行时间，或设定最短路长的下限。(7)输出结果四、代码第一步：变量初始化n=size(C,1);%n表示问题的规模(城市个数)D=zeros(n,n);%D表示完全图的赋权邻接矩阵fori二l:nforj二1:nif1=JD(i,j)=((C(i,1)-C(j,1)厂2+(C(i,2)-C(j,2)厂2)'0.5;elseD(i,j)二eps;%i=j时不计算，应该为0,但后面的启发因子要取倒数，用cps(浮点相对精度)表示endD(j,i)=D(i,j);%对称矩阵endendEta=l./D;%Eta为启发因子，这里设为距离的倒数Tau二ones(n
5、,n);%Tau为信息素矩阵Tabu二zeros(m,n);%存储并记录路径的生成NC=1;%迭代计数器，记录迭代次数Rbest二zeros(NC_max,n);%各代最佳路线L_bcst=inf.*oncs(NC_max,1);%各代最佳路线的长度L_ave=zeros(NC_max,1);%各代路线的平均长度wh订eNC<=NC_max%停止条件之一：达到最大迭代次数，停止第二步：将m只蚂蚁放到n个城市上Remdpos二[];%随即存取fori=l:(ceil(m/n))Randpos=[Randpos,randperm(n)];endTabu(:,l)=(Ran
6、dpos(l,1:m))';%此句不太理解?第三步：ni只蚂蚁按概率函数选择下一座城市，完成各自的周游forj=2:n%所在城市不计算fori=l:mvisited二Tabu(i,1:(jT));%记录已访问的城市，避免重复访问J二zeros(1,(n-j+1))；%待访问的城市P=J；%待访问城市的选择概率分布Jc=l;fork=l:niflength(find(visited==k))==0%开始时置0J(Jc)=k;Jc=Jc+l;%访问的城市个数自加1endend%下面计算待选城市的概率分布fork=l:lcngth(J)P(k)=(Tau(visited(e
7、nd),J(k))Alpha)*(Eta(visited(end),J(k))Beta);endP二P/(sum(P));%按概率原则选取下一个城市Pcum=cumsum(P);%cumsum,元素累加即求和Select=find(Pcum>=rand);%若计算的概率大于原来的就选择这条路线to_visit=J(Select(1));Tabu(i,j)二to_visit;endendifNC>=2Tabu(l,:)二Rbest(NCT,:);end第四步：记录本次迭代最佳路线L二zeros(m,1);%开始距离为0,m*l的列向量fori=l:mR
