模拟退火(simu1atcd Amea1ing,sA)算法最早的思想是由N,Mc饣opOlis等人于1953年提出。1983年,s.Kirkpatrick等成功地将退火思想引入组合优化领域。 LPO2506I-682LC它是基于 Montc-C删0迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与 般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法,理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用,如VLsI生产调度、控制工程、机器学习、神经网络、信号处理等领域。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性,从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。可以将模拟退火算法应用于求解组合优化问题,将组合优化问题解空间中的一个解对应于固体降温过程中的一个状态,将目标函数对应于该状态下的能量。

   以控制参数Γ来模拟固体的温度。对于每一个Γ,进行迭代过程,即“解变换产生新解,判别准则,新解的取舍”,并采用Mctrop01is准则来决定解的取舍。随着温度的降低,该算法有可能从局部极值区域跳出,从而达到全局最优解。模拟退火算法流程图如图3-11所示。