前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >几种蚁群算法介绍

几种蚁群算法介绍

作者头像
mwangblog
发布2018-12-06 15:51:17
1.9K0
发布2018-12-06 15:51:17
举报
文章被收录于专栏:mwangblog

蚂蚁系统

最早的蚁群算法,其在小规模TSP中性能尚可,再大规模TSP问题中性能下降,容易停滞。其解决旅行商问题(TSP)过程大致如下:

在初始时刻,m只蚂蚁被随机的放到城市中,在各条路径上的信息素初始值相等。

蚂蚁按照随机比例规则从允许的城市中选择下一个城市:

p_j = \frac{(\tau_j)^\alpha (\eta_j)^\beta}{\sum (\tau_j)^\alpha (\eta_j)^\beta}pj=∑(τj)α(ηj)β(τj)α(ηj)β

τ为信息素,η 为启发式因子,a_k 为下一步被允许城市的集合。

使用禁忌表记录蚂蚁走过的城市,不允许蚂蚁选择已经访问过的城市。

所有蚂蚁完成一次周游后,计算每只蚂蚁的路径长度,保存最短路径长度。

更新每个城市信息素:

τ=(1−ρ)τ+∑Δτ, 0≤ρ≤1

Δτ=1/d

由上可知,先挥发信息素,再增加信息素。其中d为路径距离,路径越短,信息素增加越多。∑Δτ表示所有本次觅食过程中所有经过此城市的觅食成功的路线的信息素累加。

清空禁忌表,开始下一次周游。

精英蚂蚁系统

对算法每次循环之后给予最优路径额外的信息素。

对于普通路径中的每个城市:

τ(t+1)=(1−ρ)τ(t)+∑Δτ

对于最优路径中的每个城市:

τ(t+1)=(1−ρ)τ(t)+∑Δτ+eΔτ^(bs)

Δτ^(bs)=1/L

其中L代表最优路径长度,e是一个参数,表示权值大小。

最大-最小蚂蚁系统

目前解决TSP问题最好的蚁群算法之一,在蚂蚁系统的基础上进行了如下更改:

  1. 信息素被限制在[τmin , τmax]。
  2. 信息素的初始值被设定为取其上界。
  3. 只有最优路径上的信息素会被增加,其他城市的信息素只挥发。

对于一般城市: τ(t+1)=(1−ρ)τ(t)

对于最优路径上的城市:τ(t+1)=(1−ρ)τ(t)+∑Δτ

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-11-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 mwangblog 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 蚂蚁系统
  • 精英蚂蚁系统
  • 最大-最小蚂蚁系统
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档