蚁群算法研究及前景
开篇：润墨网以专业的文秘视角，为您筛选了一篇蚁群算法研究及前景范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：蚁群算法（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时，蚁群算法的收敛速度与全局搜索能力较好。