知识卡片
局部搜索算子应匹配问题邻域
局部搜索由三个概念组成,都要按具体问题的解表示和约束来定义:
- 移动:从当前解产生新解的一次变化。
- 邻域:当前解一步(或很小距离内)能到达的解,即候选移动的集合。
- 候选集:本轮实际要评价的邻居,可以取全部邻居,也可以只挑最优的一部分或随机抽取。
不同局部搜索对“变差的移动”态度不同:爬山算法只接受让解变好的移动,到了局部最优就停下;禁忌搜索也接受不改进的移动,借此跳出局部最优。初始解质量同样影响表现,约束复杂时应先用启发式方法构造一个可行的初始解。所以模因算法的局部搜索算子要按问题的邻域结构和计算预算来选,不存在通用最优的一种。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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`)
- 结论依据:本节将移动定义为从当前解产生新解的变化,将邻域视为候选移动集合,并指出禁忌搜索可以接受非改进移动以跳出局部最优;候选集合可全量枚举或经筛选、随机抽取。
- 原始内容:部分局部搜索算法仅仅保留改进的移动,而禁忌搜索接受非改进移动,可能不会带来更好的解,但是可以使得算法跳出局部最优。候选集合一般由邻域中的邻居组成……也可以通过最优提取,也可以随机提取。