知识卡片

结构图卡 · 3766.a

遗传退火禁忌分工搜索

理解等级:中级

GA-ASATS 用三种算子求解图着色,各管一件事:

  • 遗传算法(GA):用选择、交叉、变异推进整个种群的搜索。
  • 自适应模拟退火算子(ASA):在局部寻优中既可“下山”(移向目标值更好的解),也可“上山”(按概率接受目标值变差的解),借此离开局部最优。
  • 禁忌搜索算子(TS):用禁忌表记住最近若干次做过的移动,在一定步数内暂时禁用它们,防止搜索来回兜圈。禁用并非绝对:若某个被禁的移动能带来优良状态(如优于迄今最好解),蔑视准则可予赦免。

三者分别处理种群演化、局部改进和搜索记忆;禁忌规则只是减少循环的启发式,不是全局最优的证明。原书的性能结论限于其稠密图、稀疏图实验。

结构图:

flowchart TD
  A[图着色候选种群] --> B[遗传选择、交叉与变异]
  B --> C[自适应退火局部搜索]
  C --> D[按目标函数上下移动]
  D --> E[禁忌记忆减少循环]
  E --> F[形成改进候选]
  F --> G[进入种群选择]
  G --> B
这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 4 . 1 禁 忌 搜 索 算 法 起 源 · 查看原书依据

      它的核心是“已经被找过的解在一定的步骤内不会再次被寻找”,是一种在组合优化问题中寻找近似最优解的启发式方法。禁忌搜索模拟人类进行“思考、记忆”,通过自身对已知解的记忆,把这些解加入到自己的记忆库中(即禁忌表中),从而可以接收到更多的解,避免陷入局部性的搜索中。

    参考来源

    - 位置:《智能算法导论》第 119 项《11.5.2 基于模拟退火算法的图着色问题》(源文件:`_epub-src/EPUB/xhtml/chapter11_0014.xhtml`) - 结论依据:原文分别把 GA 算子用于种群进化、ASA 用于局部上下山搜索、TS 记忆用于避免循环;这支持职责划分,但文中实验效果只适用于其报告的图实例。 - 原始内容:自适应模拟退火算子(ASA)用于在局部寻优过程中进行上山或下山搜索;禁忌搜索算子(TS)通过记忆能力防止进化过程出现反复循环。 - 位置:《智能算法导论》第 14 章《1 4 . 1 禁 忌 搜 索 算 法 起 源》(源文件:`_epub-src/EPUB/xhtml/chapter14_0001.xhtml`) - 结论依据:本节说明禁忌表记录已进行的搜索,并使近期被搜索过的解在一定步数内不再访问;该描述具体化了此卡中禁忌记忆的作用。 - 原始内容:核心是“已经被找过的解在一定的步骤内不会再次被寻找”,是一种在组合优化问题中寻找近似最优解的启发式方法。 - 位置:《智能算法导论》第 133 项《1 4 . 1 . 2 禁 忌 搜 索 算 法 基 本 思 想》(源文件:`_epub-src/EPUB/xhtml/chapter14_0002.xhtml`) - 结论依据:禁忌表记录最近若干次迭代的移动,最新迭代中的移动被暂时禁用;蔑视准则可赦免被禁的优良状态,因此禁忌限制是可例外的搜索记忆规则。 - 原始内容:禁忌表中存储最近若干次迭代过程中所实现的移动。正处于禁忌表中的移动,在最新的迭代过程中是被禁用的;禁忌搜索算法采用“蔑视准则”来赦免一些被禁忌的优良状态。 - 位置:《智能算法导论》第 134 项《1 4 . 2 禁 忌 搜 索 算 法 实 现》(源文件:`_epub-src/EPUB/xhtml/chapter14_0003.xhtml`) - 结论依据:期望条件可释放对算法有利的禁忌移动;原文举出候选全部被禁或禁忌候选优于历史最好状态等触发情形,具体阈值需由实现定义。 - 原始内容:候选解全部被禁忌,或者存在一个优于“best so far”状态的禁忌候选解,此时特设准则将某些状态解禁。