智能优化算法之蚁群算法_蚁群优化算法

初窥蚁群算法

(持续更新。。。。)

---

更新：再看蚁群算法

前言

蚁群算法适合解决各类路径优化问题，如旅行商问题（Traveling Salesman Problem, TSP）、车辆路径问题（Vehicle Routing Problem, VRP）等，也被应用于调度、网络优化、分类等多个领域。

因为其独特的集体协作特性和优秀的搜索能力，蚁群算法是一个非常受欢迎且实用的全局优化方法(但并不保证一定能得到全局最优解)。在使用蚁群算法时，研究者和工程师通常需要通过试验或根据经验来调整相关参数以达到最佳的性能。

---

一、蚁群算法是什么？

蚁群算法（Ant Clony Optimization， ACO）是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。蚁群算法最早是由意大利学者Colorni A., Dorigo M. 等于1991年提出。经过20多年的发展，蚁群算法在理论以及应用研究上已经得到巨大的进步。

蚁群算法是一种仿生学算法，是由自然界中蚂蚁觅食的行为而启发的。在自然界中，蚂蚁觅食过程中，蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。蚂蚁在移动过程中会在其路径上释放信息素，其他蚂蚁会感知这些信息素并概率性地跟随这些路径。信息素浓度高的路径会吸引更多蚂蚁跟随，因而这条路径的信息素浓度会进一步增强。然而，信息素也会随时间蒸发，这意味着不经常有蚂蚁通过的路径其信息素浓度会减少。这种机制自然形成了一种正反馈过程，帮助蚂蚁群体找到从巢穴到食物源之间的最短路径。

---

二、算法原理

(1) 基本原理

1. 蚁群在觅食时，每只蚂蚁在走过的路径上会留下一种称为信息素的物质在路径分叉口时面临选择：走左边路径还是右边路径？
2. 选择的概率：蚂蚁在选择路径时总是倾向于信息素浓度高的方向移动。
3. 一只蚂蚁的信息素总量视为有限的常数，则蚂蚁走过的路径越短、留在路径上的信息素浓度越高。
4. 信息素本身会随着时间不断挥发。

可以推导与现实相符的出结论：

1. 距离长的路径走过的蚂蚁少、后期信息素浓度增加量小于挥发量，总的变化是减少的
2. 距离短的路径走过的蚂蚁多、后期信息素浓度增加量大于挥发量，总的变化是增加的

因此形成了一个正反馈迭代：距离短的路径信息素浓度高⇒后续蚂蚁选择该路径的概率更大⇒距离短的路径上信息素浓度进一步升高，如此正反馈，整个蚁群最终走在了最短的路径上。

(2) 符号说明

以上为本博客内容的全部符号及含义解释，不需要强行记忆，可根据后文算法核心公式解析一步步进行理解！

(3) 算法核心公式

1. 公式一：蚂蚁对于下一个路径的选择 $${\mathbf{p}}_{\mathbf{ij}}^{\mathbf{k}}\left(\mathbf{t}\right)=\{\begin{array}{l}\frac{{\mathbf{\tau }}_{\mathbf{ij}}\left(\mathbf{t}\right)}{\underset{\mathbf{s}\in {\mathbf{alllow}}_{\mathbf{k}}}{\Sigma }{\mathbf{\tau }}_{\mathbf{is}}\left(\mathbf{t}\right)},\mathbf{j}\in {\mathbf{allow}}_{\mathbf{k}}\\ 0,\mathbf{j}\ni {\mathbf{allow}}_{\mathbf{k}}\end{array}$$ $${\mathbf{\tau }}_{\mathbf{ij}}\left(\mathbf{t}\right):\mathbf{t}时刻，城市\mathbf{i}\mathbf{与城市}\mathbf{j}\mathbf{之间的信息素浓度}$$ $${\mathbf{allow}}_{\mathbf{k}}:\mathbf{蚂蚁}\mathbf{k}待访城市的集合，随着时间推移，其中的城市越来越少，直到为空，表示遍历完所有的城市$$

该公式含义为蚂蚁基于其未到达的城市集合选择下一个前往的城市，利用信息素含量作为概率依据，前往某个未到达城市的概率由其本身的信息素及所有未到达城市的信息素总和所决定，充分体现了自然界中蚂蚁选择前进方向的自然原理。
公式缺点:
1. 该公式只考虑信息素浓度对蚂蚁选择路径概率的影响；
2. 最初几次迭代时每条路径的信息素浓度都很低，选择路径的随机性大；
3. 每条路径都可能有不少蚂蚁，导致蚁群的搜索范围过大，收敛速度过慢。

2. 修改后的公式一$${\mathbf{p}}_{\mathbf{ij}}^{\mathbf{k}}\left(\mathbf{t}\right)=\{\begin{array}{l}\frac{{\left[{\mathbf{\tau }}_{\mathbf{ij}}\left(\mathbf{t}\right)\right]}^{\mathbf{\alpha }}{\left[{\mathbf{\eta }}_{\mathbf{ij}}\left(\mathbf{t}\right)\right]}^{\mathbf{\beta }}}{\underset{\mathbf{s}\in {\mathbf{alllow}}_{\mathbf{k}}}{\Sigma }{\left[{\mathbf{\tau }}_{\mathbf{is}}\left(\mathbf{t}\right)\right]}^{\mathbf{\alpha }}{\left[{\mathbf{\eta }}_{\mathbf{is}}\left(\mathbf{t}\right)\right]}^{\mathbf{\beta }}},\mathbf{j}\in {\mathbf{allow}}_{\mathbf{k}}\\ 0,\mathbf{j}\ni {\mathbf{allow}}_{\mathbf{k}}\end{array}$$$$\mathbf{\alpha }:信息素因子，反映了蚂蚁运动过程中积累的信息量在指导蚁群搜索中的相对重要程度$$$$\mathbf{\beta }:启发函数因子，反映了启发式信息在指导蚁群搜索中的相对重要程度$$$${\mathbf{d}}_{\mathbf{ij}}:\mathbf{城市}\mathbf{i}\mathbf{到城市}\mathbf{j}\mathbf{之间的距离}$$$${\mathbf{\tau }}_{\mathbf{ij}}\left(\mathbf{t}\right):\mathbf{t}时刻，城市\mathbf{i}\mathbf{与城市}\mathbf{j}\mathbf{之间的信息素浓度}$$$${\mathbf{p}}_{\mathbf{ij}}^{\mathbf{k}}\left(\mathbf{t}\right):\mathbf{t}时刻，蚂蚁\mathbf{k}\mathbf{从城市}\mathbf{i}\mathbf{向城市}\mathbf{j}\mathbf{转移的概率}$$$${\mathbf{\eta }}_{\mathbf{ij}}\left(\mathbf{t}\right):{启发函数，表示蚂蚁从城市\mathbf{i}\mathbf{转移到城市}\mathbf{j}的期望程度，这里我们取值为1/\mathbf{d}}_{\mathbf{ij}}$$$${\mathbf{allow}}_{\mathbf{k}}:\mathbf{蚂蚁}\mathbf{k}待访城市的集合，随着时间推移，其中的城市越来越少，直到为空，表示遍历完所有的城市$$

修改后的公式不仅考虑了信息素的影响因素，更重要的是引入了启发函数的概念，大大推进了该算法的进步。
为了加快算法的收敛速度以及蚂蚁的选择准确性，我们选择给蚂蚁开一副“天眼”，利用我们已知的数据去促使蚂蚁在前期更容易选择更近的道路(并不代表每次选择最短的路径就是全局最优解，这是贪心的思想)，不会导致纯随机的选择结果，蚂蚁拥有该作弊器后在全局来看可以更快的选择更优的路径规划，最终尽量帮助蚁群找到全局最优解。
该公式中的信息素因子及启发函数因子的大小对于算法的收敛性具有很大影响，过高的信息素因子数值将导致蚂蚁放弃“天眼”，在前期的选择偏于随机；过高的启发函数因子数值将导致蚂蚁容易基于贪心的思想进行搜索，而贪心在大多数优化问题中并不能找到全局最优解(解决方法待更新)。

3. 公式一：路径上信息素的更新$$\{\begin{array}{l}{\mathbf{\tau }}_{\mathbf{ij}}\left(\mathbf{t}+1\right)=\left(1-\mathbf{\rho }\right)\cdot {\mathbf{\tau }}_{\mathbf{ij}}\left(\mathbf{t}\right)+△{\mathbf{\tau }}_{\mathbf{ij}},0<\mathbf{\rho }<1\\ △{\mathbf{\tau }}_{\mathbf{ij}}=\underset{\mathbf{k}=1}{\stackrel{\mathbf{m}}{\Sigma }}△{\mathbf{\tau }}_{\mathbf{ij}}^{\mathbf{k}}\\ △{\mathbf{\tau }}_{\mathbf{ij}}^{\mathbf{k}}=\{\begin{array}{l}\frac{\mathbf{Q}}{{\mathbf{L}}_{\mathbf{k}}},\mathbf{if}\mathbf{the}\mathbf{ant}\mathbf{k}\mathbf{went}\mathbf{through}\mathbf{i}\mathbf{to}\mathbf{j}\\ 0,\mathbf{else}\end{array}\end{array}$$

公式分析:
1.$${\mathbf{\tau }}_{\mathbf{ij}}\left(\mathbf{t}\right)$$ 是

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/640479