模拟退火算法和遗传算法.ppt

模拟退火算法和遗传算法
第1页，共78页，2022年，5月20日，6点43分，星期四
模拟退火算法及模型
算法的提出
模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatri
第13页，共78页，2022年，5月20日，6点43分，星期四
模拟退火算法的计算步骤及收敛性
定义
第14页，共78页，2022年，5月20日，6点43分，星期四
模拟退火算法的计算步骤及收敛性
定义
一步转移概率：
n步转移概率：
若解空间有限，称马尔可夫链为有限状态；
若 ，称马尔可夫链为时齐的。
马尔科夫链
第15页，共78页，2022年，5月20日，6点43分，星期四
模拟退火算法的计算步骤及收敛性
模拟退火算法对应了一个马尔可夫链
模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。
若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为时齐算法；
若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算法。
分析收敛性
第16页，共78页，2022年，5月20日，6点43分，星期四
模拟退火算法的计算步骤及收敛性
模拟退火过程是从一个状态（解）到另一个状态（解）不断地随机游动，我们称这种游动为变换。
从邻域Si中选出某个解j的方法称为解的产生机制.
从当前解变换到下一个解的过程称为转移，它由产生机制的应用和接受准则的应用两部分组成。
第17页，共78页，2022年，5月20日，6点43分，星期四
模拟退火算法的计算步骤及收敛性
第18页，共78页，2022年，5月20日，6点43分，星期四
模拟退火算法的计算步骤及收敛性
第19页，共78页，2022年，5月20日，6点43分，星期四
模拟退火算法实现的技术问题
冷却进度表
控制参数值Tf的选取
马尔科夫链长度Lk的选取
控制参数衰减函数的选取
第20页，共78页，2022年，5月20日，6点43分，星期四
模拟退火算法实现的技术问题
原则
(1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；
(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小；
(3)当温度趋于零时，只能接受目标函数下降的解。
方法
具体形式对算法影响不大
一般采用min[1,exp(-∆C/t)]
第21页，共78页，2022年，5月20日，6点43分，星期四
模拟退火算法实现的技术问题
方法
（1）均匀抽样一组状态，以各状态目标值得方差为初温；
（2）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温；
（3）利用经验公式。
初温
第22页，共78页，2022年，5月20日，6点43分，星期四
模拟退火算法实现的技术问题
时齐算法的温度下降函数
（1） ，α越接近1温度下降越慢，且其大小可以不断变化；
（2） ，其中t0为起始温度，K为算法温度下降的总次数。
温度更新函数
第23页，共78页，2022年，5月20日，6点43分，星期四
模拟退火算法实现的技术问题
非时齐模拟退火算法
每个温度下只产生一个或少量候选解
时齐算法——常用的Metropolis抽样稳定准则
（1）检验目标函数的均值是否稳定；
（2）连续若干步的目标值变化较小；
（3）按一定的步数抽样。
内循环终止准则
第24页，共78页，2022年，5月20日，6点43分，星期四
模拟退火算法实现的技术问题
模拟退火算法的优点
质量高；
初值鲁棒性强；
简单、通用、易实现。
模拟退火算法的缺点
由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。
模拟退火算法的优缺点
第25页，共78页，2022