《随机算法介绍》PPT课件.ppt

《《随机算法介绍》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《随机算法介绍》PPT课件.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、智能优化算法研究智能优化算法研究1引言在复杂系统的优化计算过程中，传统的确定性算法（如梯度法、共轭梯度法、牛顿法、拟牛顿法等）往往容易陷入局部极值点（如下图）。为了有效地进行全局搜索，得到问题的全局最优解或次优解，人们受自然界、或具体问题的启发提出了一些启发式的随机优化算法。模拟退火算法；遗传算法等进化计算方法；神经网络算法；蚁群算法等等。2一、模拟退火算法模拟退火算法最早由Metropolis于1953年提出，1983年Kirkpatrick等将其应用于优化问题。1.算法步骤(1)给定初温给定初温t=t0，随机产生初始状态随机产生初始状态X(1)，令，令k=0;(2)Repeat (2.1)

2、Repeat (2.1.1)产生新的状态产生新的状态X(2)=Generate(X(1);(2.1.2)if random0,1min1,expC(X(1)-C(X(2)/tk X(1)=X(2);/这里这里C(X(1)为状态为状态X(1)的目标函数的目标函数值值 (2.2)Until 抽样稳定准则满足抽样稳定准则满足 (2.3)退温退温tk+1=update(tk),并令并令k=k+1;(3)Until 算法终止准则满足算法终止准则满足;(4)输出结果输出结果3一、模拟退火算法2、三函数、二准则（新状态产生函数，新状态接受函数，退温函数，抽样稳定准则和退火结束准则）新状态产生函数：通常用领域

3、函数，并且尽可能使候选解遍布全部解空间。状态接受函数：通常用概率的方式给出，遵循以下三原则：1）在固定温度下，接受使目标函数值下降的候选解的概率要大于使用目标函数值上升的候选解的概率；2）随着温度的下降，接受使目标函数值上升的解的概率要逐渐减少；3）当温度趋于零时，只能接受目标函数值下降的解。模拟退火算法通常采用min1,expC(X(1)-C(X(2)/tk作为状态接受函数。4一、模拟退火算法 退温函数：tk+1k+1=tk k(01);抽样稳定规则：通常有三种方法:1)检验目标函数的均值是否稳定;2)连续若干步的目标值变化较小;3)按一定的步数抽样.退火结束准则：三种方法：1)设置终止温度

4、;2)设置外循环迭代次数;3)算法搜索到的最优值连续若干步保持不变。5二、势能曲面变平算法1.势能曲面变平（ELP）算法描述(1)给定一个初始状态给定一个初始状态X(1)，令，令t=1，初始化直方图函数，初始化直方图函数(2)H(E,t)，设置温度，设置温度T，计算，计算E(X(1),t)，令最优解，令最优解(3)E=E(X(1),t)，计算，计算 ；(2)更新当前状态更新当前状态X(1)，产生新的状态，产生新的状态X（2）Generate(X(1)；(3)计算计算 和和 ，令，令(4)如果如果 ，则接受，则接受X(2)，判断，判断E(X(2)E?6二、势能曲面变平算法 若是，则令若是，则令E

5、=E(X(2),t)；否则否则按下式决定是否接受按下式决定是否接受X(2)：random(0,1)106，则停止迭代，输出，则停止迭代，输出E；否则，；否则，令令t=t+1，转，转(2).2.对算法的理解对算法的理解关键是：通过增加惩罚项，对目标函数进行修改，尽量关键是：通过增加惩罚项，对目标函数进行修改，尽量避免重复访问曾经访问过的状态。避免重复访问曾经访问过的状态。7二、势能曲面变平算法3.对算法的改进1）提出好的状态更新机制：怎样产生新的状态？最好具有搜索整个状态空间的能力。具体来说：可以针对具体问题提出一些启发式策略；或考虑与遗传算法相结合；或采用与禁忌搜索相结合的方法。2）局部搜索：

6、一旦产生一个新的状态，就用某一确定性的算法（如梯度法）进一步搜索该状态附近目标函数值更低的状态。3）将退温机制加入算法4）增加补充搜索过程：即以搜索到的最优解为初始状态，再次执行势能曲面变平法，或进行局部搜索。8三、吸引盘填充算法吸引盘填充算法是势能曲面变平法与梯度法的结合。1.自适应步长的梯度算法 X2=X1-E(X1)h 其中h是自适应步长。9三、吸引盘填充算法2.吸引盘填充(Basin Filling,BF)算法BF算法是一种将随机算法（ELP）与确定性算法（如梯度法）很好地结合起来的混合算法，其中随机算法ELP用来进行全局搜索，提高采样的多样性和跳出局部极值点，梯度法则用来进行局部搜索

7、，以便快速得到全局最优或新的能量更低的状态。BF算法是一种高性能的全局优化方法。10四.应用：圆形packing问题1.问题提法问题提法问题问题1：给定一个大小确定的圆形闭区域，以及给定一个大小确定的圆形闭区域，以及M个可互不个可互不重叠地放进圆形区域中的小圆，这些小圆的半径分别为重叠地放进圆形区域中的小圆，这些小圆的半径分别为R1,R2,RM，问如何将这些小圆互不重叠地放进圆形区域，问如何将这些小圆互不重叠地放进圆形区域中中?问题问题2：给定给定M个半径分别是个半径分别是R1,R2,RM的小圆，问如何的小圆，问如何将这将这M个小圆摆放在直角坐标系平面上，使得所有个小圆摆放在直角坐标系平面上，

8、使得所有M个小圆个小圆形成的包络圆形成的包络圆(即圆形闭区域即圆形闭区域)的面积最小？的面积最小？11四.圆形packing问题一个实例：12四.圆形packing问题一个实例的布局结果13四.圆形packing问题2.问题背景问题背景圆形Packing问题是NP难度问题，在玻璃、钢板、木材、纸张和制衣等工程领域中有着广泛的应用，在这些工程应用领域中人们常常遇到圆形物体的裁剪、下料及装运问题。从实际应用的角度出发，人们开始寻找快速的近似启发式求解算法。3.研究现状研究现状Hifi和Hallah提出了动态、自适应二阶段局部搜索算法。（Hifi M,MHallah R.European Journ

9、al of Operational Research,2007）此后，他们进一步改进该算法，提出了一个基于自适应和从头开始策略的三阶段近似求解算法（Hifi M,MHallah R.Computational Optimization and Applications,2008）。14四.圆形packing问题Akeb 等给出了自适应的集束搜索算法（Akeb H.Hifi M,MHallah R.Computers and Operations Research,2008)在国内，黄文奇等提出了求解不等圆Packing问题的高效的拟物拟人算法。(Wang HQ,Huang WQ,Zhang Q

10、A,Xu DM.European Journal of Operational Research,2002;Huang WQ,Kang Y.Annals of Operations Research 2004 Huang WQ,Li Y,Li CM,Xu RC.Computers and Operations Research,2006)张德富等将禁忌搜索算法与模拟退火算法相结合，提出了圆形Packing问题的混合算法。(Zhang DF,Deng AS.Computers and Operations Research,2008)吕志鹏等将PERM算法与占角穴度算法相结合得到了求解圆形Pac

11、king问题的PERM算法。(L ZP,Huang WQ.Computers and Operations Research,2008)15四.圆形packing问题4.问题1的转换将所有给定的圆想象为光滑的具有弹性的圆饼；将圆形区域想象为一个圆形弹性容器，则M个小圆和圆形区域构成的系统的势能为：这里 表示第i个圆与第j个圆之间的嵌入深度。这样，问题1转化为优化问题：min E(X)，即要求求状态X*使得E(X*)=0。16四.圆形packing问题17四.圆形packing问题5.实验结果测试集测试集1（任意圆情况，14个算例中有9个得到新的世界纪录）18四.圆形packing问题测试集2（

12、等圆情况，10个算例中有7个达到世界纪录）19四.圆形packing问题测试集3（不等圆情况）：12个算例中有3个得到新的世界记录。203.圆形packing问题350个圆的布局结果。21五、禁忌搜索算法（一）禁忌搜索（Tabu Search,或Taboo Search,简记为TS）由Glover（1986年）提出。禁忌搜索最重要的思想是：标记已搜索到的局部最优的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止），从而保证对不同的有效搜索途径的探索。22五、禁忌搜索算法基本过程是：给定一个当前解（初始解）和一种邻域，然后在当前解的邻域中确定若干候选解；若最佳候选解对应的目标值优

13、于“best so far”状态，则忽视其禁忌特性，用其替换当前解和“best so far”状态，并将相应的对象加入禁忌表，同时修改禁忌表中各对象的任期；若不存在上述候选解，则在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与当前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程，直到满足停止准则。23五、禁忌搜索算法（二）简单禁忌搜索算法的步骤：（1）给定算法参数，随机产生初始解x，置禁忌表为空。（2）判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤。（3）利用当前解x的邻域函数产生其所有（或若干）邻域解，并从中确定若

14、干候选解。（4）对候选解判断藐视准则是否满足？若成立，则用满足藐视准则的最佳状态y替换x成为新的当前解，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，并修改禁忌表中各对象的任期，然后转步骤（6）；否则，继续以下步骤。（5）判断候选解对应的各状态的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时修改禁忌表中各对象的任期。（6）转步骤（2）。24五、禁忌搜索算法（三）禁忌搜索的关键参数和操作 （1）初始解和适配值函数；（2）邻域结构和禁忌对象；（3）候选解选择；（4）禁忌表及其长度；（5）藐视准则；（6）其中搜索和分散搜索策略；（

15、7）终止准则。其中，邻域函数是基于局部邻域搜索的思想，用于实现邻域搜索；禁忌表和禁忌对象的设置，体现了算法避免迂回搜索的特点；藐视准则，则是对优良状态的奖励，它是对禁忌策略的一种放松。25五、禁忌搜索算法1、适配值函数 可以将目标函数直接作为适配值函数。也可以将目标函数的变形作为适配值函数，譬如对极小值问题可将状态的适配值f(x)定义为M-c(x)或e-c(x)，其中M为一个足够大正数，c(x)为目标值。2、禁忌对象 所谓禁忌对象就是被置入禁忌表中的那些变化元素，而禁忌的目标则是为了尽量避免迂回搜索而多搜索一些有效的搜索途径。通常，禁忌对象可选取状态本身或状态分量或适配值的变化等。26五、禁忌

16、搜索算法(1)以状态本身或其变化作为禁忌对象是最简单、最容易理解的途径。具体而言，当状态由x变化到状态y时，将状态y(或x-y的变化)视为禁忌对象，从而在一定条件下禁止了y(或x-y的变化)的再度出现。(2)状态的变化包含了状态分量的变化，因此以状态分量的变化为禁忌对象将扩大禁忌的范围，并可减少相应的计算量。(3)以适配值或其变化为禁忌对象。此时可将处于同一适配值的状态视为相同状态，该策略在函数优化中经常采用。27五、禁忌搜索算法3、禁忌长度和候选解 禁忌长度和候选解的大小是影响TS算法性能的两个关键参数。所谓禁忌长度，即禁忌对象在不考虑藐视准则情况下不允许被选取的最大次数（即对象在禁忌表中的

17、任期），对象只有当其任期为0时才被解禁。禁忌长度t可以是固定的某个数（如t=3）；也可以是动态变化的，如根据搜索性能和问题特性设定禁忌长度的变化区间（如3,10等），而禁忌长度则可按照某种原则或公式在其区间内变化。一般而言，当算法的性能动态下降较大时，说明算法当前的搜索能力比较强，也可能当前解附近极小解形成的“波谷”较深，从而可设置较大的禁忌长度来延续当前的搜索行为。28五、禁忌搜索算法 候选解集则通常是当前状态的领域解集的一个子集。在算法的构造和计算过程中，一方面要求计算量和存储量尽量少，这就要求禁忌长度和候选解集尽量小；但是，禁忌长度过短将造成搜索的循环，候选解集过小容易造成早熟收敛，即陷

18、入局部极小。因此可以确定性或随机性地在部分邻域解中选取候选解，具体数据大小则可视问题特性和对算法的要求而定。29五、禁忌搜索算法4、藐视准则 在禁忌搜索算法中，可能会出现候选解全部禁忌，或者存在一个优于“best so far”状态的禁忌候选解，此时藐视准则将使某些状态解禁，以实现更高效的优化性能。下面是几种常用的藐视准则。（1）基于适配值的准则。若某个禁忌候选解的适配值优于”best so far”状态，则解禁候选解为当前状态和新的”best so far”状态。（2）基于搜索方向的准则。若禁忌对象上次被禁忌时使得适配值有所改善，并且目前该禁忌对象对应的候选解的适配值优于当前解，则对该禁忌对

19、象解禁。（3）基于解锁准则。若候选解均被禁忌，且不存在优于”best so far”状态的候选解，则对候选解中最佳的候选解进行解禁，以继续搜索。30五、禁忌搜索算法5、禁忌频率 记忆禁忌频率（或次数）是对禁忌属性的一种补充，可放宽选择决策对象的范围。譬如，如果某个适配值频繁出现，则可以推测算法陷入某种循环或某个极小点，或者说现有算法参数难以有助于发掘更好的状态，进而适当对算法结构或参数作修改。6、终止准则 （1）给定最大迭代步数。（2）设定某个对象的最大禁忌频率。即，若某个状态、适配值等对象的禁忌频率超过某一阀值，则终止算法，其中也包括最佳适配值连续若干步保持不变的情况。（3）设定适配值的偏离

20、幅度。首先估计问题的下限，一旦算法中最佳适配值与下限的偏离值小于某规定幅度时，则终止搜索。31六、遗传算法（一）遗传算法(Genetic algorithm,GA)遗传算法是Holland于1975年受生物进化论的启发而提出的。它将问题的求解表示为“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。32六、遗传算法（二）遗传算法的主要步骤：（1）随机产生一组初始个体，构成初始种群，并评价每个个体的适配值。（2）判断算法收敛准则是否满足。若满足则输出搜索结果；否则执行以下步骤。（3）根据适配值大小以

21、一定方式执行复制操作。（4）按照交叉概率pc执行交叉操作。如random0,1pc（5）按照变异概率pm执行变异操作。如 random0,1pm（6）返回步骤（2）。33六、遗传算法34六、遗传算法（三）算法关键参数与操作的设计1、编码 编码就是将问题的解用一种码来表示，从而将问题的状态空间与GA的码空间相对应。函数优化中，不同的码长和码制，对问题求解的精度和效率有很大影响。二进制编码将问题的解用一个二进制串来表示，十进制编码将问题的解用一个十进制串来表示。而实数编码将问题的解用一个实数来表示，实数编码解决了编码对算法精度和存储量的影响，也便利于优化中引入问题的相关信息，它在高维复杂优化问题中

22、得到广泛应用。35六、遗传算法2、适配值函数f(X)：如取f(X)=M-c(X)或1/(1+c(X)，其中M为大数，c(X)为目标函数值。3、遗传算子复制操作是为了避免有效基因的损失，使高性能的个体得以更大的概率生存，从而提高全局收敛性和计算效率。最常用的方法是比例复制（如轮盘赌）和基于排名的复制。交叉操作用于组合出新的个体，在解空间中进行有效的搜索，同时降低对有效模式的破坏概率。二进制编码中，单点交叉随机确定一个交叉位置，然后对换相应的字串；多点交叉随机确定多个交叉位置，然后对换相应的子串。36六、遗传算法 如：父串为(1011001)，(0010110)若单点交叉位置为4，则后代为(101

23、1110)，(0010001)；若多点交叉位置为2，5，则后代为(1010101)，(0011010)。十进制编码一样处理。对于实数编码则可采用算术交叉，即 =ax1+(1-a)x2，=ax2+(1-a)x1，其中a(0,1),x1,x2为父代个体，和 为后代个体。变异操作有利于增加种群的多样性，克服交叉操作产生的后代适配值没有达到最优且不再进化而早熟收敛的缺陷。二进制或十进制编码中通常采用替换式变异，即用另一种基因替换某位置原先的基因；实数编码中通常采用扰动式变异，即对原先个体附加一定机制的扰动来实现变异。37六、遗传算法4、算法参数种群数目是影响算法优化性能的因素之一。通常，种群太小则不能

24、提供足够的采样点，以致算法性能很差，甚至得不到问题的可行解；种群太大时尽管可增加优化信息以阻止早熟收敛的发生，但无疑会增加计算量，从而使收敛时间太长。交叉概率用于控制交叉操作的频率。概率太大时，种群的更新很快，进而会使高适配值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而使搜索停滞不前。变异操作是加大种群多样性的重要因素。通常一个较低的变异率足以防止整个群体中任一位置的基因一直保持不变。38六、遗传算法5、算法的终止条件最常用的终止条件就是事先给定一个最大进化步数，或者是判断最佳优化值是否连续若干步没有明显变化。总之，目前实际应用遗传算法时，许多环节一般还只是凭经验解决，尽管提出了许多

25、针对各个环节进行的一些改进的遗传算法：如对于复制操作，DeJong提出了回放和无回放式随机采样复制策略等；在交叉操作方面，Goldberg提出了部分匹配交叉算子等；在变异操作方面，一些学者提出了自适应变异、多级变异等操作；在函数优化方面，Goldberg引入分享思想将解空间分成若干子空间，然后在子空间中产生子群体成员分别进行优化。此外还有人提出了基于小生境的遗传算法，以及免疫遗传算法等等。但GA的效率还有待于进一步研究。39一些优化计算软件SNOPT（大规模线性、二次和非线性规划）；MINOS（线性和非线性规划）；LANCELOT(无约束最优化、非线性最小二乘、边界约束最优化和一般约束最优化问

26、题)；MINPACK(非线性方程组和非线性最小二乘问题)；PROC NLP(无约束最优化、非线性最小二乘、线性约束最优化、二次规划和一般约束最优化问题)；CONOPT（非线性规划）；FSQP（非线性规划和极小极大问题）；GRG2（非线性规划)；LINDO（线性、二次和混合整数规划）；LSSOL（最小二乘和二次规划）；NLPJOB（非线性多目标规划）；OPTPACK（约束和无约束最优化）；PETS（解非线性方程组和无约束问题的并行算法）；QPOPT（线性和二次规划）；SQOPT（大规模线性和凸二次规划）；SPRNLP（稀疏最小二乘,稀疏和稠密非线性规划）；SYSFIT（非线性方程组的参数估计）；

27、TENSOLVE（非线性方程组和最小二乘）等。40七、支持向量机1 支持向量机的基本思想对于线性可分数据，随机产生一个超平面并移动它，直到训练集中属于不同类别的样本点正好位于该超平面的两侧。显然，这种方法能够解决线性分类问题，但不能保证产生的超平面是最优的。支持向量机建立的分类超平面能够在保证分类精度的同时，使超平面两侧的空白区域最大化，从而实现对线性可分问题的最优分类。41七、支持向量机1.1 最优超平面的概念考虑P个线性可分样本 对于任一输入样本Xp，其期望输出为d p=，分别代表两类的类别标识。用于分类的超平面方程为：式中，X为输入向量，W为权值向量，b为偏置，则有42七、支持向量机由式

28、（1）定义的超平面与最近的样本点之间的间隔称为分离边缘，用 表示，支持向量机的目标是找到一个使分离边缘最大的超平面，即最优超平面。如下图：最优超平面支持向量43七、支持向量机假设最优超平面的方程为：则样本空间中任一点X到最优超平面的距离为：从而有判别函数，g(X)=r|W0|=W0TXb0将判别函数归一化，使所有样本满足：44七、支持向量机则对于离最优超平面最近的特殊样本Xs满足|g(Xs)|=1，称为支持向量。（2）式可表示为：从支持向量到最优超平面的代数距离为：45七、支持向量机因此，两类之间的间隔可用分离边缘表示为：（4）式表明，要使分离边缘最大化等价于使权值向量的范数|W|最小化。因此

29、，满足（3）式的条件且使|W|最小的分类超平面就是最优超平面。46七、支持向量机1.2 最优超平面的构建建立最优线性分类超平面问题可以表示成如下的约束优化问题。采用Lagrange系数方法解决此约束最优化问题，引入Lagrange函数47七、支持向量机得：将（6）式展开：48七、支持向量机将（7）式代入上式，则问题转化为：设Q（)的最优解为则最优超平面的权向量为：最优分类判断函数为：49七、支持向量机2 支持向量机神经网络支持向量机求解非线性可分模式分类的方法如下：将输入向量映射到一个高维特征向量空间，如果选用的映射函数适当且特征空间的维数足够高，则大多数非线性可分模式在特征空间中可以转化为线

30、性可分模式，因此可以在该特征空间构造最优超平面进行模式分类。50七、支持向量机设X为N维输入空间的向量，令(X)=1(X),2(X),m(X)T表示从输入空间到M维特征空间的非线性变换，称为输入向量X在特征空间诱导出的“像”。特征空间分类超平面的权向量为：51七、支持向量机超平面方程为：最优分类判别函数为52七、支持向量机 3 支持向量机的学习算法 步骤如下：（1）通过非线性变换 将输入向量映射到高维特征空间。（2）在约束条件53七、支持向量机（3）计算最优权值（4）对于分类模式X，计算分类判别函数根据f(X)为1或-1，决定X的类别归属。54七、支持向量机 4 支持向量机处理XOR问题XOR问题：4个样本如图：21X2-1-2-2 -1 x1 1 2(-1,1)(1,1)(-1,-1)(1,-1)55七、支持向量机选择映射函数10-1-2-2 -1 0 1 2可将二维训练样本映射到一个六维特征空间，这个六维空间在平面上的投影如下图。(-1,-1)(1,1)(-1,1)(1,-1)56七、支持向量机可以看出分离边缘最优超平面为X1X20。（推导过程略）注：也可选择映射函数57