不正经

这个屌丝很懒，什么也没留下！

热门标签

热门文章

当前位置: article > 正文

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

作者：不正经 | 2024-04-06 18:47:15

赞

踩

蚁群算法公式

1、蚁群算法概述

蚁群算法（Ant Colony Algorithm, ACA）由Marco Dorigo于1992年在他的博士论文中首次提出，该算法模拟了自然界中蚂蚁的觅食行为。
蚂蚁在寻找食物源时，会在其经过的路径上释放一种信息素，并能够感知其它蚂蚁释放的信息素。信息素浓度的大小表征路径的远近， 信息素浓度越高，表示对应的路径距离越短。
通常，蚂蚁会以较大的概率优先选择信息素浓度较高的路径，并释放一定量的信息素，以增强该条路径上的信息素浓度，这样，会形成一个正反馈。最终，蚂蚁能够找到一条从巢穴到食物源的最佳路径，即距离最短.
路径上的信息素浓度会随着时间的推进而逐渐衰减。

2、蚁群算法基本思路

将蚁群算法应用于解决优化问题，其基本思路为：用蚂蚁的行走路径表示待优化问题的可行解， 整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。

3、蚁群算法的核心基本流程

不失一般性，设整个蚂蚁群体中蚂蚁的数量为 $m$ ，城市的数量为 $n$ ，城市 $i$ 与城市 $j$ 之间的相互距离为 $d_{ij}(i,j=1,2,...n)$ ， $t$ 时刻城市 $i$ 与城市 $j$ 连接路径上的信息素浓度为 $\tau _{ij}(t)$ 。初始时刻，各个城市间连接路径上的信息素浓度相同，不妨设为 $\tau _{ij}(t)=\tau _{0}$ 。
蚂蚁 $k(k=1,2,...m)$ 根据各个城市间连接路径上的信息素浓度决定其下一个访问城市，设 $P_{ij}^{k}(t)$ 表示 $t$ 时刻蚂蚁 $k$ 从城市 $i$ 转移到城市 $j$ 的概率，其计算公式如下：

其中，

$\eta _{ij}(t)$ 为启发函数，

$\eta _{ij}(t)=\frac{1}{d_{ij}}$

表示蚂蚁从城市 $i$ 转移到城市 $j$ 的期望程度 $s_{allow_{k}} (k=1,2,...n)$ 为蚂蚁k待访问城市的集合。开始时 $allow_{k}$ 中有（n-1）个元素，即包括除了蚂蚁k出发城市的其它所有城市。随着时间的推进， $allow_{k}$ 中的元素不断减少，直至为空，即表示所有的城市均访问完毕。

$\alpha$ 为信息素重要因子，值越大，表示信息素浓度在转移中的作用越大，

$\beta$ 为启发函数重要因子，值越大，表示启发函数在转移中的作用越大。即蚂蚁会以较大的概率转移到距离短的城市。

在蚂蚁释放信息素的同时，各个城市间连接路径上的信息素逐渐消失，设参数 $\rho(0<\rho<1)$ 表示信息素的挥发程度。因此，当所有蚂蚁完成一次循环后，各个城市间连接路径上的信息素浓度需进行实时更新，具体公式如下：

其中， $\Delta \tau _{ij}^{k}$ 表示第 $k$ 只蚂蚁在城市 $i$ 与城市 $j$ 连接路径上释放的信息素浓度， $\Delta \tau ij$ 表示所有蚂蚁在城市 $i$ 与城市 $j$ 连接路径上释放的信息素浓度之和。

3.1.1、信息素浓度更新模型

1.ant cycle system 模型

ant cycle system模型中， $\Delta \tau _{ij}^{k}$ 的计算公式如下所示。

其中，Q为常数，表示蚂蚁循环一次所释放的信息素总量；Lk为第k只蚂蚁经过路径的长度。

2.ant quantity system 模型

ant quantity system模型中， $\Delta \tau _{ij}^{k}$ 的计算公式如下所示。

3.ant density system 模型

ant density system模型中， $\Delta \tau _{ij}^{k}$ 的计算公式如下所示。

4、核心算法流程

（1）初始化参数
在计算之初，需对相关的参数进行初始化，如蚁群规模（蚂蚁数量） $m$ 、信息素重要程度因子 $\alpha$ 、启发函数重要程度因子 $\beta$ 、信息素挥发因子 $\rho$ 、信息素释放总量 $Q$ 、最大迭代次 $iter-max$ 、迭代次数初值 $iter=1$ 。

（2）构建解空间
将各个蚂蚁随机的置于不同出发点，对每个蚂蚁 $k(k=1,2,..m)$ ，计算其下一个待访问的城市，直到所有蚂蚁访问完所有的城市。

（3）更新信息素
计算各个蚂蚁经过的路径长度 $L_{k}(1,2,...m)$ ，记录当前迭代次数中的最优解（最短路径）。同时对各个城市连接路径上的信息素浓度进行更新。

（4）判断是否终止
若iter<iter_max，则令 $iter=iter +1$ ，清空蚂蚁经过路径的记录表，并返回步骤（2）；否则，终止计算，输出最优解。

5、蚁群算法的特点

采用正反馈机制，使得搜索过程不断收敛，最终逼近于最优解；
每个个体可以通过释放信息素来改变周围的环境，且每个个体能够感知周围环境的实时变化，个体间通过环境进行间接地通讯；
搜索过程采用分布式计算方式，多个个体同时进行并行计算，大大提高了算法的计算能力和运行效率；
启发式的概率搜索方式， 不容易陷入局部最优，易于寻找到全局最优解。

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

推荐阅读

相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

闽ICP备14008679号