《现代优化技术-靳志宏》算法收敛性

《《现代优化技术-靳志宏》算法收敛性》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、现代优化技术第13讲：算法收敛性浅析一、模拟退火算法的基本思想启发注意到一个自然规则：物质总是趋于最低的能态。水总是向低处流。电子总是向最低能级的轨道排布。最低能态是最稳定的状态。物质会”自动”地趋向的最低能态。模拟退火算法（起源）物理退火原理模拟退火算法与物理退火过程的相似关系模拟退火物理退火解粒子状态最优解能量最低态设定初温熔解过程Metropolis采样过程等温过程控制参数的下降冷却目标函数能量模拟退火算法（Metropolis准则）Metropolis准则假设在状态xold时，系统受到某种扰动而使其状态变为xnew。与此相对应，系统的能量也

2、从E(xold)变成E(xnew)，系统由状态xold变为状态xnew的接受概率p：模拟退火算法（流程）随机产生一个初始解x0，令xbest＝x0，并计算目标函数值E(x0);设置初始温度T(0)=To;DowhileT>Tmin//降温过程forj=1~k//等温过程对当前最优解xbest按照某一邻域函数，产生一新的解xnew。计算新的目标函数值E(xnew)，并计算目标函数值的增量E=E(xnew)-E(xbest)。如果E＜0，则xbest=xnew；如果E＞0，则p=exp(-E/T(i));如果c=random[0,1]

3、est=xnew;否则xbest=xbest。Endfor按照温度控制策略更新T；EndDo输出当前最优点，计算结束。模拟退火算法（要素）1、状态空间与状态产生函数（邻域函数）搜索空间也称为状态空间，它由经过编码的可行解的集合所组成。状态产生函数(邻域函数)应尽可能保证产生的候选解能遍布全部解空间。通常由两部分组成，即产生候选解的方式和候选解产生的概率分布。候选解一般按照某一概率分布对解空间进行随机采样来获得。概率分布可以是均匀分布、正态分布、指数分布等等。模拟退火算法（要素）2、状态转移概率（接受概率）p状态转移概率是指从一个状态xold(一个可

4、行解)向另一个状态xnew(另一个可行解)的转移概率;通俗的理解是接受一个新解为当前解的概率;它与当前的温度参数T有关，随温度下降而减小。一般采用Metropolis准则模拟退火算法（要素）3、冷却进度表T(t)冷却进度表是指从某一高温状态To向低温状态冷却时的降温管理表。假设时刻t的温度用T(t)来表示，则经典模拟退火算法的降温方式为：而快速模拟退火算法的降温方式为：这两种方式都能够使得模拟退火算法收敛于全局最小点。模拟退火算法（要素）4、初始温度T0实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优

5、化质量和优化效率，常用方法包括：(1)均匀抽样一组状态，以各状态目标值的方差为初温。(2)随机产生一组状态，确定两两状态间的最大目标值差

6、max

7、，然后依据差值，利用一定的函数确定初温。比如，t0=－max/pr，其中pr为初始接受概率。(3)利用经验公式给出。模拟退火算法（要素）5、内循环终止准则或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。常用的抽样稳定准则包括：(1)检验目标函数的均值是否稳定；(2)连续若干步的目标值变化较小；(3)按一定的步数抽样。模拟退火算法（要素）6、外循环终止准则即算法终止准则，常用的

8、包括：(1)设置终止温度的阈值；(2)设置外循环迭代次数；(3)算法搜索到的最优值连续若干步保持不变；(4)检验系统熵是否稳定。模拟退火算法的改进也可通过增加某些环节而实现对模拟退火算法的改进。主要的改进方式包括：(1)增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。(2)增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将“BestSoFar”的状态记忆下来。(3)增加补充搜索过程。即在退火过程结束后，以

9、搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。(4)对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。(5)结合其他搜索机制的算法，如遗传算法、混沌搜索等。(6)上述各方法的综合应用。15§1随机过程的概念随机过程被认为是概率论的“动力学”部分，即它的研究对象是随时间演变的随机现象，它是从多维随机变量向一族(无限多个)随机变量的推广。给定一随机试验，其样本空间，将样本空间中的每一元作如下对应，便得到一系列结果：17例1：抛掷一枚硬币的试验，样本空间是，现定义：1234181920例5：考虑抛掷一

10、颗骰子的试验：22随机过程的分类：随机过程可根据参数集T和任一时刻的状态分为四类，参数集T可分为离散集和连续集两种情况，任