蚂蚁算法求解TSP问题

蚂蚁算法求解TSP问题

指导教师：李正学 系 别：应用数学系 班 级：2003级06班 姓 名：王源 学 号：200312082

蚂蚁算法求解TSP问题

摘 要 蚂蚁算法是通过蚂蚁觅食而发展出的一种新的启发算法，该算法已经成功的解决了诸如TSP问题。本文简要学习探讨了蚂蚁算法和TSP问题的基本内容，尝试解决一个实例问题并给出C语言算法。 关键词 蚂蚁算法；TSP问题。

1 蚂蚁算法与TSP问题

1.1 蚂蚁算法

蚂蚁算法(Ant Colony Algorithm) 是由意大利学者M.Dorigo ,V. Manierio ,A. Collorni等人于二十世纪九十年代提出的一种新型的模拟进化算法。受到人们对自然界中真实蚁群集体行为研究成果的启发,考虑到蚁群搜索食物的过程与旅行商问题的相似性,利用蚁群算法求解旅行商问题(Traveling Salesman Problem, TSP ) 、指派问题(AssignmentProblem)和调度问题( Scheduling Problem) ,取得了一些比较满意的实验结果。蚁群算法是一种适应性好、鲁棒性强,具有正反馈结构的并行算法。这些初步研究已显示出蚁群算法在求解复杂优化问题(特别是离散优化问题)方面的一些优越性,证明它是一种很有发展前景的方法。蚂蚁算法在各个领域的应用,说明该算法有着广泛的适应性,但由于该算法出现的较晚,对其研究还处于起步阶段,远不如遗传算法、人工神经网络和模拟退火算法那样成熟。算法的很多特性,如算法的收敛性,参数的设定都来自于大量实验统计结果,目前对该算法理论研究有待进一步加强。

经过研究发现，蚂蚁在觅食的过程中通过一种称之为信息素（Pheromone）的物质相互传递信息。更具体地，蚂蚁在运动过程中能够在其所经过的路径上留下信息素，而且在运动过程中能够感受到这种信息素的存在及其强度，并以此指导自己的运动方向。蚂蚁倾向于朝着信息素浓度高的方向前进，因此，由大量蚂蚁组成的蚁群的行为便表现出一种信息的正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚁群就是通过个体之间这种信息交换机制来彼此协作达到搜索食物的目的。

设有甲、乙两只蚂蚁从蚁穴A出发，分别沿AC 和ABC 路径同时在C 处

1

发现食物，又同时沿原路返回（设二者速度一样），同时在路上留下信息素，信息素随着向四周散发其浓度会不断下降。因AC 路径较短，故当蚂蚁甲返回蚁穴A 时，A C 上留下两次信息素，而乙蚂蚁则因为ABC 路径较长，此时才到达D 点，则AD路径上只留下一次信息素。故该段上信息素的浓度比A C路径上的低。而蚂蚁总是倾向于信息素浓度比较高的路径（AC），这条路径就是蚁穴A 与食物C 之间的最短路径。如图1 所示。

图1

蚁群通过信息交换与互相协作找到从蚁穴到食物源的最短路径的机制显然可以被借鉴来求解各种与最优路径相关的组合优化问题。Colorni和Dorigo等人在研究该问题的基础之上提出了一类模拟自然界蚁群觅食行为的模拟进化算法——蚁群算法。

对于进一步复杂的情况，图2形象说明了蚁群寻找最优路径的过程。30只蚂蚁从A点出发,要到达E点,有两条路径可走, ACDE和AHDE,其中BHD 长为2, BCD长为1 , t = 0时刻,蚂蚁在节点B随机选择

图2

路线,而在t = 1时刻,因为BCD 较BHD 短,故在BCD上留下的信息素浓度大,所以在c)中,更多的蚂蚁选较短的路径,留下的信息素会更多,从而吸引更多的蚂蚁选择此路径,最终所有蚂蚁都选择较短的那条路径。

蚂蚁算法在解决很多组合问题(combinato rial p roblem s)上都取得比较理想

2

的效果。其中有两个比较著名的组合问题,QA P 问题(Quadraic

AssignmentProblem) 和JSP 问题(Job- Shop Scheduling Problem) 作相应调整的蚂蚁算法可以比较好地解决这两个组合问题。

另外, 将蚂蚁算法对实际问题的解决也取得一定的进展,如大规模集成电路中的综合布线以及电信网络中的路由等方面的应用。 1. QAP 问题 QA P 问题的目标函数可以用一个nxn 的对称矩阵来描述。蚁群算法基于它和TSP 问题这方面的相似性来解决问题的。QA P 问题的目标函数矩阵S 通过距离向量D 和流向量F的组合组成, Sihdifh。蚂蚁根据可见度信息来选择ih下一个节点, 其中ih1S。矩阵S 的元素值用作启发因子。

ih2. JSP 问题

JSP 问题可以用一个加权图描述。每条边的权值用参数对{Sk1, Gk1}表示。信息Sk1和可见度Gk1是通过最长进程时间或者最短完成时间等要求决定。蚂蚁遍历节点的顺序就是相应的解决答案。在解决10×10 和10×15 的JSP 问题中, 蚂蚁算 法的解与最优解的误差在10% 之内。这是一个相当不错的结果。

1.2 TSP问题

TSP( 旅行商问题) 的简单描述是：一名商人欲到n 个城市推销商品，每两个城市i 和j之间的距离为dji，如何选择一条路径使得商人每个城市走一遍后回到起点，且所走的路径最短。用数学符号表示为：设n维向量表示一条路经

X(c1,c2,...,cn)，目标函数为：minF(x)d(ci,ci1)d(c1cn)T S P 是一个典

i1ni型的组合优化问题，并且是一个NP 难题，其可能的路径总数与城市数目n 是成指数型增长的,所以一般很难精确地求出其最优解，因而寻找出有效的近似求 解算法就具有重要的意义。

其形式化描述为：给定加权图G=（V，E，w），V为顶点集，E为边集，w：E→R+为边权函数，G中一个TSP环路就是一条不重复地访问V中所有顶点的

vkvmHamilton环路，记为Tv1,v2,...,vn，其中对任意的k和m(1kmn)，

且对1kn,vk,v(kmodn)1E,记TSP（G）为G中所有TSP环路的集合，定义w(T)w(v1,vn)w(vi,vi1)，要求权最小的TSP路T*，使得

w(T*)minTTSP(G)ww(T)。

经过多年的发展，TSP 问题的研究方法经历了从简单到复杂；从单一到多元的过程。一般的TSP 问题都是对于具体环境中复杂的，多目标的TSP 问题的一种

3

抽象和简化。随着各种新的相关学科与优化技术的发展，在TSP 问题领域也现了许多新的优化方法。如Hopfield 神经网络优化方法、遗传算法、禁忌搜索和进化规划等优化算法。在全局优化性能方面有所改善，但是很难确定合适的算法参数，且不良参数会导致收敛速度慢或早熟收敛等缺点。为了尽量克服传统算法的局限性，提出了基于模拟退火算法的Hopfield 神经网络优化方法来求解TSP 问题。

其实标准的TSP 问题可以引起许多变形问题：如路径问题、瓶颈问题、多人问题等，根据上述所描述的算法思想，也可以将其思想看成是另一种变形问题——最小比率TSP 问题：假定从一个城市走到另一个城市可得到某种收益，现要确定一条行走路线，使得走该条路线的总行程与总收益之比最小。为了寻求其最优解法，至今，仍然激发着学者们进行不断的探索，于是出现了像科厚南 (Kohonen)的自我组织图(Self-Organizing Map)，弹性网络，蚂蚁算法等方法求解TSP 问题。但情况还是不容乐观。

基于这种现状，学者正朝着混合算法作尝试性的研究，如：将Hopfield 神经网络模型和模拟退火算法相结合，利用Hopfield 算法构成主算法较快得到可行解，用模拟退火算法的概率性逃离局部极小点，而转移到目标函数的其他极小点，从而提高最优解；将遗传算法与模拟退火算法相结合，模拟退火算法采用串行优化结构，而遗传算法采用群体并行搜索。两者相结合，能够使模拟退火成为并行遗传算法，提高其优化性能，同时遗传算法作为一种自适应变概率的变异操作，增强和补充了遗传算法的进化能力；将模拟退火算法和单纯形算法相结合，利用单纯形算法搜索到局部极小点，然后利用模拟退火的突跳性搜索得到单纯形算法的初始解，使它能跳出局部极小点，伴随退温操作通过循环而趋近于全局最优解⋯⋯，算法混合的思想已发展成为提高算法优化性能的一个重要且有效的途径，其出发点就是使各种单一算法相互取长补短，产生更好的优化效率，它是解决如TSP 等优化问题很有前途的方法，所以这可能是今后解决优化问题的特点和发展趋势。

2 解决TSP问题的蚂蚁算法实现步骤

2.1 符号说明

为讨论问题方便，现作如下说明。

1，2，⋯⋯，n分别表示城市编号；m是蚁群中蚂蚁的数量；dij（i，j=1,2,

4

⋯⋯,n）表示城市i 和j之间的距离；bi(t)表示在t时刻位于城市i 的蚂蚁数量(mbi(t))；ij表示在t时刻所能提供的某种启发式信息，也表示由城

i1n市i转移到城市j的期望程度。 例如，可以取ij(t)1dij；ij(t)表示在t 时刻蚁群在城市i和j连线上

放的信息素含量，以此来模拟实际蚂蚁分泌的信息素。初始时假设各路径上

(k)的信息素恒等ij(0)C（为一预设常数）；Pij(t)表示在t时刻蚂蚁k由城

市i转移到城市j的概率。

2.2 转移概率

蚁群中的第k只蚂蚁由i城市转移到城市j 的概率为：

ij(t)ij(t),jallowedkPij(k)(t)is(t)is(t)sallowedk　其他0, （1）

其中，allowedk={1,2,...,n}\\ tabuk 表示蚂蚁k 下一步允许走过的城市的集合，而tabuk是蚂蚁k到目前为止已走过的城市；, , 为参数， 表示路径上的信息量对蚂蚁选择路径所起的作用大小，当= 0时, 算法就是传统的贪心算法； 表示ij(t)的作用，而当0时，就成了纯粹的正反馈的启发式算法。

2.3 信息素的调整

每一只蚂蚁都按照概率（1）来决定它的位置转移，当蚂蚁完成一次循环（即

产生一个闭合路径），各路径上的信息素含量将依据一定的规则调整，随着时间的推移， 以前留下的信息会逐渐消失，整个蚁群完成一组循环后，各路径上的信息素依下式调整：

ij(t1)(1)ij(t)ij(t) （2）

其中：

(0,1)表示信息素含量ij(t)随时间的推移而衰减的程度；

5

(k)ij(t)ij(t), （3）

k1mij(t)表示蚂蚁k在本次循环中在城市i和j之间留下的信息量, 它的计算公

式如下：

(k)ij(t){QLk,若蚂蚁k在本次循环中只经过ij，0，否则 （4）

其中，Q 为常数，Lk为蚂蚁k在本次循环中所走路径的长。 2.4 步骤

2.4.1初始化：指定蚁群规模m，父代种群规模n；输入初始信息素ij(0)及启发式信息ij(0)；随机生成初始蚁群；A(0)(A1(0),A2(0),......Am(0));置t=0。 2.4.2选择操作：从A(t)中按照目标函数值选择出n 只蚂蚁组成第t 代蚁群：

B(t)(Ai1(t),Ai2(t),......,Aim(t))

2.4.3重组：（1） 按公式(3)、(4)设置信息素增量。

（2） 按公式(2)调整信息素含量。 （3） 依适当方式获得启发式信息ij(t1)

（4） 独立、重复地以概率①随机产生蚂蚁Ak(t1)(k1,2,......,m)，由此组成第t+1 代蚁群：A(t1)(A1(t1),A2(t1),

2.4.4终止检验：如果解已达到精度要求，或已达到预设进化时限，则停止，输出中最好的个体为所求问题的近似解；否则，令转2.4.3。

6

图3

2.5蚂蚁算法的优点与不足 优势

根据上述蚁群算法的求解流程,可知用蚂蚁算法能够极大的缩小TSP的求解搜索范围,算法复杂度从降低,由于大规模的行计算,使蚁群算法能够在较大的空间中搜索理想的解;由于采用正反馈机制,收敛速度加快;使用构造性的贪婪算法,能在搜索的早期阶段找到较好的可接受的解。

不足

蚁群算法本质上和模拟退火算法、遗传算法等随机搜索算法一样,容易陷入

7

局部极小点,存在扩大搜索空间与寻找最优解之间的矛盾,仿真实验表明,当搜索空间较小时,难以搜索到满意解,而若要增大搜索空间以提高搜索到最优解的概率,机器运算次数将迅速增多。 改进的方法:优选各种参数。通过大量仿真实验,发现诸如信息素的消散速度,在城市数量一定的情况下,蚂蚁的数量对于算法的影响都至关重要。

2.6一个应用：蚂蚁算法解TSP在多点通信路由问题中的应用

通信网络中多点通信路由问题的实质就是寻找连接一组点的基于某种代价的最小连接树.为简单起见, 在分析问题时可将网络看成无向带权连通图, 用(G,N , C) 代表, 其中N 表示网络结点集合, E 表示网络的连路, 每条边e∈E 的代价函数为C (e) : C≥0, 典型的代价函数包括: 连路上的延迟, 可用资源, 带宽和价格. 多点通信路由问题为: 给定顶点集合DN, 寻找G 中一棵覆盖D 的子树T (V T , V E ) , 使T 的代价最小.求解多点路由问题也可看作求解Steiner 树. 当D = N 时, 所求得的Steiner 树为最小生成树(M ST ).

参考文献

[1] 吴微．神经网络计算．北京：高等教育出版社，2003．

[2] 李志伟.基于群集智能的蚁群优化算法研究[J].计算机工程与设计，2003，8.

[3] 张宗永, 孙 静,谭家华. 蚁群算法的改进及其应用[ J ].上海交通大学报, 2002, 36 (11) :

1564O1566.

[4] 忻斌健,汪 镭,吴启迪. 蚁群算法的研究现状和应用及蚂蚁智能体的硬件实现[ J ]. 同

济大学学报, 2002, 30 (1) :84O86

[5] 马 良, 项培军1 蚂蚁算法在组合优化中的应用[T ]. 管理科学学报, 2001, 4 (2) : 32—

37.

附录 蚂蚁算法求解TSP源程序

#include #include \"math.h\"

/*计算中点*/

float mid(float x1,float x2) { float m;

8

m = (x2-x1)/2; if(m<0) { m = 0-m; m=x2+m; } else m=x1+m; return m ; }

/*计算长度*/

float length(float x1,float y1,float x2,float y2) { float l;

l = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)); return l; }

/*计算坐标*/

float zuobiao(float x1,float y1,float x2,float y2,float x) { float y;

y=(x-x1)*(y2-y1)/(x2-x1)+y1; return y; }

/*把坐标值等分并得到每个等分的长度*/ float df(float x1,float x2,int n) { float a; a = (x2-x1)/n; if(a<0) a=0-a; return a; }

/*---------主函数-------------*/ main()

9

{

float P[101],x1; float shunxu[101],x;

int c,m,n,k,j,i,i2,c2,c3,c4,i1,j1,j2,i3,y,count,lines,points,pnumber; float dx,dy, b0,xm,ym,d, p[101],p0[101],p1[101],L; float pa;

float b[10][101];

float l,P1[10][101],P2[10][101]; count=1; i1=1; l=0; L=0; n=100; pa=0; k = 1; c = 1; c2 = 1; c3 = 1; c4 = 1; printf(\"Please input the number of the lines:\\n\"); scanf(\"%d\ points=2*lines; pnumber=4*lines; m=lines;

printf(\"Please intput the points:\\n\"); for(i=1;i<=pnumber;i++) scanf(\"%f\ p0[1]=0;p0[2]=0;

p0[points+3]=10;p0[points+4]=10; /*取调整线的中点*/ for(i=1;i<=points;i++) {

if(i%2==0)

{

p0[i+1]=mid(p[2*i-1],p[2*i-3]); p0[i+2]=mid(p[2*i],p[2*i-2]); }

}

printf(\"The middle points of the lines:\\n\"); for(i=1;i<=lines;i++)

printf(\"The point %d: %f,%f\\n \

/*初始化路径长度*/

for(i=1;i<=m+1;i++)

10

{l=l+length(p0[i*2-1],p0[i*2],p0[i*2+1],p0[i*2+2]);}

printf(\"The init length=%f\\n\l=0;

/*-----------------------计算-------------------------*/ Loop:

for(i=1;i<=m;i++) {

for(j=0;j<=n;j++)

{ if(p[4*i-1]!=p[4*i-3])

{ dx=df(p[4*i-1],p[4*i-3],n); if(p[4*i-1]{ p0[2*i+1] = p[4*i-3]+j*dx;}

p0[2*i+2] = zuobiao(p[4*i-3],p[4*i-2],p[4*i-1],p[4*i],p0[2*i+1]);

for(i1=1;i1<=m+1;i1++)

l=l+length(p0[i1*2-1],p0[i1*2],p0[i1*2+1],p0[i1*2+2]); P1[i][j]=1/l; pa=pa+P1[i][j]; l=0;

}

else

{ dy=df(p[4*i],p[4*i-2],n); if(p[4*i]p0[2*i+2] = p[4*i]+j*dy; else

p0[2*i+2] = p[4*i-2]+j*dy; p0[2*i+1] = p[4*i-1] ;

for(i1=1;i1<=m+1;i1++)

l=l+length(p0[i1*2-1],p0[i1*2],p0[i1*2+1],p0[i1*2+2]);

P1[i][j]=1/l; pa=pa+P1[i][j]; l=0;

11

} }

L=pa; pa=0;

for(j2=0;j2<=n;j2++) {

P[j2]=P1[i][j2]/L;

/* printf(\"xx%f\ } /*排序paixu();*/

{for(i3=0;i3<=101;i3++)

{shunxu[i3]=0+i3;/*printf(\"sx%f\ for(j1=0;j1<=99;j1++) for(i1=0;i1<=99;i1++) {

if(P[i1]x=shunxu[i1]; x1=P[i1]; shunxu[i1]=shunxu[i1+1]; P[i1]=P[i1+1]; shunxu[i1+1]=x; P[i1+1]=x1;

} }

/* printf(\" line%d:%f\}

if(p[4*i-1]!=p[4*i-3])

{

dx=df(p[4*i-1],p[4*i-3],n);

if(p[4*i-1]{ p0[2*i+1] = p[4*i-3]+shunxu[0]*dx;}

p0[2*i+2] = zuobiao(p[4*i-3],p[4*i-2],p[4*i-1],p[4*i],p0[2*i+1]); } else

12

{ dy=df(p[4*i],p[4*i-2],n); if(p[4*i]p0[2*i+2] = p[4*i]+shunxu[0]*dy; else

p0[2*i+2] = p[4*i-2]+shunxu[0]*dy; p0[2*i+1] = p[4*i-1] ; } }

c2=0;c4=1;

for(i=1;i<=m+1;i++)

{l=l+length(p0[i*2-1],p0[i*2],p0[i*2+1],p0[i*2+2]);}

/*--------------------- printf(\"lenth is:%f \ l=0;

while(k<=lines-1) { k=k+1; goto Loop; }

/*---------------------输出最终结果------------------------*/ printf(\"\\nThe final points:\\n\") ; for(i=1;i<=lines+2;i++)

printf(\"The point %d: %f,%f\\n \ for(i=1;i<=m+1;i++)

{l=l+length(p0[i*2-1],p0[i*2],p0[i*2+1],p0[i*2+2]);} printf(\"The final length=%f\\n\}

13