模拟退火算法和遗传算法精选文档.ppt

《模拟退火算法和遗传算法精选文档.ppt》由会员分享，可在线阅读，更多相关《模拟退火算法和遗传算法精选文档.ppt（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模拟退火算法和遗传算法本讲稿第一页，共七十八页模拟退火算法及模型模拟退火算法及模型 算法的提出算法的提出 模拟退火算法最早的思想由模拟退火算法最早的思想由Metropolis等（等（1953）提出，）提出，1983年年Kirkpatrick等将其应用于组合优化。等将其应用于组合优化。算法的目的算法的目的 解决解决NP复杂性复杂性问题；问题；克服优化过程陷入局部极小；克服优化过程陷入局部极小；克服初值依赖性。克服初值依赖性。物理退火过程物理退火过程本讲稿第二页，共七十八页模拟退火算法及模型模拟退火算法及模型 物理退火过程物理退火过程 什么是退火：什么是退火：退火是指将固体加热到足够高的温度，使分

2、子呈随机排列退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，状态，然后逐步降温使之冷却，最后分子以低能状态排列，达到某种稳定状态。达到某种稳定状态。物理退火过程物理退火过程本讲稿第三页，共七十八页模拟退火算法及模型模拟退火算法及模型 物理退火过程物理退火过程 加温过程加温过程增强粒子的热运动，消除系统原先可能增强粒子的热运动，消除系统原先可能存在的非均匀态；存在的非均匀态；等温过程等温过程对于与环境换热而温度不变的封闭系统，对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，系统状态的自发变化总是朝自由能减少的

3、方向进行，当自由能达到最小时，系统达到平衡态；当自由能达到最小时，系统达到平衡态；冷却过程冷却过程使粒子热运动减弱并渐趋有序，系统能量逐使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。渐下降，从而得到低能的晶体结构。物理退火过程物理退火过程本讲稿第四页，共七十八页10.1.1 模拟退火算法的基本原理模拟退火算法的基本原理 数学表述数学表述 在温度在温度T，分子停留在状态，分子停留在状态r满足满足Boltzmann概率分布概率分布物理退火过程物理退火过程本讲稿第五页，共七十八页10.1.1 模拟退火算法的基本原理模拟退火算法的基本原理 数学表述数学表述 在在同一个温度同一个

4、温度T，选定两个能量，选定两个能量E1E2，有，有在同一个温度，分子停留在能量小的状态的概率比停在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。留在能量大的状态的概率要大。本讲稿第六页，共七十八页10.1.1 模拟退火算法的基本原理模拟退火算法的基本原理 数学表述数学表述 若若|D|为状态空间为状态空间D中状态的个数，中状态的个数，D0是具有最低能量的状是具有最低能量的状态集合：态集合：当温度很高时，每个状态概率基本相同，接近平均值当温度很高时，每个状态概率基本相同，接近平均值1/|D|；状态空间存在超过两个不同能量时，具有最低能量状态状态空间存在超过两个不同能量时，

5、具有最低能量状态的概率超出平均值的概率超出平均值1/|D|；当温度趋于当温度趋于0时，分子停留在最低能量状态的概率趋于时，分子停留在最低能量状态的概率趋于1。本讲稿第七页，共七十八页10.1.1 模拟退火算法的基本原理模拟退火算法的基本原理 Metropolis准则（准则（1953）以概率接受新状态以概率接受新状态 若在温度若在温度T，当前状态，当前状态i 新状态新状态j 若若Ej=randrom0,1 s=sj;Until 抽样稳定准则满足；抽样稳定准则满足；退温退温tk+1=update(tk)并令并令k=k+1；Until 算法终止准则满足；算法终止准则满足；输出算法搜索结果。输出算法搜

6、索结果。本讲稿第十三页，共七十八页10.1.3 模拟退火算法的计算步骤及收敛性模拟退火算法的计算步骤及收敛性 定义定义 本讲稿第十四页，共七十八页10.1.3 模拟退火算法的计算步骤及收敛性模拟退火算法的计算步骤及收敛性 定义定义 一步转移概率：一步转移概率：n步转移概率：步转移概率：若解空间有限，称马尔可夫链为若解空间有限，称马尔可夫链为有限状态有限状态；若若 ，称马尔可夫链为，称马尔可夫链为时齐的时齐的。马尔科夫链马尔科夫链本讲稿第十五页，共七十八页10.1.3 模拟退火算法的计算步骤及收敛性模拟退火算法的计算步骤及收敛性 模拟退火算法对应了一个马尔可夫链模拟退火算法对应了一个马尔可夫链

7、模拟退火算法：新状态接受概率仅依赖于新状态和当前状模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。态，并由温度加以控制。若固定每一温度，算法均计算马氏链的变化直至平稳分若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为布，然后下降温度，则称为时齐算法时齐算法；若无需各温度下算法均达到平稳分布，但温度需按一若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为定速率下降，则称为非时齐算法非时齐算法。分析收敛性分析收敛性本讲稿第十六页，共七十八页10.1.3 模拟退火算法的计算步骤及收敛性模拟退火算法的计算步骤及收敛性 模拟退火过程是从一个状

8、态（解）到另一个状态（解）模拟退火过程是从一个状态（解）到另一个状态（解）不断地随机游动，我们称这种游动为不断地随机游动，我们称这种游动为变换变换。从邻域从邻域Si中选出某个解中选出某个解j的方法称为解的产生机制的方法称为解的产生机制.从当前解变换到下一个解的过程称为转移，它由产生从当前解变换到下一个解的过程称为转移，它由产生机制的应用和接受准则的应用两部分组成。机制的应用和接受准则的应用两部分组成。本讲稿第十七页，共七十八页10.1.3 模拟退火算法的计算步骤及收敛性模拟退火算法的计算步骤及收敛性 本讲稿第十八页，共七十八页10.1.3 模拟退火算法的计算步骤及收敛性模拟退火算法的计算步骤及

9、收敛性 本讲稿第十九页，共七十八页10.1.4 模拟退火算法实现的技术问题模拟退火算法实现的技术问题冷却进度表冷却进度表控制参数值控制参数值Tf的选取的选取马尔科夫链长度马尔科夫链长度Lk的选取的选取控制参数衰减函数的选取控制参数衰减函数的选取本讲稿第二十页，共七十八页10.1.4 模拟退火算法实现的技术问题模拟退火算法实现的技术问题原则原则 (1)在固定温度下，接受使目标函数下降的候选解的概率在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；要大于使目标函数上升的候选解概率；(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减随温度的下降，接受使目标函数上升

10、的解的概率要逐渐减小；小；(3)当温度趋于零时，只能接受目标函数下降的解。当温度趋于零时，只能接受目标函数下降的解。方法方法 具体形式对算法影响不大具体形式对算法影响不大 一般采用一般采用min1,exp(-C/t)本讲稿第二十一页，共七十八页10.1.4 模拟退火算法实现的技术问题模拟退火算法实现的技术问题方法方法 （1）均匀抽样一组状态，以各状态目标值得方差为）均匀抽样一组状态，以各状态目标值得方差为初温；初温；（2）随机产生一组状态，确定两两状态间的最大目标值差，）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温；根据差值，利用一定的函数确定初温；（3）利

11、用经验公式。）利用经验公式。初温初温本讲稿第二十二页，共七十八页10.1.4 模拟退火算法实现的技术问题模拟退火算法实现的技术问题时齐算法的温度下降函数时齐算法的温度下降函数 （1），越接近越接近1 1温度下降越慢，且其温度下降越慢，且其大小可以不断变化；大小可以不断变化；（2），其中，其中t0为起始温度，为起始温度，K为算法温度下降的为算法温度下降的总次数。总次数。温度更新函数温度更新函数本讲稿第二十三页，共七十八页10.1.4 模拟退火算法实现的技术问题模拟退火算法实现的技术问题非时齐模拟退火算法非时齐模拟退火算法 每个温度下只产生一个或少量候选解每个温度下只产生一个或少量候选解时齐算法时

12、齐算法常用的常用的Metropolis抽样稳定准则抽样稳定准则 （1）检验目标函数的均值是否稳定；）检验目标函数的均值是否稳定；（2）连续若干步的目标值变化较小；）连续若干步的目标值变化较小；（3）按一定的步数抽样。）按一定的步数抽样。内循环终止准则内循环终止准则本讲稿第二十四页，共七十八页10.1.4 模拟退火算法实现的技术问题模拟退火算法实现的技术问题模拟退火算法的优点模拟退火算法的优点 质量高；质量高；初值鲁棒性强；初值鲁棒性强；简单、通用、易实现。简单、通用、易实现。模拟退火算法的缺点模拟退火算法的缺点 由于要求较高的初始温度、较慢的降温速率、较低的终由于要求较高的初始温度、较慢的降温

13、速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程止温度，以及各温度下足够多次的抽样，因此优化过程较长。较长。模拟退火算法的优缺点模拟退火算法的优缺点本讲稿第二十五页，共七十八页模拟退火算法的实现与应用模拟退火算法的实现与应用算法流程算法流程 30城市城市TSP问题问题本讲稿第二十六页，共七十八页模拟退火算法的实现与应用模拟退火算法的实现与应用运行过程运行过程 30城市城市TSP问题问题本讲稿第二十七页，共七十八页模拟退火算法的实现与应用模拟退火算法的实现与应用运行过程运行过程 30城市城市TSP问题问题本讲稿第二十八页，共七十八页模拟退火算法的实现与应用模拟退火算法的实现与应用运

14、行过程运行过程 30城市城市TSP问题问题本讲稿第二十九页，共七十八页10.2 遗传算法遗传算法 遗传算法（遗传算法（Genetic Algorithm，简称，简称GA）是一种以自然）是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则选择和遗传理论为基础，将生物进化过程中适者生存规则与种群内部染色体的随机交换机制相结合的随机化搜索算与种群内部染色体的随机交换机制相结合的随机化搜索算法。法。本讲稿第三十页，共七十八页10.2 遗传算法遗传算法 达尔文的自然选择说达尔文的自然选择说遗传（遗传（heredity）：子代和父代具有相）：子代和父代具有相 同或相似的性状，保证物种的稳定性；同

15、或相似的性状，保证物种的稳定性；变异（变异（variation）：子代与父代，子代不同个体之间总）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；有差异，是生命多样性的根源；生存斗争和适者生存：具有适应性变异的个体被保留，不生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。具适应性变异的个体被淘汰。自然选择过程是长期的、缓慢的、连续的过程。自然选择过程是长期的、缓慢的、连续的过程。生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 本讲稿第三十一页，共七十八页10.2 遗传算法遗传算法 遗传学基本概念与术语遗传学基本概念与术语基因座（基因座（lo

16、cus）：遗传基因在染色体中所占据的位置，）：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因（同一基因座可能有的全部基因称为等位基因（allele）；）；个体（个体（individual）：指染色体带有特征的实体；）：指染色体带有特征的实体；种群（种群（population）：个体的集合，该集合内个体数称为种）：个体的集合，该集合内个体数称为种群的大小；群的大小；遗传算法的基本原理和特点遗传算法的基本原理和特点 本讲稿第三十二页，共七十八页10.2 遗传算法遗传算法 遗传学基本概念与术语遗传学基本概念与术语进化（进化（evolution）：生物在其延续生存的过程中，逐渐

17、）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；命现象称为进化；适应度（适应度（fitness）：度量某个物种对于生存环境的适）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝繁殖机会就会相对较少，甚至逐渐灭绝;遗传算法的基本原理和特点遗传算法的基本原理和特点本讲稿第三十三页，共七十八页10.2 遗传算法

18、遗传算法 遗传学基本概念与术语遗传学基本概念与术语选择（选择（selection）：指决定以一定的概率从种群中选）：指决定以一定的概率从种群中选择若干个体的操作择若干个体的操作；复制（复制（reproduction）：细胞在分裂时，遗传物质）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因了旧细胞的基因;交叉（交叉（crossover）：在两个染色体的某一相同位置处）：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重

19、组，俗称体。又称基因重组，俗称“杂交杂交”;遗传算法的基本原理和特点遗传算法的基本原理和特点本讲稿第三十四页，共七十八页10.2 遗传算法遗传算法 遗传学基本概念与术语遗传学基本概念与术语变异（变异（mutation）：在细胞进行复制时可能以很小的概）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使率产生某些复制差错，从而使DNA发生某种变异，发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状产生出新的染色体，这些新的染色体表现出新的性状;编码（编码（coding）：表现型到基因型的映射；）：表现型到基因型的映射；解码（解码（decoding）：从基因型到表现型的映射。）：

20、从基因型到表现型的映射。遗传算法的基本原理和特点遗传算法的基本原理和特点本讲稿第三十五页，共七十八页10.2 遗传算法遗传算法 遗传算法的基本思路遗传算法的基本思路 遗传算法实现的技术问题遗传算法实现的技术问题本讲稿第三十六页，共七十八页10.2 遗传算法遗传算法 遗传算法实现的技术问题遗传算法实现的技术问题 遗传算法的工作步骤本讲稿第三十七页，共七十八页10.2 遗传算法遗传算法 遗传算法实现的技术问题遗传算法实现的技术问题本讲稿第三十八页，共七十八页10.2 遗传算法遗传算法 问题的提出问题的提出 一元函数求最大值：一元函数求最大值：简单函数优化的实例简单函数优化的实例 本讲稿第三十九页，

21、共七十八页10.2 遗传算法遗传算法 编码编码 表现型：表现型：x 基因型：二进制编码（串长取决于求解精度）基因型：二进制编码（串长取决于求解精度）串长与精度之间的关系串长与精度之间的关系：若要求求解精度到若要求求解精度到6位小数，区间长度为位小数，区间长度为2-(-1)3，即，即需将区间分为需将区间分为3/0.000001=3106等份。等份。所以编码的二进制串长应为所以编码的二进制串长应为22位。位。简单函数优化的实例简单函数优化的实例 本讲稿第四十页，共七十八页10.2 遗传算法遗传算法 产生初始种群产生初始种群 产生的方式：随机产生的方式：随机 产生的结果：长度为产生的结果：长度为22

22、的二进制串的二进制串 产生的数量：种群的大小（规模），如产生的数量：种群的大小（规模），如30，50，1111010011100001011000 1100110011101010101110 1010100011110010000100 1011110010011100111001 0001100101001100000011 0000011010010000000000 简单函数优化的实例简单函数优化的实例 本讲稿第四十一页，共七十八页10.2 遗传算法遗传算法 计算适应度计算适应度 不同的问题有不同的适应度计算方法不同的问题有不同的适应度计算方法 本例：直接用目标函数作为适应度函数本例：

23、直接用目标函数作为适应度函数 将某个体转化为将某个体转化为-1,2区间的实数：区间的实数：s=x=0.637197 计算计算x的函数值（适应度）：的函数值（适应度）：f(x)=xsin(10 x)+2.0=2.586345 简单函数优化的实例简单函数优化的实例 本讲稿第四十二页，共七十八页10.2 遗传算法遗传算法 计算适应度计算适应度 二进制与十进制之间的转换二进制与十进制之间的转换：第一步，将一个二进制串（第一步，将一个二进制串（b21b20b0）转化为）转化为10进制数：进制数：第二步，第二步，x对应的区间对应的区间-1,2内的实数：内的实数：简单函数优化的实例简单函数优化的实例 (00

24、00000000000000000000)-1(1111111111111111111111)2本讲稿第四十三页，共七十八页10.2 遗传算法遗传算法 遗传操作遗传操作 选择：轮盘赌选择法；选择：轮盘赌选择法；交叉：单点交叉；交叉：单点交叉；变异：小概率变异变异：小概率变异 简单函数优化的实例简单函数优化的实例 本讲稿第四十四页，共七十八页10.2 遗传算法遗传算法 模拟结果模拟结果 设置的参数设置的参数：种群大小种群大小50；交叉概率；交叉概率0.75；变异概率；变异概率0.05；最大代数；最大代数200。得到的最佳个体得到的最佳个体：smax=;xmax=1.8506;f(xmax)=3.

25、8503;简单函数优化的实例简单函数优化的实例 本讲稿第四十五页，共七十八页10.2 遗传算法遗传算法 世代数世代数自变量自变量适应度适应度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503模拟结果模拟结果 进化的过程进化的过程：简单函数优化的实例简单函数优化的实例 本讲稿第四十六页，共七十八页10.2 遗传算法遗传算法 编码原则编码原则完备性（完备性（completeness）：问题空间的所有解都能表示）：问题空间的所有

26、解都能表示为所设计的基因型；为所设计的基因型；健全性（健全性（soundness）：任何一个基因型都对应于一个可）：任何一个基因型都对应于一个可能解；能解；非冗余性（非冗余性（non-redundancy）：问题空间和表达空间一一）：问题空间和表达空间一一对应。对应。本讲稿第四十七页，共七十八页10.2 遗传算法遗传算法 适应度函数的重要性适应度函数的重要性 适应度函数的选取直接影响遗传算法的收敛速度以及能适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解。否找到最优解。一般而言，适应度函数是由目标函数变换而成的，对一般而言，适应度函数是由目标函数变换而成的，对目标函数值域的某种映射

27、变换称为适应度的目标函数值域的某种映射变换称为适应度的尺度变换尺度变换（fitness scaling）。）。适应度函数及其尺度变换适应度函数及其尺度变换 本讲稿第四十八页，共七十八页10.2 遗传算法遗传算法 几种常见的适应度函数几种常见的适应度函数若目标函数为最大化问题：若目标函数为最大化问题：若目标函数为最小化问题：若目标函数为最小化问题：适应度函数及其尺度变换适应度函数及其尺度变换 本讲稿第四十九页，共七十八页10.2 遗传算法遗传算法 适应度函数的线性变换法适应度函数的线性变换法 f=*f+系数的确定满足以下条件：系数的确定满足以下条件：缩放前后的平均适应度相等缩放前后的平均适应度相

28、等.favg=favg 缩放后的最大适应度要等于原平均适应度缩放后的最大适应度要等于原平均适应度 的指定倍数的指定倍数 fmax=cmult favg cmult=1.02.0 适应度函数及其尺度变换适应度函数及其尺度变换 本讲稿第五十页，共七十八页10.2 遗传算法遗传算法 适应度函数的作用适应度函数的作用 适应度函数设计不当有可能出现欺骗问题：适应度函数设计不当有可能出现欺骗问题：（1）进化初期，个别超常个体控制选择过程；）进化初期，个别超常个体控制选择过程；（2）进化末期，个体差异太小导致陷入局部极值。）进化末期，个体差异太小导致陷入局部极值。适应度函数及其尺度变换适应度函数及其尺度变换

29、 本讲稿第五十一页，共七十八页10.2 遗传算法遗传算法 适应度函数的设计适应度函数的设计单值、连续、非负、最大化单值、连续、非负、最大化合理、一致性合理、一致性计算量小计算量小通用性强通用性强 适应度函数及其尺度变换适应度函数及其尺度变换 本讲稿第五十二页，共七十八页10.2 遗传算法遗传算法 个体选择概率的常用分配方法个体选择概率的常用分配方法按比例的适应度分配（按比例的适应度分配（proportional fitness assignment）某个体某个体i，其适应度为，其适应度为fi，则其被选取的概率，则其被选取的概率Pi为：为：遗传操作遗传操作选择选择 个体个体ff2P12.56.2

30、50.1821.01.000.0333.09.000.2641.21.440.0452.14.410.1360.80.640.0272.56.250.1881.31.690.0590.90.810.02101.83.240.09本讲稿第五十三页，共七十八页10.2 遗传算法遗传算法 个体个体1234567891011适应度适应度2.01.81.61.41.21.00.80.60.40.20.1选择概率选择概率0.180.160.150.130.110.090.070.060.030.020.0累计概率累计概率0.180.340.490.620.730.820.890.950.981.001.0

31、0常用选择方法常用选择方法轮盘赌选择法（轮盘赌选择法（roulette wheel selection）遗传操作遗传操作选择选择 本讲稿第五十四页，共七十八页10.2 遗传算法遗传算法 实值重组实值重组离散重组离散重组 子个体的每个变量可以按等概率随机地挑选父个体。子个体的每个变量可以按等概率随机地挑选父个体。遗传操作遗传操作交叉交叉/基因重组基因重组 父个体父个体1 12 25 5父个体父个体2 123 4 34子个体子个体1 123 4 5子个体子个体2 12 4 34本讲稿第五十五页，共七十八页10.2 遗传算法遗传算法 实值重组实值重组中间重组中间重组 子个体父个体子个体父个体1（父个

32、体（父个体2父个体父个体1）是比例因子，由是比例因子，由-d,1+d上均匀分布地随机数产生。上均匀分布地随机数产生。d=0时为中间重组，一般取时为中间重组，一般取d=0.25。子代的每个变量均产生一个子代的每个变量均产生一个。遗传操作遗传操作交叉交叉/基因重组基因重组 本讲稿第五十六页，共七十八页10.2 遗传算法遗传算法 实值重组实值重组中间重组中间重组 遗传操作遗传操作交叉交叉/基因重组基因重组 父个体父个体1 12 25 5父个体父个体2 123 4 34子个体子个体1子个体子个体2值样本值样本1 0.5 1.1 -0.1值样本值样本2 0.1 0.8 0.5120.5（12312）=6

33、7.567.5251.1（425）=1.91.92.1120.1（12312）=23.123.18.219.5本讲稿第五十七页，共七十八页10.2 遗传算法遗传算法 实值重组实值重组线性重组线性重组 遗传操作遗传操作交叉交叉/基因重组基因重组 父个体父个体1 12 25 5父个体父个体2 123 4 34子个体子个体1子个体子个体2值样本值样本1 0.5值样本值样本2 0.1120.5（12312）=67.567.5250.5（425）=14.514.519.5120.1（12312）=23.123.122.97.9本讲稿第五十八页，共七十八页10.2 遗传算法遗传算法 实值重组实值重组线性重

34、组线性重组 遗传操作遗传操作交叉交叉/基因重组基因重组 本讲稿第五十九页，共七十八页10.2 遗传算法遗传算法 二进制交叉二进制交叉单点交叉单点交叉 遗传操作遗传操作交叉交叉/基因重组基因重组 本讲稿第六十页，共七十八页10.2 遗传算法遗传算法 二进制交叉二进制交叉多点交叉多点交叉 遗传操作遗传操作交叉交叉/基因重组基因重组 本讲稿第六十一页，共七十八页10.2 遗传算法遗传算法 变异是将某一个体的某一位字符进行补运算，即将变异是将某一个体的某一位字符进行补运算，即将1变为变为0，或将，或将0变为变为1.遗传操作遗传操作变异变异 本讲稿第六十二页，共七十八页10.2 遗传算法遗传算法 运行程

35、序运行程序 算法的设计与实现算法的设计与实现 本讲稿第六十三页，共七十八页10.2 遗传算法遗传算法 运行程序运行程序 算法的设计与实现算法的设计与实现 本讲稿第六十四页，共七十八页10.2 遗传算法遗传算法 运行程序运行程序 算法的设计与实现算法的设计与实现 本讲稿第六十五页，共七十八页10.2 遗传算法遗传算法 运行程序运行程序 算法的设计与实现算法的设计与实现 本讲稿第六十六页，共七十八页10.2 遗传算法遗传算法 模式模式 将种群中的个体即基因串中的相似样板称为将种群中的个体即基因串中的相似样板称为模式模式。在二进制编码的串中，模式是基于三个字符集（在二进制编码的串中，模式是基于三个字

36、符集（0，1，*）的字符串，符号的字符串，符号*称作通配符，代表任意字符，即称作通配符，代表任意字符，即0或或1。如模式如模式*1*描述了一个四个元的子集描述了一个四个元的子集010，011，110，111。模式定理模式定理 本讲稿第六十七页，共七十八页10.2 遗传算法遗传算法 模式阶和定义距模式阶和定义距 模式模式 H 中确定位置的个数（即中确定位置的个数（即H 中中0或或1的个数）称为模的个数）称为模式式 H 的的模式阶模式阶，记作，记作 O(H)，如，如 O(0 1 1*1*)=4。模式阶用来反映不同模式间确定性的差异，模式阶越模式阶用来反映不同模式间确定性的差异，模式阶越高，模式的确

37、定性就越高，所匹配的样本个数就越少。高，模式的确定性就越高，所匹配的样本个数就越少。模式定理模式定理 本讲稿第六十八页，共七十八页10.2 遗传算法遗传算法 模式阶和定义距模式阶和定义距 模式模式 H 中第一个确定位置和最后一个确定位置之间中第一个确定位置和最后一个确定位置之间的距离称为模式的的距离称为模式的定义距定义距，记作，记作(H)，如，如 (0 1 1*1*)=5-1=4。阶数相同的模式会有不同的性质，定义距就反映了这种性阶数相同的模式会有不同的性质，定义距就反映了这种性质的差异。质的差异。模式定理模式定理 本讲稿第六十九页，共七十八页10.2 遗传算法遗传算法 平均适应度平均适应度

38、模式模式H的平均适应度是指在一个确定的群体内，的平均适应度是指在一个确定的群体内，与与H相匹配的所有个体之平均适应度，记做相匹配的所有个体之平均适应度，记做f(H).模式定理模式定理 本讲稿第七十页，共七十八页10.2 遗传算法遗传算法 模式模式定理（定理（schema theorem）在给定时间步在给定时间步 t,一个特定模式一个特定模式 H 有有 m 个代表串包含在个代表串包含在种群种群 A(t)中，记为中，记为 m=m(H,t)，在再生阶段，每个串根，在再生阶段，每个串根据它的适应值据它的适应值fi进行复制，一个串进行复制，一个串 Ai 的再生概率为的再生概率为 模式定理模式定理 本讲稿

39、第七十一页，共七十八页10.2 遗传算法遗传算法 模式模式定理（定理（schema theorem）当采用非重叠的当采用非重叠的 n 个串的种群替代种群个串的种群替代种群 A(t)，可以得到：，可以得到：其中其中 f(H)是在时间是在时间 t 表示模式表示模式 H 的串的平均适应度。的串的平均适应度。模式定理模式定理 本讲稿第七十二页，共七十八页10.2 遗传算法遗传算法 模式定理模式定理 模式模式定理（定理（schema theorem）假设从假设从 t=0 开始，某一特定模式适应度值保持在种开始，某一特定模式适应度值保持在种群平均适应度以上一个群平均适应度以上一个 cf（c 为一常数），则

40、模式为一常数），则模式的选择生长方程为的选择生长方程为本讲稿第七十三页，共七十八页10.2 遗传算法遗传算法 模式模式定理（定理（schema theorem）考虑交叉操作，模式考虑交叉操作，模式 H 被破坏的概率为被破坏的概率为(H)/(l-1)，模式，模式 H 生存概率为生存概率为 1-(H)/(l-1)，若交叉操作发生的概率为，若交叉操作发生的概率为 pc，因此对于模式，因此对于模式 H 的生存概率计算为：的生存概率计算为：同时考虑选择、交叉操作对模式的影响，可得：同时考虑选择、交叉操作对模式的影响，可得：模式定理模式定理 H1=*1 *0H2=*1 0 *本讲稿第七十四页，共七十八页1

41、0.2 遗传算法遗传算法 模式模式定理（定理（schema theorem）考虑变异操作，单个等位基因存活的概率为考虑变异操作，单个等位基因存活的概率为 pm，当模式，当模式 H 中中 O(H)个确定位都存活时，模式个确定位都存活时，模式 H 才被保留，存活概才被保留，存活概率为：率为：同时考虑选择、交叉和变异操作对模式的影响，可得：同时考虑选择、交叉和变异操作对模式的影响，可得：模式定理模式定理 H1=*1 *0H2=*1 0 *0本讲稿第七十五页，共七十八页10.2 遗传算法遗传算法 隐并行机理隐并行机理：在遗传算法中尽管每一代只处理：在遗传算法中尽管每一代只处理n个个体，个个体，但实际上却是处理了但实际上却是处理了O(n3)个模式个模式.隐并行机理隐并行机理 本讲稿第七十六页，共七十八页10.2 遗传算法遗传算法 隐并行机理隐并行机理 本讲稿第七十七页，共七十八页结束结束谢谢观看谢谢观看本讲稿第七十八页，共七十八页