能否使用Scipy模拟退火求解器解决旅行商问题？

Scipy的basinhopping默认确实是为连续空间的数值优化设计的，但并非完全不能用于TSP这类组合优化问题——关键是要自定义核心组件，适配排列型解的特性。

为什么默认用不了？ #

• 默认的扰动逻辑是对浮点数数组做高斯随机扰动，而TSP的解是城市索引的排列（每个索引唯一、无重复），这种扰动会直接生成无效解（比如出现非整数、重复城市索引），完全不符合TSP的约束。
• 默认的局部优化器（比如L-BFGS-B）针对连续空间设计，对离散的排列数组无法进行有效优化。

怎么适配？ #

你需要自定义两个核心部分，同时调整优化参数：

• 自定义邻域生成（step函数）：实现TSP专属的邻域解生成逻辑，比如交换两个随机城市、反转一段子路径，确保生成的新解是合法排列。
• 自定义接受准则（accept_test）：过滤掉无效解，同时保留模拟退火的Metropolis接受逻辑（即根据温度和代价变化决定是否接受更差的解）。
• 跳过局部优化：因为局部优化器对排列无效，设置niter_success=0，让basinhopping只执行全局的模拟退火跳变逻辑。

简单实现示例 #

import numpy as np
from scipy.optimize import basinhopping
from scipy.optimize._basinhopping import Metropolis

# 生成10个随机城市坐标
n_cities = 10
cities = np.random.rand(n_cities, 2)

# TSP目标函数：计算路径总长度
def tsp_cost(perm):
    path = cities[perm.astype(int)]
    # 计算相邻城市距离，加上回到起点的闭环距离
    segment_dists = np.linalg.norm(path[1:] - path[:-1], axis=1)
    total_dist = segment_dists.sum() + np.linalg.norm(path[0] - path[-1])
    return total_dist

# 自定义邻域生成：交换两个随机城市的位置
def tsp_swap_step(x):
    x_copy = x.copy()
    # 随机选两个不同的城市索引
    i, j = np.random.choice(len(x_copy), 2, replace=False)
    x_copy[i], x_copy[j] = x_copy[j], x_copy[i]
    return x_copy

# 自定义接受准则：确保解是合法排列，同时遵循Metropolis规则
class TSPAcceptor(Metropolis):
    def __call__(self, **kwargs):
        new_solution = kwargs['new_x']
        # 检查是否是合法排列：元素唯一且覆盖0到n_cities-1
        if not np.array_equal(np.sort(new_solution.astype(int)), np.arange(n_cities)):
            return False
        # 调用原生Metropolis的接受逻辑
        return super().__call__(**kwargs)

# 初始解：随机生成合法排列
initial_perm = np.random.permutation(n_cities)

# 配置basinhopping参数
optimizer_config = {
    'func': tsp_cost,
    'x0': initial_perm,
    'step': tsp_swap_step,
    'accept_test': TSPAcceptor(),
    'niter': 1000,  # 迭代次数
    'niter_success': 0,  # 跳过局部优化
    'stepsize': 1  # 该参数对自定义step无效，但必须指定
}

# 运行优化
result = basinhopping(**optimizer_config)

print("最优路径长度:", round(result.fun, 4))
print("最优路径（城市索引）:", result.x.astype(int))

总结 #

Scipy的标准优化例程不是天生适配组合优化，但通过自定义扰动、接受准则，并关闭不适用的局部优化逻辑，完全可以用来求解TSP这类问题。当然，如果你的场景对性能要求极高，专门的组合优化库会更高效，但用basinhopping快速实现原型是完全可行的。

内容的提问来源于stack exchange，提问作者Rohit Pandey