范秋生

（黄冈职业技术学院计算机科学与技术系，湖北 黄冈 438002）

浅谈旅行商问题与蚁群算法

范秋生

（黄冈职业技术学院计算机科学与技术系，湖北 黄冈 438002）

蚁群算法是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等启发式搜索算法之后的又一种应用于组合优化问题的算法。根据蚁群算法的特性，求解旅行商问题，利用仿真实验程序对蚁群求解旅行商问题进行模拟。

蚁群算法；信息素；旅行商问题(TSP)

引言

蚁群算法就是利用群集智能解决组合优化问题的典型例子。它是继模拟退火算法、遗传算法、禁忌搜索(Tabu Search)算法、人工神经网络算法等启发式搜索算法之后的又一种应用于组合优化问题的算法[1]。

1、旅行商问题(TSP)简介及旅行商问题描述：

给定n个城市的集合{0，1，2，…，n-1}及城市之间环游的费用 ci(j0 ≤i≤n-1，0≤j≤n-1，i≠j)或者距离。TSP问题是指找到一条经过每个城市一次且回到起点的最小费用的环游。若将每个顶点看成是图上的节点，费用 为c连ij接顶点Vi、Vj边上的权，则TSP问题就是在一个具有n个节点的完全图上找到一条费用最小的Hamilton回路[1]。本文所讨论的TSP问题为对称的TSP问题，而不是非对称的TSP问题，对于非对称的TSP问题(ASTP)详情访问TSPLIB。

以下是5个城市集的TSP

图1 -1 对称的TSP

图1 -2 非对称的TSP

旅行商问题的传统求解算法

当了解TSP问题后，我们会感觉到这种求解最优解的问题不算复杂，并且可以很快地的利用所学的传统方法进行模拟求解。

大致算法可能如下：

(1)得到问题的规模，即城市的数量大小；

(2)利用数学中的排列组合求出该问题的所有不同的回路；

(3)利用循环、判断、比较得到最优回路。

在第2步中，可以得到一个完全图的Hamilton回路的数量为

当n=3时，a=1；当然n的最小值为3

当n=4时，a=3；

当n=5时，a=12；对于小规模的n，可以快速地得到最优解。

……但在实际当中n是比较大的，如在TSPLIB提供的数据中n的大小往往不小于30，那么a的值由于(n-1)的作用变得异常的庞大，这对计算的速率带来问题。

首先需要通过n得到所有的Hamilton回路，计算该步时程序片段将会根据n的大小而出现大量的嵌套循环，而这点是难以忍受的，而且由于不得不保存这些回路的各城市信息，大量的插入操作也影响了整体计算的效率，优化的余地较小，如果这一步出现遗漏将影响下一步。

传统算法中会对第3步进行优化，如加上一个初始值较大的最小值Rmin，用于提前结束一些计算，而遗憾的是循环次数根本没有减少。

2、旅行商问题的特点

TSP问题只是NP完全问题的一个缩影，类似TSP的问题较多，如：资源二次分配问题，图的着色问题，车辆的交通调度问题，集成电路的设计问题，通信网络负载问题，0-1背包问题，甚至军事中巡航导弹的导航问题[11]等等。由此可见他们与生活联系紧密，存在普遍性，普遍性的存在导致了处理数据的随机性。

如图的着色问题(三色地图)：相邻的着色块颜色不同，用最少的颜色进行着色。

图2 -3 着色前

图2 -4 着色后

蚁群算法的基本原理可大致描述如下：蚂蚁属于群居昆虫，个体行为极其简单，而群体行为却相当复杂。相互协作的一群蚂蚁很容易找到从蚁穴到食物源的最短路径，而单个蚂蚁则不能。人们通过大量的研究发现，蚂蚁之所以能做到这一点是因为蚂蚁个体之间通过在其所经过的路径上留下一种可称之为信息素的物质来进行信息传递。蚂蚁可以嗅到这种信息素，而且可以根据信息素的浓度来指导自己对前进方向的选择。同时，该信息素会随着时间的推移逐渐挥发掉，基于此，路径的长短及该路径上通过的蚂蚁的数量就对残余信息素的强度产生影响。反过来信息素的强弱又指导着其它蚂蚁的行动方向。蚂蚁倾向朝着信息素强度高的方向移动。于是，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后者选择该路径的概率越大。蚂蚁个体之间就是通过这种信息的交通达到搜索食物的目的。蚂蚁算法是基于以上原理产生的。它是一种随机搜索算法，与其他模型进化算法一样，是通过候选解组成的群体进化过程来寻找最优解[12]。

3、模拟蚁群算法

3.1 利用java语言模拟ant cycle system算法

3.1.1 城市类City.java

由于该类主要是用于存储tsp文件数据，所以该类的设计比较简单。

主要的属性有：城市的编号id，城市的横坐标coordinateX、纵坐标coordinateY。

主要的方法有：setId()，getId()，setCo o rd inateX()，getCo o rd inateX()，setCoordinateY()，getCoordinateY()。

3.1.2 蚂蚁类Ant.java

利用java中的线程模拟蚁群中的蚂蚁。

为了在以后蚂蚁类能够更好的扩展，使每只蚂蚁都能够设置自身的参数α、β、ϱ、Q，所以增设了这些属性。当然tabuk与allowedk是必不可少的，其他属性有编号，初始城市编号，当前城市编号，当前蚂蚁走过的距离，蚂蚁选择下一城市的概率数组等。

允许每只蚂蚁可以根据自身的特点设置自身的选择城市的方法以及更新信息素的方法。这样便可以将蚂蚁类设计为一抽象类，并继承线程类。主要方法有设置选城概率setChooseProbability()，根据随机数判断所选城市，tabuk与allowedk的增减操作，对于run()方法只需按照步骤2至步骤5编写即可。(由于更新信息素的方法的相同，所以将该方法提至到主类)

3.1.3主线程代码

/**

*主线程

*/

public void run(){

while(loopCurrent＜loopCount&&!isAntsStop()){

if(getFinishAntCount()==antCount){//所有蚂蚁完成一次遍历

setBestResult()；//设置最短结果

if(bestChange){

bestDistanceField.setText(""+this.getBestDistance())；

changeTimesValue.setText(""+changeTimes)；

bestRoutArea.setText("起点"+this.getBestRout().toString().replaceAll("，"，"--＞")+"终点")；

tspCanvas.repaint()；

}

updateCitysPheromone()；//更新城市间的信息素

resetAnts()；//重新设置蚂蚁们的相关数据

setFinishAntCount(0)；

loopCurrent++；

this.loopCurrentValue.setText(""+loopCurrent)；

if(loopCurrent＞=loopCount){

setAntsStop(true)；//终止蚂蚁们的遍历

}

for(int i=0；i＜antCount；i++){//唤醒所有等待的蚂蚁

synchronized(ANTS[i]){

ANTS[i].notify()；

}

}

}

}

}

4、结语

本文描述了旅行商问题，利用传统算法求解时的弊端，蚁群算法的基本原理，如何将蚁群算法运用与旅行商问题。

[1]姜长元.基于混合信息素递减的蚁群算法[J].计算机工程与应用,2007,43(32)：62-64.

[2]Colorni A，Dorigo M，Maniezzo V.An investigation of some properties of an ant algorithm[C]//Proc of the Parallel Problem Solving from Nature Conference(PPSN’ 92).Brussels，Belgium：Elsevier Publishing，1992：509～520

[3]王会颖,贾瑞玉,章义刚,齐平.一种求解0-1背包问题的快速蚁群算法[J].计算机技术与发展,2007,17(1)：104-107.

[4]吴庆洪，张纪会，徐心和.具有变异特征的蚁群算法[J].计算机研究与发展，1999，36(10)：1240-1245.

On the Traveling Salesman Problem with the Ant Colony Algorithm

FAN Qiu-sheng
(Huanggang Polytechnic College，Huanggang 438002 Hubei)

Ant colony algorithm is another algorithm applied in combinatorial optimization problems following the simulated annealing algorithm,genetic algorithm,tabu search algorithm,artificial neural network algorithm heuristic search algorithm.According to the characteristics of ant colony algorithm,solving the traveling salesman problem,we can use the simulation programs to simulate the ant colony algorithm traveling salesman problem.

Ant colony algorithm;Pheromone;Traveling salesman problem(TSP)

A

1 672－1047（2010）06－0017-0 3

10.3969/j.issn.1672－1047.2010.06.05

2010-10-03

范秋生，男，副教授。E-mail:fanqiu@hgpu.edu.cn.

［责任审校：金为民］