模拟退火算法0852

《模拟退火算法0852》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.2模拟退火算法SimulatedAnnealing模拟退火算法1、基本思想(1)是基于MonteCarlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。(2)结合爬山法和随机行走注：SA算法最早是由Metropolis等(1953)提出模拟退火算法1、基本思想模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优解。模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。模拟退火算法

2、的设计与原理猜想物质自动趋向的最低能态与函数最小值之间有相似性！！！我们能不能设计一种算法求函数最小值，就像物质”自动”地趋向最低能态？降温图像离散函数图像相似性?最小值最低能态模拟退火算法的设计与原理物理模型——固体退火退火俗称固体降温先把固体加热至足够高温，使固体中所有粒子处于无序的状态（最高的熵值），然后将温度缓慢下降，粒子渐渐有序（熵值下降），这样只要温度上升得足够高，冷却过程足够慢，则所有粒子最终会处于最低能态（最低的熵值）。最低能态时间温度模拟退火算法2、物理退火过程和Metropolis准则⑵等温过程。物理学的知识告诉我们，对

3、于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。⑶冷却过程。目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。优化与物理退火相似性模拟退火算法2、物理退火过程和Metropolis准则Metropolis等在1953年提出了重要性采样法，即以概率接受新状态。具体而言，在温度t,由当前状态i产生新状态j，两者的能量分别为，若则接受新状态j为当前状态；否则，若概率大于区间内的随机数则仍旧接受新状态j为当前状态，若不成立则保留i为当前状态，其中k为

4、Boltzmann常数。模拟退火算法2、物理退火过程和Metropolis准则这种重要性采样过程在高温下可接受与当前状态能量差较大的新状态，而在低温下基本只接受与当前能量差较小的新状态，而且当温度趋于零时，就不能接受比当前状态能量高的新状态。这种接受准则通常称为Metropolis准则。模拟退火算法2、算法步骤标准模拟退火算法的一般步骤可描述如下：⑴给定初温，随机产生初始状态，令；⑵Repeat:①Repeat产生新状态；模拟退火算法Until抽样稳定准则满足；②退温，并令；Until算法终止准则满足；⑶输出算法搜索结果。模拟退火算法3、算法关

5、键参数和操作的设定从算法流程上看，模拟退火算法包括三函数两准则，即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则，这些环节的设计将决定SA算法的优化性能。此外，初温的选择对SA算法性能也有很大影响。模拟退火算法3、算法关键参数和操作的设定⑴状态产生函数设计状态产生函数（邻域函数）的出发点应该是尽可能保证产生的候选解遍布全部的解空间。通常，状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布。模拟退火算法3、算法关键参数和操作的设定⑵状态接受函数状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于接

6、受概率的形式不同。设计状态接受概率，应该遵循以下原则：①在固定温度下，接受使目标函数值下降的候选解的概率要大于使目标值上升的候选解的概率；模拟退火算法3、算法关键参数和操作的设定⑵状态接受函数②随温度的下降，接受使目标函数值上升的解的概率要逐渐减小；③当温度趋于零时，只能接受目标函数值下降的解。状态接受函数的引入是SA算法实现全局搜索的最关键的因素，SA算法中通常采用min[1,exp(-△C/kt)]作为状态接受函数。模拟退火算法3、算法关键参数和操作的设定⑶初温初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程(ann

7、ealingschedule)。实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括：模拟退火算法3、算法关键参数和操作的设定⑶初温①均匀抽样一组状态，以各状态目标值的方差为初温。②随机产生一组状态，确定两两状态间的最大目标值差，然后依据差值，利用一定的函数确定初温。譬如，其中为初始接受概率③利用经验公式给出。模拟退火算法3、算法关键参数和操作的设定⑷温度更新函数温度更新函数，即温度的下降方式，用于在外循环中修改温度值。目前，最常用的温度更新函数为指数退温函数。模拟退火算

8、法3、算法关键参数和操作的设定⑸内循环终止准则内循环终止准则，或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。在非时齐SA算