蚁群算法 | 集智百科
“集智百科精选”是一个长期专栏，持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目，集智百科希望打造复杂性科学领域最全面的百科全书，欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入！
意大利学者Marco Dorigo从蚁群找最短路径的现象中受到启发，于1992年在博士论文中提出了蚁群算法：一种用来在图中寻找优化路径的概率型算法。此后，蚁群算法不断丰富变化，形成了一个算法家族。有代表性的包括蚁群系统和Max-Min蚂蚁系统等。有趣的是，还有学者在大自然的启发下提出了蜂群、鸟群、鱼群算法等。我们会在以后的集智百科中与大家分享。
目录
一、蚁群算法原理
二、蚁群算法应用
三、蚁群算法优劣
四、相关学者
五、蚁群算法延展
六、相关资源推荐
七、集智百科词条志愿者招募
蚁群算法源自对自然界中蚁群觅食行为的深刻观察。科学家发现，蚁群在可以在有障碍物的环境下，找到一条最短到达食物的路径。出现这个现象的原因并非由于某只蚂蚁在指挥，而是依靠整个蚁群的信息传递机制。
这个机制其实很容易理解：蚂蚁在经过的路径上会释放一种气味记号，即信息素。后到的蚂蚁会沿着信息素浓度较高的路径行走。在所有可能的路径中，由于往返最短路径花的时间少，通过频率高，所以信息素浓度高。这又会吸引更多蚂蚁走这条路径，形成正反馈。一段时间后，整个蚁群就会沿着最短路径到达食物了。
每只蚂蚁并不需要知道全局的信息。他们只根据眼前的局部信息，使用简单的规则进行决策。这样，在蚁群集体里，复杂的智能行为会自然涌现。大自然给予我们启示：如果个体都遵循相同的简单规则，就有可能在宏观层面创造出一种集体智慧。
图1：蚁群寻找最短路径机制示意图。N为蚁巢，F为食物。在所有可能的路径中，最短路径上累积的信息素最多。
表1：类比蚁群觅食行为对客观世界的算法描述：
2.蚁群算法应用
2.蚁群算法应用
近年来，蚁群算法应用领域不断扩张。可以有效地解决从旅行商问题、指派问题、图着色问题、网络路由问题到车间调度问题、车辆路径问题、分配问题等等。这些问题总结起来主要是NP-hard的组合优化问题，用传统算法难以或者无法求解。此外，在学术界，许多专门针对蚁群算法的会议吸引大量学者参与到蚁群算法的讨论。在商业界，诸如AntOptima之类的专门公司把蚁群算法应用到商业实战中，充分发挥蚁群算法的市场价值。
蚁群算法最经典的应用场景是解决旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。
问题：假设有一个旅行商人要拜访N个城市，每个城市只能拜访一次，而且最后要回到开始出发的城市。问商人如何能选择一条满足条件的最短路径？
图3：蚂蚁算法解决旅行商问题。三幅图从左至右分别表示迭代过程、各路径信息素累积量和最短路径。
蚁群算法思路：
将N个城市和城市之间的路径看做一个图。放置m只蚂蚁在图中移动。
寻找最短路径步骤：每只蚂蚁都随机选择一个城市作为其出发城市。蚂蚁依据各路径的信息素值和可见度做出选择，运动到下一个城市。等所有蚂蚁都完成他们的旅行后，找到他们中的最短路径（一个解），此步骤完成。
更新信息素：更新各个路径的信息素数值，包括原有信息素的蒸发和有蚂蚁经过的路径上信息素的增加。
重复上述两个步骤。当达到预定的迭代次数或解不再变化时，算法结束，以当前最短路径作为问题的最优解。
图4：蚁群算法流程图
想亲自动手操作一下的同学，欢迎进入集智百科页面查看解决旅行商问题的蚁群算法Python代码实现：
https://wiki.swarma.org/index.php?title=蚁群算法
3.蚁群算法优劣
易获得全局最优解；
应用面广，易于其他问题结合；
分布式计算方式，多个个体并行运算，大大提升了算法的运行效率；
鲁棒性强，采用正反馈机制，使得搜索过程不断收敛，逼近最优解；
蚁群算法的劣势：
虽然一定会收敛，但无法确定收敛所需时间；
理论分析较为困难，算法更侧重于实践层面；
Marco Dorigo
图5：Marco Dorigo
Marco Dorigo是比利时科学研究基金会（The Belgian Funds for Scientific Research F.R.S.-FNRS）的终身研究员，布鲁塞尔自由大学（Université Libre de Bruxelles）的人工智能实验室IRIDIA的联合主任。
他是蚁群优化元启发式（Ant Colony Optimization Metaheuristic）的发明者，并且是群体智能研究领域的创始人之一。他还是《群体智能》（Swarm Intelligence）的创始编辑和总编辑，《群体智能》是群智能研究领域的核心出版物，致力于报道该学科领域的最新研究和新进展。
Thomas Stützle
图6：Thomas Stützle
Thomas Stützle是比利时科学研究基金会的高级研究员，与比利时布鲁塞尔自由大学的IRIDIA实验室合作。他发表了大量论文。仅在元启发法领域的期刊，会议论文集或经其编辑的书籍中，就超过200篇被同行广泛引用。
Luca Maria Gambardella
图7：Luca Maria Gambardella
Luca Maria Gambardella是一位意大利计算机科学家。他是瑞士提契诺州Manno的Dalle Molle人工智能研究所的所长。他和Marco Dorigo及其他人发表了关于使用蚁群算法解决商旅问题的相关理论研究。
5.蚁群算法延展
5.蚁群算法延展
蚁群算法提出之后，不断有学者对其进行丰富与变形，形成了一个算法家族。下面是一些常见的变形算法：
蚁群系统 Ant Colony System (ACS)
蚁群系统算法在三个方面进行了改进：
蚂蚁路径选择的规则：更加倾向于选择具有大量信息素的最短路径;
全局更新规则：每次迭代结束后的全局更新仅应用于最优的蚂蚁而非所有蚂蚁；
新增了局部信息素更新规则。
Max-Min 蚂蚁系统 Max-Min Ant System (MMAS)
目前解决TSP问题最好的蚁群算法之一，在蚂蚁系统的基础上进行了如下更改：
每条路径上可能的信息素数量的范围限制在一个区间内；
信息素的初始值被设定为最大信息素量；
只有最短路径上的信息素会增加，其他城市的信息素挥发。
感兴趣的话可以进一步了解其他变体，包括精英蚂蚁系统 (Elitist Ant System)、基于排序的蚁群系统 (Rank-based Ant System)、连续正交的蚂蚁系统 (Continuous Orthogonal Ant Colony)、递归蚁群优化 (Recursive Ant Colony Optimization) 等。
6.相关资源推荐
6.相关资源推荐
书籍：
蚁群优化算法 Ant Colony Optimization
该书由Marco Dorigo等人编写，描述了关于蚁群算法家族的理论发现，主要算法和目前应用。
图8：Ant Colony Optimization
蚁群优化算法 Ant Colony Optimization
https://www.goodreads.com/book/show/95229.Ant_Colony_Optimization
网站：
笔者用比较简练的语言介绍蚁群算法，同时有Python代码实战和分析。
10分钟搞懂蚁群算法慕课手记
https://m.imooc.com/article/23910?block_id=tuijian_wz
课程：
本课程中，蚁群算法创始人Marco Dorigo介绍了布鲁塞尔自由大学人工智能实验室IRIDIA所做的集群机器人研究项目，以及其参与的两个欧洲研究项目的主要成果，让同类和异类集群机器人从行为上和思维上合作，执行若干不同的任务。通过课程可以更加深入了解集群算法的应用。
蚁群算法创始人Prof. Marco Dorigo分享集群机器人的研究进展和成果
https://campus.swarma.org/course/670
7.百科项目志愿者招募
7.百科项目志愿者招募
作为集智百科项目团队的成员，本文内容由翻译：许菁、审校：李鹏、整理：刘世康，编辑：王淑慧参与贡献。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页，更多信息可以访问其集智百科个人主页：
翻译
许菁：
https://wiki.swarma.org/index.php?title=Yillia_Jing
审校
李鹏：
https://wiki.swarma.org/index.phptitle=木子二月鸟
整理
刘世康：
https://wiki.swarma.org/index.phptitle=Liushikang1992
编辑
王淑慧：
https://wiki.swarma.org/index.php?title=用户:费米子
以上内容都是我们做这项目的起点，作为来自不同学科和领域的志愿者，我们建立起一个有效的百科团队，分配有审校、翻译、编辑、宣传等工作。我们秉持：知识从我而来，问题到我为止的信念，认真负责编撰每一个词条。
在这里从复杂性知识出发与伙伴同行，同时我们希望有更多志愿者加入这个团队，使百科词条内容得到扩充，并为每位志愿者提供相应奖励与资源，建立个人主页与贡献记录，使其能够继续探索复杂世界。
欢迎扫描下方二维码添加负责人加入集智百科团队！
参考资料：
[1]蚁群算法 Scholarpedia：
http://www.scholarpedia.org/article/Ant_colony_optimization
[2]蚁群算法 维基百科：
https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms
[3]蚁群算法 百度百科 :
https://baike.baidu.com/item/蚁群算法/9646604?fr=aladdin
[4]蚁群算法 集智百科
https://wiki.swarma.org/index.php?title=蚁群算法
[5] 集智学园课程
https://campus.swarma.org/play/play?id=10596
[6]集智俱乐部推文
https://swarma.org/?p=18854
来源：集智百科翻译：许菁审校：李鹏整理：刘世康
编辑：王淑慧、曾祥轩
推荐阅读
集智俱乐部QQ群｜877391004
商务合作及投稿转载｜swarma@swarma.org
◆ ◆ ◆
搜索公众号：集智俱乐部
加入“没有围墙的研究所”
让苹果砸得更猛烈些吧！
👇点击“阅读原文”，阅读集智百科的蚁群算法条