群蚁算法文献综述

群算法的严格理论基础尚未奠定，但这种新兴的智能进化仿生算法已展现出勃勃生机。

针对蚁群优化算法的缺点，本文对其进行了研究,并做了改进，然后将改进的算法应用于困难的组合优化问题，现对本文的工作做如下总结：

首先将蚁群算法应用于旅行商问题。针对基本蚁群算法容易出现早熟和停滞现象的缺点，本文提出了一种动态自适应蚁群算法,通过引入信息素的自适应调整策略、限制信息素的范围，和动态增加了信息素的局部更新方式，有效的抑制了收敛过程中的停滞现象，提高了算法的搜索能力。该算法的性能在14点旅行商问题、中国旅行商问题和Ei150问题上得到了验证。

目前物流配送中心选址问题是物流系统中的一个热点问题，它也是一个困难的组合优化问题。目前国内用蚁群算法来解决该问题的论文还不多。针对此问题，本文提出了一种改进的蚁群算法，通过在迭代后期引入动态局部更新准则，减少那些没有被选择的路径上的信息素数量，加大了较优路径和较差路径上的信息素强度的差距，加快了算法的收敛速度，之所以在后期加入此方法，是为了保证算法迭代初期的搜索能力。通过在实际例子上的计算，证明了改进算法的有效性。

车辆路径问题是物流问题中的一个热点问题,也是一个难点问题,它是旅行商问题的一般化,具有比旅行商问题更复杂的内容。针对该问题的特点,本文引入了MMSA中的信息素限制策略,同时增加了动态平滑信息素轨迹策略：当迭代进行到一半时,此时算法已经收敛或者接近于收敛,这时对信息素轨迹进行平滑处理，能有效增加那些较低信息素轨迹解元素被选择的概率，从而提高算法的搜索能力。实验结果表明了改进算法的效果。

由于时间所限,本文仅取得了初步的成果。今后的研究方向可以集中在以下几个方面：

1.进一步完善蚁群优化算法在组合优化问题上的应用研究

TSP问题、VRP问题是著名的组合优化问题,都己被证明为NP难题，目前启发式算法在这方面的研究已很多。本文在采用蚁群优化算法应用于TSP问题、VRP问题上进行了一些研究，但是也发现在小规模问题上的性能比较好，在短时间内就可以获得较优解，获得最优解的概率也很大但随着问题规模的增大，本文的改进算法在求解时效果比较差。而蚁群优化算法在大规模问题上的性能是非常好

13

的，远非其他算法能比,因此本文的算法还不是很成功，还有待于提高性能。同样，物流配送中心选址问题也具有这样的问题。如何对ACO算法作进一步改进，如何设置参数，如何调整策略，以较好地解决中大规模的组合优化问题，还待进一步研究。

2.蚁群优化算法与其他仿生优化算法的融合

蚁群算法本身存在着一定的缺点，针对它的缺点，将其与其他算法相融合，取长补短，弥补自身的不足，可以取得比较好的效果。目前已经有了蚁群算法和遗传算法、免疫算法、神经网络以及等算法的融合。但也只是初步尝试,很多都是针对具体问题来进行的。所解决的问题不同，其融合策略也就存在着很多差异，因此应该在现有成果的基础上继续进行深入研究，努力探索蚁群算法与一种或几种仿生优化算法相融合的统一机制。 3.蚁群优化算法基础数学理论的研究

蚁群优化算法的发展,需要坚实的理论基础，这方面的工作还极其缺乏。1998年，Gutjahr首先在他的论文中借助图论工具证明了ACO算法的收敛性。但这只是一个初步的工作。ACO算法的收敛性严格的数学证明，在更强的概率意义下的收敛性条件,算法中信息素挥发度对算法的收敛性的影响，ACO算法的动力学模型以及根据其动力学模型对算法的性能分析以及ACO算法最终收敛至全局最优解的时间复杂度等工作应是进一步研究的方向。

4.蚁群优化算法应用领域的拓展及与其它相关学科的交叉研究

蚁群优化算法目前最为成功的应用是在大规模的组合优化问题中,下一步应将蚁群优化算法引入更多的应用领域，如自动控制和机器学习等，并与这些相关学科进行深层次的交叉研究，更进一步地促进算法的研究和发展。

参考文献

[1]旅行商问题[DB/OL]. http://baike.http://www.china-audit.com//view/1162183.htm

[2] Dorigo M C, Man I V. Distributed optimization by ant Colonies[ C ]. Proc. 1st European Coof. A rtificial, Pans, France: Elsevier, 1991: 134 - 142

[3] Colom I A. Dor I M, Man I V. An investigation of some properties of an ant algorithm [ C ]. Proceeding of parallel Problem Solving from Nature

14

( PPSN )， France: Elsevier, 1992: 509 - 520

[4] Colomia. Dor I M, Man I V, et al. Ant system for job - shop scheduling [ J ]. Belgian Journal of Operations Statistics and Computer Science, 1994, 34 (1):39 - 53

[5] 定建立，陈增强，袁著祉．遗传算法与蚂蚁算法的融合[J]．计算机研究与发展，2003，40(9):1531-1536

[6] 唐立三 等．非数值并行算法(第一册)——模拟退火算法[M]．北京: 科学出版社，2000

[7] Dorigo M， Gambardella L M． Ant colony system：A Cooperative Learning Approach to the T raveling Salesman Problem[J]． IEEE Trans．On Evolutionary Computation，1997，1(1)：53～66

[8] Colorni A，Dorigo M，Maniezzo V．Distributed optimization by ant colonies [C]．In：Proceedings of ECAL91-European Conference on Artificial Life. Paris，France：Elsevier Publishing，1991:134～142

[9] Watkins C J C H．Learning with delayed rewards [D].University of Cambridge，1989

[10] Dorigo M，Gambardella L M．A study of some properties of Ant-Q[C]. In： Proc；PPSN IV-4th Int．Conf．Parallel Problem Solving from Nature. Berlin ， Germany：Springer-Verlag，1996:656～665

[11] Johnson D S，McGeoch L A. The travelling salesman problem：a case study in local optimization[C]．In：Local Search in Combinatorial Optimization．E H ．L A arts，et a1．e d s．New York ：Wiley and Sons, 1997.

[12] Stutzle T，Hoos H．Improvements on the Ant System：Introducing MAX_MIN Ant System [C]．In：Proceedings of the International CoMerence on Artificial Neural Networks and Genetic Algorithms，Springer Verlag， wien，1997:245～249

[13] Stutzle T，Hoos H．Max-Min ant system [J]．Future Generation Computer System，2000，16 ：889～9l4

15

[14] Lin S, Kernighan B W ． An effective heuristic algorithm for the traveling Salesman Problems [J]．Operations Research，1973，21：498～516

[15] Maniezzo V. Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem．INFORMS J．Comput，1999，11(4)：358～369

[16] Reimann M，Doerner K，Hartl R F．D-ants：savings based ants divide and conquer the vehicle routing problems．Comput．oper．Res，2004，3 1(4)： 563～591

[17] Sorges U，Gunes M，Bouazizi I. ara-the ant colony based routing algorithm for manets．In：Proc．of the 2002 ICPP Workshop on Ad H o e N etworks(IWAHN 2002).2000:79～85

[18] Casta D，Hertz A. Ant Can Colour Graphs [J]．Journal of the operational Research Society，1997，48：295～305

[19] Fan X P，Luo X ，Yi S，et a1． Path planning for robots based on ant colony optimization algorithm under complex environment [J]．Control and Decision，2004，19(2)：166～17O

[20] Dorigo M，Di Caro G. The Ant Colony Optimization meta-heuristic．In： New Ideas Optimization．D. Corne, et a1.,eds．McGraw Hill，London，UK，1999:11～32

[21] Dorige M，Caro G D，Gambardella L M，Ant Algorithms for Discrete Optimization [J]．Artificial Life，1999，5(3)：137～172

16