模拟退火算法疑问：局部最优、全局追踪及算法对比

将本文内容同步自cs.stackexchange，多数模拟退火算法的实现与维基百科伪代码一致：

Let s = s0
For k = 0 through kmax (exclusive):
  T ← temperature( 1 - (k+1)/kmax )
  Pick a random neighbour, snew ← neighbour(s)
  If P(E(s), E(snew), T) ≥ random(0, 1):
    s ← snew
Output: the final state s

疑问与解答 #

1. 若不添加追踪全局最优解的改进，该算法是否仍极易陷入局部最优？ #

是的，这种情况确实极易陷入局部最优。高温阶段虽能接受劣解以跳出当前区域，但如果降温后已经远离了之前找到的更优解，而当前区域的局部最优又无法通过低温阶段极低概率的跳变离开，最终就会停在局部峰值上。毕竟低温阶段接受劣解的概率几乎可以忽略，此时算法和普通爬山法没区别，一旦进入局部最优就很难脱身。

2. 添加全局最优追踪后，相比重复随机爬山法这类简单随机搜索，其优势何在？ #

首先，模拟退火绝非全靠“碰巧”找全局最优。重复随机爬山法是多次独立的局部搜索，每次都从头随机初始化，各次搜索之间毫无关联；而模拟退火是带记忆的渐进式搜索：从初始点出发，通过温度调度逐步从“探索”转向“利用”，整个过程是在解空间里有方向地移动，而非完全随机瞎逛。

就算没在高温阶段碰运气找到全局最优，它也能通过前期的探索遍历更多解空间区域，后期收敛到更优的局部（甚至全局）解；而重复随机爬山法如果初始点选得差，多次重复也可能一直困在差的局部最优里。此外，模拟退火的温度调度是有策略的平衡机制，相比完全依赖随机初始化运气的重复爬山法，在解空间大、局部最优多的问题上，找到优质解的效率要高得多。

3. 模拟退火算法在哪些场景下比重复随机爬山法更适用？这类问题需具备哪些特性？ #

模拟退火更适合解空间庞大、局部最优解数量多、且解之间存在清晰邻域连通性的问题，这类问题通常具备以下特性：

• 解空间规模极大（连续或离散），穷举完全不可能；
• 目标函数存在大量局部最优，简单爬山法极易卡壳；
• 解的邻域结构清晰，能方便生成邻居解（比如旅行商问题中交换两个城市路径、函数优化中微调变量值）；
• 需要通过暂时接受劣解来跳出局部最优，且这种跳出的代价可通过温度调度合理控制。

典型适用场景包括旅行商问题（TSP）、多峰函数全局优化、电路布局优化、组合优化问题等。这些问题里，重复随机爬山法要么效率极低，要么根本找不到满意解，而模拟退火通过温度引导的探索-利用平衡，能更高效地逼近全局最优。

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