模拟退火多次运行最优解为初始解的原因排查咨询

1. 初始可行解质量过高是否是原因？ #

有可能，但需先明确初始解的性质：

• 如果初始解已是全局最优解，SA自然无法找到更优解，属于正常结果。
• 如果初始解只是局部最优，问题大概率不在初始解质量本身，而是SA的搜索机制没能跳出局部最优，或是邻域设计未覆盖到更优解的区域。

2. 冷却因子和初始温度的作用及无效原因 #

初始温度与冷却因子的核心是调控SA的探索-利用平衡：

• 初始温度：决定算法初期接受劣质解的概率，温度越高越易接受差解，利于探索新区域；温度过低则直接陷入局部最优。
• 冷却因子：控制降温速度，因子越接近1（如0.99），降温越慢，搜索越充分；因子过小（如0.5）则降温过快，无足够时间探索。

若小规模实例调整参数后仍无改善，大概率不是参数本身的问题，而是邻域生成、接受准则等其他环节存在bug，导致参数调整的作用无法体现。

3. 是否未生成有效邻解？ #

这是极可能的原因，建议先做验证：

• 手动或随机生成若干由SWAP和2-OPT生成的邻解，计算其目标值，查看是否存在比初始解更优的解。
  • 若不存在：说明当前SWAP+2-OPT的邻域设计无法生成更优解，需调整邻域策略（比如加入3-OPT、Or-Opt等其他操作）。
  • 若存在：说明SA的接受机制未正确捕捉到这些更优解，需检查接受准则的实现逻辑。

其他遗漏因素 #

• 接受准则实现错误：比如最小化问题中，Metropolis准则的符号搞反（误将ΔE>0的解直接拒绝，或错误计算exp(ΔE/T)而非exp(-ΔE/T)）。
• 迭代次数定义模糊：如果“每次迭代超500次”指总迭代次数而非每个温度下的内循环次数，会导致每个温度下的搜索不充分，无法挖掘有效邻解。
• 目标值计算bug：初始解或邻解的目标值计算出错，导致误以为无更优解存在。
• 邻解生成随机性不足：比如SWAP固定交换相邻位置、2-OPT固定选择特定区间的边，导致邻域探索范围受限。
• 终止条件不合理：温度未降到足够低就提前终止，或是迭代次数不足以覆盖关键搜索区域。

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