知识卡片

普通读书笔记卡 · 3739.d

局部搜索算子应匹配问题邻域

理解等级:中级

局部搜索由三个概念组成,都要按具体问题的解表示和约束来定义:

  • 移动:从当前解产生新解的一次变化。
  • 邻域:当前解一步(或很小距离内)能到达的解,即候选移动的集合。
  • 候选集:本轮实际要评价的邻居,可以取全部邻居,也可以只挑最优的一部分或随机抽取。

不同局部搜索对“变差的移动”态度不同:爬山算法只接受让解变好的移动,到了局部最优就停下;禁忌搜索也接受不改进的移动,借此跳出局部最优。初始解质量同样影响表现,约束复杂时应先用启发式方法构造一个可行的初始解。所以模因算法的局部搜索算子要按问题的邻域结构和计算预算来选,不存在通用最优的一种。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 4 . 2 禁 忌 搜 索 算 法 实 现 · 查看原书依据

      部分局部搜索算法仅仅保留改进的移动,而禁忌搜索接受非改进移动,可能不会带来更好的解,但是可以使得算法跳出局部最优。 (3)候选集合一般由邻域中的邻居组成,可以将某解的所有邻居作为候选集合,也可以通过最优提取,也可以随机提取。

    参考来源

    - 位置:《智能算法导论》第 3 章 3.2.2 节“Memetic 算法改进”(`EPUB/xhtml/chapter3_0004.xhtml`);局部搜索算子段。 - 结论依据:原书把局部搜索列为区别于遗传算法的关键,并要求针对不同问题选择爬山、模拟退火或禁忌等机制。 - 原始内容:针对不同问题,应选择不同的局部搜索方法 - 位置:《智能算法导论》第 133 项《1 4 . 1 . 2 禁 忌 搜 索 算 法 基 本 思 想》(源文件:`_epub-src/EPUB/xhtml/chapter14_0002.xhtml`) - 结论依据:作者指出禁忌搜索立足邻域搜索、初始解优劣影响性能,并建议复杂约束问题用启发式方法确保初始解可行。 - 原始内容:禁忌搜索算法立足于邻域搜索,所以初始解的优劣对该算法性能影响比较大。对于较为复杂的约束问题……应该采用一些启发式方法确保禁忌搜索的初始解是可行解。 - 位置:《智能算法导论》第 134 项《1 4 . 2 禁 忌 搜 索 算 法 实 现》(源文件:`_epub-src/EPUB/xhtml/chapter14_0003.xhtml`) - 结论依据:本节将移动定义为从当前解产生新解的变化,将邻域视为候选移动集合,并指出禁忌搜索可以接受非改进移动以跳出局部最优;候选集合可全量枚举或经筛选、随机抽取。 - 原始内容:部分局部搜索算法仅仅保留改进的移动,而禁忌搜索接受非改进移动,可能不会带来更好的解,但是可以使得算法跳出局部最优。候选集合一般由邻域中的邻居组成……也可以通过最优提取,也可以随机提取。