模拟退火算法

模拟退火算法（Simulated Annealing）是一种基于概率的全局优化算法，用于在大搜索空间中找到最优解。它模拟了固体退火过程中的原子在高温下自由运动和冷却过程中逐渐凝固的过程。

算法步骤如下：

1. 初始化参数：设置初始温度T和迭代次数M，以及初始解x0。
2. 迭代搜索：重复以下步骤M次或直到达到停止条件：
   1. 生成新解：在当前解的邻域中随机生成一个新解xnew。
   2. 计算目标函数差值Δf = f(xnew) - f(x)，其中f(x)为当前解的目标函数值。
   3. 判断是否接受新解：
      • 若Δf < 0，即新解比当前解更优，则接受新解，将新解作为当前解。
      • 若Δf > 0，即新解比当前解差，则以概率exp(-Δf / T)接受新解，若接受则将新解作为当前解。
   4. 降低温度：通过降低温度函数来减小温度T，例如T = T * α，其中α为衰减系数。
3. 输出结果：输出最优解或近似最优解。

模拟退火算法的关键在于接受差解的概率计算，其原理是在初始温度较高的时候，以较大的概率接受差解，逐渐降低温度后，接受差解的概率减小，最终收敛到最优解。

模拟退火算法具有全局搜索能力，能够避免陷入局部最优解，并且能够在解空间中进行随机搜索。它广泛应用于组合优化、旅行商问题、图着色问题等领域