蚁群算法在求解旅行商问题中的改进

严小燕 李 旸 夏桂林

（1安徽农业大学信息与计算机学院，安徽 合肥 230036）

（2巢湖学院计算机系，安徽 巢湖 238000）

蚁群算法在求解旅行商问题中的改进

严小燕1，2李 旸1夏桂林2

（1安徽农业大学信息与计算机学院，安徽 合肥 230036）

（2巢湖学院计算机系，安徽 巢湖 238000）

蚁群算法是一种启发式优化算法，在求解旅行商问题等多种组合优化问题上有着优越性。但基本蚁群算法收敛速度慢，易于陷入局部最优解，导致停滞现象出现。针对算法的这些缺点，提出给各条边赋予不同的信息素初始量以加强算法初期信息素的作用，缩小算法的搜索范围；并在进行全局信息素更新时，对到目前为止的最优解、最差解和普通解采用不同的更新策略。实验结果表明，改进的蚁群算法在实验环境下，解决旅行商问题时的性能较基本蚁群算法有较好的表现。

蚁群算法；旅行商问题；信息素初始化；信息素更新

1 引言

旅行商问题 （Traveling Salesman Problem，TSP），是近代组合优化领域的一个典型难题。[1]TSP问题可以形象描述为：给定n个城市（记为：r1，r2，…，rn）和它们两两之间的直达距离（记为：d（ri，rj）），一个旅行商从某一个城市出发，访问每个城市一次且仅一次后再回到原出发城市，要求找出一条最短的旅行路线。即寻找一条巡回路径R=（r1，r2，…rn，），使得公式（1）所示的目标函数最小。

上式中ri为城市号，取值范围为从1到n的自然数。

TSP问题在科学、工程及经济的各个方面具有广泛的应用如：网络通讯、电网规划、管道铺设、交通调度、物流货物配送等。这些问题或者是TSP问题的原型，或者可以转化为TSP问题。TSP问题形式简单、易于描述，是诸多领域内出现的复杂问题的集中概括和简化形式。因此，快速、有效地解决TSP问题有着极高的实际应用价值。

目前求解TSP问题的算法主要可以分为两类：精确算法 （Exact Algorithm）和启发式算法（Heuristic Algorithm）。近年来，启发式算法在求解优化问题领域显示出了自身的优越性。较精确算法，启发式算法可以获得较快的收敛速度和较高质量的全局解。

常用的启发式算法有遗传算法、模拟退火算法、粒子群算法和蚁群算法等。其中，蚁群算法是一种群体启发式算法，与其他优化算法相比具有信息正反馈性、较强的鲁棒性、采用分布式并行计算机制、易于与其它算法相结合等主要特点。[2]

但其不足之处是由于蚂蚁是随机选择路径，导致算法收敛速度较慢，搜索时间较长；且易于陷入局部最优解，易出现早熟、停滞现象。本文将针对基本蚁群算法的上述缺点，在信息素、搜索速度、搜索策略等相应方面对算法进行改进，以改善蚁群算法在解决TSP问题时的性能。

2 蚁群算法原理及数学模型

2.1 蚁群算法的原理

生物学家和仿生学家观察研究发现，蚂蚁在觅食走过的路径上释放一种特有的分泌物——信息素（Pheromone），[3]当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路径越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路口时，选择信息素强度较高路径的概率相对较大。当一条路径上走过的蚂蚁越来越多，其留下的信息素强度也会越来越高，后来的蚂蚁选择这条路径的概率也越来越大，从而进一步增加该路径的信息素强度，这样便形成了一个正反馈机制。而其它的路径上的信息素强度却会随着时间的流逝而削弱。蚂蚁个体之间通过这种信息素传递信息，相互协作，最终蚁群寻找到从蚁穴到食物源的最短路径。

从蚁群在觅食过程中寻找最短路径得到启发，20世纪90年代，意大利学者 Dorigo M，Maniezzo V和Colorni A提出了人工蚁群算法，[4]简称蚁群算法（Ant Colony Algorithm，ACA）。蚁群算法吸收了真实蚂蚁的行为特性，是通过模拟真实蚂蚁群体觅食行为的过程来完成对问题求解的一种仿生优化算法。

2.2 蚁群算法数学模型[5，6]

以求解平面上n个城市（1，2，…，n为城市编号）的TSP问题为例，说明基本蚁群算法模型。首先引入算法相关记号：m是蚁群中蚂蚁的总数目；n是TSP问题规模；dij为城市i与城市j之间的距离；ŋij（t）为启发函数，在 TSP 问题中，一般取ŋij（t）=1/dij； τij（t）为 t时刻路径（i，j）上的信息素量，以此来模拟实际蚂蚁的分泌物；tabuk为禁忌表，用以记录蚂蚁k当前所走过的城市，tabuk集合随着进化过程做动态调整；Pkij（t）表示在 t时刻蚂蚁k由城市i转移到城市j的概率；α是信息启发式因子，表示轨迹的相对重要性；β是期望启发式因子，表示能见度的相对重要性；ρ是信息素挥发系数（0≤ρ＜1)，表示信息素含量 τij（t)随时间的推移而衰减的程度，1-ρ为信息素残留系数。基本蚁群算法的优化过程主要体现在两个方面：路径选择机制和信息素更新机制。

（1）路径选择机制

在算法初始时刻，各条路径上的信息素相等，并设τij（0）=非零常数。将m只蚂蚁随机放在n座城市上，并将每只蚂蚁当前所在的城市设置为它的禁忌表的第一个元素。蚂蚁k（k=1，2，…，m）在搜索过程中，根据各条路径上的信息素量及路径的启发信息（城市之间的距离）来计算状态转移概率以决定其转移方向。每只蚂蚁被随机放到其中的一个城市上，路径构造依据一定的转移概率进行，在t时刻，蚂蚁k由城市i转向城市j的状态转移概率为Pkij（t），其计算公式如下：

其中，allowedk={1，2，…，n}-tabuk表示蚂蚁 k下一步允许选择的城市。上式表明：转移概率Pkij（t）与 ταi·jηβij成正比，蚂蚁在选择路径时会尽量选择路程短且信息素浓度较大的路径。

（2）信息素更新机制

为了模拟避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历（一个循环结束）后，要对残留信息素进行更新处理。（t+n)时刻，所有的蚂蚁完成了一次周游，路径（i，j）上信息素可根据以下公式做调整：

式中△τij（t）表示一次循环中路径（i，j）上的信息素增量，初始时刻△τij（0）=0；τi（jk)（t）表示第 k 只蚂蚁在一次循环中在路径（i，j)上留下的信息素量。

3 蚁群算法的改进与实现流程

基本蚁群算法一般需要较长的搜索时间，且容易出现停滞现象。当一条路径上的信息素较其他的路径多时，后面的蚂蚁会偏向于走这条路径，使之信息素越来越多，算法易于陷入局部最优，即搜索进行到一定时间或程度后，所有蚂蚁个体所发现的解趋于一致。这样不利于进一步搜索得到更好的结果，可能导致无法找到全局最优解。

针对基本蚁群算法存在的不足，本文提出了一种改进的蚁群算法。先求出离各城市最近的若干个城市，构成一个子集。然后，

（1）对每一个当前城市，判断下一个城市是否属于这个子集，从而对各条边赋予不同的初始信息素量以加强算法初期信息素的作用；

（2）在路径状态转移上，增强搜索过程的指导性，同样对每一个当前城市，判断下一个城市是否属于这个子集，再确定转移概率；

（3）信息素更新上，对最优解进行更大限度的增强，而对最差解进行削弱；

（4）为避免由于第（3）点中最优与最差路径信息量之间差距加剧而引起的搜索停滞现象，防止搜索过快地集中到局部最优解的周围，增加对TSP中的每条边上的信息素量的范围限制。

根据以上分析，改进的蚁群算法求解TSP问题的实现步骤如下：

第1步：参数初始化。并令循环次数Nc=0，设置最大循环次数Ncmax，将m只蚂蚁置于n个顶点（城市）上，有区别的给每条边（i，j）设置初始时刻信息量 τij（0），且初始时刻△τij（0）=0。

第2步：将各蚂蚁的初始出发点置于各自的禁忌表中。

第 3 步：每只蚂蚁 k（k=1，2，3，…，m)根据状态转移概率公式计算的概率选择顶点（城市）j，并将蚂蚁移至 j，其中 j∈allowedk，将顶点（城市）j置于该蚂蚁的禁忌表中。

第4步：循环执行第3步，直到每只蚂蚁都生成一条路径；

第5步：求出到目前为止的最优解和最差解；

第6步：分别更新最优解、最差解和普通解中边上的信息量。

第7步：判断各路径上的信息素值是否在限制范围内，如果超出此范围，则强制设为最小值或者是最大值。

第8步：如果循环次数Nc≥Nmax，则循环结束并输出最优路径，否则清空禁忌表，Nc←Nc+1并跳转到第3步，继续下一轮循环。

4 算法实现及结果分析

选用国际上通用的TSPLIB基准库中的Oliver30为例，对本论文提出的改进的蚁群算法进行实验仿真，用VC++编程实现，以验证其有效性。实验环境：操作系统为Microsoft Windows XP Professional，CPU 为酷睿 2 双核（1.6GHz），内存为1G。

分别对基本蚁群算法和改进的蚁群算法进行仿真。改进的蚁群算法的参数配置为：m=26，α=1.0，β=5.0，ρ=0.53，Q=1500，q0=0.22， 基本蚁群 算 法 参 数 配 置 为 ：m=26，α=1.0，β=5.0，ρ=0.53，Q=1500，将两种算法的最大迭代次数都设置为1000次，分别进行15次试验，结果如表1所示。另外，改进的蚁群算法得到的最优解如图1所示。

图1 改进的蚁群算法求解Oliver30问题的最优解

表1 基本蚁群算法和改进的蚁群算法求解Oliver30问题结果比较

从表1中可以看出，在相同的实验环境下，相同的参数设置，相同的最大迭代次数，本文提出的改进蚁群算法得到的最优解（423.912)和平均值（428.585)都要优于基本蚁群算法得到的最优解（440.555)和平均值（456.472)。 仿真结果表明，改进后的算法是有效的。

5 结束语

本文提出的改进蚁群算法通过对信息素初始量以及信息素更新策略等方面的改进，有效地克服了基本蚁群算法收敛速度慢，易于陷入局部最优解的缺点。对TSP问题（Oliver30）进行仿真实验结果表明，改进蚁群算法的性能较基本蚁群算法有明显的改善。

[1]E L Lawler，J K Lenstra and D B Shmoys（eds.）.The Traveling Salesman Problem： A Guided Tour of Combinatorial Opti mization[M].New York： John Wiley&Sons，1985.

[2]李士勇.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社，2004.

[3]孙京浩，李秋艳，杨欣斌等.基于蚁群算法的故障识别[J].华东理工大学学报，2004，30（2）：194-198.

[4]Colorni A.，Dorigo M.，Maniezzo V，et al.Distributed optimization by ant colonies[C].Proceedings of the First European Conference on Artificial Life，1991：134-142.

[5]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.

[6]周康，强小利，同小军等.求解 TSP 算法[J].计算机工程与应用，2007，43（29）：43-47.

AN ANT COLONY ALGORITHM BASED IMPROVEMENT FOR TSP SOLUTIONS

YAN Xiao-yan1，2LI Yang1XIA Gui-lin2
（1 School of Information and Computer Science，Anhui Agricultural University，Hefei Anhui 230036）
（2 Computer Department of Chaohu College，Chaohu Anhui 238000 ）

The ant colony algorithm is a heuristic algorithm.It has advantages on a variety of combinatorial optimization problems such as the TSP.However，basic ant colony algorithm may converge slowly and fall into local optimal solution easily，which leads to stagnation.to avoid these shortcomings of the algorithm，it is proposed that different initial amount of pheromone be given to different edges in order to enhance the effects of the pheromone in the early algorithm and narrow the algorithm search range； it is also the purpose to carry out the global pheromone update，the best solution，the worst solution and general solution with different update strategies.Experimental results show that improved ant colony algorithm has better performance in solving the TSP than the basic ant colony algorithm in experimental conditions.

ant colony algorithm；TSP；initialization of pheromone；update of pheromone

TP301.6

A

1672－2868（2010）06－0021－04

2010－08-21

严小燕（1984-），女，安徽庐江人。安徽农业大学计算机应用技术专业研究生，巢湖学院计算机系教师。研究方向：计算机网络。

责任编辑：陈 侃