2.4 通用优化引擎：模拟退火与数值方法

2.4 通用优化引擎：模拟退火与数值方法

本节摘要：当优化问题无法用专用算法精确求解时，工程上依赖两类通用引擎：模拟退火代表随机搜索一族，靠"允许变差"跳出局部最优；梯度类数值方法代表解析下降一族，靠目标函数的光滑性快速收敛。本节给出两者的完整算法骨架、参数调节的实操经验，以及在 EDA 各环节中的适用边界。这一节是工具箱投资——第 3 章布局规划将直接复用。

算不动的问题长什么样

综合与物理实现里的多数问题可以写成同一副面孔：在一个巨大的离散解空间里找一个配置，使代价函数最小，同时满足一堆约束。布局规划里解空间是所有模块的摆放顺序；引脚排列是引脚顺序；逻辑重构的搜索空间是所有等价变换序列。这些问题有三个共同特征让精确算法失效：解空间组合爆炸（n 个元素的排列有 n 的阶乘种）；代价函数存在大量局部极小（贪心爬坡必然卡住）；约束互相纠缠（动一个模块牵动一串合法性）。

对这类问题，工程界形成了两条互补的路线。随机搜索路线不要求目标函数有任何解析性质，把解空间当黑盒，靠随机试探加接受准则找全局最优，代表是模拟退火。解析下降路线把目标函数写成光滑可导的形式（哪怕为此做近似），利用梯度信息一步步下降，代表是梯度法与牛顿法。两条路线的取舍标准非常清晰：能写出光滑目标函数且初始点不太差，用数值方法；解空间离散、目标函数坑坑洼洼，用退火。

模拟退火：允许变差的贪心

模拟退火的物理原型是金属退火：高温下原子可以自由移动（接受任何新状态），缓慢降温后原子逐渐锁进能量最低的晶格。算法对应物：从当前解出发随机产生一个邻域解，若新解更优就接受；若更差，以概率 exp(负 ΔC 除以 T) 接受——ΔC 是代价增量，T 是当前温度。温度高时几乎来者不拒，温度低时退化为纯贪心。接受变差的概率随温度下降而衰减，正是这层概率毛毯让算法有机会爬出局部最优的坑。

// 模拟退火骨架（布局规划的典型用法）
SA(cost, initialSolution, moveSet) {
    s = initialSolution;
    T = 初温;                     // 常取初始接受率约 80% 对应的温度
    while (T > 终温) {
        for (i = 0; i < 每温步数; i++) {
            s2 = s 经 moveSet 随机扰动;        // 交换两个模块 / 平移 / 旋转
            dC = cost(s2) - cost(s);
            if (dC <= 0) s = s2;               // 改善必接受
            else if (random() < exp(-dC / T)) s = s2;  // 变差按概率接受
        }
        T = alpha * T;            // 几何降温，alpha 常取 0.85 到 0.98
    }
    return 历史最优解;            // 别只返回最终状态，要留最优快照
}
​

参数调节的实操经验比公式本身更值钱。初温的标定方法：先随机走一百步统计 ΔC 的均值，令初温使初始接受率落在六到八成；降温系数 alpha 越接近 1 结果越好但时间越长，工程上 0.9 上下是常见折中；每温步数通常取邻域规模或问题规模的数倍。增温重启（卡在同一个解太久就把 T 拉回去）与并行多链（多条独立的退火链共享最优解）是两个廉价而有效的增强。退火的代价也要认账：同一配置跑两次结果不同、收敛无严格保证、调参依赖经验——所以它常出现在离线或近离线环节（布局规划、引脚排列），而不会出现在签核路径上。

数值方法：把离散问题光滑化

数值路线的第一步是把离散目标函数改写成光滑函数。布局是最典型的例子：半周长线长（HPWL，一个网所有引脚的包围盒周长和）本来是分段线性、处处有折点的函数，没法求导；把包围盒周长用指数和（log-sum-exp）近似，就得到一个光滑且凸性良好的替代品。从此每条线对每个单元位置都有连续的梯度，整个布局问题变成一个高维无约束（或带密度约束）的连续优化——百万变量规模，但每一步迭代只是稀疏矩阵运算。

下降法的三档速度对应三档代价。梯度下降沿负梯度走，实现最简，病态问题时收敛极慢。共轭梯度不用二阶信息却能在二次函数上 n 步收敛，内存只多存一组方向向量，是中大规模问题的主力。牛顿法解 Hessian 方程组，二次收敛（误差平方级下降），但 Hessian 的存储与求解在大规模下不可承受，工程上只对子问题或用近似 Hessian（拟牛顿）使用。布局引擎的典型配置：主线长用 log-sum-exp 加共轭梯度，密度约束用罚函数加泊松方程求解（ePlace 路线），二者交替迭代直到密度与线长同时达标。

边界与组合：什么时候用哪件武器

判断题的做法是问三个问题。第一问：目标函数写得光滑吗？时序违例对单元位置的偏导可以写出（延迟是位置的函数），于是时序驱动布局能用数值方法；而"工艺库单元能否映射"这种离散选择写不出梯度，只能退火或动态规划。第二问：初始解好吗？数值方法在烂初始点上会掉进最近的坑，退火不挑初始点——所以常见组合是"退火出粗解、数值法精修"。第三问：答案要不要可复现？签核与交付物要求可复现，随机算法的结果要么不用，要么固定随机种子并把验收标准改成"统计意义上足够好"。

最后预埋一个接口：第 3.4 节的布局规划会把本节的退火装进 sequence pair 这个表示框架里——解空间的"邻域移动"被定义为交换序列对中的两个元素，退火骨架原封不动。到时你会发现，学过的通用引擎加上一个聪明的表示，就是一篇可以写进论文的算法贡献。EDA 算法的很多创新，本质上就是这两件事的排列组合。

本节要点回顾

• 两类通用引擎：随机搜索（退火）吃离散黑盒问题，数值下降（梯度族）吃光滑连续问题。
• 接受准则：exp(负 ΔC 除以 T) 允许变差，温度衰减让算法从全局探索过渡到局部精修。
• 退火调参：初温标定初始接受率六到八成，alpha 取 0.9 上下，保留历史最优快照。
• 光滑化是钥匙：HPWL 用 log-sum-exp 近似后，百万变量布局变成连续优化问题。
• 三档下降法：梯度最简、共轭梯度是中大规模主力、牛顿法快但规模不可承受。
• 选型三问：目标光滑吗、初始解好吗、要可复现吗——常见组合是退火粗解加数值精修。