知识卡片
终止条件不等于全局最优证明
GA 常见三类停止条件:
- 达到最大进化代数:搜索预算用尽。
- 连续若干代最优个体未变化或适应度基本未改进:判定停滞。
- 近似最优值达到预设阈值:达到目标门槛。
前两类控制预算或停滞,第三类表达门槛;都不构成全局最优证明。记录结果时应写明触发了哪一项,并区分“达到阈值”和“已证明最优”。DE 同样可用最大代数或适应度阈值停止;增大代数可能提高精度,也增加运行时间。禁忌搜索还可按未改善次数、禁忌频率或评价值偏离阈值停止,同样只控制何时退出。
补充教学示例(非书中数据)。最大代数设为 200,第 200 代停下只说明预算用尽;若阈值是适应度 ≥ 0.99 而停,只说明达到门槛。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 0 . 1 差 分 进 化 算 法 与 遗 传 算 法 · 查看原书依据
通常设定的算法终止条件为:①迭代次数达到最大进化代数;②连续若干代最优个体没有发生变化或个体适应度值基本没有改进;③求解得到的近似最优解小于预先设定的阈值。
参考来源
- 位置:《智能算法导论》第 1 章 1.2.1 节“算法终止条件”(`EPUB/xhtml/chapter1_0004.xhtml`)。
- 结论依据:原文给出迭代次数上限与解变化阈值两种终止条件,未给最优性证明。第 200 代与适应度门槛为例为依据定义补充的教学示例,非书中数据。
- 原始内容:遗传算法终止条件通常有两种:一是设定迭代次数,当算法迭代次数达到设定值时,算法停止;二是当解的变化小于某一设定的较小值时,认为结果收敛,算法停止。
- 位置:《智能算法导论》第 10 章《10.1 差分进化算法与遗传算法》中的 GA 流程(源文件:`_epub-src/EPUB/xhtml/chapter10_0002.xhtml`)
- 结论依据:本节另列连续若干代没有改进及近似解低于预设阈值两种停止情形,支持把停滞与目标达标分开;仍没有给出最优性证明。
- 原始内容:通常设定的算法终止条件为:①迭代次数达到最大进化代数;②连续若干代最优个体没有发生变化或个体适应度值基本没有改进;③求解得到的近似最优解小于预先设定的阈值。
- 位置:《智能算法导论》第 10 章《10.2 差分进化算法实现》(源文件:`_epub-src/EPUB/xhtml/chapter10_0005.xhtml`)
- 结论依据:原文列出最大进化代数与适应度阈值两种停止依据,并指出增大代数可能提高精度但延长运行时间;这支持把停止条件视为计算预算与精度之间的权衡,而非最优性证明。
- 原始内容:根据需要,可以通过增大最大进化代数来提高算法的求解精度,但同时也会延长算法运行时间,增大计算复杂度。
- 位置:《智能算法导论》第 134 项《1 4 . 2 禁 忌 搜 索 算 法 实 现》(源文件:`_epub-src/EPUB/xhtml/chapter14_0003.xhtml`)
- 结论依据:禁忌搜索除最大迭代数外,还可按未改善次数、对象禁忌频率或评价值偏离阈值停止;这些条件控制停止时机,不提供全局最优证明。
- 原始内容:若算法得到的结果连续在最大迭代次数中都没有得到改善,则退出循环。……还有一种终止规则是设定适配值的偏离阈值。