陈 芳

（大同市安福仪器仪表有限责任公司，山西大同037003）

多元组合ACS-TSP系统

陈 芳

（大同市安福仪器仪表有限责任公司，山西大同037003）

文章提出了用多算法结合蚁族系统（ACS）求解旅行商问题（TSP）的方法，介绍了在ACS-TSP问题上的遗传算法，目的是为了寻找处理旅行商早期停滞现象的解空间。此外，还提出了一种新的最小生成树（MST）算法，结合最近邻（NN）来创建一个初始架构，以便又快又好地解决旅行商问题。

ACS-TSP；遗传算法；最小生成树；最近邻

蚂蚁系统（AS）[1-2]也称为蚁族系统（ACS）[3]，是由Dorigo和他的同事首先提出的，后来经过不断地完善而发展起来的一种蚁群算法。蚁族系统已经被成功地应用于许多领域，如旅行商问题（TSP）[4]、二次分配问题[5]、数据挖掘[6]、空间规划[7]、作业车间调度和其他方面[8-9]。

ACS-TSP算法与遗传算法（GA）、模拟退火（SA）和进化规划（EP）[10]等算法相比较能够产生更好的效果，但仍然需要解决两类问题，即早期停滞和收敛时间。早期停滞是一种现象，当信息素几个弧的强度变的很高时，蚂蚁将一次又一次地构建相应的路线，这就使得在选择最优路径时变得不可能。本文的目的是结合其他算法解决上述问题。

1 基于蚁族系统的TSP问题

蚁族系统是在蚂蚁行为尤其是觅食行为的启发下产生的，自然界中的蚂蚁通过信息素来存放信息，以实现互相沟通。蚂蚁的选择倾向于以正相关的强度来发现线索的特定路径。如果其他蚂蚁没有获得更多的信息素，那么信息素就会消失，即信息失去强度。相反，如果许多蚂蚁选择某一路径下的信息素，会使得路径的信息强度增大，从而吸引越来越多的蚂蚁。

应用ACS解决TSP的工作原理是：M蚂蚁最初被随机定位在n个城市，每只蚂蚁根据转移概率规则来选择城市，从而制定完整的路线。在构建路线的同时，蚂蚁通过应用本地更新规则来改变信息素的数量，当所有蚂蚁构建完成了他们的路线时，全局性的更新将被应用。ACS算法框架为：

1.1 状态转换规则

k蚂蚁的任务是构建一条访问所有城市，然后回到起点的路线。与k相关的还有待参观的城市Jk(r)，其中，r是蚂蚁k目前所处的城市。蚂蚁k从城市r到城市s所使用的规则称为伪随机比例选择规则（或称状态转换规则）：

其中，τ(r,u)代表边缘信息素的量；η(r,u)是城市r和城市u之间距离倒数的启发式函数；β是用来衡量信息素路径相对重要性的参数；q表示在区间[0,1]上随机选择的概率；q0是一个参数，0≤q0≤1；s是随机变量，表明了蚂蚁从城市r选择去城市s的可能路径。

s由下述方程给出：

1.2 局部更新规则

构建一个解决TSP的方案，蚂蚁通过应用下面的本地更新规则来访问边缘路径和改变信息素路径的数量：

其中，ρ表示信息素衰减的参数，0＜ρ＜1；Δτ(r,s)代表初始信息素的水平，Δτ(r,s)＝(n*Lnn)-1；Lnn代表由最近邻启发式产生的路径长度；n代表节点数。

1.3 全局更新规则

全局更新是在所有蚂蚁已经完成了他们的路径之后被执行的，信息素的数量是通过应用下面的全局更新规则来更新的：

其中，α代表信息素衰减参数，0＜α＜1；Lgb是最优路径长度。

2 解决方案

本文运用遗传算法来寻找解空间，以避免出现早期停滞现象，从而获得解决TSP问题的全局最优解。此外，应用最小生成树（MST）构建初始路径来提高算法的效率。

2.1 遗传算法

在每次循环中，通过让最好的蚂蚁去更新路径来提高ACS的性能。但太早排除其他潜在的蚂蚁会导致早期停滞现象，所以在解决ACS问题上引入遗传算法来处理早期停滞现象。

遗传算法（GA）[11]是一种基于遗传和自然选择原则的优化和搜索技术，由John Holland等人开发。遗传算法是在基因概念的基础上衍生出来的，其中包括三个重要的环节，即复制、交叉和变异。这些基因操作只使用原始操作，如复制、交换和翻转基因。利用遗传算法求解最优化问题的优点：（1）遗传算法包括开发以及在操作过程中的探索，这与优化的方法（如梯度下降法）不同；（2）通过利用遗传算法，不仅能够解决线性与非线性规划，还能解决整数规划。

在全局更新阶段，采用了两相策略来提高寻找解空间的能力。在第一阶段，当所有蚂蚁完成了他们的路线后，在所有的蚂蚁路径中选择三条有代表性的路径：一是最优路径，二是中等路径，三是最劣路径。对于这三条路径，应用遗传算法交叉算子的后代方法。在第二阶段，应用最优路径和GA所构建的三条其他路径来解决全局边缘信息素的更新问题。全局更新规则为：

利用上述方法，可以改进ACS-TSP算法框架为：

2.2 旅行商问题的构建方法

最近邻（NN）方法通常是用来构建一个旅行商路线，但这样的方法可能会产生严重的错误。最小生成树（MST）的问题是找到一个最小总成本的生成树图，可以由krushal和Prim算法验证，一个最优路径通常包含70～80%的边缘最小生成树。

基于上述现象，采用一种新的与NN相结合的MST方法来构建一个初始路径。根据具体的TSP问题，构建相应的MST树，形成属于MST树的候选边缘集。因为MST是一个n树，其节点的自由度大于2，选择最长的路径，把从后代节点到祖先节点作为起始路线。然后，把初始路径的结束点作为新的起始节点。选择下一个节点方法为：（1）存在一个没有被候选边缘集访问的边缘，该边缘连接新的起始节点。（2）如果上述方法不成功，则运用NN方法选择最近的没有被访问的节点作为下一个节点。

在初始阶段，利用上面提到的方法，增加少量的信息素以便蚂蚁寻找路径，从而减少收敛时间，最初的路径构建程序框架如下：

3 实验结果

为了验证上述方法的合理性，在计算机上进行模拟。在实验中设置如下参数：q0=0.9，ρ=0.5，α=1，β=2，计算机模拟运行=50。此外，在实验中使用了20只蚂蚁，与之前Dorigo提出的ACSTSP方法相比较，试验结果表明：a280、att532、rat783、u1060、fl1400、rl1889是基准问题。图1显示的是ACS-TSP路径长度和使用rl1889基准问题的对比情况。ACS+TSP+ls与Improved+ls计算路径长度的对比结果，见表1。结果表明，利用TSP与遗传算法以及最小生成树相结合的方法，较好地解决了全局最优解或接近全局最优解的问题。

图1 ACS-TSP路径长度和使用rl1889基准问题的对比

表1 ACS+TSP+ls与Improved+ls计算路径长度的对比

4 结语

多元组合ACS-TSP系统是一种新的可以迅速提高初始路径的战略方法，对大型TSPs决策也能胜任。

[1]Colori A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies[A].Varela F,Bourgine P.Proceedings of the first Europe an conference on artificial life[C].Paris:Elsevier Publishing,1991:134-142.

[2]Dorigo M,Maniezzo V,Colorni A.The ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics-Part B,1996,26(1):29-41.

[3]Dorigo M,Gambardella L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,l(1):53-66.

[4]Tsai Cheng-fa,Tsai Chun-wei,Tseng Ching-chang.A new Hybrid heuristic approach for solving large traveling salesman problem[J].Information Sciences,2004,166(1-4):67-81.

[5]Maniezzo V,Colorni A.The ant system applied to the quadratic assignment problem[J].IEEE Transactions on Knowledge and Data Engineering,1999,11(5):769-778.

[6]Parpinelli R S,Lopes H S,Freitas A A.Data mining with an ant colony optimization algorithm[J].IEEE Transactions on Evolutionary Computation,2002,6(4):321-328.

[7]Bland J A.Space-planning by ant colony optimization[J].International Journal of Computer Applications in Technology,1999,12(6):320-328.

[8]Blum Christian.Ant colony optimization:introduction and recent trends[J].Physics of Life Reviews,2005,2(4):353-373.

[9]Dorigo M,Caro G D,Gambardella L M.Ant algorithms for discrete optimization[J].Artificial Life,1999,5(2):137-172.

[10]Bonabeau E,Dorigo M,Theraulaz G.Swarm Intelligence:From Natural to Artificial Systems[M].New York:Oxford University Press,1999.

[11]Holland J.Adaptation in Natural and Artificial Systems[M].Ann Arbor:University of Michigan Press,1975.

A Multi-Metaheuristic Combined ACS-TSP System

CHEN Fang
（Datong Anfu Instrument and Meter Limited Liability Company,Datong Shanxi,037003)

This paper presents a Multi-Metaheuristic combined Ant Colony System(ACS)-Travelling Salesman Problem(TSP)al⁃gorithm for solving the TSP.We introduce genetic algorithm in ACS-TSP to search solutions space for dealing with the early stagnation problem of the traveling salesman problem.Moreover,we present a new strategy of Minimum Spanning Tree(MST)coupled with Nearest Neighbor(NN)to construct a initial tour for improving TSP thus obtaining good solutions quickly.According to our simulation results,the new algorithm can provide a significant improvement for obtaining a global optimum solution or a near global optimum solution in large TSPs.

ACS-TSP;genetic algorithm;minimum spanning tree;nearest neighbor

TP301

A

1674-0874(2015)05-0069-04

2015-09-20

陈芳（1991-），女，山西大同人，助理工程师，研究方向：企业信息化软件开发与应用。

〔责任编辑 王东〕