《基于蚁群算法的旅行商问题解决方案》由会员分享，可在线阅读，更多相关《基于蚁群算法的旅行商问题解决方案（7页珍藏版）》请在金锄头文库上搜索。
1、基于蚁群算法的旅行商问题解决方案一 引言旅行商问题（TSP, Traveling Salesman Problem）是在1859年由威廉汉密尔顿爵士首次提出的，它是物流领域中的典型问题，这个问题的求解具有十分重要的理论和现实意义。所谓TSP问题是指：有N个城市，要求旅行商到达每个城市各一次，且仅一次，并回到起点，且要求旅行路线最短。这是一个典型的优化问题，对一个具有中等顶点规模的图来说，精确求解也是很复杂的，计算量随着城市个数的增加而呈指数级增长，即属于所谓的 NP问题。TSP在工程领域有着广泛的应用 ，并常作为比较算法性能的标志。如网络通讯、货物运输、电气布线、管道铺设、加工调度、专家系统、
2、柔性制造系统等方面，都是TSP广泛应用的领域。求解算法包括贪婪法（GM）、极小代数法（MA）、模拟退火法（SA）和遗传算法（GA）等。而应用蚁群算法求解旅行商问题是近年来研究的新方向，由于其并行性与分布性，特别适用于大规模启发式搜索，实验结果证明了其可行性和有效性。二 蚁群系统基本原理 在蚂蚁群找到食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素（phero-mone）。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。当后来的蚂蚁再次碰到这个路口的时候，选
3、择激素浓度较高路径概率就会相对较大。这样形成了一个正反馈。最优路径上的激素浓度越来越大，而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。在整个寻径过程中，虽然单个蚂蚁的选择能力有限，但是通过激素的作用，整个蚁群之间交换着路径信息，最终找出最优路径。三 基于蚁群算法的旅行商问题求解方案TSP问题描述如下：设有n个城市C=（1，2,.,n），任意两个城市i，j之间的距离为dij ，求一条经过每个城市的路径=（1），（2），.，（n），使得距离最小。主要符号说明 C n个城市的坐标，n2的矩阵 NC_max 最大迭代次数 m 蚂蚁个数 Alpha 表征信息素重要程度的参数
4、 Beta 表征启发式因子重要程度的参数 Rho 信息素蒸发系数 Q 信息素增加强度系数 R_best 各代最佳路线 L_best 各代最佳路线的长度 求解TSP问题的蚂蚁算法中，每只蚂蚁是一个独立的用于构造路线的过程，若干蚂蚁过程之间通过自适应的信息素值来交换信息，合作求解，并不断优化。这里的信息素值分布式存储在图中，与各弧相关联。蚂蚁算法求解TSP问题的过程如下：（1）首先初始化，设迭代的次数为NC。初始化NC=0（2）将m个蚂蚁置于n个顶点上（3）m只蚂蚁按概率函数选择下一座城市，完成各自的周游每个蚂蚁按照状态变化规则逐步地构造一个解，即生成一条回路。蚂蚁的任务是访问所有的城市后返回到起
5、点，生成一条回路。设蚂蚁k当前所在的顶点为i，那么，蚂蚁k由点i向点j移动要遵循规则而不断迁移，按不同概率来选择下一点。（4）记录本次迭代最佳路线（5）全局更新信息素值应用全局信息素更新规则来改变信息素值。当所有m个蚂蚁生成了m个解，其中有一条最短路径是本代最优解，将属于这条路线上的所有弧相关联的信息素值进行更新。全局信息素更新的目的是在最短路线上注入额外的信息素，即只有属于最短路线的弧上的信息素才能得到加强，这是一个正反馈的过程，也是一个强化学习的过程。在图中各弧上，伴随着信息素的挥发，全局最短路线上各弧的信息素值得到增加。（6） 终止若终止条件满足，则结束；否则NC=NC+1，转入步骤（2
6、）进行下一代进化。终止条件可指定进化的代数，也可限定运行时间，或设定最短路长的下限。（7）输出结果四 数据实验及结果 通过计算机仿真，得出旅行商问题优化结果和平均距离和最短距离，如图所示：四 分析与总结 本文设计了一种基于MATLAB实现的蚁群算法，用以求解组合优化难题中的典型代表旅行商问题。对30个城市旅行商问题进行了测试，所得结果能达到优化作用，解决了这个问题。 经过对旅行商问题的深入理解，得到了能解决问题的基本数学模型，然后设计算法的基本思想，技术路线，最后编码。在多次调试，修改后，本算法成功运行，并实现了最初的设定目标。另外，MATLAB具有丰富的绘图函数，对于绘图十分方便，这是选择M
7、ATLAB解决TSP问题的算法编写、调试的原因。蚁群算法解决旅行商问题MATLAB程序x=41 37 54 25 7 2 68 71 54 83 64 18 22 83 91 25 24 58 71 74 87 18 13 82 62 58 45 41 44 4;y=94 84 67 62 64 99 58 44 62 69 60 54 60 46 38 38 42 69 71 78 76 40 40 7 32 35 21 26 35 50;C=x y;NC_max=50;m=30;Alpha=1.5;Beta=2;Rho=0.1;Q=106;%-% 主要符号说明% C n个城市的坐标，n2的
8、矩阵% NC_max 最大迭代次数% m 蚂蚁个数% Alpha 表征信息素重要程度的参数% Beta 表征启发式因子重要程度的参数% Rho 信息素蒸发系数% Q 信息素增加强度系数% R_best 各代最佳路线% L_best 各代最佳路线的长度%=%第一步：变量初始化n=size(C,1);%n表示问题的规模（城市个数）D=zeros(n,n);%D表示完全图的赋权邻接矩阵for i=1:n for j=1:n if i=j D(i,j)=(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)2)0.5; else D(i,j)=eps; %i=j时不计算，应该为0，但后面的启发因
9、子要取倒数，用eps（浮点相对精度）表示 end D(j,i)=D(i,j); %对称矩阵 endendEta=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=
10、J(Select(1); Tabu(i,j)=to_visit; endendif NC=2 Tabu(1,:)=R_best(NC-1,:);end%第四步：记录本次迭代最佳路线L=zeros(m,1); %开始距离为0，m*1的列向量for i=1:m R=Tabu(i,:);for j=1:(n-1) L(i)=L(i)+D(R(j),R(j+1); %原距离加上第j个城市到第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
11、,:)=Tabu(pos(1),:); %此轮迭代后的最佳路线L_ave(NC)=mean(L); %此轮迭代后的平均距离NC=NC+1; %迭代继续%第五步：更新信息素Delta_Tau=zeros(n,n); %开始时信息素为n*n的0矩阵for i=1:m for j=1:(n-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i); %此次循环在路径（i，j）上的信息素增量 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); %找到最佳路径（非0为真）Shortest_Route=R_best(Pos(1),:) %最大迭代次数后最佳路径Sh
