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

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

作者：李艳平

来源：《计算机光盘软件与应用》2013年第14期

摘 要：目前求解旅行商问题效果最好的混合算法是最大最小蚂蚁算法和局部搜索算法，本文对蚁群算法的仿真学原理进行概要介绍，蚁群算法是受自然界中蚁群搜索食物行为启发而提出的一种智能多目标优化算法，通过蚁群觅食过程中最短路径的搜索策略，给出基于MATLAB的蚁群算法在旅行商问题中的应用，并通过实例仿真结果表明，此算法有一定优越性。

关键词：蚁群算法；旅行商问题；仿真；多目标优化 中图分类号：TP301.6

旅行商问题（TSP）是一个经典的组合优化问题。TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个N P完全问题。随着问题规模的增大，人们对复杂事物和复杂系统建立数学模型并进行求解的能力是有限的，目标函数和约束条件往往不能以明确的函数关系表达，或因函数带有随机参、变量，导致基于数学模型的优化方法在应用于实际生产时，有其局限性甚至不适用。基于仿真的优化（Simulation Based Optimization，SBO）方法正是在这样的背景下发展起来的。近年来应用蚁群算法求解旅行商问题，由于其并行性与分布性，特别适用于大规模启发式搜索，实验结果表明这种研究方法是可行的。 1 蚁群算法的仿生学原理

蚁群算法最早是由意大利学者M.Dorigo提出来的，它的灵感来源于蚂蚁在寻找食物过程中发现路径的行为，蚂蚁集体寻找路径时，利用称为“外激素”的生物信息激素选择后继行为的智能过程。蚂蚁是一种群居昆虫，在觅食等活动中，彼此依赖、相互协作共同完成特定的任务。

蚁群的行为是整体协作，相互分工，以一个整体去解决一些对单个蚂蚁来说不可能完成的任务。总体来讲，蚁群有三个方面的行为特征对算法研究具有一定的启发意义，分别是觅食行为、任务分配和死蚁堆积阁。蚁群的觅食行为指蚂蚁从巢穴出发寻找食物并且将食物搬回巢穴过程。当蚂蚁外出寻找食物时，会在自己走过的路径上释放一种称为信息素的物质。每只蚂蚁都朝向信息素最多的方向移动，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向走下去。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一个位置最近已经走过了，它就会尽量避开。蚂蚁一般倾向于走那些信息素强度更高的路径，较短路

龙源期刊网 http://www.qikan.com.cn

径上单位时间内通过的蚂蚁数目越多，留下的信息素也就越多（浓度更高），对蚂蚁产生的吸引力也更强烈，所以使得更多的蚂蚁来走较短的路径。这样就形成了一个正反馈机制，最终能够使得所有的蚂蚁都走蚁穴到食物源的最短路径。 2 用matlab算法求解旅行商问题 2.1 问题分析

旅行商问题的各个城市间的距离可以用代价矩阵来表示，就是邻接矩阵表示法。设s1，s2，……，sp，s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求s1到S的最短路径，显然s1，s2，……，sp，s一定构成一条从s1到S的最短路径，如果不然，设s1，r1，r2，……，rp，s是一条从s1到S的最短路径且经过n-1个城市，则s，s1，r1，r2，……，rp，s将是从S出发的路径长度最短的简单回路且比s，s1，s2，……，sp，s要短，从而导致矛盾。所以，旅行商问题一定满足最优性原理。 2.2 蚂蚁算法求解TSP问题的过程

在求解旅行商问题的蚂蚁算法中，每只蚂蚁都是一个独立的个体，它能够构造路线过程，蚂蚁之间通过信息素值来交换信息，合作求解并且不断优化。初始的蚁群算法是基于图的蚁群算法：graph-based ant system，简称为GBAS，是由Gutjahr W J在2000年的Future Generation Computing Systems提出的，算法描述如下：

（1）初始化，设迭代次数为NC。初始化NC的值为0，给 初始化：t0=nLnn-1。 （2）将m个蚂蚁放置到n个顶点上。

（3）构造解。每个蚂蚁按照状态变化规则逐步地构造一个解，即生成一条线路。蚂蚁的任务是访问完所有的城市后回到起点，生成一条回路。设蚂蚁k当前所在的顶点为i，那么，蚂蚁k由点i向点j移动要遵循状态变化规则而不断迁移，按不同概率来选择下一点。 开发（Exploration）是指按浓度高概率高的原则选路V，这样可以保证选择路径的多样性；q是一个随机数，它的取值范围是在[0，1]之间，当q￡q0时，按（1）式来选最优的路径。

（4）应用全局信息素更新规则来改变信息素值。当所有m个蚂蚁生成了m个解，其中有一条最短路径是本代最优解，将属于这条路线上的所有弧相关联的信息素值按下式更新： tij（t+1）=（1-r）tij（t）+rDtijgb（t） 2.3 MATLAB程序代码

龙源期刊网 http://www.qikan.com.cn

一只蚂蚁搜索路径的MATLB程序如下：

Function [y，val]=travel（distance，tao，alpha，beta） [m，n]=size（distance）；

p=fix（m*rand）+1； %fix取整函数 val=0；%初始路径长度设为0

tabuk=[p]；%假设该蚂蚁都是从第p个城市出发的 for i=1：m-1

np=tabuk（length（tabuk））；%蚂蚁当前所在的城市号 p_sum=0； for j=1：m if isin（j，tabuk） continue； else

ada=1/distance（np，j）；

p_sum=p_sum+tao（np，j）^alpha*ada^beta； end end

cp=zeros（1，m）；%转移概率 for j=1：m if isin（j，tabuk） continue； else

龙源期刊网 http://www.qikan.com.cn

ada=1/distance（np，j）；

cp（j）=tao（np，j）^alpha*ada^beta/p_sum； end end

NextCity=pchoice（cp）； tabuk=[tabuk，NextCity]；

val=val+distance（np，NextCity）； end 3 实例

一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。城市坐标如表1所示。 表1 城市坐标图 城市

坐标 1 2 3 4 5 6 7 8 9

行值 304 639 177 712 488 326 238 196 312 列植 312 315 244 399 535 556 229 104 790 城市

坐标 10 11 12 13 14 15 16 17 18

行值 386 107 562 788 381 332 715 918 161 列植 570 970 756 491 676 695 678 179 370

应用上面的步骤可以解出最短路径出来，结果如图1所示。可得每次最短路径长度的平均值，得出：15-14-25-10-6-28-18-3-7-1-26-8-19-17-27-13-4-2的和是最短路径线路。 图1 最短路径图

龙源期刊网 http://www.qikan.com.cn

4 总结

蚁群算法（ACA）不仅利用了正反馈原理，在一定程度上可以加快进化过程，而且是一种本质并行的算法，个体之间通过不断的交流和传递信息，以便于发现一个最优解。单个个体容易收敛于局部最优，但多个个体通过合作，很快收敛于解空间的某一子集，有利于对解空间的进一步探索，从而不易陷入局部最优。但是ACA也具有速度慢、易陷入局部最优等缺点。蚁群中个体的运动是往往随机的，当群体规模较大时，要找到一条较好的路径就会需要很长的搜索时间，因此还需要对算法进行不断的改进。 参考文献：

[1]陈文兰，戴树贵.旅行商问题算法研究综述[J].滁州学院学报，2010，8：1-6.

[2]薛定宇，陈阳泉.高等应用数学问题MATLAB求解[M].北京：清华大学出版社，2011：197-209.

[3]司守奎.数学建模算法[M].大连：海军航空工程学院出版社，2007：395-411. [4]储理才.基于MATLAB的遗传算法设计及TSP问题求解[J].集美大学学报，2010. [5]王轩，李元香.一种结合局部搜索策略的求解TSP的演化算法[J].计算机工程，2006，32（9）：16-18.

作者单位：菏泽学院 计算机与信息工程系，山东菏泽 274015