基于蚁群算法的TSP问题研究

来学伟

（三门峡职业技术学院信息传媒学院，河南三门峡472000）

基于蚁群算法的TSP问题研究

来学伟

（三门峡职业技术学院信息传媒学院，河南三门峡472000）

阐述了蚁群算法的设计思想、基本原理及基本过程，利用蚁群算法对TSP问题进行求解，体现了进化计算的优越性。

蚁群算法；TSP问题；算法

1 蚁群算法的设计思想

众所周知，蚂蚁是一种群居类动物，常常成群结队地出现于人类的日常生活环境中。科学工作者发现，蚂蚁的个体生活习性相当简便容易，相对来说，蚁群的生活行为就特别复杂，通过这种复杂的行为特征可以实现较为复杂的活动，而且蚁群能根据环境的变迁调整自己的行为特征。比如，蚁群在行进时，道路上的障碍物被蚂蚁发现，它们可以快速地找到在当时条件下最好的行进路径。通过仔细观察研究，我们发现蚂蚁与蚂蚁之间经过信息素来实现信息的交流和传递，因而实现互相合作，表现出有序而复杂的行为习性［1］。蚁群的这种生活习性引起了一些学者的注意，20世界90年代，通过观察和研究自然界蚁群觅食的规律和习性，意大利学者M.Dorigo得出了第一个蚁群算法，进而应用在TSP问题的求解过程中。蚁群算法被提出之后，其应用范围逐渐广泛，算法本身也不断地被完善改进，形成了一系列的蚁群算法（ant colony optimization ACO）。

1.1 蚁群算法的基本原理

通过观察和研究，蚂蚁外出觅食和获得食物后回巢穴的路径中，会在每一处路过的地方留下一些信息素作为标记，留下的信息素可以被和它是同一蚁群中比它后来的蚂蚁感知出来，该信息素会被后来的蚂蚁认为是一种信号，因而对后来的蚂蚁产生巨大的影响。详细地说，就是后来的蚂蚁选择走信息素比较强的路径的可能性比选择走信息素比较弱的路径的可能性大很多，后来的蚂蚁再经过该路径，会加强该路径的信息素的强度。如此循环往复，该路径经过的蚂蚁越多，信息素的强度就越大，信息素越强，经过的蚂蚁就越多，该循环会一直持续到几乎绝大多数蚂蚁都行走在最短的路径为止，该行为就是信息正反馈的一种现象。经过信息素的交流，蚂蚁就会寻觅到蚁穴和食物之间的最短路径。图1是一个生物原型，我们可以通过该原型来了解蚁群算法的原理［2］。

假设有一群（数量比较大）蚂蚁在寻找食物的过程中，随意随机地向不同方向去觅食，其中有一只蚂蚁寻找到食物后，沿着来的时候的路径回到巢穴，在它所经过的路径上会留下信息素，信息素会被蒸发扩散到四面八方，因而路径上的信息素的浓度会越来越低。假设有两只蚂蚁都通过不同的路径找到食物，而且都沿着来的时候的路径回到巢穴，从巢穴到食物所在地可以选择DEF路径，也可以选择DF，很明显，DEF路径长，而DF路径短一些，假设有甲乙丙三只蚂蚁去寻找食物，首先，让甲乙先出发，它们会随机选择DEF和DF两条路径，选择的几率几乎一样，假设甲选择的是DF，乙选择DEF这条路径，它们同时出发，当甲寻找到食物后准备返回时，此时因为乙选择的路径比较长，可能还在路上，由于DF路径上已经存在有甲寻找食物时留下的信息素，而DEF路径上因为乙还没有走完［3］，靠近食物这一端还没有信息素，而蚂蚁的生物特性是沿着信息素浓度强的路径前进，因此蚂蚁甲仍会沿着FD返回，当甲返回至巢穴时，蚂蚁丙开始出发，因为DF路径上，蚂蚁甲一去一回，信息素的浓度显然比DEF强得多，因为乙此时还没有返回，所以丙肯定会选择DF路径去寻找食物，如此循环往复，路径DF上的信息素的浓度只会越来越强，大量的蚂蚁个体会选择DF路径，这样一来，绝大多数蚂蚁选择的都是最短路径。

图1 生物原型

1.2 蚁群算法的基本过程

基于信息正反馈的原理，蚁群算法结合一种启发式的算法，通过选择、刷新及协和调整共三个过程来实现优化，在进行选择的流程中，选择信息素高的路径的概率比较大；而在刷新的流程中，随着经过该路径上的蚂蚁的数量越多，该路径上的信息素的浓度也越大，当然，同时根据时间的推移，挥发的也越多，信息素的浓度也会下降；在协和调整的流程中，通过信息素，蚂蚁进行信息的沟通交流和互相协作。通过选择和刷新的流程，最短路径上的信息素的浓度变的越来越高，从而使下一只蚂蚁通过较短路径使算法收敛，与此同时信息素的不断挥发又使得算法具有探索新的扩展解的多样性，以免算法陷入局部的最优解［4］。

2 应用实例

有关TSP问题是指某个旅行家旅行要经过m个城市，最后回到最早出发的城市，条件是经过各个城市仅一次，同时使得走过的总路程最小。一旦经过城市数量变大，TSP问题的可能解也会迅速地增长，例如，10个城市的TSP问题有大约180 000个可能解，20个城市的TSP问题大约6×106个可能解，50个城市的TSP问题有大约10 525 715 001 371 600个可能解。

下面以TSP问题为例说明蚁群算法的求解过程。假设蚁群中蚂蚁的数量为m，城市i与城市j之间的距离为dij（i，j=1，2，…，n）；t时处于城市i的蚂蚁个数为bi（t），则时刻在城市i和城市j之间残留的信息量为τij（t），而且τij（0）=C（C为常数）。蚂蚁k（k=1，2,…，m）在运动过程中，根据各条路径上的信息量选择路径，且按概率进行选择，即

其中，Lk表示第k只蚂蚁在本次循环中所走路径的总长度。

蚂蚁由式（1）选择构造路径，由式（2）更新路径上的信息素，这两个步骤重复迭代搜索整个空间，最终搜索到信息素较浓的路径形成较短的最优路径。

3 结语

群体的智能的特别的实现案例——蚁群算法，经过模拟生物寻优能力来解决实际问题，受到学术界的广泛关注。从本质上讲，蚁群算法是一种进化模拟算法，它的出现、产生及发展和进化算法的发展是分不开的。假如蚁群算法与群体搜索策略结合起来应用，并且确保群体中的每一个个体之间的信息交流互换，那么蚁群算法就可以表现出进化计算的优越性，也可以得到更广泛的应用［6］。

［1］黄席樾,胡小兵.蚁群算法在K-TSP问题中的应用［J］.计算机仿真,2004,21（12）:162-164.

［2］曹庭珠.投入产出优化模型的发展与创新机遇［J］.山西财经大学学报,2005,27（2）:86-90.

［3］何武.基于蚁群优化算法的无线传感器网络路由算法研究［D］.成都:西南交通大学,2008．

［4］谢宏.蚁群算法解决TSP问题的研究［J］.农业网络信息,2007（3）:22-24.

［5］王冬梅.群集智能优化算法的研究［D］.武汉:武汉科技大学,2004.

［6］陈娟,马晓慧.基于TSP的蚁群算法的研究［J］.现代计算机,2013（3）:8-11.

【责任编辑：王桂珍 foshanwgzh@163.com】

The application of greedy algorithm in TSP problem

LAI Xue-wei
（Institute of Information Media,Sanmenxia Polytechnic,Sanmenxia 472000,China）

The paper introduces the ant colony algorithm design idea and basic principle and basic process,and then use the ant colony algorithm to solve TSP problem,ant colony algorithm can reflect the evolutionary computation superiority.

ant colonyalgorithm;TSP algorithm;algorithm

TP31

A

1008-0171（2017）03-0072-03

2016-11-17

来学伟（1981-），男，河南灵宝人，三门峡职业技术学院讲师。