Python中MILP模型转Simulated Annealing求解的扰动与约束问题咨询

扰动生成优化 #

• 整数变量局部邻域调整：放弃全量随机重置，对单个整数变量做±1的微调（先检查变量上下界，确保调整后在可行范围内），每次仅扰动1-2个整数变量，避免解的突变幅度过大。
• 连续变量小范围采样：基于当前解执行高斯扰动，公式为 新值 = 当前值 + N(0, σ)，其中σ取变量值域的5%-10%；每次仅扰动部分连续变量，而非全部变量同时调整。
• 分层动态扰动：迭代前期适当扩大扰动范围（如σ设为值域的15%），配合高温阶段的探索需求；后期缩小扰动范围，聚焦于当前最优解邻域的 exploitation。

无惩罚函数的约束硬处理 #

• 扰动后即时修复：生成扰动解后立刻校验约束：
  • 等式约束：若为线性约束（如 a₁x₁ + a₂x₂ = b），固定多数变量，反推单个变量的取值（优先调整连续变量，避免破坏整数变量的可行性）。
  • 不等式约束：若变量违反边界，直接将其拉回约束边界（连续变量设为边界值，整数变量取最近的可行整数值）。
• 可行域内采样：扰动时直接限定在可行域内生成新值：整数变量仅在其可行整数集合中选邻域值，连续变量在约束上下界内做高斯采样，从源头减少不可行解。

迭代逻辑优化 #

• 温度调度调整：若迭代中成本无变化，说明初始温度过低或降温过快。可将初始温度设为初始可行解成本的50%-100%，降温速率调整为 T = T * 0.95（慢于常规的0.8）。
• 接受准则补充：在Metropolis准则基础上，每100次迭代强制接受1次更差的解，避免算法过早收敛到局部最优。
• 最优解追踪：每次迭代后，无论是否接受新解，都要记录当前找到的最优可行解，防止因接受差解丢失已找到的最优值。

调试验证步骤 #

• 单独测试扰动函数：固定一个已知可行解，多次运行扰动函数，检查输出解的约束满足情况与多样性——若解几乎无变化，说明扰动范围过小；若大量解不可行，说明扰动逻辑存在漏洞。
• 对标Pulp最优解结构：分析Pulp得到的最优解中整数变量的取值、连续变量的分布特征，在初始化与扰动时优先调整与该最优解差异较大的变量，引导算法向全局最优区域靠近。

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