如何配置scipy.optimize.dual_annealing的bounds求解旅行商问题？

我正尝试使用scipy的dual_annealing函数求解经典旅行商问题：给定城市坐标列表，寻找遍历所有城市的最短路径。已通过暴力法解决该问题，现希望用dual_annealing实现。

尝试代码如下：

import numpy as np
from scipy import optimize
from scipy import spatial


def total_distance(a):
    prev = None
    total_distance = 0
    for curr in a:
        if prev is None:
            prev = curr
            continue
        else:
            total_distance += spatial.distance.euclidean(prev, curr)
    return total_distance


# List of coordinates with cities to visit. 
inputs = [(485, 475), (1150, 750), (1008, 480), (1562, 134), (1155, 523)]
a = np.array(inputs)
min_distance = optimize.dual_annealing(total_distance, a)

执行最后一行代码时出现错误：

Exception has occurred: ValueError
Bounds are not consistent min < max

dual_annealing函数要求必填参数bounds，文档说明如下：

bounds : sequence or Bounds
Bounds for variables. There are two ways to specify the bounds:
Instance of Bounds class.
Sequence of (min, max) pairs for each element in x.

给定输入的城市坐标数组，该如何配置该参数以满足要求？不理解文档中提到的“(min, max) pairs”含义。

核心问题分析 #

你当前的代码逻辑有误：dual_annealing是连续空间的优化器，而旅行商问题的变量是城市的访问顺序（离散排列），直接传入坐标数组作为bounds完全不符合函数的输入要求。

文档里的“(min, max) pairs”指的是：优化器的输入变量x是一个一维数组，每个元素对应一个待优化的连续变量，(min, max)对就是每个变量的取值范围。比如如果x有3个变量，bounds就是[(x1_min, x1_max), (x2_min, x2_max), (x3_min, x3_max)]。

适配TSP的正确做法 #

要想用dual_annealing解决TSP，需要把离散的排列问题转化为连续优化问题，常用的方法是实数编码映射为排列：

• 定义优化变量为长度等于城市数量的一维连续数组
• 每次计算目标函数时，将连续数组排序后的索引作为城市访问顺序
• 为每个变量设置合理的取值范围（比如(0, 1)或(0, N)，N为城市数量）

修正后的代码 #

import numpy as np
from scipy import optimize
from scipy import spatial


def total_distance(x, coords):
    # 将连续数组x的排序索引作为访问顺序
    order = np.argsort(x)
    # 按顺序取城市坐标，最后回到起点（TSP要求闭合路径）
    path = coords[order]
    path = np.vstack([path, path[0]])
    # 计算总距离
    return spatial.distance.cdist(path[:-1], path[1:], 'euclidean').sum()


# 城市坐标
inputs = [(485, 475), (1150, 750), (1008, 480), (1562, 134), (1155, 523)]
coords = np.array(inputs)
n_cities = len(coords)

# 配置bounds：每个变量的取值范围设为(0, n_cities)，共n_cities个变量
bounds = [(0, n_cities)] * n_cities

# 运行模拟退火优化
result = optimize.dual_annealing(total_distance, bounds, args=(coords,))

# 输出结果
print(f"最短路径距离: {result.fun:.2f}")
optimal_order = np.argsort(result.x)
print(f"最优访问顺序: {optimal_order + 1}")  # 加1是为了从1开始编号城市

关键说明 #

• 目标函数total_distance新增了coords参数，通过args传递给优化器，避免把坐标作为优化变量
• bounds是一个包含n_cities个(0, n_cities)元组的列表，对应每个连续优化变量的取值范围
• 利用np.argsort(x)把连续数组转化为城市的访问顺序，实现离散问题的连续化适配

内容的提问来源于stack exchange，提问作者johan rex