← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3766.b

退火优化新种群增加计算成本

理解等级:高级

把模拟退火用于遗传算法新生成的种群,可在下一代使用前先做局部优化,结合种群搜索和邻域改进。代价是每个新个体都要再跑一轮退火;图规模变大时顶点数增加,种群往往跟着变大,计算复杂度会累积,影响收敛速度。是否值得混合,须比较单位预算下的解质与耗时,不能只看搜索能力。

补充教学示例(非书中数据)。每代 50 个个体、每个个体退火再评价 20 次,一代就要多 1000 次评价;顶点数从 20 增到 200、种群跟着放大时,这笔附加成本按种群规模倍增。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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产生的新的种群进行局部优化,优化后的种群才能作为下一代种群继续使用;对于规模较大的图着色问题,随着顶点的个数增加,种群的规模也会相应增大,最终导致算法的计算复杂度大幅度增加。