知识卡片

普通读书笔记卡 · 3744.b

信息素挥发率调节群体记忆

理解等级:高级

式(5-2)的信息素更新:τ(i, j) ← (1 − ρ)·τ(i, j) + Σk Δτk(i, j)。

  • ρ:蒸发率,0 < ρ ≤ 1,表示每轮旧信息素挥发掉的比例。
  • Δτk(i, j):若蚂蚁 k 本轮走过边 (i, j),等于 1/Ck,否则为 0。
  • Ck:蚂蚁 k 本轮整条路线的总长度。

示例(补充演算,数值为假设):ρ = 0.5,边上原有 τ = 2,本轮有两只蚂蚁走过它,路线总长分别为 10 和 20。更新后 τ = 0.5×2 + 1⁄10 + 1⁄20 = 1.15。路线越短,留下的量越多;ρ 越大,过去的记忆忘得越快。

需要注意的是,正文先说所有蚂蚁完成路径后才做全局更新,伪代码步骤 3 却写成每只蚂蚁选城后用同一公式“更新局部信息素”。原书没有解释这处冲突,不能据此实现局部更新规则;ρ 的取值也须按具体问题核验。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 5 . 2 蚁 群 算 法 实 现 · 查看原书依据

      其次,在信息素更新的过程中,当所有的蚂蚁构建完路径后,算法会对所有的路径进行全局信息素的更新,此次更新是在全部蚂蚁均完成路径的构造后才进行的,信息素浓度的变化与蚂蚁在这轮中构建的路径长度有关。

    参考来源

    - 位置:《智能算法导论》第 5 章“5.2 蚁群算法实现”(源文件:EPUB/xhtml/chapter5_0003.xhtml,式(5-2))。 - 结论依据:式(5-2)保留 1−ρ 倍旧信息素,并对本轮各蚂蚁在所经边上累加 1/Ck;正文将 Ck 定义为完整路径长度。正文的全局更新说明与伪代码步骤3“局部信息素”互相矛盾。τ = 2、两只蚂蚁的演算为依据式(5-2)补充的教学示例,非书中数据。 - 原始内容:其次,在信息素更新的过程中,当所有的蚂蚁构建完路径后,算法会对所有的路径进行全局信息素的更新,此次更新是在全部蚂蚁均完成路径的构造后才进行的,信息素浓度的变化与蚂蚁在这轮中构建的路径长度有关