知识卡片
退火速度权衡质量与时间
布线实例中,两个参数共同决定退火的质量与耗时:
- 变化因子 d_t:温度按 t₀ 乘以 d_t 的方式逐轮衰减(0 < d_t < 1),d_t 越小,每轮降得越多。
- 马氏链长度 L:在同一温度下连续产生并判断多少个候选解,该实例取 L = 10n(n 为引脚数)。
示例(补充演算):初温 t₀ = 100,按每轮乘以 d_t 理解,3 轮后 d_t = 0.5 时只剩 12.5,d_t = 0.9 时仍有 72.9。前者很快进入低温,接受较差解的概率随之迅速变小,搜索早早固定下来,可能影响最终解质量;后者探索更久,但耗时更长。同理,L 越大,每个温度下的搜索越充分,计算时间也成倍增加。
因此两者都要按质量与时间的需求取舍:原文建议在取得最优解的前提下尽量减小 L。原书衰减式的上下标在提取文本中缺失,上面“每轮乘以 d_t”是结合 11.2.2 节“T 乘以 0 到 1 之间的常数”所作的理解,结论不宜脱离该实例外推。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 1 . 3 . 2 优 化 目 标 · 查看原书依据
控制参数t的递减率dt的值影响着算法的收敛性,若dt太小,控制参数下降速度会加快,降低了算法接受较差解的概率,从而影响最终解的质量;若dt太大,计算所需的时间代价会增大,影响算法的效率[29]。
参考来源
- 位置:《智能算法导论》第11章《1 1 . 3 . 2 优 化 目 标》(源文件:`_epub-src/EPUB/xhtml/chapter11_0008.xhtml`)
- 结论依据:原文把冷却变化率和马氏链长与接受较差解概率、最终解质量和计算时间联系起来,并建议按质量与时间需求取舍;L = 10n 为原文参数设定。t₀ = 100 的三轮降温演算为依据原书衰减方式补充的教学示例,非书中数据。
- 原始内容:若d t 太小,控制参数下降速度会加快,降低了算法接受较差解的概率,从而影响最终解的质量;若d t 太大,计算所需的时间代价会增大,影响算法的效率 [ 2 9 ] 。同理,增大马氏链长 L 的取值,算法会得到更多的最优解,但计算时间的消耗也会大大增加 [ 3 1 ] ,因此,应当在取得最优解的同时尽可能减小 L 的值。