蚁群算法学习
标签搜索

蚁群算法学习

BeforeIeave
2022-10-22 / 0 评论 / 318 阅读 / 正在检测是否收录...
蚁群算法

蚁群算法

算法介绍

假如蚁群中所有蚂蚁的数量为m,所有城市之间的信息素用矩阵pheromone表示,最短路径为bestLength,最佳路径为bestTour。每只蚂蚁都有自己的内存,内存中用一个禁忌表(Tabu)来存储该蚂蚁已经访问过的城市,表示其在以后的搜索中将不能访问这些城市;还有用另外一个允许访问的城市表(Allowed)来存储它还可以访问的城市;另外还用一个矩阵(Delta)来存储它在一个循环(或者迭代)中给所经过的路径释放的信息素;还有另外一些数据,例如一些控制参数(α,β,ρ,Q)。

算法参数设置

蚂蚁数量(m):一般设置为目标数量的1.5倍。

信息素常量(Q):根据经验一般取值在[10,1000]。

最大迭代次数(t):一般选择[100,500]之间,取200次为优。

信息素因子(α):反映了在蚂蚁运动的过程中路径上积累的信息素的量在指导蚁群搜索中的相对重要程度,取值范围常在[1,4]。

启发函数因子(β):反映了启发式信息在指导一群搜索中的相对重要程度,蚁群寻优过程中先验性、确定性因素作用的强度,取值范围常在[0,5]。

信息素挥发因子(ρ):反映了信息素的消失水平,1-ρ反映了信息素的保持水平,取值范围通常在[0.2,0.5]。

路径构建

  • 每只蚂蚁随机选择一个城市作为其出发城市,并维护一个记忆向量(禁忌表),用于存放该蚂蚁已经经过的城市。

  • 在蚂蚁构建路径的每一步中,使用轮盘赌法选择下一步要到达的城市。

    kijPijk={τijα(t)ηijβ(t)sallowedkτijα(t)ηijβ(t)jallowedk0
    • ij 分别代表起点和终点。
    • ηij(t)=1dij 是起点 i 和终点 j距离的倒数,用于表示蚂蚁从 i 到 j 的能见度。(距离越小能见度更大)
    • τij(t) 是时间 t 时,由 ij 的信息素浓度。
    • allowedk 是尚未访问过的节点的集合。

信息素的更新

τij(t+1)=τij(t)(1ρ)+Δτij0<ρ<1:Δτij=k=1mΔτijk
  • τij(t+1) 表示第t+1次循环后城市 i 到城市 j 上的信息素含量。
  • 1-ρ 表示信息素残留系数
  • Δτij 表示新增信息素含量 = m只蚂蚁在城市 i 到 j 路径上留下的信息素总和。

而根据不同的规则,我们可以将蚁群算法分为三种模型:蚁周模型(Ant-Cycle)、蚁量模型(Ant-Quantity)、蚁密模型(Ant-Density)。

蚁周模型(Ant-Cycle)

蚁周模型的规则是:完成一次路径循环后,蚂蚁才释放信息素。

Δτijk={QLkkij0

Lk 表示蚂蚁 k 所经过的路径之和

蚁量模型(Ant-Quantity)

Δτijk={Qdkkij0

dk表示城市 i 和城市 j 间的距离。

蚁密模型(Ant-Density)

Δτijk={Qkij0

通常使用蚁周模型作为基础

迭代次数的判断

一次迭代是指m只蚂蚁都走完所有能走的城市,即存在m个搜索路径。后将所有的路径进行比较,选择出长度最短的路径,做出一次迭代的可视化结果,更新信息素。后将此路径和之前的最短的路径长度进行对比,同时迭代次数+1。

python代码示例

MatLab算法实现(目前不是最优)

 

步骤总结

  1. 变量的初始化

    • α :表示信息素在指导蚂蚁选择路径的重要程度。
    • β :表示能见度η(启发式因子)在路径选择中的重要程度
    • ρ :表示信息素挥发的效率
    • m :表示蚂蚁的数量(目标数量的1.5倍左右)
    • Q :表示每只蚂蚁所含的信息素(不同的模型拥有不同的计算方法)
    • t :表示最大的迭代次数
  2. 迭代的初始化

    分别(使用矩阵或者变量)记录变量

    1. city_distance:记录每两个城市之间的距离(可以使用对称矩阵)
    2. city_pheromones:城市间的路径内的信息素浓度
    3. ant_way:记录蚂蚁行径城市的顺序
    4. ant_city_choice_P:记录每次询问时,选择每一座城市的概率
    5. 初始化禁忌表
    6. 初始化蚂蚁总距离的记录
  3. 每一次迭代,先要将蚂蚁随机分布在城市中,最后都需要蚂蚁回到起点,所以路径需要加上终点距离起点的的距离

补充

邻接矩阵(Adjacency Matrix)

邻接矩阵是表示顶点之间相邻关系的矩阵。

设G=(V,E)是一个图,其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵:

①对无向图而言,邻接矩阵一定是对称的,而且对角线一定为零,有向图则不一定如此。

②在无向图中,任一顶点 i 的为第 i 列所有元素的和,在有向图中顶点 i 的出度为第 i 行所有元素的和,而入度为第 i 列所有元素的和

③用邻接矩阵法表示图共需要n^2个空间,由于无向图的邻接矩阵一定具有对称关系,所以扣除对角线为零外,仅需要存储上三角形或下三角形的数据即可,因此仅需要n(n-1)/2个空间。

0

评论

博主关闭了所有页面的评论