蚁群算法
 |
蚁群算法（Ant Colony Optimization，ACO），又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文“Ant system: optimization by a colony of cooperating agents”中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。
常见的扩展
[编辑]下面是一些最常用的变异蚁群算法：[1]
精英蚂蚁系统
[编辑]全局最优解决方案在每个迭代以及其他所有的蚂蚁的沉积资讯素。
最大最小蚂蚁系统（MMAS）
[编辑]添加的最大和最小的资讯素量[ τmax，τmin ]，只有全局最佳或迭代最好的巡逻沉积的资讯素。所有的边缘都被初始化为τmax并且当接近停滞时重新初始化为τmax。
蚁群系统
[编辑]蚁群系统已被提出。
基于排序的蚂蚁系统（ASrank）
[编辑]所有解决方案都根据其长度排名。然后为每个解决方案衡量资讯素的沉积量，最短路径相比较长路径的解沉积了更多的资讯素。
连续正交蚁群（COAC）
[编辑]COAC的资讯素沉积机制能使蚂蚁协作而有效地寻解。利用正交设计方法，在可行域的蚂蚁可以使用增大的全局搜索能力和精度，快速、高效地探索他们选择的区域。 正交设计方法和自适应半径调整方法也可推广到其他优化算法中，在解决实际问题施展更大的威力。
收敛
[编辑]一些版本的算法可以被证明是收敛的（即它能够在有限时间找到全局最优解）。第一个蚁群算法收敛的证据制作于2000年，建立了基于图像的蚁群算法，继而是ACS和MMAS的算法。像大多数元启发式方法一样，估计理论收敛速度是很难的。在2004年，Zlochin和他的同事们表明，COA-type算法在分布算法的叉熵和估计方面能被随机梯度下降法吸收。他们建议这些元启发式方法作为一个“研究性模式”。
应用
[编辑]蚁群优化算法已应用于许多组合优化问题，包括蛋白质折叠或路由车辆的二次分配问题，很多派生的方法已经应用于实变量动力学问题，随机问题，多目标并行的实现。它也被用旅行推销员问题的拟最优解。在图表动态变化的情况下解决相似问题时，他们相比模拟退火算法和遗传算法方法有优势；蚁群算法可以连续运行并适应实时变化。这在网络路由和城市交通系统中是有利的。
第一蚁群优化算法被称为“蚂蚁系统”，它旨在解决推销员问题，其目标是要找到一系列城市的最短遍历路线。总体算法相对简单，它基于一组蚂蚁，每只完成一次城市间的遍历。在每个阶段，蚂蚁根据一些规则选择从一个城市移动到另一个：它必须访问每个城市一次;一个越远的城市被选中的机会越少（能见度更低）;在两个城市边际的一边形成的资讯素越浓烈，这边被选择的概率越大;如果路程短的话，已经完成旅程的蚂蚁会在所有走过的路径上沉积更多资讯素，每次迭代后，资讯素轨迹挥发。
调度问题
[编辑]车间作业调度问题（JSP）
开放式车间调度问题（OSP）
排列流水车间问题（PFSP）
单机总延迟时间问题（SMTTP）
单机总加权延迟问题（SMTWTP）
资源受限项目调度问题（RCPSP）
车间组调度问题（GSP）
附带依赖安装时间顺序的单机总延迟问题（SMTTPDST）
附带顺序相依设置/转换时间的多阶段流水车间调度问题（MFSP）
车辆路径问题
[编辑]限量车辆路径问题（CVRP）
多站车辆路径问题（MDVRP）
周期车辆路径问题（PVRP）
分批配送车辆路径问题（SDVRP）
随机车辆路径问题（SVRP）
装货配送的车辆路径问题（VRPPD）
带有时间窗的车辆路径问题（VRPTW）
依赖时间的时间窗车辆路径问题（TDVRPTW）
带时间窗和复合服务员工的车辆路径问题（VRPTWMS）
分配问题
[编辑]二次分配问题（QAP）
广义分配问题（GAP）
频率分配问题（FAP）
冗余分配问题（RAP）
设置问题
[编辑]覆盖设置问题（SCP）
分区设置问题（SPP）
约束重量的树图划分问题（WCGTPP）
加权弧L-基数树问题（AWlCTP）
多背包问题（MKP）
最大独立集问题（MIS）
其他
[编辑]面向关系的网络路由
无连接网络路由
数据挖掘
项目调度中的贴现现金流
分布式资讯检索
网格工作流调度问题
图像处理
系统识别
蛋白质折叠
电子电路设计
相关的方法
[编辑]遗传算法（GA）支持一系列的解决方案。解的合并或突变增加了解集，其中质量低劣的解被丢弃，寻找高级解决方案的过程模仿了这一演变。
模拟退火（SA）是一个全局优化相关的通过产生当前解的相邻解来遍历搜索空间的技术。高级的相邻解总是可接受的。低级的相邻解可能会根据基于质量和温度参数的差异的概率被接受。温度参数随着算法的进程被修改以改变搜索的性质。
反作用搜索优化的重点在于将机器学习与优化的结合，加入内部反馈回路以根据问题、根据实例、根据当前解的附近情况的特点自动调整算法的自由参数。
禁忌搜索（TS）类似于模拟退火，他们都是通过测试独立解的突变来遍历解空间的。而模拟退火算法对于一个独立解只生成一个突变，禁忌搜索会产生许多变异解并且移动到产生的解中的符合度最低的一个。为了防止循环并且促进在解空间中的更大进展，由部分或完整的解组建维系了一个禁忌列表。移动到元素包含于禁忌列表的解是禁止，禁忌列表随着解遍历解空间的过程而不断更新。
人工免疫系统（AIS）算法仿照了脊椎动物的免疫系统。
粒子群优化（PSO），群智慧方法。
引力搜索算法（GSA），群智慧方法。
蚁群聚类方法（ACCM中），这个方法利用了聚类方法扩展了蚁群优化。
随机传播搜索（SDS），基于代理的概率全局搜索和优化技术，最适合于将目标函数分解成多个独立的分布函数的优化问题。
历史
[编辑]蚁群优化算法的年表：
1959年，Pierre-Paul Grassé发明了Stigmergy理论来解释白蚁建设巢的行为。
1983年，Deneubourg和他的同事们研究了蚂蚁的集体行为。
1988年，Moyson Manderick写了一篇蚂蚁自组织的文章。
1989年，Goss, Aron, Deneubourg和Pasteels关于阿根廷蚂蚁的集体行为的研究，给蚁群优化算法的思想提供了灵感。
1989年，Ebling和他的同事落实了觅食行为的模型。
1991年，M. Dorigo在他的博士论文中提出了蚂蚁系统（文章于1992年发表）。一份从论文中提取的技术报告五年后出版，由V. Maniezzo和A.Colorni合著。
1996年，蚂蚁系统的文章出版。
1996年，Hoos与Stützle发明了最大最小蚂蚁系统。
1997年，Dorigo和Gambardella发布了蚁群系统。
1997年，Schoonderwoerd和他的同事们开发了对电信网络的首次应用。
1998年，Dorigo发起了第一次蚁群算法的专题会议。
1998年，Stützle提出初步的并行实现。
1999年，Bonabeau, Dorigo和Theraulaz的出版了一本书，主要关于人工蚂蚁。
2000年，未来电脑系统杂志上发表了蚂蚁算法特刊。
2000年，调度的最早期的应用程式，调度了序列和约束的满意度。
2000年，Gutjahr提供了一个蚁群算法收敛的第一个证据。
2001年，COA算法首次被使用（Eurobios和AntOptima）。
2001年，IREDA和他的同事们发表了第一个多对象算法。
2002年，调度设计的首次应用，贝叶斯网络。
2002年，比安奇和她的同事提出了随机问题的最早算法。
2004年，Zlochin和Dorigo表明，有些算法等价于随机梯度下降法，交叉熵优化法和估计分布算法。[2]
2005年，首次在蛋白质折叠问题上的应用。
- ^ 一文搞懂蚁群算法（含例程） - 掘金. juejin.cn. [2024-08-09]. （原始内容存档于2024-08-09）.
- ^ M. Zlochin, M. Birattari, N. Meuleau, et M. Dorigo, Model-based search for combinatorial optimization: A critical survey, Annals of Operations Research, vol. 131, pp. 373-395, 2004.