知识卡片
遗传退火禁忌分工搜索
GA-ASATS 用三种算子求解图着色,各管一件事:
- 遗传算法(GA):用选择、交叉、变异推进整个种群的搜索。
- 自适应模拟退火算子(ASA):在局部寻优中既可“下山”(移向目标值更好的解),也可“上山”(按概率接受目标值变差的解),借此离开局部最优。
- 禁忌搜索算子(TS):用禁忌表记住最近若干次做过的移动,在一定步数内暂时禁用它们,防止搜索来回兜圈。禁用并非绝对:若某个被禁的移动能带来优良状态(如优于迄今最好解),蔑视准则可予赦免。
三者分别处理种群演化、局部改进和搜索记忆;禁忌规则只是减少循环的启发式,不是全局最优的证明。原书的性能结论限于其稠密图、稀疏图实验。
结构图:
flowchart TD
A[图着色候选种群] --> B[遗传选择、交叉与变异]
B --> C[自适应退火局部搜索]
C --> D[按目标函数上下移动]
D --> E[禁忌记忆减少循环]
E --> F[形成改进候选]
F --> G[进入种群选择]
G --> B
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 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”状态的禁忌候选解,此时特设准则将某些状态解禁。