智能算法-蚁群算法(1)

智能算法-蚁群算法(1)插图

1. 蚁群算法

通俗理解:一群蚂蚁想寻找食物。在讨论下,它们决定分头去寻找食物,为每只蚂蚁随机选择出发地,规定每只蚂蚁爬行速度相同,并且每只蚂蚁在爬过的地方会释放信息素,信息素会随着时间逐渐挥发,残留在地上的浓度会越来越低。之后的蚂蚁会更倾向于去探索信息素残留浓度高的那条路,因为这说明上一只蚂蚁爬过这条路找到当前最优解所用的时间短,也就是这条路的距离更短。以这样的方式,不断重复,最终找到最优解。

2. 相应名词对应

  • 蚁群:对应搜索空间的一组有效解(种群规模m)
  • 觅食空间:问题的搜索空间(表现为问题的规模、解的维数n)
  • 信息素:信息素浓度变量
  • 蚁巢到食物的一条路径:一个有效解
  • 找到的最短路径:问题的最优解

3. 主要公式

3.1 蚂蚁的选择概率公式

蚂蚁𝑘当前从城市 𝑖 出发,选择城市 𝑗 作为下一个访问对象的概率为: 智能算法-蚁群算法(1)插图1 其中

  • 𝜏(𝑖,𝑗) 表示当前路径的信息素浓度
  • 𝜂(𝑖,𝑗) 表示当前路径的能见度,计算公式为 𝜂(𝑖,𝑗)=1/𝑑𝑖𝑗,即城市ij距离的倒数
  • 𝛼是预先设置的参数,用来控制相应浓度
  • 𝛽是预先设置的参数,用来控制相应能见度
  • 公式的分子含义为某条路的信息素与能见度的乘积
  • 公式的分母含义为当前所有可走路径的信息素与能见度乘积再加和

3.2 信息素更新公式

当所有蚂蚁进行完一整轮探索,需要重新更新每条路径上的信息素浓度,从而来进行下一轮探索。

智能算法-蚁群算法(1)插图2 其中

  • m表示蚂蚁个数(有m只蚂蚁)
  • 𝜌为信息素的蒸发率,取值范围是 0<𝜌≤1,则(1-𝜌)为挥发系数
  • 𝜏(𝑖,𝑗)为城市i到城市j路径上的信息素浓度
  • Δ𝜏𝑘(𝑖,𝑗)表示:第𝑘只蚂蚁在它经过的边上释放的信息素量,等于蚂蚁k本轮构建路径长度的倒数。
  • 𝐶𝑘 表示路径长度,它是𝑅𝑘 中所有边的长度和。

公式表达的含义为:上一轮探索在路径i-j上留下的信息素浓度:𝜏(𝑖,𝑗)(t)
+ 这一轮所有蚂蚁在i-j路径上新释放的信息素浓度: 智能算法-蚁群算法(1)插图3

就是新一轮i-j路径上的信息素浓度𝜏(𝑖,𝑗)(t+1)(更新后的信息素浓度)

  • Δ𝜏𝑘(𝑖,𝑗)表示:第𝑘只蚂蚁在它经过的边上释放的信息素量,等于蚂蚁k本轮构建路径长度的倒数。\
  • 𝐶𝑘 表示路径长度,它是𝑅𝑘 中所有边的长度和。

4. 算法流程图

智能算法-蚁群算法(1)插图4

发表评论

后才能评论