摘要：蚁群算法（ACA）是一种优秀的启发类分布进化算法，对处理组合优化类问题具有极佳的效果。分布式与正反馈机制使得弱小的个体能够与种群联系起来，从而解决复杂的问题。本文简单介绍了算法的原理，描述以及参数的影响。文末列举了该算法在实际生活中的应用及其前景。
关键词： 蚁群算法；参数；TSP
中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）35-0270-03
The Study and Prospect of Ant Colony Algorithm
WANG Yan-wei
（North China University of Technology， Beijing 100144， China）
Abstract：Ant colony algorithm （ACA） is a new kind of heuristic bionic algorithm， which has excellent performance in solving combinatorial optimization problems. Distributed and positive feedback mechanism makes small and weak individual can be connected with the colony， so as to solve complex problems. This paper simply introduces the principle， description of the algorithm and the influence of the parameters. At the end of this paper， the application and prospect of the algorithm in real life are enumerated.
Key words：Ant colony algorithm；parameters；TSP
1 引言
仿生学的飞速发展，生物的行为模式给了人类研究学者很大的启发，他们便由此提出了解决像NP类复杂问题的新颖方法。蚁群算法（ACA）是一个成功的例子。它是一种基于蚂蚁觅食行为的仿生进化算法，M .Dorigo 等人在1991年首次提出了这个算法。蚁群中的蚂蚁在觅食过程中会在其经过的路径上释放“信息素”，蚂蚁并行的探索路径，依靠信息素作为反馈信息选择路径，异步取得最优解，该算法的核心就在于并行分布与反馈[1-2]。蚁群算法对解决TSP，QAP，SJP等问题具有良好的效果，现在其应用已经扩展到各个行业的各方各面。
2 蚁群算法原理
由于蚁群算法是受蚂蚁觅食行为启发而想到的一种仿生进化算法。为了更简单地理解这个算法，为此我们首先来观察蚂蚁觅食的过程到底是怎样的。
蚂蚁在觅食时，总能找到最短的路线，这是因为当首只蚂蚁首先到达路口时（无信息素），我们假设其等概率选择其间某一条路径，然后蚂蚁会在其经过的路径上释放“信息素”，而信息素会被蚁群中的其它蚂蚁感知到，后来到达路口的蚂蚁会根据信息素浓度选择路径，浓度越高，蚂蚁走这条路径的可能性越大。在一定时间内，宏观上来看，距离更短的路径会被更多的蚂蚁经过，使得这条路径信息素浓度更高[8]。并且随着时间推移，其他路径上的信息素会逐渐挥发（或者说蚂蚁们的记忆减弱），信息素的差异会越来越明显，最终蚁群一定会找到那条最优路径。即使突然出现了障碍物，蚁群也会在短时间内找到最优路径。在寻优过程中，蚂蚁们并行寻路，虽然个体能力不足，但它们通过信息素作为反馈信号与种群进行间接地交流，然后找到了最优路径。
人工蚁群与自然蚁群具有很高的相似性，二者的觅食模式是相同的，但是人工蚁群在选择路径时，并不会像自然蚂蚁那样仅仅根据信息素盲目的选择，它会根据已知数据有意识的做出更好的选择，例如我们在TSP问题中，我们是知道点与点之间的路径长度以及访问过的节点的，人工蚁群会根据路径长度与信息素浓度二者综合考量来选择路径。
3 基本蟻群算法描述
景，由仿真实验来确定。在不同的实际应用场景下，参数的选择会极大地影响算法的性能。自蚁群算法出现以来，大量的ACO类算法被提出，例如AS，ACS，MMAS算法，并且与其他算法相融合的算法也称层出不穷，但依然缺乏一种普适算法。
4 蚁群算法参数详解
4.1 蚂蚁数量m
蚁群算法是一种启发式仿生进化算法，通过多只蚂蚁组成的种群来获得最优路径。这个过程中，蚂蚁分布式的探路，但是间接地与种群交流协作才是至关重要的。显然，m越大，子集越大，蚁群算法的全局搜索能力和算法的稳定性得以提高，但当m过大时，单只蚂蚁释放的信息素对总体的影响微乎其微，信息正反馈作用会被削弱，搜索时间加长。反之，m 越小，子集越小，个体的影响过于突出，很明显正反馈作用突出，然而收敛速度过快的快，极易陷入局部最优解。蚂蚁数量的多少对于蚁群算法搜索的循环次数大致上是线性关系的，文献[5]提出：当蚂蚁数量处于0.6倍城市数量和0.9倍城市数量之间时，在短时间内可以得到一个相对优秀的解。m值的选择依靠于实际情况，对于不同的问题，一般通过仿真实验得到适应的参数。
4.2 信息素挥发因子ρ
前文中提到人工蚁群具有一定的记忆能力，仿照人类记忆的特点，随着时间发展，记忆应该被减弱。在算法中设置了ρ来代表信息素的挥发程度。收敛速度慢，局部最优解是蚁群算法不可避免的两大缺点。而ρ的选择对这些缺点的影响极其巨大。如果ρ过大的话，以前路径上的信息素挥发过快，本次循环中能见度占主导地位，正反馈加强，收敛速度加快，却容易得到局部最优解，降低了全局的搜索能力。反之，ρ过小的话，正反馈相对较弱，收敛速度缓慢，耗时过长，相对的也增加了全局搜索能力。参考文献[4]的研究，我们了解到当ρ取值接近0.5时，蚁群算法的收敛速度与全局搜索能力较好。
4.3 信息启发因子α和期望启发因子β
5 应用及前景
蚁群算法自提出以来已经解决了很多实际的问题。例如在网络中数据的传递，路由器就相当于城镇，各个路由器的连接存储在路由表中，而需要传递的数据就相当于蚂蚁，如何更快更准确的找到最优的路径，这和TSP问题是很相似的。蚁群算法在该领域的可行性在文献[6]中已经得到证实，其得到的路径长度和呼叫拒绝率均优于最小节点负载优先的方法。还有生产调度类问题，比较著名的QAP和JSP，蚁群算法都具有良好的性能。而在电力系统优化问题中，机组最优投入问题是寻求一个周期内各个负荷水平下机组的最优组合方式及开停机计划，使运行费用最小。利用路径信息，决策信息，以及电网状态信息等相关参数，将机组最优投入问题类比为一个TSP问题[7]， 从而可方便地利用蚁群算法来求解.在连续函数优化，机器人路径规划，光谱解析等各个领域，蚁群算法都表现出了极佳的性能，该算法的前景可以说是一片光明。
但是对于该算法的认识还远远不足，我们还有很长的路要走。就目前而言，大量的研究还是基于对蚁群算法的仿真和优化，研究的深度还远远不够。随机优化和动态优化，新的分析方法和模型，参量的合理选择将会是本算法将来重要的研究方面。即使蚁群算法在一些领域中表现优秀，但它仍然不具有普适性，如何扩大其应用范围，增强其稳定性与速度必也是研究学者不得不考虑的一大难题。
6 结语
蚁群算法是一种新型的仿生进化模拟算法，大量的实验研究已经表明其在组合优化问题中的巨大优势，具有广阔的发展前景。而且蚁群算法鲁棒性强，并且易与其他算法相结合。虽然现在应用依然局限在实际问题上，但随着仿生学的发展和研究的进步，相信会形成一套科学的理论体系和研究方法，这会是一个长期的过程，我们的研究还需不断加深。
参考文献：
[1] Colorni A， Dorigo M ，Maniezzo V， et al .Distributedoptimization by ant colonies[A].Proceedings of the 1stEuropean Conference on Artificial Life[C] .1991.134-142.
[2] DorigoM.Optimization， learning and natural algorithms[D] .Department of Electronics， PolitecnicodiMilano，Italy， 1992.
[3] Walter J， Gutjahr.AGraph_based Ant System and its convergence[J].Future Generation Computer System， 2000（16）：837-888.
[4]詹士昌，徐婕. 蚁群算法中有关参数的最优选择[J].科技同报，2003，19（5）：381-386.
[5]蒋玲艳，张军，钟树鸿.蚁群算法的参数分析[J].计算机工程与应用，2007，43（20）：31-36
[6]李连源，刘泽民，周正.“基于ACS的动态分布式路由算法，”北京邮电大学学报， 2000，23（2）.
[7] Sisw o rahardjo N S， El-Keib A A. Unit commitmentusing the a nt colony sear chalgorithm[A] . Proc of the2002 I ntConf on Pow erSy stem Technology[C]. Kunming， 2002. 2-6.
[8]溫文波.蚁群算法概述[J].石油化工自动化，2001（1）：19-22.