知识卡片
子问题好解应即时共享
大规模弧路由(LSCARP)先按 RDG 拆成多个子问题。原文对比两种用法:RDG 只把搜到的最好解留下来,不根据当前群体信息给各子问题重新分配解,也不让该解参与其他子问题;IRDG-MAENS 则在某个子问题刚得到较好可行解时立刻替换当前解,并通过邻域共享交给邻近子问题继续搜。
示例(补充教学示例,非书中数据):子问题 A、B 各自管一组街道。A 刚找到一条更短的可行路线,立刻写入当前解,并把这条路线提供给任务相邻的 B。B 下一轮不必从过时方案起步。收益仍取决于怎么分解、邻域有多宽;表 3.5 给出及时更替的循环示意图,原书未在正文列出其逐格数字。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 3 . 4 . 2 子 问 题 解 的 更 替 · 查看原书依据
在获得子问题最优解后立即用较好的解进行更替并通过邻域共享参与当前子代问题的求解。这不仅能够加快算法的收敛速度,还及时更替每个子问题较好的解,参与该循环和其他子问题的求解,这种方法更利于邻域共享和获得潜在的更好的解。
参考来源
- 位置:《智能算法导论》第 3 章 3.4.2 节“子问题解的更替”(`EPUB/xhtml/chapter3_0011.xhtml`);表 3.5。
- 结论依据:原文先指出 RDG 只保留最好解、不动态再分配,再说明 IRDG-MAENS 在获得子问题最优解后立即更替并通过邻域共享参与当前子代求解;表 3.5 为该过程示意图。两子问题示例为依据该对比补充的教学示例,非书中数据。
- 原始内容:在获得子问题最优解后立即用较好的解进行更替并通过邻域共享参与当前子代问题的求解。