1.3.2 模拟退火算法
固体退火是一种物理过程，物体在加热至一定温度后，所有的分子在状态空间中自由移动，随着温度的下降，这些分子逐渐停留在不同的状态，在温度最低时，分子重新以一定的结构排列，统计力学的研究表明，分子的状态满足波尔兹曼(Boltzmann)分布。1953年，Metropolis以波尔兹曼分布为基础提出Metropolis准则来模拟固体的退火过程。1982年，Kirkpatrick等科学家发现固体的退火与优化问题的求解，这两个过程有诸多的相同点，于是将Metropolis准则引入到组合优化问题的求解算法中，提出了模拟退火(Simulated Annealing，简称SA)算法，也叫做蒙特卡罗退火、统计冷却、概率爬山、随机松弛和概率交换算法，它是基于对热力学退火过程的模拟［14-15］。模拟退火中需要手动调整很多关键参数，如初始温度、温度下降的方案、固定温度时的迭代长度和温度的终值。SA算法的流程如下。
Step1:给定初始温度T的值，随机产生一个当前点x。
Step2:根据一系列指标判定算法是否可以停止，如果算法终止就根据需要输出相应的结果，否则执行后续步骤。
Step3:在当前点x的邻域内选择一新点y，如果y的适应值优于x，则用y替代x;否则，以一定概率接受这个新点，接受概率依赖于这两个点的相对性能，即它们对应的评估函数值之间的差别，即当rand［0，1］＜e
时，接受新点y。
Step4:判断是否满足终止条件，若不满足，Step3重复执行KT次(KT为温度为T时的迭代长度);否则继续执行后续的步骤。
Step5:根据冷却率g(T，t)计算得到新的温度T。
Step6:转Step2。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
