文档介绍：模拟退火算法许多实际优化问题的目标问题是非凸的,存在着许多的局部最优解,特别是随着优化问题的不断增大,局部最优解的数目将大量增加。因此,对非凸目标函数的全局优化问题是一个优化领域的重要问题。求解全局优化问题的方法可分为两类:一类是确定性方法;另一类是随机性方法。确定性算法一般适用于求解满足特定要求的一些特殊问题,而梯度法和一般的随机搜索方法则沿着目标函数的下降方向搜索,因此常常陷入局部而非全局最优值。模拟退火算法(SimulateAnnealArithmetic)最早思想由Metropolis在1953年提出,是一种高效的随机全局优化方法,1982年,KirkPatrick将退火思想引入组合优化领域,提出一种解大规模组合优化问题的算法,对NP完全组合优化问题尤其有效。NP(NondeterministicPolynomial)问题是找不到一个“可用多项式时间”的解决方法,只能对所有方案一一尝试,如果必须把解域里面的所有可能都穷举了之后才能得出答案,这样的问题是NP里面最难的,这种问题叫做NP完全(plete)问题。模拟退火算法是在1982年由KirkPatrick将退火思想引入组合优化领域,提出的一种解大规模组合优化问题的算法,对NP完全组合优化问题尤其有效。它源于固体的退火过程,即先将温度加到很高,再缓慢降温(即退火),使达到能量最低点。如果急速降温(即为淬火)则不能达到最低点。模拟退火算法是一种用于求解大规模优化问题的随机搜索算法,它以优化问题求解过程与物理系统退火过程之间的相似性为基础;优化的目标函数相当于金属的内能;优化问题的自变量组合状态空间相当于金属的内能状态空间;问题的求解过程就是找一个组合状态,使目标函数值最小。利用Metropolis准则并适当地控制温度的下降过程实现模拟退火,从而达到在多项式时间内求解全局优化问题的目标。模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据Metropolis准则,粒子在温度T时趋于平衡的概率为,其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(CoolingSchedule)控制,包括控制参数的初值t0及其衰减因子a、每个t值时的迭代次数(称为一个Mapkov链的长度)L和停止条件S。有理论已经证明,模拟退火算法在初始温度足够高、温度下降足够慢的条件下,能以概率1收敛到全局最优解。由于它以某种概率接受较差的点,从而具有跳出局部最优解的能力。但在实际计算中不可能完全满足初始温度足够高、温度下降足够慢的条件。模拟退火算法的实现步骤可以表达为:初始化:给定充分大的初始温度T0,随机生成初始解状态S0作为算法迭代的起点,规定每个T值的迭代次数L和计算终止条件q,终止条件通常取为连续若干个新解都没有被接受时终