蚁群算法原理及其应用【浅谈指导变异蚁群算法】
摘要：蚁群算法是意大利学者Dorigo于1991年提出的一种模拟进化算法，通过模拟蚂蚁在协作搜索食物时的搜索行为来寻求最优解。蚁群算法提出后却在组合优化中获得广泛的应用,如调度、二次分配和网络路由等。同时大量的实验结果表明蚁群优化结果优于遗传算法、进化算法和模拟退火算法，因此如何将蚁群算法应用到连续问题优化并获得其在离散优化问题上同样优异的性能，成为目前的一个研究热点，也是该文的主要研究内容。
关键词：蚁群算法;连续优化;指导变异
中图分类号：TP311文献标识码：A文章编号：1009-3044(2012)18-4407-03
Guided-mutation Ant Colony Algorithm
HU Zhen-yu1,2, WU Xiao-ling3
(1.Zengcheng Radio and Television University, Guangzhou 511300, China; 2.Zengcheng Oriental Occupation Technical School, Guang? zhou 511300, China;3.Zhixin High School, Guangzhou 510080, China)
Abstract: Ant algorithm(AS) is a simulated evolutionary algorithm,proposed by a Italian scholar Dorigo in 1991, and find the optimal solu? tion by simulating the searching mechanism of ant while collaboratively finding food. Since AS was proposed, it has gradually been applied to combinatorial optimization problems,such as scheduling、QAP、and network routing.Because a large of experimental results shows that the results obtained by AS are better than that of genetic algorithm、evolutionary algorithm and simulated annealing algorithm,so how to ap? ply AS to continuous optimization problems and get the performance as that in discrete optimization problems become a research focus, and it is the main research work of this paper.
Key words: ant algorithm optimization; continuous optimization; guided-mutation
智能优化算法作为一种新兴的演化计算技术己成为越来越多研究者的关注焦点。蚁群算法是一种新兴的智能优化算法,主要特点就是:通过正反馈、分布式协作来寻找最优路径。蚁群算法自提出以后在组合优化方面取得了较好的效果,产生了大量的改进算法,如ACS、MMAS、GAAA、CACS带杂交因子的蚁群算法和自适应蚁群算法等[1-4]。该文主要讨论将蚁群算法应用到连续优化问题.
该文详细介绍了蚁群算法在连续空间优化上的一些关键问题如连续空间的离散化,以及在离散化了的连续空间上的状态转移方式。同时也详细阐述了该文提出的新型高精度蚁群算法的几个关键方面,并用实验对该文提出的算法进行测试,结果表明与遗传算法、连续蚁群优化算法、模拟退火算法相比，该文提出的算法计算复杂性大大减少。
构造了visible矩阵中,就可以用来指导蚂蚁变异,若蚂蚁在构建候选解的过程中已经选择了某一节点,且该节点要进行变异,只须比较visible矩阵中选择的节点所在列中与选择的节点直接相邻的两个节点上的值的大小,选择值较小的节点为变异后的值。1.6局部搜索--步长加速法
在蚁群算法中,为获得期望的精度而使迭代次数大大增加,为了减少运算量,该文利用蚁群算法在较少的迭代次数少收敛到优化问题最优解的较小的邻域内某点,再从蚁群算法的搜索到的最优点用步长加速法来搜索最优解,这样可以大大减少运算量。其算法流程见文献[5]。
本节介绍新蚁群算法的主要流程,主要过程如下:
1）蚁群算法初始化,包括蚂蚁数目ant_num、迭代次数iteration、信息素挥发系数volaolittion (2-14)tile、信息素相对重要程度系数Alpha、伪随机比例因子Q0等。