《计算智能课程作业》由会员分享，可在线阅读，更多相关《计算智能课程作业（13页珍藏版）》请在金锄头文库上搜索。
1、利用蚁群算法求解tsp 问题TSP 问题又称最短路径问题， 还称为旅行商问题， 是一种比较经典的 NP 难题，问题描述较简单，而获得最优解却十分困难。求解 TSP 问题不仅为其他算法提供了使用平台，而且算法的优劣性能也可通过其求得TSP 问题的解集来验证。旅行商问题的经典描述为：已知 N 个城市及相互间的距离，旅行商从某城市出发遍历这N 个城市后再回到原点，在旅行商每个城市都只访问一次的前提下确定一条最短路径。蚁群算法是一种基于种群的启发式仿生进化系统。该算法通过模拟自然界的蚂蚁觅食过程对目标进行搜索，而在搜索过程中人工蚂蚁会在其经过的路径上释放信息素，蚁群依赖于同类散发在周围环境中的特殊物质
2、信息素的轨迹来决定自己的去向。当某些路径上走过的蚂蚁越来越多时，留下的信息素也会越来越多，以致后蚂蚁选择该路径的概率也越来越高，从而更增加了该路径的吸引强度，逐渐形成了一条它们自己事先并未意识到的最短路线。蚁群算法实现TSP 过程为： 将 m 只蚂蚁放入到 n 个随机选择的城市中，那么每个蚂蚁每步的行动是：根据一定的依据选择下一个它还没有访问的城市；同时在完成一步（从一个城市到达另一个城市）或者一个循环（完成对所有 n 个城市的访问）后，更新所有路径上的信息素浓度蚁群算法的实现步骤步骤 1 初始化相关参数如蚂蚁的数目。步骤2将蚂蚁随机或均匀分布到各个城市。步骤3每只蚂蚁通过访问各个城市而形成一
3、个解并在访问的过程中 将已访问到的城市保留在i 中。在城市i 中每只蚂蚁要从没有访问的城市中选择访问下一个城市j 时须根据概率公式(1) 进行选择如此循环直到所有的蚂蚁访问完所有的城市。步骤 4 计算每只蚂蚁行走的总路径长度Lk 并保存最优解。数学模型的建立(1).基本参数、信息素浓度公式、择路概率设蚂蚁的数量为m,城市的数量为n,城市i与城市j之间的距离为dij, t 时刻城市1与城市j之间的信息素浓度为0(,初始时刻，各个城市间连接路 径上的信息素浓度相同，不妨记为%(0)=1。0蚂蚁k(k=12.)根据各城市间连接路径上的信息素浓度，决定其下一个要 访问的城市，设P(t)表示t时刻，蚂蚁
4、k从城市i到城市j的概率，其计算公 式为如下：L丁 % F0I式t)为启发式函数，%(t户砌,表小蛆蚁从城市】转移到城而J的期望程 序；皿口收=1,2+.皿)表示蚂蚁k待访问的城市的集合，开始时RlloWk为其他n-1城市，随着时间推进，其中的元素不断减少，直至为空，表示所有城市访 问完，即遍历所有城市.a为信息素的重要程度因子，其值越大，转移中起的作用越大P为启发函数的重要程度因子，其值越大，表示启发函数在转移中的作用越大, 即蚂蚁以较大的概率转移到距离短的城市.蚂蚁释放的信息素会随时间的推进而减少，设参数p(Opl)表示信息素的 挥发度，当所有蚂蚁完成一次循环后，各个城市间连接路径上的信息
5、素浓度， 需要实时更新。%(t+l)=(l-p)q十八%=4其中：表示蚂蚁k在城市i与城市j的连接路径上，释放的信息素浓度%表示所有蚂蚊在城市1与城市j的连接路径上，释放的信息素浓度。(2)、的计算方法k第#只蚂蚁从城市i访问城市j八卢j 0其他蚁群算法解决TSP问题的MATLAB实现出动m只蚂蚁，每只蚂蚁各随机选择一条路径，记为 I=1 2 3 m,长度记为long(I);计算出每条路径的信息素浓度，记为 P(I)=1/long(I),并进行归一化处理；重新出动m只蚂蚁，按如下规则选择路径：1,每只蚂蚁都以一个概率pl选择新路径(路径随机)2,未选择新路径的蚂蚁以概率 P(I)选择路径I;3
6、,所有蚂蚁都以一个小概率p2对自己的路径进行局部变化;更新所有路径，计算出每条路径的信息素浓度；重复上述步骤，直至仅剩一条路径。Matlab算法实现functionR_best,L_best,L_ave,Shortest_Route,Shortest_Length=ACATSP(C,NC_max,m,Alpha,Beta,Rh o,Q)%=% ACATSP.m% Ant Colony Algorithm for Traveling Salesman Problem% ChengAihua,PLA Information Engineering University,ZhengZhou,Chin
7、a% Email:% All rights reserved% 主要符号说明% C n 个城市的坐标，n x 2的矩阵% NC_max 最大迭代次数% m蚂蚁个数% Alpha表征信息素重要程度的参数% Beta表征启发式因子重要程度的参数% Rho信息素蒸发系数% Q信息素增加强度系数% R_best各代最佳路线% L_best各代最佳路线的长度%=第一步：变量初始化n=size(C,1);%n 表示问题的规模(城市个数)D=zeros(n,n);%D 表示完全图的赋权邻接矩阵for i=1:nfor j=1:nif i=jD(i,j)=(C(i,1)-CO,1)A2+(C(i,2)-CO,
8、2)A2)A0.5;elseD(i,j)=eps;endD(j,i)=D(i,j);end endEta=1./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,1);%L_ave=zeros(NC_max,1);% 各代路线的平均长度while NC=rand);to_visit=J(Select(1);Tabu(i,j)=to_visit;en
9、dendif NC=2Tabu(1,:)=R_best(NC-1,:);end第四步：记录本次迭代最佳路线L=zeros(m,1);for i=1:mR=Tabu(i,:);for j=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);for i=1:mfor j=1:(n-1)De
10、lta_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)subp
11、lot(1,2,1)DrawRoute(C,Shortest_Route)subplot(1,2,2)plot(L_best)hold onplot(L_ave)function DrawRoute(C,R)%=% DrawRoute.m% 画路线图的子函数% C Coordinate节点坐标，由一个 NX 2的矩阵存储% 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),2) hold onfor ii=2:Nplot(C(R(ii-1),1),C(R(
12、ii),1),C(R(ii-1),2),C(R(ii),2) hold onend代码运行：现在输入 31 个城市的坐标进行计算设置初始参数如下m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;31 城市坐标为：1304,2312;3639,1315;4177,2244;3712,1399;3488,1535;3326,1556;3238,1229;4196,1004;4312,790;4386,570;3007,1970;2562,1756;2788,1491;2381,1676;1332,695;3715,1678;3918,2179;4061,2370;3780,2212;3676,2578;4029,2838;4263,2931;3429,1908;3507,2367;3394,2643;第 9 页 共 13 页3439,3201;2935,3240;3140,3550;2545,2357;2778,2826;2370,2975;运行后得到15602的巡游路径，路
