智能优化算法之蚁群算法

x2864272644 · 发表于 2023-4-3 14:59

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只蚂蚁在城市i与城市连接路上释放得信息素浓度， \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、蚁群算法的特点

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

欢迎沟通交流：可以访问blog.csdn.net/qq_20412595?type=lately。
如有程序定制的需求，可联系QQ小号：3617351952（梦回江南）

		自动登录	找回密码
密码			立即注册

智能优化算法之蚁群算法

本帖子中包含更多资源