知识卡片
选城概率融合信息素与距离
蚂蚁 k 在城市 i 时,选城市 j 作为下一站的概率(式 5-1)为:
p(i, j) = τ(i, j)^α · η(i, j)^β ÷ Σ[对所有尚可访问的城市 u] τ(i, u)^α · η(i, u)^β;不可访问的城市概率为 0。
- τ(i, j):边 (i, j) 上的信息素浓度,代表群体的历史经验。
- η(i, j) = 1/dij:启发值,距离越短越大,代表“眼前看近的”这一局部偏好。
- α、β:分别调节信息素和启发值的影响力。
示例(补充演算,数值为假设):从 i 出发可去 A(距离 2、τ = 1)或 B(距离 4、τ = 3)。
| 参数 | A 的权重 | B 的权重 | P(A) | P(B) |
|---|---|---|---|---|
| α = β = 1 | 1×0.5 = 0.5 | 3×0.25 = 0.75 | 0.4 | 0.6 |
| α = 0,β = 1 | 0.5 | 0.25 | 约 0.67 | 约 0.33 |
| α = 1,β = 0 | 1 | 3 | 0.25 | 0.75 |
α = 0 时信息素不起作用,退化为随机贪心,最近的城市概率最大;β = 0 时只跟随信息素,算法会很快收敛,原书指出这样得到的路径往往与实际目标差距较大。两个权重表达的是搜索偏好来自哪里,单调调大其中一个并不能保证解的质量。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 5 . 2 蚁 群 算 法 实 现 · 查看原书依据
1. 路径构建 设蚂蚁当前所在城市为i,则其选择城市j作为下一个访问对象的概率为: kk 其中,k表示第k只蚂蚁,k∈(1,2,…,m),对于每只蚂蚁k,路径记忆向量R按照访问顺序记录了所有蚂蚁k经过的城市序号;Jk(i)表示从城市i可以直接到达的且又不在蚂蚁访问过的城市序列R中的城市集合;τ(i,j)表示信息素浓度值;η(i,j)表示启发式信息,通常由直接计算得到,表示蚂蚁从城市i到城市j的期望程度;dij表示从城市i到城市j之间的距离,可以看出长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大;α和β是两个预先设置的参数,用来控制启发式信息和信息素浓度作用的权重关系,当α=0时,算法演变成传统的随机贪心算法,最邻近城市被选中的概率最大,当β=0时,蚂蚁完全根据信息素浓度确定路径,算法将很快收敛,这样构建出来的最优路径往往与实际目标有较大的差异,算法性能比较糟糕。
参考来源
- 位置:《智能算法导论》第 5 章“5.2 蚁群算法实现”(源文件:EPUB/xhtml/chapter5_0003.xhtml,式(5-1))。
- 结论依据:式(5-1)以 τ 和 η 的 α、β 次幂构造可行城市的归一化概率,正文另定义 η 为距离倒数,并解释两个参数为零时的搜索行为与局限。A、B 两城的概率表为依据式(5-1)补充的教学演算,非书中数据。
- 原始内容:当 α =0时,算法演变成传统的随机贪心算法,最邻近城市被选中的概率最大,当 β =0时,蚂蚁完全根据信息素浓度确定路径,算法将很快收敛,这样构建出来的最优路径往往与实际目标有较大的差异