知识卡片
退火优化新种群增加计算成本
把模拟退火用于遗传算法新生成的种群,可在下一代使用前先做局部优化,结合种群搜索和邻域改进。代价是每个新个体都要再跑一轮退火;图规模变大时顶点数增加,种群往往跟着变大,计算复杂度会累积,影响收敛速度。是否值得混合,须比较单位预算下的解质与耗时,不能只看搜索能力。
补充教学示例(非书中数据)。每代 50 个个体、每个个体退火再评价 20 次,一代就要多 1000 次评价;顶点数从 20 增到 200、种群跟着放大时,这笔附加成本按种群规模倍增。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 1 . 5 . 2 基 于 模 拟 退 火 算 法 的 图 着 色 问 题 · 查看原书依据
为了提高图着色算法的寻优效率,提出将SAA与GA相结合,即利用SAA对GA产生的新的种群进行局部优化,优化后的种群才能作为下一代种群继续使用,这种方法虽然同时提高了算法全局优化和局部优化的能力,但是对于规模较大的图着色问题,随着顶点的个数增加,种群的规模也会相应增大,最终导致算法的计算复杂度大幅度增加,影响收敛速度和寻优效率。
参考来源
- 位置:《智能算法导论》第 119 项《11.5.2 基于模拟退火算法的图着色问题》(源文件:`_epub-src/EPUB/xhtml/chapter11_0014.xhtml`)
- 结论依据:原文将 SAA 用于 GA 新种群的局部优化,并指出较大图随顶点数和种群规模增长会大幅增加计算复杂度。每代 1000 次评价为依据该代价关系补充的教学示例,非书中数据。
- 原始内容:利用SAA对GA产生的新的种群进行局部优化,优化后的种群才能作为下一代种群继续使用;对于规模较大的图着色问题,随着顶点的个数增加,种群的规模也会相应增大,最终导致算法的计算复杂度大幅度增加。