【路径规划】模拟退火算法结合LNS求解车辆路径规划问题【含Matlab源码 2333期】

⛄一、模拟退火算法简介

1 模拟退火算法的原理
模拟退火算法（SA）是一种适用于大规模组合优化问题的有效近似算法，来源于对固体退火过程的模拟。统计力学表明，在给定初始温度的条件下，通过将温度缓慢降低，微观粒子会在各个温度达到热平衡状态，当物体冷却到常温时达到基态，内能达到最小。模拟固体退火的过程，给定一个初始温度和初始解，随着温度的下降，每一个温度状态下，通过解的变换生成新的解。如果解的目标函数值小于前一个解，接受当前解；否则，以概率接受新解。最终的解是迭代寻优的结果。模拟退火算法以概率突跳性，能够跳出局部最优陷阱，找到全局最优解。模拟退火算法依据Metropolis接收准则接受新解，而不是使用完全确定的规则。它构成了模拟退火算法退火过程的基础。当固体从状态i经过降温变化到状态j，它所具有的能量从E(i）变化到E(j）。显然，如果E(j)<E(i），接受新的状态j。否则，依据概率P接受新解。

其中，K是物理学波尔兹曼常数，T是固体的温度。

这种概率，在路径规划的问题中，就是当新解的目标函数值小于原来的解的函数值，新解仍被接受的概率。以x表示温度T下的一个解，通过退火，可以生成一个新解x′。那么，接收x′的概率为：