9.4 高性能计算案例：模拟退火加速

9.4 高性能计算案例：模拟退火加速

同一个模拟退火程序，从朴素版一路优化到多线程版，实测每一步的收益。这是第 5 章方法论的完整演习：测量驱动、逐步改造、每步验证。

问题：用退火解旅行商小实例

using Random

# 20 个随机城市的坐标
Random.seed!(42)
n = 20
cities = rand(2, n)

tour_cost(order) = begin
    c = 0.0
    for i in 1:n-1
        c += norm(cities[:, order[i]] .- cities[:, order[i+1]])
    end
    c += norm(cities[:, order[n]] .- cities[:, order[1]])   # 回到起点
    c
end
​

版本一：朴素退火

function anneal(cities; T0 = 10.0, steps = 200_000)
    n = size(cities, 2)
    order = collect(1:n)
    best = copy(order)
    bestc = tour_cost(order)
    T = T0
    for step in 1:steps
        i, j = rand(1:n, 2)
        order[i], order[j] = order[j], order[i]      # 随机交换
        newc = tour_cost(order)
        if newc < bestc || rand() < exp(-(newc - bestc) / T)
            if newc < bestc
                bestc, best = newc, copy(order)
            end
        else
            order[i], order[j] = order[j], order[i]  # 撤销
        end
        T *= 0.999
    end
    bestc, best
end
​

版本二：先测量，再动手

using BenchmarkTools
@btime anneal(cities)        # 记录基线：假设约 1.2 秒
​

Profile 热点会指向 tour_cost 的 norm 调用与临时数组 .−。逐项改造：

function tour_cost2(order)                    # 展开计算，消灭临时数组与 norm 泛型开销
    c = 0.0
    @inbounds for i in 1:n-1
        dx = cities[1, order[i]] - cities[1, order[i+1]]
        dy = cities[2, order[i]] - cities[2, order[i+1]]
        c += sqrt(dx * dx + dy * dy)
    end
    dx = cities[1, order[n]] - cities[1, order[1]]
    dy = cities[2, order[n]] - cities[2, order[1]]
    c + sqrt(dx * dx + dy * dy)
end
​

单点改造通常就有数倍收益，且逻辑不变、可直接验证结果一致：

@test anneal(cities)[2] |> tour_cost ≈ anneal(cities)[2] |> tour_cost2  # 语义一致性抽查
​

版本三：多次独立退火并行化

退火是随机算法，跑 K 次取最好本身就是标准用法——完美并行任务，套 5.2 的 @spawn 模式：

using Base.Threads: @spawn

function parallel_anneal(K)
    tasks = [ @spawn anneal(cities) for _ in 1:K ]
    results = fetch.(tasks)
    reduce(results) do r1, r2
        r1[1] < r2[1] ? r1 : r2
    end
end

@btime parallel_anneal(16)    # 8 线程下约为串行 16 次的 1/8 时间
​

三版演进的收益构成

⚠️ 常见坑：并行收益低于预期时，先查两点——退火内部用了全局变量 cities（非 const 全局会拖慢所有线程），以及任务粒度太细导致调度开销吃掉收益。

💡 关键直觉：随机算法的并行姿势是"多跑几个随机种子"，不是"把一次运行拆碎"。后者引入同步开销，前者几乎免费。

结果验证与调参解读

性能改造完成后要回答两个问题：结果还对吗、参数该设多少。结果验证上，退火的输出是访问顺序，比较三版改造的最终成本：多随机种子下各版本的成本分布应统计一致（均值差异在随机波动内），若并行版系统性偏差，多半是随机数种子被多任务共享导致序列异常。调参解读上，两个参数直接影响解质量：初始温度 T0 决定前期"敢不敢乱跳"——太高则长时间瞎逛、太低则立刻陷入局部最优；降温速率（本例每步乘 0.999）决定搜索总"能量预算"。经验做法是固定步数，扫 T0 ∈ {1, 10, 100} 与降温系数 ∈ {0.999, 0.9995}，看最优成本与达到稳定所需的步数，选"成本足够低且步数不爆炸"的组合。这套扫参正好复用 5.2 的并行模式，几分钟就能得到一张参数对照表——高性能计算的最后一步永远是把机器时间花在"回答问题的实验"上，而不是省在实验设计上。

本节要点回顾

• 测量先行：@btime 定基线，profile 找热点，别凭感觉优化；
• 单核优化收益常大于并行，先做版本二再做版本三；
• 随机算法并行 = 多独立实例取最优，@spawn + fetch 三行搞定；
• 每步改造后验证语义一致，性能优化不能改变答案；
• 参数扫描本身也值得并行，机器时间应花在回答问题的实验上。

回顾这个案例的演进顺序还有一层方法论价值：三个版本分别对应"能跑"、"跑得快"、"跑得广"（多实例提升解质量），每一步都有测量数字背书。把这条演进线记在心里，将来面对自己的慢程序时照抄顺序即可——它就是第 5 章全部内容的一次完整彩排。

另外注意本案例的并行化没有改动算法本身一行：单核优化版与并行版用的是同一个 anneal 函数，并行发生在"运行多少次"的层面。这种"外层并行、内核不动"的模式是随机算法的标准加速路径，好处是单核版的全部优化成果自动被并行版继承，两条优化线互不干扰、可以独立推进。