知识卡片
分治拆解大规模路由问题
大规模限量弧路由问题(LSCARP)指待服务任务很多的车辆弧路由问题,解空间随规模指数增长,整体搜索代价太高。RDG-MAENS 采用分治策略:
- 分解:按路由距离分组(RDG)把任务拆成多个子问题。
- 求解:对每个子问题分别求解。
- 合成:由各子问题的解拼出完整方案。
拆分把一次大搜索变成多次小搜索,于是“怎么分”和“怎么合”成了设计重点。原书提到的后续改进 IRDG-MAENS,针对的正是 RDG-MAENS 把个体分配到子种群的方式不合理,改进后收敛性明显提高。分组方法见 [[按路由距离聚类任务]],子问题解的共享见 [[子问题好解应即时共享]]。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 3 . 4 基 于 M e m e t i c 算 法 的 限 量 弧 路 由 问 题 · 查看原书依据
为了解决LSCARP,2014年提出的RDG-MAENS采用了一种分治策略[30-31],把问题分解成很多子问题,分别予以解决,然后再由子问题的解得到完整的解。
参考来源
- 位置:《智能算法导论》第 3 章“基于 Memetic 算法的限量弧路由问题”(源文件:`_epub-src/EPUB/xhtml/chapter3_0009.xhtml`)。
- 结论依据:原文将 RDG-MAENS 的分治流程概括为拆分子问题、分别求解并由子题解构成完整解。
- 原始内容:为了解决LSCARP,2014年提出的RDG-MAENS采用了一种分治策略 [ 3 0 - 3 1 ] ,把问题分解成很多子问题,分别予以解决,然后再由子问题的解得到完整的解。