《《现代优化算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《现代优化算法》PPT课件.ppt（88页珍藏版）》请在三一办公上搜索。
1、智能优化算法,智能优化算法,智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。,常用的智能优化算法,（1）遗传算法（Genetic Algorithm，简称GA）（2）模拟退火算法（Simulated Annealing，简称SA）（3）禁忌搜索算法（Tabu Search，简称TS）,智能优化算法的特点,它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化
2、性能。,遗传算法原理与应用,报告提纲,一、遗传算法概述 二、遗传算法原理三、遗传算法的应用,一、遗传算法概述,1、智能优化算法 2、基本遗传算法 3、遗传算法的特点,遗传算法起源,遗传算法是由美国的J.Holland教授于1975年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。,遗传算法的搜索机制,遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标
3、为止。,2、基本遗传算法,基本遗传算法（Simple Genetic Algorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。,基本遗传算法的组成,（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数,编码,GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。,函数优化示例,求下列一元函数的最大值：,x-1,2，求解结果精确到6位小
4、数。,SGA对于本例的编码,由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3106等份。又因为221 3106 222，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间-1，2内对应的实数值转化为一个二进制串（b21b20b0）。,几个术语,基因型：,表现型：0.637197,编码,解码,个体（染色体）,基因,初始种群,SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。,适应度函数,遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是
5、进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。,选择算子,遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。,轮盘赌选择方法,轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为：,轮盘赌选择方法的实现步骤,（1）计算群体中所有个体的适应度函数值（需要解码
6、）；（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。,交叉算子,所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。SGA中交叉算子采用单点交叉算子。,单点交叉运算,交叉前：交叉后：,交叉点,变异算子,所谓变异运算，是指依据变异概率 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而
7、形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中变异算子采用基本位变异算子。,基本位变异算子,基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。,基本位变异算子的执行过程,变异前：0000010000变异后：1000010000,变异点,运行参数,（1）M：种群规模
8、（2）T：遗传运算的终止进化代数（3）Pc：交叉概率（4）Pm：变异概率,SGA的框图,3、遗传算法的特点,（1）群体搜索，易于并行化处理；（2）不是盲目穷举，而是启发式搜索；（3）适应度函数不受连续、可微等条件的约束，适用范围很广。,二、遗传算法原理,1、遗传算法的数学基础 2、遗传算法的收敛性分析 3、遗传算法的改进,1、遗传算法的数学基础,（1）模式定理（2）积木块假设,模式,模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集(0,1,*)的字符串，符号*代表任意字符，即 0 或者 1。模式示例：10*1,两个定义,定义1：模
9、式 H 中确定位置的个数称为模式 H 的阶，记作O(H)。例如O(10*1)=3。定义2：模式 H 中第一个确定位置和最后一个确定位置之间的距离称为模式 H 的定义距，记作(H)。例如(10*1)=4。,模式的阶和定义距的含义,模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。,模式定理,模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学
10、基础。,模式定理,从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。,积木块假设,积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。,2、遗传算法的收敛性分析,遗传算法要实现全局收敛，首先要求任意
11、初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。,种群规模对收敛性的影响,通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。,选择操作对收敛性的影响,选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。,交叉概率对
12、收敛性的影响,交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。,变异概率对收敛性的影响,变异操作是对种群模式的扰动，有利于增加种群的多样性。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。,遗传算法的本质,遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最
13、终得到问题的最优解。,3、遗传算法的改进,遗传欺骗问题：在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解。,遗传算法的改进途径,（1）对编码方式的改进（2）对遗传算子 的改进（3）对控制参数的改进（4）对执行策略的改进,对编码方式的改进,二进制编码优点在于编码、解码操作简单，交叉、变异等操作便于实现，缺点在于精度要求较高时，个体编码串较长，使算法的搜索空间急剧扩大，遗传算法的性能降低。格雷编码克服了二进制编码的不连续问题，浮点数编码改善了遗传算法的计算复杂性。,对遗传算子 的改进,排序选择 均匀交
14、叉 逆序变异,（1）对群体中的所有个体按其适应度大小进行降序排序；（2）根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体；（3）以各个个体所分配到的概率值作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产生下一代群体。,对遗传算子 的改进,排序选择 均匀交叉 逆序变异,（1）随机产生一个与个体编码长度相同的二进制屏蔽字P=W1W2Wn；（2）按下列规则从A、B两个父代个体中产生两个新个体X、Y：若Wi=0，则X的第i个基因继承A的对应基因，Y的第i个基因继承B的对应基因；若Wi=1，则A、B的第i个基因相互交换，从而生成X、Y的第i个基因。,对遗传算子 的改进
15、,排序选择 均匀交叉 逆序变异,变异前：3 4 8|7 9 6 5|2 1变异前：3 4 8|5 6 9 7|2 1,对控制参数的改进,Schaffer建议的最优参数范围是：M=20-100，T=100-500，Pc，Pm。,对控制参数的改进,Srinvivas等人提出自适应遗传算法，即PC和Pm能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低的PC和Pm，使性能优良的个体进入下一代，而低于平均适应值的个体，采用较高的PC和Pm，使性能较差的个体被淘汰。,对执行策略的改进,混合
16、遗传算法免疫遗传算法小生境遗传算法单亲遗传算法并行遗传算法,三、遗传算法的应用,1、遗传算法的应用领域 2、遗传算法的应用示例,1、遗传算法的应用领域,（1）组合优化（2）函数优化（3）自动控制（4）生产调度（5）图像处理（6）机器学习（7）人工生命（8）数据挖掘,遗传算法应用于组合优化,随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在计算机上用枚举法很难甚至不可能求出其最优解。实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、网络路由等具有NP难度的组合优化问题上取得了成功的应用。,模拟退火算法(simulated annealing,简称SA)的思想最早是由
17、Metropolis等(1953)提出的，1983年Kirkpatrick等将其用于组合优化。SA算法是基于Monte Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。,模拟退火算法,模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优解。模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。,物理退火过程和Metropolis准则简单而言，物理退火过程由以下三部分组成：加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。
18、当温度足够高时，固体将溶解为液体，从而消除系统原先可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。溶解过程与系统的熵增过程联系，系统能量也随温度的升高而增大。,等温过程。物理学的知识告诉我们，对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。冷却过程。目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。,Metropolis等在1953年提出了重要性采样法，即以概率接受新状态。具体而言，在温度t,由当前状态i产生新状态j，两者的能量分别为，若 则接受新状态j为当前状态；否则，若概率
19、 大于 区间内的随机数则仍旧接受新状态j为当前状态，若不成立则保留i为当前状态，其中k为Boltzmann常数。,这种重要性采样过程在高温下可接受与当前状态能量差较大的新状态，而在低温下基本只接受与当前能量差较小的新状态，而且当温度趋于零时，就不能接受比当前状态能量高的新状态。这种接受准则通常称为Metropolis准则。,模拟退火算法的基本思想和步骤1983年Kirkpatrick等意识到组合优化与物理退火的相似性，并受到Metropolis准则的启迪，提出了模拟退火算法。模拟退火算法是基于Monte Carlo 迭代求解策略的一种随机寻优算法，其出发点是基于物理退火过程与组合优化之间的相似
20、性，SA由某一较高初温开始，利用具有概率突跳特性的Metropolis抽样策略在解空间中进行随机搜索，伴随温度的不断下降重复抽样过程，最终得到问题的全局最优解。,标准模拟退火算法的一般步骤可描述如下：给定初温，随机产生初始状态，令；Repeat:Repeat 产生新状态；,Until 抽样稳定准则满足；退温，并令；Until 算法终止准则满足；输出算法搜索结果。,模拟退火算法关键参数和操作的设定从算法流程上看，模拟退火算法包括三函数两准则，即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则，这些环节的设计将决定SA算法的优化性能。此外，初温的选择对SA算法性能也有很大影
21、响。,状态产生函数设计状态产生函数（邻域函数）的出发点应该是尽可能保证产生的候选解遍布全部的解空间。通常，状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布。,状态接受函数状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率的形式不同。设计状态接受概率，应该遵循以下原则：在固定温度下，接受使目标函数值下降的候选解的概率要大于使目标值上升的候选解的概率；,随温度的下降，接受使目标函数值上升的解的概率要逐渐减小；当温度趋于零时，只能接受目标函数值下降的解。状态接受函数的引入是SA算法实现全局搜索的最关键的因素，SA算法中通常采用min1,exp(-C/t)作为状态接
22、受函数。,初温初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程(annealing schedule)。实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括：,均匀抽样一组状态，以各状态目标值的方差为初温。随机产生一组状态，确定两两状态间的最大目标值差，然后依据差值，利用一定的函数确定初温。譬如，其中 为初始接受概率利用经验公式给出。,温度更新函数温度更新函数，即温度的下降方式，用于在外循环中修改温度值。目前，最常用的温度更新函数为指数退温函数，即，其中且其大小可以不断变化。,内循环终止准则内循环
23、终止准则，或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。在非时齐SA算法理论中，由于在每个温度下只产生一个或少量候选解，所以不存在选择内循环终止准则的问题。,而在时齐SA算法理论中，收敛条件要求在每个温度下产生候选解的数目趋于无穷大，以使相应的马氏链达到平稳概率分布，显然在实际应用算法时这是无法实现的。常用的抽样准则包括：检验目标函数的均值是否稳定；连续若干步的目标值变化较小；按一定的步数抽样。,外循环终止准则外循环终止准则，即算法终止准则，用于决定算法何时结束。设置温度终值是一种简单的方法。SA算法的收敛性理论中要求温度终值趋于零，这显然不合实际。通常的做法是：,
24、设置终止温度的阈值；设置外循环迭代次数；算法收敛到的最优值连续若干步保持不变；检验系统熵是否稳定。,2、遗传算法的应用示例,弹药装载问题（Ammunition Loading Problem，简称ALP），就是在满足各类通用弹药运输规程和安全性的前提下，如何将一批通用弹药箱装入军用运输工具，使得通用弹药的装载效率达到最大值的问题。,AGSAA的基本原理,在弹药装载中，考虑到模拟退火算法的基本思想是跳出局部最优解，将模拟退火思想引入遗传算法，应用改进型遗传算法和模拟退火算法相结合，构建自适应遗传模拟退火算法（AGSAA），从而综合了全局优化和局部搜索的特点，为解决弹药装载这一组合优化问题提供了新
25、的思路。,AGSAA的编码方式,AGSAA采用二进制编码方式，每一个二进制位对应一个待装弹药箱，若为，表示该弹药箱装入运输工具，为则不装。,AGSAA的解码和适应度函数,AGSAA采用弹药装载的启发式算法来解码，解码后最终确定装入运输工具的弹药箱。适应度函数主要考虑两个方面，即载重率和积载率，对这两个因素加权，来计算适应度函数值。,弹药装载的启发式算法,（1）定位规则（Locating rule）定位规则是指用来确定当前待装弹药箱在运输工具剩余装载空间中摆放位置的规则。（2）定序规则（Ordering rule）定序规则是指用来确定弹药箱放入运输工具装载空间先后顺序的规则。,遗传算子的选择,A
26、GSAA的选择算子采用轮盘赌选择算子，并结合最优保存策略；变异算子采用基本位变异算子；同时，在变异运算之后，增加退火算子，以增强算法的局部搜索能力；交叉概率和变异概率为自适应概率，以提高种群的进化效率。,交叉算子的选择,由于AGSAA是采用将弹药箱的编号排列成串来进行编码的，如果个体交叉采用传统方式进行，就有可能使个体的编码产生重复基因（即一个弹药箱编号在一个个体中出现两次以上），从而产生不符合条件的个体，因此，AGSAA采用的是部分映射交叉算子。,部分映射交叉算子,交叉前：8 7|4 3|1 2 6 5 1 2|5 7|8 3 4 6交叉后：8 3|6 7|1 2 4 5 1 7|6 2|8
27、 3 4 5,禁忌搜索算法,禁忌搜索（TS）算法是一种全局性领域搜索算法，它模拟人类具有记忆功能的最优特征。,禁忌搜索的基本原理：,禁忌搜索算法是记住以往已搜索过的局部最优解，并在进一步迭代搜索中尽量避开这些局部最优解，进而使得搜索途径多样化，以此跳出局部最优解，在禁忌搜索算法中涉及邻域，候选解禁忌表，禁忌表规模，以及破禁水平等内容。,禁忌搜索的基本原理：,禁忌搜索算法首先确定一个初始可行解X，初始可行解X可以从可行解集合中随机选择，然后选择一系列的特定的搜索方向，作为试探，选择实现让特定的目标函数值减少最多的移动。为了避免陷入局部最优解，禁忌搜索中采用了一种灵活的记忆技术，对已经进行的优化过
28、程进行记录和选择，以此指导下一步的搜索方向的选择。,参考文献,1 张伟，李守智，高峰等.几种智能最优化算法的比较研究.Proceedings of the 24th Chinese Control Conference,Guangzhou,P.R.China July 15-18,2005:131613202马玉明,贺爱玲,李爱民.遗传算法的理论研究综述.山东轻工业学院学报,2004,18(3):77803 Andreas Bortfeldt,Hermann Gehring.A Hybrid Genetic Algorithm for The Container Loading Problem
29、.European Journal of Operational Research,2001(131):143161.4,.Research on Solution to Complex Container Loading Problem Based on Genetic Algorithm.The First International Conference on Machine Learning and Cybernetics.Beijing-China,2002:7882,参考文献,5 C.Pimpawat,N.Chaiyaratana.Using A Co-Operative Co-E
30、volutionary Genetic Algorithm to Solve A Three-Dimensional Container Loading Problem.The Second International Conference on Machine Learning and Cybernetics.Mongkut-Thailand,2003:119712046王春水，肖学柱，陈汉明.遗传算法的应用举例.计算机仿真2005，22(6):1551577姚文俊.遗传算法及其研究进展.计算机与数字工程,2004，32(4):41438吉根林.遗传算法研究综述.计算机应用与软件,2004，
31、21(2):69739高艳霞，刘峰，王道洪.改进型遗传算法及其应用研究.上海大学学报,2004(10):249253,参考文献,10马立肖,王江晴.遗传算法在组合优化问题中的应用.计算机工程与科学,2005，27(7):7273、8211曹先彬,刘克胜,王煦法.基于免疫遗传算法的装箱问题求解.小型微型计算机系统.2000,21(4):361363 12 Rudolf Berghammer,Florian Reuter.A Linear Approximation Algorithm for Bin Packing with Absolute Approximation Factor.Science of Computer Programming,2003(48):678013严心池,安伟光,赵维涛等.遗传算法中“免疫算子”的构造与性能.哈尔滨工程大学学报,2005，26(6):732735,
