基于MATLAB的蚁算法解决旅行商问题(附带源程序、仿真)

---

摘要：旅行商问题的传统求解方法是遗传算法，但此算法收敛速度慢，并不能

获得问题的最优化解。蚁算法是受自然界中蚁搜索食物行为启发而提出的一

种智能优化算法，通过介绍蚁觅食过程中基于信息素的最短路径的搜索策略，

给出基于MATLAB的蚁算法在旅行商问题中的应用，对问题求解进行局部优

化。经过计算机仿真结果表明，这种蚁算法对求解旅行商问题有较好的改进效

果。

关键词：蚁算法；旅行商问题；MATLAB；优化

一、意义和目标

旅行商问题是物流领域中的典型问题，它的求解具有十分重要的理论和现实

意义。采用一定的物流配送方式，可以大大节省人力物力，完善整个物流系统。

已被广泛采用的遗传算法是旅行商问题的传统求解方法，但遗传算法收敛速

度慢，具有一定的缺陷。本文采用蚁算法，充分利用蚁算法的智能性，求解

旅行商问题，并进行实例仿真。进行仿真计算的目标是，该算法能够获得旅行商

问题的优化结果，平均距离和最短距离。

二、国内外研究现状

仿生学出现于20世纪50年代中期，人们从生物进化机理中受到启发，提出

了遗传算法、进化规划、进化策略等许多用以解决复杂优化问题的新方法。这些

以生物特性为基础的演化算法的发展及对生物落行为的发现引导研究人员进

一步开展了对生物社会性的研究，从而出现了基于智能理论的蚁算法，并掀

起了一股研究的热潮。

20世纪90年代意大利科学家M最早提出了蚁优化算法——蚂

-.-word资料-

---

蚁系统（Antsystem,AS），在求解二次分配、图着问题、车辆调度、集成电路

设计以及通信网络负载问题的处理中都取得了较好的结果。

旅行商问题（TSP,TravelingSalesmanProblem）被认为是一个基本问题，

是在1859年由威廉·汉密尔顿爵士首次提出的。所谓TSP问题是指：有个城市，

要求旅行商到达每个城市各一次，且仅一次，并回到起点，且要求旅行路线最短。

这是一个典型的优化问题，对一个具有中等顶点规模的图来说，精确求解也是很

复杂的，计算量随着城市个数的增加而呈指数级增长，即属于所谓的P问题。

TSP在工程领域有着广泛的应用，并常作为比较算法性能的标志。如网络通讯、

货物运输、电气布线、管道铺设、加工调度、专家系统、柔性制造系统等方面，

都是TSP广泛应用的领域。求解算法包括贪婪法（GM）、极小代数法（MA）、模

拟退火法（SA）和遗传算法（GA）等。而应用蚁算法求解旅行商问题是近年

来研究的新方向，由于其并行性与分布性，特别适用于大规模启发式搜索，实验

结果证明了其可行性和有效性。

三、蚁系统基本原理

在蚂蚁到食物时，它们总能到一条从食物到巢穴之间的最优路径。这

是因为蚂蚁在寻路径时会在路径上释放出一种特殊的信息素（phero-mone）。

当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行。与此同时释

放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。当后来的蚂蚁

再次碰到这个路口的时候，选择激素浓度较高路径概率就会相对较大。这样形成

了一个正反馈。最优路径上的激素浓度越来越大，而其它的路径上激素浓度却会

随着时间的流逝而消减。最终整个蚁会出最优路径。在整个寻径过程中，虽

然单个蚂蚁的选择能力有限，但是通过激素的作用，整个蚁之间交换着路径信

-.-word资料-

---

息，最终出最优路径。

四、基于MATLAB的蚁算法求解旅行商问题

TSP问题描述如下：

设有n个城市C=（1，2,...,n），任意两个城市i，j之间的距离为dij

，求一

条经过每个城市的路径π=（π（1），π（2），...，π（n）），使得距离最小。

主要符号说明

Cn个城市的坐标，n×2的矩阵

C_max最大迭代次数

m蚂蚁个数

Alpha表征信息素重要程度的参数

Beta表征启发式因子重要程度的参数

Rho信息素蒸发系数

Q信息素增加强度系数

R_best各代最佳路线

L_best各代最佳路线的长度

求解TSP问题的蚂蚁算法中，每只蚂蚁是一个独立的用于构造路线的过程，

若干蚂蚁过程之间通过自适应的信息素值来交换信息，合作求解，并不断优化。

这里的信息素值分布式存储在图中，与各弧相关联。蚂蚁算法求解TSP问题的

过程如下：

（1）首先初始化，设迭代的次数为C。初始化C=0

（2）将m个蚂蚁置于n个顶点上

（3）m只蚂蚁按概率函数选择下一座城市，完成各自的周游

-.-word资料-

---

每个蚂蚁按照状态变化规则逐步地构造一个解，即生成一条回路。蚂蚁的任

务是访问所有的城市后返回到起点，生成一条回路。设蚂蚁k当前所在的顶点为

i，那么，蚂蚁k由点i向点j移动要遵循规则而不断迁移，按不同概率来选择下

一点。

（4）记录本次迭代最佳路线

（5）全局更新信息素值

应用全局信息素更新规则来改变信息素值。当所有m个蚂蚁生成了m个解，

其中有一条最短路径是本代最优解，将属于这条路线上的所有弧相关联的信息素

值进行更新。

全局信息素更新的目的是在最短路线上注入额外的信息素，即只有属于最短

路线的弧上的信息素才能得到加强，这是一个正反馈的过程，也是一个强化学习

的过程。在图中各弧上，伴随着信息素的挥发，全局最短路线上各弧的信息素值

得到增加。

（6）终止

若终止条件满足，则结束；否则C=C+1，转入步骤（2）进行下一代进化。

终止条件可指定进化的代数，也可限定运行时间，或设定最短路长的下限。

（7）输出结果

-.-word资料-

---

五、数据实验及结果

通过计算机仿真，得出旅行商问题优化结果和平均距离和最短距离，如图所

示：

-.-word资料-

---

六、分析与总结

本文设计了一种基于MATLAB实现的蚁算法，用以求解组合优化难题中的

典型代表旅行商问题。对30个城市旅行商问题进行了测试，所得结果能达到优

化作用，实现了本文的研究目标。

经过对旅行商问题的深入理解，得到了能解决问题的基本数学模型，然后设

计算法的基本思想，技术路线，最后编码。在多次调试，修改后，本算法成功运

行，并实现了最初的设定目标。另外，MATLAB具有丰富的绘图函数，对于绘图

十分方便，这是选择MATLAB解决TSP问题的算法编写、调试的原因。

蚁算法研究处于初期，还有许多问题值得研究，如算法的参数选择、蚂蚁

数的比例等只能通过仿真实验，无法给出理论指导。

-.-word资料-

---

附录：

蚁算法解决旅行商问题MATLAB程序

functionyy=ACATSP

x=[4783987541444]';

y=[948467626499584462696269717876435

50]';

C=[xy];

C_max=50;

m=30;

Alpha=1.5;

Beta=2;

Rho=0.1;

Q=10^6;

%%-------------------------------------------------------------------------

%%主要符号说明

%%Cn个城市的坐标，n×2的矩阵

%%C_max最大迭代次数

%%m蚂蚁个数

%%Alpha表征信息素重要程度的参数

%%Beta表征启发式因子重要程度的参数

%%Rho信息素蒸发系数

%%Q信息素增加强度系数

%%R_best各代最佳路线

%%L_best各代最佳路线的长度

%%=========================================================================

%%第一步：变量初始化

n=size(C,1);%n表示问题的规模（城市个数）

D=zeros(n,n);%D表示完全图的赋权邻接矩阵

fori=1:n

forj=1:n

ifi~=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，但后面的启发因子要取倒数，用eps

（浮点相对精度）表示

end

D(j,i)=D(i,j);%对称矩阵

end

end

-.-word资料-

---

Eta=1./D;%Eta为启发因子，这里设为距离的倒数

Tau=ones(n,n);%Tau为信息素矩阵

Tabu=zeros(m,n);%存储并记录路径的生成

C=1;%迭代计数器，记录迭代次数

R_best=zeros(C_max,n);%各代最佳路线

L_best=inf.*ones(C_max,1);%各代最佳路线的长度

L_ave=zeros(C_max,1);%各代路线的平均长度

whileC<=C_max%停止条件之一：达到最大迭代次数，停止

%%第二步：将m只蚂蚁放到n个城市上

Randpos=[];%随即存取

fori=1:(ceil(m/n))

Randpos=[Randpos,randperm(n)];

end

Tabu(:,1)=(Randpos(1,1:m))';

%%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游

forj=2:n%所在城市不计算

fori=1:m

visited=Tabu(i,1:(j-1));%记录已访问的城市，避免重复访问

J=zeros(1,(n-j+1));%待访问的城市

P=J;%待访问城市的选择概率分布

Jc=1;

fork=1:n

iflength(find(visited==k))==0%开始时置0

J(Jc)=k;

Jc=Jc+1;%访问的城市个数自加1

end

end

%下面计算待选城市的概率分布

fork=1:length(J)

P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);

end

P=P/(sum(P));

%按概率原则选取下一个城市

Pcum=cumsum(P);%cumsum，元素累加即求和

Select=find(Pcum>=rand);%若计算的概率大于原来的就选择这条路线

to_visit=J(Select(1));

Tabu(i,j)=to_visit;

end

end

ifC>=2

Tabu(1,:)=R_best(C-1,:);

end

%%第四步：记录本次迭代最佳路线

L=zeros(m,1);%开始距离为0，m*1的列向量

-.-word资料-

---

fori=1:m

R=Tabu(i,:);

forj=1:(n-1)

L(i)=L(i)+D(R(j),R(j+1));%原距离加上第j个城市到第j+1个城市的距离

end

L(i)=L(i)+D(R(1),R(n));%一轮下来后走过的距离

end

L_best(C)=min(L);%最佳距离取最小

pos=find(L==L_best(C));

R_best(C,:)=Tabu(pos(1),:);%此轮迭代后的最佳路线

L_ave(C)=mean(L);%此轮迭代后的平均距离

C=C+1;%迭代继续

%%第五步：更新信息素

Delta_Tau=zeros(n,n);%开始时信息素为n*n的0矩阵

fori=1:m

forj=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）上的信息素增量

end

Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);

%此次循环在整个路径上的信息素增量

end

Tau=(1-Rho).*Tau+Delta_Tau;%考虑信息素挥发，更新后的信息素

%%第六步：禁忌表清零

Tabu=zeros(m,n);%%直到最大迭代次数

end

%%第七步：输出结果

Pos=find(L_best==min(L_best));%到最佳路径（非0为真）

Shortest_Route=R_best(Pos(1),:)%最大迭代次数后最佳路径

Shortest_Length=L_best(Pos(1))%最大迭代次数后最短距离

subplot(1,2,1);%绘制第一个子图形

DrawRoute(C,Shortest_Route);%画路线图的子函数

subplot(1,2,2);%绘制第二个子图形

plot(L_best);

holdon%保持图形

plot(L_ave,'r');

title('平均距离和最短距离')%标题

functionDrawRoute(C,R)

%%=========================================================================

%%DrawRoute.m

%%画路线图的子函数

%%-------------------------------------------------------------------------

%%CCoordinate节点坐标，由一个×2的矩阵存储

%%RRoute路线

-.-word资料-

---

%%=========================================================================

=length(R);

scatter(C(:,1),C(:,2));

holdon

plot([C(R(1),1),C(R(),1)],[C(R(1),2),C(R(),2)],'g');

holdon

forii=2:

plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)],'g');

holdon

end

title('旅行商问题优化结果')

-.-word资料-