计算智能课程作业.docVIP

利用蚁群算法求解tsp问题 ? TSP问题又称最短路径问题，还称为旅行商问题，是一种比较经典的?NP?难 题，问题描述较简单，而获得最优解却十分困难。求解?TSP?问题不仅为其他算法提供了使用平台，而且算法的优劣性能也可通过其求得?TSP?问题的解集来验证。旅行商问题的经典描述为：已知N?个城市及相互间的距离，旅行商从某城市出发遍历这?N?个城市后再回到原点，在旅行商每个城市都只访问一次的前提下确定一条最短路径。? 蚁群算法是一种基于种群的启发式仿生进化系统。该算法通过模拟自然界的蚂蚁觅食过程对目标进行有哪些信誉好的足球投注网站，而在有哪些信誉好的足球投注网站过程中人工蚂蚁会在其经过的路径上释放信息素，蚁群依赖于同类散发在周围环境中的特殊物质—信息素的轨迹来决定自己的去向。当某些路径上走过的蚂蚁越来越多时，留下的信息素也会越来越多，以致后蚂蚁选择该路径的概率也越来越高，从而更增加了该路径的吸引强度，逐渐形成了一条它们自己事先并未意识到的最短路线。? ???蚁群算法实现TSP?过程为：将?m?只蚂蚁放入到?n?个随机选择的城市中，那么每个蚂蚁每步的行动是：根据一定的依据选择下一个它还没有访问的城市；同时在完成一步（从一个城市到达另一个城市）或者一个循环（完成对所有?n?个城市的访问）后，更新所有路径上的信息素浓度 蚁群算法的实现步骤 步骤1初始化相关参数如蚂蚁的数目。 步骤2将蚂蚁随机或均匀分布到各个城市。 步骤3每只蚂蚁通过访问各个城市而形成一个解并在访问的过程中将已访问到的城市保留在i中。在城市i中每只蚂蚁要从没有访问的城市中选择访问下一个城市j时须根据概率公式(1)进行选择如此循环直到所有的蚂蚁访问完所有的城市。 步骤4计算每只蚂蚁行走的总路径长度Lk并保存最优解。 数学模型的建立 蚁群算法解决TSP问题的MATLAB实现 出动m只蚂蚁，每只蚂蚁各随机选择一条路径，记为I=[1 2 3···m]，长度记为long(I); 计算出每条路径的信息素浓度，记为P(I)=1/long(I)，并进行归一化处理; 重新出动m只蚂蚁，按如下规则选择路径： ? 1, 每只蚂蚁都以一个概率p1选择新路径(路径随机) 2, 未选择新路径的蚂蚁以概率P(I)选择路径I； 3, 所有蚂蚁都以一个小概率p2对自己的路径进行局部变化； 更新所有路径，计算出每条路径的信息素浓度； 重复上述步骤，直至仅剩一条路径。 Matlab算法实现 function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)%%=========================================================================%% ACATSP.m%% Ant Colony Algorithm for Traveling Salesman Problem%% ChengAihua,PLA Information Engineering University,ZhengZhou,China%% Email:aihuacheng@%% All rights reserved%%-------------------------------------------------------------------------%% 主要符号说明%% C n个城市的坐标，n×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)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;elseD(i,j)=eps;endD(j,i)=D(i,j);endendEta=1./D;%Eta为启发因子，这里设为距离的倒数Tau=ones(n,n);%Tau为信息素矩阵Tabu=zeros(m,n);%存储并记录路径的生成N