文档介绍：模拟退火算法模拟退火算法(simulatedannealing,简称SA)的思想最早是由Metropolis等(1953)提出的,1983年Kirkpatrick等将其用于组合优化。SA算法是基于MonteCarlo迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法模拟退火算法在某一初温下,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部优解能概率性地跳出并最终趋于全局最优解。模拟退火算法是一种通用的优化算法,目前已在工程中得到了广泛应用。简单而言,物理退火过程由以下三部分组成:⑴加温过程。其目的是增强粒子的热运动,使其偏离平衡位置。当温度足够高时,固体将溶解为液体,从而消除系统原先可能存在的非均匀态,使随后进行的冷却过程以某一平衡态为起点。溶解过程与系统的熵增过程联系,系统能量也随温度的升高而增大。1物理退火过程和Metropolis准则⑵等温过程。物理学的知识告诉我们,对于与周围环境交换热量而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态。⑶冷却过程。目的是使粒子的热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的晶体结构。Metropolis等在1953年提出了重要性采样法,即以概率接受新状态。具体而言,在温度t,由当前状态i产生新状态j,两者的能量分别为,若则接受新状态j为当前状态;否则,若概率大于区间内的随机数则仍旧接受新状态j为当前状态,若不成立则保留i为当前状态,其中k为Boltzmann常数。这种重要性采样过程在高温下可接受与当前状态能量差较大的新状态,而在低温下基本只接受与当前能量差较小的新状态,而且当温度趋于零时,就不能接受比当前状态能量高的新状态。这种接受准则通常称为Metropolis准则。1983年Kirkpatrick等意识到组合优化与物理退火的相似性,并受到Metropolis准则的启迪,提出了模拟退火算法。模拟退火算法是基于MonteCarlo迭代求解策略的一种随机寻优算法,其出发点是基于物理退火过程与组合优化之间的相似性,SA由某一较高初温开始,利用具有概率突跳特性的Metropolis抽样策略在解空间中进行随机搜索,伴随温度的不断下降重复抽样过程,最终得到问题的全局最优解。2模拟退火算法的基本思想和步骤标准模拟退火算法的一般步骤可描述如下:⑴给定初温,随机产生初始状态,令;⑵Repeat:①Repeat产生新状态;Until抽样稳定准则满足;②退温,并令;Until算法终止准则满足;⑶输出算法搜索结果。从算法流程上看,模拟退火算法包括三函数两准则,即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则,这些环节的设计将决定SA算法的优化性能。此外,初温的选择对SA算法性能也有很大影响。3模拟退火算法关键参数和操作的设定