关于Scipy Dual Annealing算法的工作原理、参数及伪代码咨询

一、工作机制差异 #

Dual Annealing是对标准模拟退火（SA）的针对性改进，核心区别体现在三点：

• 多区域并行搜索：标准SA是单轨迹搜索，从单个初始点出发逐步迭代；而Dual Annealing会将整个搜索空间划分为多个独立子区域，同时在每个子区域内运行SA链，通过子区域间的信息交换避免过早收敛到局部最优。
• 内置局部优化环节：每次全局退火迭代后，算法会调用局部优化器（默认是L-BFGS-B）对每个子区域的当前最优解进行精细优化——这是标准/广义SA没有的步骤，既保留SA的全局搜索能力，又能加速收敛到高精度解。
• 自适应温度调度：标准SA采用全局单调降温策略，Dual Annealing则为每个子区域分配独立的温度，温度下降速度会根据子区域的搜索进度自适应调整，搜索初期更宽容地接受劣解，后期聚焦局部搜索。

二、maxiter参数的本质 #

maxiter指的是全局退火迭代的总次数，而非函数评估次数。每次全局迭代包含多个会产生函数评估的步骤：

1. 每个子区域内生成若干候选解，每个候选解都需要一次函数评估；
2. 局部优化阶段，局部优化器（如L-BFGS-B）为了找到更优解，会进行大量的函数/梯度评估；
3. 子区域间交换信息后，新生成的交叉解也需要评估。

举个直观的例子：如果maxiter=20，每个迭代在4个子区域各生成3个候选解，每个子区域的局部优化需要15次函数评估，那么总函数评估数会是20*(43 + 415) = 20*(12+60)=1440，远大于20的迭代次数。

三、核心伪代码（贴合Scipy实现逻辑） #

# 简化版伪代码，对应scipy.optimize.dual_annealing核心流程
def dual_annealing(f, bounds, maxiter=100, local_optimizer="L-BFGS-B"):
    # 初始化：划分搜索子区域，设置各子区域的初始参数
    num_subregions = 5  # 示例值，实际由算法自适应调整
    subregions = []
    for _ in range(num_subregions):
        x_init = random_sample_from_bounds(bounds)
        subregions.append({
            "x": x_init,
            "f_val": f(x_init),
            "temp": initial_temperature()
        })
    global_best_x = min(subregions, key=lambda s: s["f_val"])["x"]
    global_best_f = f(global_best_x)

    for iter_idx in range(maxiter):
        # 1. 子区域内的退火搜索
        for s in subregions:
            # 基于当前温度和位置生成候选解
            x_candidate = perturb_solution(s["x"], s["temp"], bounds)
            f_candidate = f(x_candidate)
            # Metropolis接受准则
            if accept_probability(s["f_val"], f_candidate, s["temp"]) > random.random():
                s["x"] = x_candidate
                s["f_val"] = f_candidate
            # 更新子区域温度
            s["temp"] = cool_temperature(s["temp"], iter_idx, maxiter)
        
        # 2. 局部优化每个子区域的当前解
        for s in subregions:
            # 调用局部优化器
            local_x, local_f = local_optimize(f, s["x"], bounds, method=local_optimizer)
            if local_f < s["f_val"]:
                s["x"] = local_x
                s["f_val"] = local_f
            # 更新全局最优
            if local_f < global_best_f:
                global_best_x = local_x
                global_best_f = local_f
        
        # 3. 子区域间交换解（避免独立搜索陷入局部最优）
        exchange_solutions_between_subregions(subregions)

    return global_best_x, global_best_f

内容的提问来源于stack exchange，提问作者9hihowareyou9