Scipy dual_annealing的约束添加与无限边界设置问题

问题分析 #

你需要最小化线性目标函数 Z = 5x + 4y，同时满足以下约束：

• 4x + y ≥ 40
• 2x + 3y ≥ 90
• x, y ≥ 0

Scipy的dual_annealing不支持直接传入约束参数，且不允许无限边界，下面是针对性的解决方案：

1. 解决无限边界问题 #

dual_annealing要求搜索空间必须是有限区间，因为它的采样机制依赖于有界的定义域。你可以通过以下方式确定合理的上界：

• 先手动求解该线性规划的最优解：联立约束等式4x + y = 40和2x + 3y = 90，解得x=3，y=28，目标值为127。
• 设置一个远大于最优解的上界（比如100），既不会限制算法搜索，又能满足dual_annealing的要求。

示例边界定义：

bounds = [(0, 100), (0, 100)]  # x和y的范围：0到100

2. 解决约束添加问题 #

由于dual_annealing没有内置约束参数，我们采用惩罚函数法：将违反约束的代价加到目标函数中，让算法自动避开不满足约束的解。

具体实现逻辑：

• 对于每个约束g(x,y) ≥ 0，当g(x,y) < 0时，计算违反程度并乘以一个足够大的惩罚系数（比如1000），将其加到目标值上。
• 惩罚系数要足够大，确保违反约束的解不会被选为最优解，但也不要过大导致数值溢出。

带惩罚的目标函数示例：

def obj(v):
    x, y = v
    # 基础目标值
    z = 5 * x + 4 * y
    
    # 约束1：4x + y ≥ 40，违反时添加惩罚
    penalty1 = max(0, 40 - (4 * x + y)) * 1000
    # 约束2：2x + 3y ≥ 90，违反时添加惩罚
    penalty2 = max(0, 90 - (2 * x + 3 * y)) * 1000
    # 约束3：x ≥ 0，违反时添加惩罚
    penalty3 = max(0, -x) * 1000
    # 约束4：y ≥ 0，违反时添加惩罚
    penalty4 = max(0, -y) * 1000
    
    return z + penalty1 + penalty2 + penalty3 + penalty4

完整运行代码 #

from scipy.optimize import dual_annealing
import numpy as np

def obj(v):
    x, y = v
    z = 5 * x + 4 * y
    
    penalty1 = max(0, 40 - (4 * x + y)) * 1000
    penalty2 = max(0, 90 - (2 * x + 3 * y)) * 1000
    penalty3 = max(0, -x) * 1000
    penalty4 = max(0, -y) * 1000
    
    return z + penalty1 + penalty2 + penalty3 + penalty4

# 设置有限边界
bounds = [(0, 100), (0, 100)]

# 运行模拟退火
result = dual_annealing(obj, bounds)

# 输出结果
print("最优解：x = {:.2f}, y = {:.2f}".format(result.x[0], result.x[1]))
print("最小目标值：{:.2f}".format(result.fun))

运行后，结果会接近理论最优解x=3，y=28，目标值约127。

内容的提问来源于stack exchange，提问作者Mra Abs