起点。溶解过程与系统的熵增过程联系,系统能量也随温度的升高而增大。Р模拟退火算法Р⑵等温过程。物理学的知识告诉我们,对于与周围环境交换热量而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态。?⑶冷却过程。目的是使粒子的热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的晶体结构。Р模拟退火算法РMetropolis等在1953年提出了重要性采样法,即以概率接受新状态。具体而言,在温度t,由当前状态i产生新状态j,两者的能量分别为,若则接受新状态j为当前状态;否则,若概率Р大于区间内的随机数则仍旧接受新状态j为当前状态,若不成立则保留i为当前状态,其中k为Boltzmann常数。Р模拟退火算法Р这种重要性采样过程在高温下可接受与当前状态能量差较大的新状态,而在低温下基本只接受与当前能量差较小的新状态,而且当温度趋于零时,就不能接受比当前状态能量高的新状态。这种接受准则通常称为Metropolis准则。Р模拟退火算法Р12.1.2 模拟退火算法的基本思想和步骤?1983年Kirkpatrick等意识到组合优化与物理退火的相似性,并受到Metropolis准则的启迪,提出了模拟退火算法。模拟退火算法是基于Monte Carlo 迭代求解策略的一种随机寻优算法,其出发点是基于物理退火过程与组合优化之间的相似性,SA由某一较高初温开始,利用具有概率突跳特性的Metropolis抽样策略在解空间中进行随机搜索,伴随温度的不断下降重复抽样过程,最终得到问题的全局最优解。Р模拟退火算法Р标准模拟退火算法的一般步骤可描述如下:? ⑴给定初温,随机产生初始状态,令;?⑵Repeat:? ①Repeat? 产生新状态;Р模拟退火算法РUntil 抽样稳定准则满足; ? ②退温,并令; ? Until 算法终止准则满足; ?⑶输出算法搜索结果。
全文预览
