模拟退火（1）

模拟退火（Simulated annealing）

什么是退火——物理上的由来

退火 (annealing) 现象指物体逐渐降温的物理现象，温度愈低，物体的能量状态会低；够低后，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。但是，如果过程过急过快，快速降温（亦称「淬炼」，quenching）时，会导致不是最低能态的非晶形。

算法概述

• 若目标函数 在第 步移动后比第 步更优，即，则总是接受该移动；
• 若（即移动后的解比当前解要差），则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）。
• 上述概率 采用 Metroplis 准则设定。温度越高，算法接受新解的概率越高，而随着程序运行（时间），温度逐渐降低，开始退火，接受新解的概率降低。 其中， k 是常数，t 是温度，

可以知道，

具体算法

1. 随机生成问题的一个解 , 并初始化温度 和每轮执行次数 ;
2. 设置温度的冷却步长（或系数），通常有 3 种方法来冷却温度：
3. 从 的邻近解 中找到一个解 ,计算新解的目标值 和原来解的目标值 之差
4. 若新解优于原解（设问题为最小化问题）即 ,则接收新解 ，否则（），以 Metroplis 准则来确定是否接收新解;
5. 执行步骤 3 和 4 共 次;
6. 判断是否达到终止条件，如果没有，则按照问题的冷却设置降低温度 ，回到步骤 3，否则算法结束。

具体实例

• 旅行商问题
  • 输入：旅行图、初始温度、最小温度、降温系数
  • 输出：旅行回路
• 算法
  • 随机选择城市顺序
  • 在第 步的基础上，随机交换两个（或多个）城市的顺序（移动一步）
  • 如果第 步的代价更小，则作为当前哈密顿回路，否则依据 Metroplis 准则定义的概率，有概率地将当前步作为当前解，重复执行此步骤 次
  • 按照降温系数降低温度，重复以上步骤直到迭代次数达到预设值或者温度达到最小值