模拟退火算法和遗传算法.ppt

模模模模拟拟退火算法及模型退火算法及模型退火算法及模型退火算法及模型 w算法的提出算法的提出 模模拟退火算法最早的思想由退火算法最早的思想由Metropolis等（等（1953）提出，提出，1983年年Kirkpatrick等将其等将其应用于用于组合合优化。化。w算法的目的算法的目的 解决解决NP复复杂性性问题；克服克服优化化过程陷入局部极小；程陷入局部极小；克服初克服初值依依赖性。性。物理退火物理退火物理退火物理退火过过程程程程1.模模模模拟拟退火算法及模型退火算法及模型退火算法及模型退火算法及模型 w物理退火物理退火过程程 什么是退火：什么是退火：退火是指将固体加退火是指将固体加热到足到足够高的温度，使分子呈随高的温度，使分子呈随机排列状机排列状态，然后逐步降温使之冷却，最后分子以，然后逐步降温使之冷却，最后分子以低能状低能状态排列，达到某种排列，达到某种稳定状定状态。物理退火物理退火物理退火物理退火过过程程程程2.模模模模拟拟退火算法及模型退火算法及模型退火算法及模型退火算法及模型 w物理退火物理退火过程程 加温加温过程程增增强粒子的粒子的热运运动，消除系，消除系统原先可原先可能存在的非均匀能存在的非均匀态；等温等温过程程对于与于与环境境换热而温度不而温度不变的封的封闭系系统，系，系统状状态的自的自发变化化总是朝自由能减少的方向是朝自由能减少的方向进行，当自由能达到最小行，当自由能达到最小时，系，系统达到平衡达到平衡态；冷却冷却过程程使粒子使粒子热运运动减弱并减弱并渐趋有序，系有序，系统能量逐能量逐渐下降，从而得到低能的晶体下降，从而得到低能的晶体结构。构。物理退火物理退火物理退火物理退火过过程程程程3.10.1.1 10.1.1 模模模模拟拟退火算法的基本原理退火算法的基本原理退火算法的基本原理退火算法的基本原理 w数学表述数学表述 在温度在温度T，分子停留在状，分子停留在状态r满足足Boltzmann概率分概率分布布物理退火物理退火物理退火物理退火过过程程程程4.10.1.1 10.1.1 模模模模拟拟退火算法的基本原理退火算法的基本原理退火算法的基本原理退火算法的基本原理 w数学表述数学表述 在在同一个温度同一个温度T，选定两个能量定两个能量E1E2，有，有在同一个温度，分子停留在能量小的状在同一个温度，分子停留在能量小的状态的概率比的概率比停留在能量大的状停留在能量大的状态的概率要大。的概率要大。5.10.1.1 10.1.1 模模模模拟拟退火算法的基本原理退火算法的基本原理退火算法的基本原理退火算法的基本原理 w数学表述数学表述 若若|D|为状状态空空间D中状中状态的个数，的个数，D0是具有最低能是具有最低能量的状量的状态集合：集合：当温度很高当温度很高时，每个状，每个状态概率基本相同，接近平均概率基本相同，接近平均值1/|D|；状状态空空间存在超存在超过两个不同能量两个不同能量时，具有最低能量，具有最低能量状状态的概率超出平均的概率超出平均值1/|D|；当温度当温度趋于于0时，分子停留在最低能量状，分子停留在最低能量状态的概率的概率趋于于1。6.10.1.1 10.1.1 模模模模拟拟退火算法的基本原理退火算法的基本原理退火算法的基本原理退火算法的基本原理 wMetropolis准准则（1953）以概率接受新状以概率接受新状态 若在温度若在温度T，当前状，当前状态i 新状新状态j 若若Ej=randrom0,1 s=sj;Until 抽抽样稳定准定准则满足；足；退温退温tk+1=update(tk)并令并令k=k+1；Until 算法算法终止准止准则满足；足；输出算法搜索出算法搜索结果。果。12.10.1.3 10.1.3 模模模模拟拟退火算法的退火算法的退火算法的退火算法的计计算步算步算步算步骤骤及收及收及收及收敛敛性性性性 w定定义 13.10.1.3 10.1.3 模模模模拟拟退火算法的退火算法的退火算法的退火算法的计计算步算步算步算步骤骤及收及收及收及收敛敛性性性性 w定定义 一步一步转移概率：移概率：n步步转移概率：移概率：若解空若解空间有限，称有限，称马尔可夫可夫链为有限状有限状态；若若 ，称，称马尔可夫可夫链为时齐的的。马尔马尔科夫科夫科夫科夫链链14.10.1.3 10.1.3 模模模模拟拟退火算法的退火算法的退火算法的退火算法的计计算步算步算步算步骤骤及收及收及收及收敛敛性性性性 w模模拟退火算法退火算法对应了一个了一个马尔可夫可夫链 模模拟退火算法：新状退火算法：新状态接受概率接受概率仅依依赖于新状于新状态和和当前状当前状态，并由温度加以控制。，并由温度加以控制。若固定每一温度，算法均若固定每一温度，算法均计算算马氏氏链的的变化直至平化直至平稳分布，然后下降温度，分布，然后下降温度，则称称为时齐算法算法；若无需各温度下算法均达到平若无需各温度下算法均达到平稳分布，但温度需按分布，但温度需按一定速率下降，一定速率下降，则称称为非非时齐算法算法。w分析收分析收敛性性15.10.1.3 10.1.3 模模模模拟拟退火算法的退火算法的退火算法的退火算法的计计算步算步算步算步骤骤及收及收及收及收敛敛性性性性 w模模拟退火退火过程是从一个状程是从一个状态（解）到另一个状（解）到另一个状态（解）不断地随机游（解）不断地随机游动，我，我们称称这种游种游动为变换。从从邻域域Si中中选出某个解出某个解j的方法称的方法称为解的解的产生机制生机制.从当前解从当前解变换到下一个解的到下一个解的过程称程称为转移，它由移，它由产生机制的生机制的应用和接受准用和接受准则的的应用两部分用两部分组成。成。16.10.1.3 10.1.3 模模模模拟拟退火算法的退火算法的退火算法的退火算法的计计算步算步算步算步骤骤及收及收及收及收敛敛性性性性 17.10.1.3 10.1.3 模模模模拟拟退火算法的退火算法的退火算法的退火算法的计计算步算步算步算步骤骤及收及收及收及收敛敛性性性性 18.10.1.4 10.1.4 模模模模拟拟退火算法退火算法退火算法退火算法实现实现的技的技的技的技术问题术问题冷却冷却进度表度表控制参数控制参数值Tf的的选取取马尔科夫科夫链长度度Lk的的选取取控制参数衰减函数的控制参数衰减函数的选取取19.10.1.4 10.1.4 模模模模拟拟退火算法退火算法退火算法退火算法实现实现的技的技的技的技术问题术问题w原原则 (1)在固定温度下，接受使目在固定温度下，接受使目标函数下降的候函数下降的候选解的解的概率要大于使目概率要大于使目标函数上升的候函数上升的候选解概率；解概率；(2)随温度的下降，接受使目随温度的下降，接受使目标函数上升的解的概率函数上升的解的概率要逐要逐渐减小；减小；(3)当温度当温度趋于零于零时，只能接受目，只能接受目标函数下降的解。函数下降的解。w方法方法 具体形式具体形式对算法影响不大算法影响不大 一般采用一般采用min1,exp(-C/t)20.10.1.4 10.1.4 模模模模拟拟退火算法退火算法退火算法退火算法实现实现的技的技的技的技术问题术问题w方法方法 （1）均匀抽）均匀抽样一一组状状态，以各状，以各状态目目标值得方差得方差为初温；初温；（2）随机）随机产生一生一组状状态，确定两两状，确定两两状态间的最大的最大目目标值差，根据差差，根据差值，利用一定的函数确定初温；，利用一定的函数确定初温；（3）利用）利用经验公式。公式。初温初温初温初温21.10.1.4 10.1.4 模模模模拟拟退火算法退火算法退火算法退火算法实现实现的技的技的技的技术问题术问题w时齐算法的温度下降函数算法的温度下降函数 （1），越接近越接近1 1温度下降温度下降越慢，且其大小可以不断越慢，且其大小可以不断变化；化；（2），其中，其中t0为起始温度，起始温度，K为算法温算法温度下降的度下降的总次数。次数。温度更新函数温度更新函数温度更新函数温度更新函数22.10.1.4 10.1.4 模模模模拟拟退火算法退火算法退火算法退火算法实现实现的技的技的技的技术问题术问题w非非时齐模模拟退火算法退火算法 每个温度下只每个温度下只产生一个或少量候生一个或少量候选解解w时齐算法算法常用的常用的Metropolis抽抽样稳定准定准则 （1）检验目目标函数的均函数的均值是否是否稳定；定；（2）连续若干步的目若干步的目标值变化化较小；小；（3）按一定的步数抽）按一定的步数抽样。内循内循内循内循环终环终止准止准止准止准则则23.10.1.4 10.1.4 模模模模拟拟退火算法退火算法退火算法退火算法实现实现的技的技的技的技术问题术问题w模模拟退火算法的退火算法的优点点 质量高；量高；初初值鲁棒性棒性强；简单、通用、易、通用、易实现。w模模拟退火算法的缺点退火算法的缺点 由于要求由于要求较高的初始温度、高的初始温度、较慢的降温速率、慢的降温速率、较低低的的终止温度，以及各温度下足止温度，以及各温度下足够多次的抽多次的抽样，因此，因此优化化过程程较长。模模模模拟拟退火算法的退火算法的退火算法的退火算法的优优缺点缺点缺点缺点24.模模模模拟拟退火算法的退火算法的退火算法的退火算法的实现实现与与与与应应用用用用w算法流程算法流程 3030城市城市城市城市TSPTSP问题问题25.模模模模拟拟退火算法的退火算法的退火算法的退火算法的实现实现与与与与应应用用用用w运行运行过程程 3030城市城市城市城市TSPTSP问题问题26.模模模模拟拟退火算法的退火算法的退火算法的退火算法的实现实现与与与与应应用用用用w运行运行过程程 3030城市城市城市城市TSPTSP问题问题27.模模模模拟拟退火算法的退火算法的退火算法的退火算法的实现实现与与与与应应用用用用w运行运行过程程 3030城市城市城市城市TSPTSP问题问题28.10.2 10.2 遗传遗传算法算法算法算法 遗传算法（算法（Genetic Algorithm，简称称GA）是一种）是一种以自然以自然选择和和遗传理理论为基基础，将生物，将生物进化化过程中程中适者生存适者生存规则与种群内部染色体的随机交与种群内部染色体的随机交换机制相机制相结合的随机化搜索算法。合的随机化搜索算法。29.10.2 10.2 遗传遗传算法算法算法算法 w达达尔文的自然文的自然选择说遗传（heredity）：子代和父代具有相）：子代和父代具有相 同或相似的性状，保同或相似的性状，保证物种的物种的稳定性；定性；变异（异（variation）：子代与父代，子代不同个体之）：子代与父代，子代不同个体之间总有差异，是生命多有差异，是生命多样性的根源；性的根源；生存斗争和适者生存：具有适生存斗争和适者生存：具有适应性性变异的个体被保异的个体被保留，不具适留，不具适应性性变异的个体被淘汰。异的个体被淘汰。自然自然选择过程是程是长期的、期的、缓慢的、慢的、连续的的过程。程。生物生物生物生物进进化理化理化理化理论论和和和和遗传遗传学的基本知学的基本知学的基本知学的基本知识识 30.10.2 10.2 遗传遗传算法算法算法算法 w遗传学基本概念与学基本概念与术语基因座（基因座（locus）：）：遗传基因在染色体中所占据的基因在染色体中所占据的位置，同一基因座可能有的全部基因称位置，同一基因座可能有的全部基因称为等位基因等位基因（allele）；）；个体（个体（individual）：指染色体）：指染色体带有特征的有特征的实体；体；种群（种群（population）：个体的集合，）：个体的集合，该集合内个体集合内个体数称数称为种群的大小；种群的大小；遗传遗传算法的基本原理和特点算法的基本原理和特点算法的基本原理和特点算法的基本原理和特点 31.10.2 10.2 遗传遗传算法算法算法算法 w遗传学基本概念与学基本概念与术语进化（化（evolution）：生物在其延）：生物在其延续生存的生存的过程中，程中，逐逐渐适适应其生存其生存环境，使得其品境，使得其品质不断得到改良，不断得到改良，这种生命种生命现象称象称为进化；化；适适应度（度（fitness）：度量某个物种）：度量某个物种对于生存于生存环境的境的适适应程度。程度。对生存生存环境适境适应程度程度较高的物种将高的物种将获得得更多的繁殖机会，而更多的繁殖机会，而对生存生存环境适境适应程度程度较低的物低的物种，其繁殖机会就会相种，其繁殖机会就会相对较少，甚至逐少，甚至逐渐灭绝;遗传遗传算法的基本原理和特点算法的基本原理和特点算法的基本原理和特点算法的基本原理和特点32.10.2 10.2 遗传遗传算法算法算法算法 w遗传学基本概念与学基本概念与术语选择（selection）：指决定以一定的概率从种群）：指决定以一定的概率从种群中中选择若干个体的操作若干个体的操作；复制（复制（reproduction）：）：细胞在分裂胞在分裂时，遗传物物质DNA通通过复制而复制而转移到新移到新产生的生的细胞中，新的胞中，新的细胞胞就就继承了旧承了旧细胞的基因胞的基因;交叉（交叉（crossover）：在两个染色体的某一相同位）：在两个染色体的某一相同位置置处DNA被切断，其前后两串分被切断，其前后两串分别交叉交叉组合形成两合形成两个新的染色体。又称基因重个新的染色体。又称基因重组，俗称，俗称“杂交交”;遗传遗传算法的基本原理和特点算法的基本原理和特点算法的基本原理和特点算法的基本原理和特点33.10.2 10.2 遗传遗传算法算法算法算法 w遗传学基本概念与学基本概念与术语变异（异（mutation）：在）：在细胞胞进行复制行复制时可能以很小可能以很小的概率的概率产生某些复制差生某些复制差错，从而使，从而使DNA发生某种生某种变异，异，产生出新的染色体，生出新的染色体，这些新的染色体表些新的染色体表现出新出新的性状的性状;编码（coding）：表）：表现型到基因型的映射；型到基因型的映射；解解码（decoding）：从基因型到表）：从基因型到表现型的映射。型的映射。遗传遗传算法的基本原理和特点算法的基本原理和特点算法的基本原理和特点算法的基本原理和特点34.10.2 10.2 遗传遗传算法算法算法算法 w遗传算法的基本思路算法的基本思路 遗传遗传算法算法算法算法实现实现的技的技的技的技术问题术问题35.10.2 10.2 遗传遗传算法算法算法算法 遗传遗传算法算法算法算法实现实现的技的技的技的技术问题术问题 遗传算法的工作步骤36.10.2 10.2 遗传遗传算法算法算法算法 遗传遗传算法算法算法算法实现实现的技的技的技的技术问题术问题37.10.2 10.2 遗传遗传算法算法算法算法 w问题的提出的提出 一元函数求最大一元函数求最大值：简单简单函数函数函数函数优优化的化的化的化的实实例例例例 38.10.2 10.2 遗传遗传算法算法算法算法 w编码 表表现型：型：x 基因型：二基因型：二进制制编码（串（串长取决于求解精度）取决于求解精度）串串长与精度之与精度之间的关系的关系：若要求求解精度到若要求求解精度到6位小数，区位小数，区间长度度为2-(-1)3，即需将区，即需将区间分分为3/0.000001=3106等份。等份。所以所以编码的二的二进制串制串长应为22位。位。简单简单函数函数函数函数优优化的化的化的化的实实例例例例 39.10.2 10.2 遗传遗传算法算法算法算法 w产生初始种群生初始种群 产生的方式：随机生的方式：随机 产生的生的结果：果：长度度为22的二的二进制串制串 产生的数量：种群的大小（生的数量：种群的大小（规模），如模），如30，50，1111010011100001011000 1100110011101010101110 1010100011110010000100 1011110010011100111001 0001100101001100000011 0000011010010000000000 简单简单函数函数函数函数优优化的化的化的化的实实例例例例 40.10.2 10.2 遗传遗传算法算法算法算法 w计算适算适应度度 不同的不同的问题有不同的适有不同的适应度度计算方法算方法 本例：直接用目本例：直接用目标函数作函数作为适适应度函数度函数 将某个体将某个体转化化为-1,2区区间的的实数：数：s=x=0.637197 计算算x的函数的函数值（适（适应度）：度）：f(x)=xsin(10 x)+2.0=2.586345 简单简单函数函数函数函数优优化的化的化的化的实实例例例例 41.10.2 10.2 遗传遗传算法算法算法算法 w计算适算适应度度 二二进制与十制与十进制之制之间的的转换：第一步，将一个二第一步，将一个二进制串（制串（b21b20b0）转化化为10进制制数：数：第二步，第二步，x对应的区的区间-1,2内的内的实数：数：简单简单函数函数函数函数优优化的化的化的化的实实例例例例 (0000000000000000000000)-1(1111111111111111111111)242.10.2 10.2 遗传遗传算法算法算法算法 w遗传操作操作 选择：轮盘赌选择法；法；交叉：交叉：单点交叉；点交叉；变异：小概率异：小概率变异异 简单简单函数函数函数函数优优化的化的化的化的实实例例例例 43.10.2 10.2 遗传遗传算法算法算法算法 w模模拟结果果 设置的参数置的参数：种群大小种群大小50；交叉概率；交叉概率0.75；变异概率异概率0.05；最大；最大代数代数200。得到的最佳个体得到的最佳个体：smax=;xmax=1.8506;f(xmax)=3.8503;简单简单函数函数函数函数优优化的化的化的化的实实例例例例 44.10.2 10.2 遗传遗传算法算法算法算法 w模模拟结果果 进化的化的过程程：简单简单函数函数函数函数优优化的化的化的化的实实例例例例 45.10.2 10.2 遗传遗传算法算法算法算法 w编码原原则完完备性（性（completeness）：）：问题空空间的所有解都的所有解都能表示能表示为所所设计的基因型；的基因型；健全性（健全性（soundness）：任何一个基因型都）：任何一个基因型都对应于一个可能解；于一个可能解；非冗余性（非冗余性（non-redundancy）：）：问题空空间和表达空和表达空间一一一一对应。46.10.2 10.2 遗传遗传算法算法算法算法 w适适应度函数的重要性度函数的重要性 适适应度函数的度函数的选取直接影响取直接影响遗传算法的收算法的收敛速度以速度以及能否找到最及能否找到最优解。解。一般而言，适一般而言，适应度函数是由目度函数是由目标函数函数变换而成的，而成的，对目目标函数函数值域的某种映射域的某种映射变换称称为适适应度的度的尺度尺度变换（fitness scaling）。）。适适适适应应度函数及其尺度度函数及其尺度度函数及其尺度度函数及其尺度变换变换 47.10.2 10.2 遗传遗传算法算法算法算法 w几种常几种常见的适的适应度函数度函数若目若目标函数函数为最大化最大化问题：若目若目标函数函数为最小化最小化问题：适适适适应应度函数及其尺度度函数及其尺度度函数及其尺度度函数及其尺度变换变换 48.10.2 10.2 遗传遗传算法算法算法算法 w适适应度函数的度函数的线性性变换法法 f=*f+系数的确定系数的确定满足以下条件：足以下条件：缩放前后的平均适放前后的平均适应度相等度相等.favg=favg 缩放后的最大适放后的最大适应度要等于原平均适度要等于原平均适应度度 的指定倍数的指定倍数 fmax=cmult favg cmult=1.02.0 适适适适应应度函数及其尺度度函数及其尺度度函数及其尺度度函数及其尺度变换变换 49.10.2 10.2 遗传遗传算法算法算法算法 w适适应度函数的作用度函数的作用 适适应度函数度函数设计不当有可能出不当有可能出现欺欺骗问题：（1）进化初期，个化初期，个别超常个体控制超常个体控制选择过程；程；（2）进化末期，个体差异太小化末期，个体差异太小导致陷入局部极致陷入局部极值。适适适适应应度函数及其尺度度函数及其尺度度函数及其尺度度函数及其尺度变换变换 50.10.2 10.2 遗传遗传算法算法算法算法 w适适应度函数的度函数的设计单值、连续、非、非负、最大化、最大化合理、一致性合理、一致性计算量小算量小通用性通用性强 适适适适应应度函数及其尺度度函数及其尺度度函数及其尺度度函数及其尺度变换变换 51.10.2 10.2 遗传遗传算法算法算法算法 w个体个体选择概率的常用分配方法概率的常用分配方法按比例的适按比例的适应度分配（度分配（proportional fitness assignment）某个体某个体i，其适，其适应度度为fi，则其被其被选取的概率取的概率Pi为：遗传遗传操作操作操作操作选择选择 52.10.2 10.2 遗传遗传算法算法算法算法 w常用常用选择方法方法轮盘赌选择法（法（roulette wheel selection）遗传遗传操作操作操作操作选择选择 53.10.2 10.2 遗传遗传算法算法算法算法 w实值重重组离散重离散重组 子个体的每个子个体的每个变量可以按等概率随机地挑量可以按等概率随机地挑选父个体。父个体。遗传遗传操作操作操作操作交叉交叉交叉交叉/基因重基因重基因重基因重组组 父个体父个体1 12 25 5父个体父个体2 123 4 34子个体子个体1 123 4 5子个体子个体2 12 4 3454.10.2 10.2 遗传遗传算法算法算法算法 w实值重重组中中间重重组 子个体父个体子个体父个体1（父个体（父个体2父个体父个体1）是比例因子，由是比例因子，由-d,1+d上均匀分布地随机数上均匀分布地随机数产生。生。d=0时为中中间重重组，一般取，一般取d=0.25。子代的每个子代的每个变量均量均产生一个生一个。遗传遗传操作操作操作操作交叉交叉交叉交叉/基因重基因重基因重基因重组组 55.10.2 10.2 遗传遗传算法算法算法算法 w实值重重组中中间重重组 遗传遗传操作操作操作操作交叉交叉交叉交叉/基因重基因重基因重基因重组组 父个体父个体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）=67.567.5251.1（425）=1.91.92.1120.1（12312）=23.123.18.219.556.10.2 10.2 遗传遗传算法算法算法算法 w实值重重组线性重性重组 遗传遗传操作操作操作操作交叉交叉交叉交叉/基因重基因重基因重基因重组组 父个体父个体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.957.10.2 10.2 遗传遗传算法算法算法算法 w实值重重组线性重性重组 遗传遗传操作操作操作操作交叉交叉交叉交叉/基因重基因重基因重基因重组组 58.10.2 10.2 遗传遗传算法算法算法算法 w二二进制交叉制交叉单点交叉点交叉 遗传遗传操作操作操作操作交叉交叉交叉交叉/基因重基因重基因重基因重组组 59.10.2 10.2 遗传遗传算法算法算法算法 w二二进制交叉制交叉多点交叉多点交叉 遗传遗传操作操作操作操作交叉交叉交叉交叉/基因重基因重基因重基因重组组 60.10.2 10.2 遗传遗传算法算法算法算法 w变异是将某一个体的某一位字符异是将某一个体的某一位字符进行行补运算，即将运算，即将1变为0，或将，或将0变为1.遗传遗传操作操作操作操作变变异异异异 61.10.2 10.2 遗传遗传算法算法算法算法 w运行程序运行程序 算法的算法的算法的算法的设计设计与与与与实现实现 62.10.2 10.2 遗传遗传算法算法算法算法 w运行程序运行程序 算法的算法的算法的算法的设计设计与与与与实现实现 63.10.2 10.2 遗传遗传算法算法算法算法 w运行程序运行程序 算法的算法的算法的算法的设计设计与与与与实现实现 64.10.2 10.2 遗传遗传算法算法算法算法 w运行程序运行程序 算法的算法的算法的算法的设计设计与与与与实现实现 65.10.2 10.2 遗传遗传算法算法算法算法 w模式模式 将种群中的个体即基因串中的相似将种群中的个体即基因串中的相似样板称板称为模式模式。在二在二进制制编码的串中，模式是基于三个字符集（的串中，模式是基于三个字符集（0，1，*）的字符串，符号）的字符串，符号*称作通配符，代表任意称作通配符，代表任意字符，即字符，即0或或1。如模式如模式*1*描述了一个四个元的子集描述了一个四个元的子集010，011，110，111。模式定理模式定理模式定理模式定理 66.10.2 10.2 遗传遗传算法算法算法算法 w模式模式阶和定和定义距距 模式模式 H 中确定位置的个数（即中确定位置的个数（即H 中中0或或1的个数）的个数）称称为模式模式 H 的的模式模式阶，记作作 O(H)，如，如 O(0 1 1*1*)=4。模式模式阶用来反映不同模式用来反映不同模式间确定性的差异，模式确定性的差异，模式阶越高，模式的确定性就越高，所匹配的越高，模式的确定性就越高，所匹配的样本个数就本个数就越少。越少。模式定理模式定理模式定理模式定理 67.10.2 10.2 遗传遗传算法算法算法算法 w模式模式阶和定和定义距距 模式模式 H 中第一个确定位置和最后一个确定位置之中第一个确定位置和最后一个确定位置之间的距离称的距离称为模式的模式的定定义距距，记作作(H)，如，如 (0 1 1*1*)=5-1=4。阶数相同的模式会有不同的性数相同的模式会有不同的性质，定，定义距就反映了距就反映了这种性种性质的差异。的差异。模式定理模式定理模式定理模式定理 68.10.2 10.2 遗传遗传算法算法算法算法 w平均适平均适应度度 模式模式H的平均适的平均适应度是指在一个确定的群体度是指在一个确定的群体内，与内，与H相匹配的所有个体之平均适相匹配的所有个体之平均适应度，度，记做做f(H).模式定理模式定理模式定理模式定理 69.10.2 10.2 遗传遗传算法算法算法算法 w模式模式定理（定理（schema theorem）在在给定定时间步步 t,一个特定模式一个特定模式 H 有有 m 个代表串包个代表串包含在种群含在种群 A(t)中，中，记为 m=m(H,t)，在再生，在再生阶段，段，每个串根据它的适每个串根据它的适应值fi进行复制，一个串行复制，一个串 Ai 的再的再生概率生概率为 模式定理模式定理模式定理模式定理 70.10.2 10.2 遗传遗传算法算法算法算法 w模式模式定理（定理（schema theorem）当采用非重叠的当采用非重叠的 n 个串的种群替代种群个串的种群替代种群 A(t)，可以，可以得到：得到：其中其中 f(H)是在是在时间 t 表示模式表示模式 H 的串的平均适的串的平均适应度。度。模式定理模式定理模式定理模式定理 71.10.2 10.2 遗传遗传算法算法算法算法 模式定理模式定理模式定理模式定理 w模式模式定理（定理（schema theorem）假假设从从 t=0 开始，某一特定模式适开始，某一特定模式适应度度值保持在种保持在种群平均适群平均适应度以上一个度以上一个 cf（c 为一常数），一常数），则模模式的式的选择生生长方程方程为72.10.2 10.2 遗传遗传算法算法算法算法 w模式模式定理（定理（schema theorem）考考虑交叉操作，模式交叉操作，模式 H 被破坏的概率被破坏的概率为(H)/(l-1)，模式，模式 H 生存概率生存概率为 1-(H)/(l-1)，若交叉操作，若交叉操作发生的概率生的概率为 pc，因此，因此对于模式于模式 H 的生存概率的生存概率计算算为：同同时考考虑选择、交叉操作、交叉操作对模式的影响，可得：模式的影响，可得：模式定理模式定理模式定理模式定理 H1=*1 *0H2=*1 0 *73.10.2 10.2 遗传遗传算法算法算法算法 w模式模式定理（定理（schema theorem）考考虑变异操作，异操作，单个等位基因存活的概率个等位基因存活的概率为 pm，当模式当模式 H 中中 O(H)个确定位都存活个确定位都存活时，模式，模式 H 才才被保留，存活概率被保留，存活概率为：同同时考考虑选择、交叉和、交叉和变异操作异操作对模式的影响，可模式的影响，可得：得：模式定理模式定理模式定理模式定理 H1=*1 *0H2=*1 0 *074.10.2 10.2 遗传遗传算法算法算法算法 w隐并行机理并行机理：在：在遗传算法中尽管每一代只算法中尽管每一代只处理理n个个个体，但个体，但实际上却是上却是处理了理了O(n3)个模式个模式.隐隐并行机理并行机理并行机理并行机理 75.10.2 10.2 遗传遗传算法算法算法算法 隐隐并行机理并行机理并行机理并行机理 76.结结束束谢谢观谢谢观看看77.