《《现代优化技术-靳志宏》算法收敛性.ppt》由会员分享，可在线阅读，更多相关《《现代优化技术-靳志宏》算法收敛性.ppt（71页珍藏版）》请在三一办公上搜索。
1、现代优化技术,第13讲：算法收敛性浅析,一、模拟退火算法的基本思想,启发注意到一个自然规则：物质总是趋于最低的能态。水总是向低处流。电子总是向最低能级的轨道排布。最低能态是最稳定的状态。物质会”自动”地趋向的最低能态。,模拟退火算法（起源）,物理退火原理,模拟退火算法与物理退火过程的相似关系,模拟退火算法（Metropolis准则）,Metropolis准则假设在状态xold时，系统受到某种扰动而使其状态变为xnew。与此相对应，系统的能量也从E(xold)变成E(xnew)，系统由状态xold变为状态xnew的接受概率p：,模拟退火算法（流程）,随机产生一个初始解x0，令xbest x0，并
2、计算目标函数值E(x0);设置初始温度T(0)=To;Do while T Tmin/降温过程for j=1k/等温过程对当前最优解xbest按照某一邻域函数，产生一新的解xnew。计算新的目标函数值E(xnew)，并计算目标函数值的增量E=E(xnew)-E(xbest)。如果E 0，则xbest=xnew；如果E 0，则p=exp(-E/T(i);如果c=random0,1 p，xbest=xnew;否则 xbest=xbest。End for按照温度控制策略更新T；End Do输出当前最优点，计算结束。,模拟退火算法（要素）,1、状态空间与状态产生函数（邻域函数）搜索空间也称为状态空间，
3、它由经过编码的可行解的集合所组成。状态产生函数(邻域函数)应尽可能保证产生的候选解能遍布全部解空间。通常由两部分组成，即产生候选解的方式和候选解产生的概率分布。候选解一般按照某一概率分布对解空间进行随机采样来获得。概率分布可以是均匀分布、正态分布、指数分布等等。,模拟退火算法（要素）,2、状态转移概率（接受概率）p状态转移概率是指从一个状态xold(一个可行解)向另一个状态xnew(另一个可行解)的转移概率;通俗的理解是接受一个新解为当前解的概率;它与当前的温度参数T有关，随温度下降而减小。一般采用Metropolis准则,模拟退火算法（要素）,3、冷却进度表T(t)冷却进度表是指从某一高温状
4、态To向低温状态冷却时的降温管理表。假设时刻t的温度用T(t)来表示，则经典模拟退火算法的降温方式为：而快速模拟退火算法的降温方式为：这两种方式都能够使得模拟退火算法收敛于全局最小点。,模拟退火算法（要素）,4、初始温度T0实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括：(1)均匀抽样一组状态，以各状态目标值的方差为初温。(2)随机产生一组状态，确定两两状态间的最大目标值差|max|，然后依据差值，利用一定的函数确定初温。比如，t0=max/pr，其中pr为初始接受概率。(3)利用经验公式给出。,模拟退火算法（要素
5、）,5、内循环终止准则或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。常用的抽样稳定准则包括：(1)检验目标函数的均值是否稳定；(2)连续若干步的目标值变化较小；(3)按一定的步数抽样。,模拟退火算法（要素）,6、外循环终止准则即算法终止准则，常用的包括：(1)设置终止温度的阈值；(2)设置外循环迭代次数；(3)算法搜索到的最优值连续若干步保持不变；(4)检验系统熵是否稳定。,模拟退火算法的改进,也可通过增加某些环节而实现对模拟退火算法的改进。主要的改进方式包括：(1)增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进
6、程中的当前状态，避免算法在局部极小解处停滞不前。(2)增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将“Best So Far”的状态记忆下来。(3)增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。(4)对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。(5)结合其他搜索机制的算法，如遗传算法、混沌搜索等。(6)上述各方法的综合应用。,15,1 随机过程的概念,随机过程被认为是概率论的“动力学”部分，即它的研究对象是随时间演变的随机现象，它是从多维随机变量
7、向一族(无限多个)随机变量的推广。给定一随机试验，其样本空间，将样本空间 中的每一元作如下对应，便得到一系列结果：,17,例1：抛掷一枚硬币的试验，样本空间是，现定义：,18,19,20,例5：考虑抛掷一颗骰子的试验：,22,随机过程的分类：随机过程可根据参数集T和任一时刻的状态分为四类，参数集T可分为离散集和连续集两种情况，任一时刻的状态分别为离散型随机变量和连续型随机变量两种：连续参数连续型的随机过程，如例2，例3连续参数离散型的随机过程，如例1，例4离散参数离散型的随机过程，如例5离散参数连续型的随机过程，如下例,马尔科夫Markov链,引例假定某大学有1万学生，每人每月用1支牙膏，并且
8、只使用“中华”牙膏与“黑妹”牙膏两者之一。根据本月（12月）调查，有3000人使用黑妹牙膏，7000人使用中华牙膏。又据调查,使用黑妹牙膏的3000人中，有60的人下月将继续使用黑妹牙膏，40的人将改用中华牙膏；使用中华牙膏的7000人中，有70的人下月将继续使用中华牙膏，30的人将改用黑妹牙膏。据此，可以得到如表所示的统计表,状态和状态转移状态是指客观事物可能出现或存在的状况。如企业的产品在市场上可能畅销，也可能滞销。状态转移是指客观事物由一种状态到另一种状态的变化。客观事物的状态不是固定不变的，它可能处于这种状态，也可能处于那种状态，往往条件变化，状态也会发生变化。如某种产品在市场上本来是
9、滞销的，但是由于销售渠道变化了，或者消费心理发生了变化等，它便可能变为畅销产品。,转移概率与转移概率矩阵假定某大学有1万学生，每人每月用1支牙膏，并且只使用“中华”牙膏与“黑妹”牙膏两者之一。根据本月（12月）调查，有3000人使用黑妹牙膏，7000人使用中华牙膏。又据调查,使用黑妹牙膏的3000人中，有60的人下月将继续使用黑妹牙膏，40的人将改用中华牙膏；使用中华牙膏的7000人中，有70的人下月将继续使用中华牙膏，30的人将改用黑妹牙膏。据此，可以得到如表所示的统计表,上表中的4个概率就称为状态的转移概率，而这四个转移概率组成的矩阵B 称为转移概率矩阵。可以看出，转移概率矩阵的一个特点是
10、其各行元素之和为,2 转移概率矩阵及柯尔莫哥洛夫定理,例1 某计算机机房的一台计算机经常出故障，研究者每隔15min观察一次计算机的运行状态，收集了24h的数据（共作97次观察）。用1表示正常状态，用0表示不正常状态，所得的数据序列如下：,近邻探索过程,全局最优解,局部最优解2,局部最优解1,邻域,目标函数値,模拟退火算法的数学模型可以描述为，在给定邻域结构后，模拟退火过程是从一个状态到另一个状态不断地随机游动，我们可以用马尔科夫链描述这一过程，对给定的温度t，两个状态的转移概率定义为：,称为从i到j的产生概率（generation probability），表示在状态i时，j状态被选取的概率
11、，比较容易理解的是j为i的邻居，如果在邻域中等概率选取，则j被选中的概率为：,称为接受概率（acceptance probability），表示产生状态j后，j状态被接受的概率，在模拟退火算法中常见的是：,由上面三组公式可以看出，一步转移概率只同状态i转移到状态j有关，同第几次迭代无关，因此，马氏链是时齐的，正是这个原因，将这一类算法取名为时齐算法。下面，介绍几个概率论中常用概念，辅助同学们理解算法收敛性的讨论过程。,若存在n，使得，则称状态i可达状态j，记成 若状态i和状态j满足 且，则称状态i和状态j相通，记成。有如下定理：定理：若 且 则有。,定义从i到达j的首达时刻的随机变量为：,其概
12、率定义为：,迟早到达概率定义为：,定理：的充分必要条件是,定理：状态j是常返的，则以概率1系统无穷次返回状态j，状态j是非常返的，则以概率1，系统只有限次返回状态j。记 表示自状态i出发，系统通过j状态至少m次的概率，记 表示状态i出发通过j状态至少m次的时间。,于是，有，进而，所以，,常返的含义,常返中的一种特殊情况为正常返，定义：,当 时为正常返，当 时为零常返。,常返定理表明常返是以概率1无穷次返回同一状态，上式表明有些常返状态的平均返回次数是有限的，而有些是无限的。当马氏链的离散状态均为常返且平均返回次数有限，就称该马氏链是正常返的。,在模拟退火的理论中，经常用到的一个概念是不可约，不
13、可约中用到的一个概念是闭集。一个集合C是闭集的定义为：有，这表示集合C是一个封闭的集合，i不可达到j，对任意n成立。除整个状态空间外，没有别的闭集的马氏链成为不可约的马氏链。,定理1：不可约、有限状态且时齐的马氏链是正常返的。定理2：非周期、不可约且时齐的马氏链是正常返的充分必要条件：存在唯一平稳分布，满足,模拟退火算法的时齐算法，当具有以下条件成立时，则可以认为该模拟退火算法收敛全局最优解：（1）在每一个给定的温度t，给出算法一步转移概率 的一些限定条件，使得定理2成立，由此得到平稳分布概率。（2）给出平稳分布应该满足的条件，使得当温度渐进达到0度时，平稳分布的极限存在，即要求（3）进一步要
14、求平稳分布的极限具有全局最优性条件：其中 是最优状态集合。,探索空间（search space）与实行可能域（feasible solution field）(1),探索空间=实行可能域,目标函数值 探索评价基准,近邻例一台机器的交货期最小迟延排序问题,工件的集合 1,2,3,4,可行解的集合 从1,2,3,4中構成4!种可能的排序,目标函数一台机器的交货期最小迟延排序问题,目标函数交货期迟延的合計（最小化）,可行解（順列）1234 所对应的目标函数,J1,=6,近邻一台机器的交货期最小迟延排序问题,近邻两个相邻工件交換后得到的排序,可行解1 2 3 4 的近邻,1 2 4 3,1 3 2 4
15、,2 1 3 4,一台机器的交货期最小迟延排序问题 近邻图,1234,1243,点与解一一对应,6,6,7,7,5,4,3,5,7,7,10,8,7,8,6,6,8,5,5,4,6,10,目标函数值,2134,1324,探索空间（search space）与实行可能域（feasible solution field）(2),探索空间,目标函数值(objective function value)+惩罚函数值(penalty function value）,实行可能域,探索空间,实行可能域,探索评价基准,带有时间窗约束的VRP问题：,邻域交换不能随意进行，因为需要满足客户时间窗的硬性要求,处理办
16、法有两种：（1）不排斥不可行解，用惩罚函数进行处理（通常为在目标函数设置一个惩罚项，如果突破时间窗则使目标函数为一个正无穷大的值）。该种做法的实质是扩大了解空间，使近邻搜索空间具有完备性，同时又不影响搜索结果，但会影响搜索路径（有好有坏）。这样的改造会使邻域内选择解的概率满足上述定理的假设条件，充分满足随机性，会提高算法的各方面性能，因此是推荐方法。（2）排斥不可行解，直接忽略。不能满足上述定理的条件，影响算法收敛性,解空间的搜索,解,离散随机状态,随机状态的跳转,满意解,最终状态,SA接受准则/GA算子,状态转移概率矩阵,目标函数的导向性,稳态概率最大似然值对应状态,考试题型,选择（20）、判断（20）、简答（60）简答内容：（1）对于概念，技术细节的描述，原理的阐述（2）编码设计（3）编写算法伪代码（4）算法的时间复杂度计算（5）收敛性简要分析,下次课,（1）数学模型，算法设计以及程序设计的关系（难点：约束条件的算法处理，模式定理与积木块假设，算法迭代中不可行解的处理办法）（2）算法程序实现的实例详解（适应度函数编写的难点：复杂模型的程序推进核心：时间残值矩阵）,Q&A,
