基于蚁群算法的旅行商问题的研究

    李辉

    摘 要：群居性昆虫行为的研究为计算机科学家提供了设计分布式控制和优化算法的有力方法。对以蚁群算法为代表的群集智能的研究已经逐渐成为一个研究热点。蚁群算法在实际的生活中有很大的用处，比如求解旅行商问题，文章介绍了一种求解复杂TSP的蚁群算法，阐述了该算法的基本原理及实现过程，并且在本文中尝试用编码的形式将基本蚁群算法应用到求解旅行商问题中去。

    关键词：基本蚁群算法；信息素；旅行商问题

    1 意义和目标

    近年来，许多学者对蜜蜂、蚂蚁等一些昆虫的行为进行了大量的研究，特别是他们的集体行为，而这些动物一般都是群居昆虫。每个昆虫的能力虽然十分有限，但昆虫群体的能力却远远超过所有个体能力的总和。比如，蚂蚁群可以快速建立起巢穴与食物之间的最短路径。令人惊奇的是，每只蚂蚁并不直接比较每条路径，而仅仅只是遵守信息素释放/跟随规则就能找到最佳路径。蚂蚁群的这种能力很自然地引起了计算机科学家的兴趣。旅行商问题的定义并不统一，一般广泛认为这样定义：假若有多个城市，而这多个城市的距离为已知条件，这个距离也可以理解为多个城市之间的开销，若要得到某一个旅行商走遍所有城市的一条回路，但必须满足所有城市之间的距离的和为最小，也可以是城市之间的开销达到最小值的这样的一条回路。求解TSP问题的算法较多，但文章使用基本蚁群算法来解决旅行商问题。

    2 国内外研究现状

    为了得到解决组合优化问题的某种计算机智能方法，Mnaeizzo、Cootmi、Dorigo在意大利的米兰理工学院，发现了蚂蚁系统，也就是本文中提到的蚁群算法，这是第一次提出的蚁群算法思想，是从蚂蚁寻找食物的过程中发现的。人们由蚁群的集体行为得到了蚁群算法，可以说传统求解组合优化问题的算法可以称之为新型仿生算法，而蚁群算法就是其中一种。从第一次提出蚁群算法以后，Dorigo等人又对蚁群算法做了不少改进，这些改进可以从以下模块来理解：首先，加强了蚁群算法的实际应用的背景；其次，又有新的算法模型的出现，是从原来蚁群算法的基础上做了较大的改进。20世纪初，科学家们逐渐关注了一种蚁群算法模型，这种模型叫做蚂蚁群体优化，也就是antcolonyoptimization，这是由Dorigo、cmabardena以蚁群算法为前期知识得到的一种求解组合优化问题的方法。后来，wanger，stutzle，Mnomarhce等人在此基础上不断进行研究。由此得到的两种模型被实践到了工作布置机器人和信息分析等领域，这两种模型是分别由Bnobaeau得到的简单闭值模型和Dneuebuogr等人得到的BM模型。其中，简单闭值模型是从蚂蚁群体的分工合作总结出来的，而BM模型是由蚂蚁的筑造墓地的动作集总结出来的。在用蚁群算法解决旅行商问题上，研究者Thomastuzel、Hoferhoos进行了大量的研究，他们发现了一种叫做最大最小系统的求解旅行商问题的方法，他的英文是maxminantsysetm，他的求解结果要胜于普通的蚁群算法。而在国内的蚁群算法研究领域，也呈现了一股热浪，一些研究类的文献也逐渐涌现。由此，在蚁群算法的应用方面也做了很大的改进，比如在路由调度应用和优化应用等方面都进行了大量的时间，当然也有一些进步的地方，下面举出几个有改进和突出性的两个人物：其中自适应蚁群算法，是由王颖发现的，他的英文名字是adpativeAntSystem，在蚁群算法的基础上加上变异参数，是由吴庆洪发现的，他的英文名字叫做MutationAntsystem。从世界自然的生物群中，可以模拟得到很多生物算法，在这很短暂的几十年的发展中，这些生物算法是模拟仿生的，一般来说他的特征是：鲁棒性和通用性，尤其优秀表现在组合优化问题中，特别是离散型方面，同时也获得了大量科学家进行研究。本文尝试的是用蚁群算法解决旅行商问题，是因为蚁群算法在旅行商问题上有很好的解决结果，当然，除了旅行商问题以外，在其他的方面，蚁群算法也能表现的非常优秀、及其强大的生命力和非常好的进步空间，这些主要的问题包括：作业调度问题、GCP问题、NP难题二次分配问题、LSI（Large Scale Integration）设计、通讯互联网中的负载均衡问题、互联网的routing table的选择问题等等。

    3 算法理论分析

    人们通过观察蚂蚁的觅食过程，总结出了蚁群算法。蚂蚁在觅食的过程中，采取了分工合作的机制，并且依靠一种叫做信息激素的化学物质来实现，人们发现，蚂蚁总是能够找到从蚂蚁的窝巢找到食物的最近的路径，这种是通过蚂蚁之间的合作和信息激素来实现的。整个过程可以描述如下：首先，第一只蚂蚁在寻找食物的过程中，是随机行走路径去寻找的，没有一定的依据，也没有前面提到的信息激素，但这只蚂蚁在经过的路径上都会留下一定的信息激素，当第二只蚂蚁路过寻找食物的时候，就根据留下的信息激素去寻找食物，而蚂蚁留下的信息激素具有一定的特征，该信息激素会随着时间的推移逐渐挥发，我们总是假设一只蚂蚁在单位路程上留下的信息激素是相等的，那么经常被蚂蚁经过的路径上留下的信息激素就越高，所有的蚂蚁都是行走在信息激素较高的路径上，久而久之，行走的蚂蚁就越来越多，那么随着时间的推移，寻找的最短路径上留下的信息激素也就最多，这样，所有的蚂蚁都会随着这条最短的路径去寻找食物，那么从蚂蚁窝巢到食物的最短路径就产生了，蚁群算法就是根据这个理论实现的。

    4 算法的技术路线

    从算法的理论分析看出，在蚁群算法中，正是因为信息激素的作用，能够找到最短的路径，走过的蚂蚁越多，留下的信息激素也就越多，而蚂蚁又是根据信息激素较多的路径行走的，正是这种激发的效应实现了蚁群算法。我们的算法也是，在获得最终的最优解也就是最短解的过程中，总是由信息激素的多寡和一些启发式的信息获取下一步的解，并且这个解是对整个全局的最终解的最优解，这样一步一步得到解组合成最终解，注意在整个过程中信息激素是不断挥发的。最后，将这一过程用算法来进行表达：

    ⑴算法涉及到的参数必须在第一步进行确定。主要的参数包括，蚂蚁：N只，信息激素：Y，一般激素的单位为强度，城市：m个，总的迭代次数：k，信息启发式因子：r，期望启发式因子：I，信息素挥发系数：d。城市一般不用名称，用数字代替，分别为：1，2，3，4…m，接着进入下一步。

    ⑵根据总的迭代次数的值，如果此次迭代次数的值小于k，那么进入第六步，否则进入下一步。

    ⑶在其中一个时间，将一个城市定为mi，命令其中一只蚂蚁从mi开始游历所有的城市，当然，蚂蚁会在游历的过程中留下所谓的信息激素，当这只蚂蚁游历完以后，再命令另外一只蚂蚁进行游历，同样，该蚂蚁也会在路上留下信息激素，同样的过程，命令所有蚂蚁都对所有城市进行一次游历，接着进入下一步。

    ⑷这一步是让所有的城市都要作为起点进行游历，如果有没有作为起点的城市，接着执行上一步，当所有城市作为起点游历完毕，进入下一步。

    ⑸统计得到群补蚂蚁游历的路径距离值，且获取路径上的新的信息激素的值，然后将迭代次数累计，计入上面的第二步。

    ⑹得到最终值，算法终止。

    5 数据实验及结果

    针对51、76个城市的TSP问题的解决方案，将上述提出的蚁群算法结合到改问题中并应用到该问题中，最后进行了仿真实验。

    实验采用visual C++ 6.0 作为开发工具，所用语言为c++。

    实验所需要的硬件环境：硬件为内存为256M，CPU为Pentium Ⅲ的计算机。

    实验的仿真结果如表1、表2所示：

    6 结语

    文章最初的目的只是一个简单的应用，用蚁群算法来解决著名的旅行商问题，只是将理论实践到了具体的问题，所以，本文还有很多的改进空间，这只是一个基本蚁群算法的实现，所以，在实验设计方面还有很大的改进空间。

    [参考文献]

    [1]GutjahrW J.A graph2based ant system and its convergence[J].Future Generation Computer System，2000，16（8）：873-888.

    [2]Dorigo M，Dicaro G.The ant colony optimization metaheuristic New Ideas in Optimization.London，U K：McGrawHill， 1999：11-32.

    [3]邹鹏，周智，江贺，等.求解旅行商问题的循环局部搜索算法的运行时间和性能分布分析[J].计算机学报，2006，29（1）：92-99.

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

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

    [6]林威.基于遗传算法的Job Shop调度问题求解[J].计算机应用，2006，26（7）：1694-l696.

    [7]蔡之华，彭锦国，高伟，等.一种改进的求解TSP问题的演化算法[J].计算机学报，2005（28）：823-828.

    [8]朱喜基.基于蚁群算法的旅行商问题的研究[J].无线互联科技，2012（8）：23-25..