蚁群算法在TSP问题中的参数设定.doc

蚁群算法在TSP问题中的参数设定
　　摘要：蚁群算法是一种新型的模拟进化算法，该算法在解决离散优化问题性能良好。该文介绍了对蚁群算法中的ACO算法的基本思想和实现方法，并对其中的参数进行了说明。关于TSP问题中的各个规模的城市数目，对蚁群算法的参数设置进行了实验分析，并给出了合理的参数设置，对规模类似的离散优化问题能够提供有效的借鉴。
　　关键词：蚁群算法；模拟进化算法；参数设定
　　中图分类号：TP18文献标识码：A文章编号：1009-3044(2011)20-4944-03
　　Parameters Setting of Ant Colony Algorithm in TSP Problem
　　HU Qing-wan, LIU Yong-cai, DIAN Jun-bao, WU Shang
　　(Department of Mathematics and Information Science, Qujing Normal University, Qujing 655011, China)
　　Abstract: Ant colony algorithm is a novel simulated evolutionary algorithm to solve discrete optimization problems with good performance. This article describes the basic idea, the parameters and implementation of ACO algorithm. About the several numbers of cities in the TSP problem, gives ideal parameters of the ant colony algorithm for experimental analysis, the results can be set to similar to the size of discrete optimization problems.
　　Key words: ant colony algorithm; simulates evolutionary algorithm; set parameters
　　20世纪90年代意大利学者M．Dorigo等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法―― 蚁群算法（Ant Colony Optimization，ACO）。用该方法求解TSP问题、分配问题，取得了较好的试验结果。研究显示，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法。其中蚁群算法中参数的设置直接影响到算法的性能，对参数设置的研究越来越重要，但是目前对它的研究大多还处于实验分析阶段。
　　1 蚁群算法基本原理
　　蚁群算法是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现