第4章-遗传算法优秀PPT.ppt

第第4章章 遗传算法遗传算法Contents算法简介算法简介 1 1基本流程基本流程 2 2改进研究改进研究 3 3相关应用相关应用 4 44.1 遗传算法简介遗传算法简介遗传算法是什么？遗传算法是什么？遗传算法遗传算法（Genetic Algorithm，GA）是进化计算的一个分支，是进化计算的一个分支，是一种模拟自然界生物进化过程的随机搜是一种模拟自然界生物进化过程的随机搜寻算法。寻算法。遗传算法的思想来源是怎样的？遗传算法的思想来源是怎样的？它由谁提出的？它由谁提出的？GA思想源于自然界思想源于自然界“自然选择自然选择”和和“优胜劣优胜劣汰汰”的进化规律，的进化规律，通过模拟生物进化中的自然选择和交配变通过模拟生物进化中的自然选择和交配变异找寻问题的全局最优解。异找寻问题的全局最优解。它最早由美国密歇根高校教授它最早由美国密歇根高校教授John H.Holland提出，提出，现在已经广泛应用于各种工程领域的优化现在已经广泛应用于各种工程领域的优化问题之中。问题之中。4.1.1 基本原理基本原理遗传算法遗传算法遗传算法遗传算法 达尔文进化论达尔文进化论现代遗传学现代遗传学生物模拟技术生物模拟技术生物进化生物进化生命自从在地球上诞生以来，就起先了漫长的生物生命自从在地球上诞生以来，就起先了漫长的生物演化历程，低级、简洁的生物类型渐渐发展为高级、演化历程，低级、简洁的生物类型渐渐发展为高级、困难的生物类型。这一过程已经由古生物学、胚胎困难的生物类型。这一过程已经由古生物学、胚胎学和比较解剖学等方面的探讨工作所证明。生物进学和比较解剖学等方面的探讨工作所证明。生物进化的缘由自古至今有着各种不同的说明，其中被人化的缘由自古至今有着各种不同的说明，其中被人们广泛接受的是达尔文的自然选择学说。们广泛接受的是达尔文的自然选择学说。4.1.1 基本原理基本原理自然选择学说认为，生物要生存下去，就必需进行生存斗自然选择学说认为，生物要生存下去，就必需进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物与无机环争。生存斗争包括种内斗争、种间斗争以及生物与无机环境之间的斗争三个方面。境之间的斗争三个方面。在生存斗争中，具有有利变异在生存斗争中，具有有利变异(mutation)的个体简洁存活的个体简洁存活下来，并且有更多的机会将有利变异传给后代，具有不利下来，并且有更多的机会将有利变异传给后代，具有不利变异的个体简洁被淘汰，产生后代的机会也少得多。变异的个体简洁被淘汰，产生后代的机会也少得多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存、不适者淘较强的。达尔文把这种在生存斗争中适者生存、不适者淘汰的过程叫做自然选择。汰的过程叫做自然选择。达尔文的自然选择学说表明，遗传和变异是确定生物进化达尔文的自然选择学说表明，遗传和变异是确定生物进化的内在因素。的内在因素。4.1.1 基本原理基本原理4.1.1 基本基本原理原理生物遗传进化生物遗传进化群体群体种群种群染色体染色体基因基因适应能力适应能力交配交配变异变异进化结束进化结束遗传算法遗传算法搜索空间的一组有效搜索空间的一组有效解解选择得到的新群体选择得到的新群体可行解的编码串可行解的编码串染色体的一个编码单染色体的一个编码单元元染色体的适应值染色体的适应值染色体交换部分基因得到新染色体交换部分基因得到新染色体染色体染色体某些基因的数值改变染色体某些基因的数值改变算法结束算法结束生物遗传进化过程生物遗传进化过程遗传算法遗传算法类比关系类比关系4.1.1 基本基本原理原理生物进化过程生物进化过程遗传基因重组过程遗传基因重组过程1、模式的定义、模式的定义 模式也称积木块（模式也称积木块（building block），是描述位串子），是描述位串子集的相像性模板，表示基因串中某些特征位相同的集的相像性模板，表示基因串中某些特征位相同的结构。结构。定义定义1 模式：群体中编码的某些位置具有相像结构模式：群体中编码的某些位置具有相像结构的染色体集合。的染色体集合。如：染色体的编码是由如：染色体的编码是由0或者或者1组成的二进制序列，组成的二进制序列，模式模式01*0表示以表示以01开头且以开头且以0结尾的编码串对应的结尾的编码串对应的染色体的集合。染色体的集合。4.1.1 基本基本原理原理模式定理模式定理模式举例模式举例模式*10101110 与以下两个字符串匹配：010101110 110101110而模式 *1010110 与以下四个字符串匹配：010100110 010101110 110100110 1101011104.1.1 基本基本原理原理定义定义2 一个模式的阶是出现在模式中的一个模式的阶是出现在模式中的“0”和和“1”的数的数目，记为目，记为o(s)。即具有确定取值的基因个数。即具有确定取值的基因个数。如：模式如：模式“0*”的阶为的阶为1，模式，模式“10*1*”的阶为的阶为3。定义定义3 一个模式的长度是出现在模式中第一个确定位置和一个模式的长度是出现在模式中第一个确定位置和最终一个确定位置之间的距离，记为最终一个确定位置之间的距离，记为 。如：模式如：模式“01*”的长度为的长度为1，模式，模式“0*1”的长度为的长度为4。遗传算法的实质是通过选择、交叉、变异对模式进行搜寻，遗传算法的实质是通过选择、交叉、变异对模式进行搜寻，低阶、定义长度较小且平均适应值高于群体平均适应值的模低阶、定义长度较小且平均适应值高于群体平均适应值的模式在群体中的比例将呈指数级增长，即随着进化的不断进行，式在群体中的比例将呈指数级增长，即随着进化的不断进行，较优染色体的个数将快速增加。较优染色体的个数将快速增加。模式定理证明白遗传算法寻求最优解的可能性。但不能保证模式定理证明白遗传算法寻求最优解的可能性。但不能保证算法确定找到全局最优。算法确定找到全局最优。4.1.1 基本基本原理原理2、积木块假设：指低阶、定义长度较小且平均、积木块假设：指低阶、定义长度较小且平均适应度值高于群体平均适应值的模式。适应度值高于群体平均适应值的模式。积木块假设认为在遗传算法运行过程中，积木块积木块假设认为在遗传算法运行过程中，积木块在遗传算子的影响下能相互结合，产生新的更加在遗传算子的影响下能相互结合，产生新的更加优秀的积木块，最终接近全局最优解。优秀的积木块，最终接近全局最优解。积木块假设对模式定理作了补充，说明遗传算法具有积木块假设对模式定理作了补充，说明遗传算法具有能够找到全局最优解的实力。能够找到全局最优解的实力。目前的探讨还不能对积木块假设是否成立给出一个严目前的探讨还不能对积木块假设是否成立给出一个严整的论断和证明，但大量的试验和应用为积木块假设整的论断和证明，但大量的试验和应用为积木块假设供应了支持。供应了支持。4.1.1 基本基本原理原理4.1.2 探讨进展探讨进展GA 探讨内容与方向探讨内容与方向 算法性能算法性能算法性能算法性能研究研究研究研究混合算法混合算法混合算法混合算法研究研究研究研究并行算法并行算法并行算法并行算法研究研究研究研究算法应用算法应用算法应用算法应用研究研究研究研究与与GA相关的重要学术期刊与国际会议相关的重要学术期刊与国际会议重要学术期刊重要学术期刊lEvolutionary ComputationlIEEE Transactions on Evolutionary Computationl重要国际会议重要国际会议lInternational Conference on Genetic AlgorithmlACM Genetic and Evolutionary Computation ConferencelWorkshop on Foundations of Genetic Algorithms and Classifier SystemslGenetic Programming ConferencelInternational Workshop on Artificial Lifel 4.1.3 基本思想基本思想潜在解集内选择一组可能解集潜在解集内选择一组可能解集确定数目的经过基因编码的个体所组成确定数目的经过基因编码的个体所组成产生初代种群产生初代种群优胜劣汰、适者生存优胜劣汰、适者生存经过解码得到近似最优解经过解码得到近似最优解4.1.4 基本流程基本流程4.2 遗传算法的流程遗传算法的流程流程结构流程结构l染色体编码染色体编码l群体初始化群体初始化l适应值评价适应值评价l选择算子选择算子l交配算子交配算子l变异算子变异算子l算法流程图和伪代码算法流程图和伪代码应用举例应用举例l函数优化问题函数优化问题l算法的执行步骤示意图算法的执行步骤示意图基本遗传算法基本遗传算法(Simple Genetic Algorithm:SGA)又又称为简洁遗传算法，只运用选择算子、交叉算子和称为简洁遗传算法，只运用选择算子、交叉算子和变异算子这三种基本的遗传算子。变异算子这三种基本的遗传算子。染色体编码方法：首先必需对问题的解空间进行编染色体编码方法：首先必需对问题的解空间进行编码，使之能用遗传算法进行操作。较常用的是二进码，使之能用遗传算法进行操作。较常用的是二进制编码方法，现在运用非二进制编码的也渐渐增多。制编码方法，现在运用非二进制编码的也渐渐增多。基本基本遗传遗传算法的构成要素算法的构成要素染色体编码染色体编码二进制编码方法（二进制编码方法（Binary Representation）浮点数编码方法（浮点数编码方法（Float Point Representation）0000000011111111一般状况下，遗传算法在群体初始化阶段接受的一般状况下，遗传算法在群体初始化阶段接受的是随机数初始化方法。接受生成随机数的方法，是随机数初始化方法。接受生成随机数的方法，对染色体的每一维变量进行初始化赋值。初始化对染色体的每一维变量进行初始化赋值。初始化染色体时必需留意染色体是否满足优化问题对有染色体时必需留意染色体是否满足优化问题对有效解的定义。效解的定义。假如在进化起先时保证初始群体已经是确定程度假如在进化起先时保证初始群体已经是确定程度上的优良群体的话，将能够有效提高算法找到全上的优良群体的话，将能够有效提高算法找到全局最优解的实力。局最优解的实力。群体初始化群体初始化评估函数用于评估各个染色体的适应值，进而区评估函数用于评估各个染色体的适应值，进而区分优劣。评估函数常常依据问题的优化目标来确分优劣。评估函数常常依据问题的优化目标来确定，比如在求解函数优化问题时，问题定义的目定，比如在求解函数优化问题时，问题定义的目标函数可以作为评估函数的原型。标函数可以作为评估函数的原型。在遗传算法中，规定适应值越大的染色体越优。在遗传算法中，规定适应值越大的染色体越优。因此对于一些求解最大值的数值优化问题，我们因此对于一些求解最大值的数值优化问题，我们可以干脆套用问题定义的函数表达式。但是对于可以干脆套用问题定义的函数表达式。但是对于其他优化问题，问题定义的目标函数表达式必需其他优化问题，问题定义的目标函数表达式必需经过确定的变换。经过确定的变换。适应值评价适应值评价选择选择算子算子轮盘赌选择算法轮盘赌选择算法fi为个体的适应度；为个体的适应度；fsum为种群的总适应度；为种群的总适应度；pi为个体为个体i的选的选择概率。择概率。轮盘选择的具体描述过程轮盘选择的具体描述过程依次累计群体内各个体的适应度，得相应的累计依次累计群体内各个体的适应度，得相应的累计值值 ，设群体有，设群体有n个个体，最终一个累个个体，最终一个累计值为计值为Sn。在在0，Sn 区间内产生匀整分布的随机数区间内产生匀整分布的随机数r。依次用依次用 Si 与与 r比较，第一个出现大于或等于比较，第一个出现大于或等于r的的Si所对应的个体所对应的个体i被选为复制对象。被选为复制对象。重复其次步和第三步，直到满足所须要的复制个重复其次步和第三步，直到满足所须要的复制个体数目。体数目。交配算子交配算子在染色体交配阶段，每个染色体能否进行交配由交配概在染色体交配阶段，每个染色体能否进行交配由交配概率率PcPc（一般取值为（一般取值为0.40.4到到0.990.99之间）确定，其具体过程为：之间）确定，其具体过程为：对于每个染色体，假如对于每个染色体，假如Random(0,1)Random(0,1)小于小于PcPc则表示该染色则表示该染色体可进行交配操作（其中体可进行交配操作（其中Random(0,1)Random(0,1)为为0,10,1间匀整分布间匀整分布的随机数），否则染色体不参与交配干脆复制到新种群的随机数），否则染色体不参与交配干脆复制到新种群中。中。每两个依据每两个依据PcPc交配概率选择出来的染色体进行交配，经交配概率选择出来的染色体进行交配，经过交换各自的部分基因，产生两个新的子代染色体。具过交换各自的部分基因，产生两个新的子代染色体。具体操作是随机产生一个有效的交配位置，染色体交换位体操作是随机产生一个有效的交配位置，染色体交换位于该交配位置后的全部基因。于该交配位置后的全部基因。交配算子交配算子单点交叉单点交叉双点交叉双点交叉子代子代1：01|000|00110子代子代2：11|101|10100父代父代1：01|101|00110父代父代2：11|000|10100交叉点交叉点1双点交叉双点交叉交叉点交叉点2染色体的变异作用于基因之上，对于交配后新种群中染染色体的变异作用于基因之上，对于交配后新种群中染色体的每一位基因，依据变异概率色体的每一位基因，依据变异概率PmPm推断该基因是否进推断该基因是否进行变异。行变异。假如假如Random(0,1)Random(0,1)小于小于PmPm，则变更该基因的取值（其中，则变更该基因的取值（其中Random(0,1)Random(0,1)为为0,10,1间匀整分布的随机数）。否则该基因间匀整分布的随机数）。否则该基因不发生变异，保持不变。不发生变异，保持不变。变异算子变异算子4、运行参数、运行参数N：群体大小，即群体中包含的个体的数量。群体大小，即群体中包含的个体的数量。T：遗传算法终止的进化代数。遗传算法终止的进化代数。Pc：交叉概率，一般取为交叉概率，一般取为 0.40.99。Pm：变异概率，一般取为变异概率，一般取为 0.00010.1。遗传算法流程图和伪代码遗传算法流程图和伪代码问题的求解问题的求解-群体爬山群体爬山进化算法的求解问题过程进化算法的求解问题过程是一个不断爬山的过程是一个不断爬山的过程爬山的模拟爬山的模拟 xyfitnessminmaxsearch space随机地生成初始解随机地生成初始解爬山的模拟爬山的模拟 xysearch space不断地通过交叉变不断地通过交叉变异以及选择来达到异以及选择来达到爬山的效果爬山的效果fitnessminmax爬山的模拟爬山的模拟xysearch space不断地通过交叉变不断地通过交叉变异以及选择来达到异以及选择来达到爬山的效果爬山的效果fitnessminmax爬山的模拟爬山的模拟xysearch space不断地通过交叉变不断地通过交叉变异以及选择来达到异以及选择来达到爬山的效果爬山的效果fitnessminmax爬山的模拟爬山的模拟xysearch space不断地通过交叉变不断地通过交叉变异以及选择来达到异以及选择来达到爬山的效果爬山的效果fitnessminmax爬山的模拟爬山的模拟xysearch space不断地通过交叉变不断地通过交叉变异以及选择来达到异以及选择来达到爬山的效果爬山的效果fitnessminmax爬山的模拟爬山的模拟xysearch space不断地通过交叉变不断地通过交叉变异以及选择来达到异以及选择来达到爬山的效果爬山的效果fitnessminmax爬山的模拟爬山的模拟xysearch space最终达到最优最终达到最优fitnessminmax4.2.2 应用举例应用举例例4.1已知函数 ，其中 ，用遗传算法求解y的 最大值。运行步骤运行步骤算子选择算子选择参数设置参数设置动态策略和自适应策略动态策略和自适应策略混合遗传算法混合遗传算法并行遗传算法并行遗传算法4.3 遗传算法的改进遗传算法的改进 尽管尽管遗传遗传算法有很多算法有很多优优点，但目前存在的点，但目前存在的问题问题照照旧很多，如早熟旧很多，如早熟现现象，在接近最象，在接近最优优解解时时收收敛较敛较慢慢等。等。很多很多专专家学者家学者进进行不断探行不断探讨讨，致力于推，致力于推动遗传动遗传算算法的法的发发展，展，对编码对编码方式、限制参数的确定、方式、限制参数的确定、选择选择和交叉方式和交叉方式进进行了深化探行了深化探讨讨，引入了，引入了动态动态策略和策略和自适自适应应策略来改善策略来改善遗传遗传算法的性能，提出了各种算法的性能，提出了各种变变形的形的遗传遗传算法（算法（Variants of Canonical Genetic Algorithms，简简称称VCGA）。）。4.3 遗传算法的改进遗传算法的改进 确定性采样确定性采样排挤模型排挤模型最佳个体保存模型最佳个体保存模型4.3.1 算子选择算子选择适应值比例模型适应值比例模型排序模型排序模型随机锦标赛模型随机锦标赛模型无回放余数随机采样无回放余数随机采样期望值模型期望值模型选择算子选择算子选择算子选择算子交配算子交配算子交配算子交配算子单性孢子交配算子单性孢子交配算子边重组交配算子边重组交配算子循环交配算子循环交配算子顺序交配算子顺序交配算子部分匹配交配算子部分匹配交配算子多点交配算子多点交配算子算术交配算子算术交配算子均匀交配算子均匀交配算子两点交配算子两点交配算子边集合交配算子边集合交配算子变异算子变异算子变异算子变异算子非均匀变异算子非均匀变异算子高斯变异算子高斯变异算子边界变异算子边界变异算子群体规模群体规模N 染色体长度染色体长度L 影响算法的搜寻实力和运行效率。影响算法的搜寻实力和运行效率。若若N N设置较大，一次进化所覆盖的模式较多，可以保证设置较大，一次进化所覆盖的模式较多，可以保证群体的多样性，从而提高算法的搜寻实力，但是由于群群体的多样性，从而提高算法的搜寻实力，但是由于群体中染色体的个数较多，势必增加算法的计算量，降低体中染色体的个数较多，势必增加算法的计算量，降低了算法的运行效率。了算法的运行效率。若若N N设置较小，虽然降低了计算量，但是同时降低了每设置较小，虽然降低了计算量，但是同时降低了每次进化中群体包含更多较好染色体的实力。次进化中群体包含更多较好染色体的实力。N N的设置一般为的设置一般为2010020100。影响算法的计算量和交配变异操作的效果。影响算法的计算量和交配变异操作的效果。L L的设置跟优化问题亲密相关，一般由问题定义的解的的设置跟优化问题亲密相关，一般由问题定义的解的形式和选择的编码方法确定。形式和选择的编码方法确定。对于二进制编码方法，染色体的长度对于二进制编码方法，染色体的长度L L依据解的取值范依据解的取值范围和规定精度要求选择大小。围和规定精度要求选择大小。对于浮点数编码方法，染色体的长度对于浮点数编码方法，染色体的长度L L 跟问题定义的解跟问题定义的解的维数的维数D D相同。相同。除了染色体长度确定的编码方法，除了染色体长度确定的编码方法，GoldbergGoldberg等人还提出等人还提出了一种变长度染色体遗传算法了一种变长度染色体遗传算法Messy GAMessy GA，其染色体的长，其染色体的长度并不是固定的。度并不是固定的。4.3.2 参数设置参数设置交配概率交配概率Pc 变异概率变异概率Pm 确定了进化过程种群参与交配的染色体平均数目。确定了进化过程种群参与交配的染色体平均数目。取值一般为取值一般为0.40.4至至0.990.99。也可接受自适应方法调整算法运行过程中的交配概率。也可接受自适应方法调整算法运行过程中的交配概率。增加群体进化的多样性，确定了进化过程中群体发生变增加群体进化的多样性，确定了进化过程中群体发生变异的基因平均个数。异的基因平均个数。PmPm的值不宜过大。因为变异对已找到的较优解具有确定的值不宜过大。因为变异对已找到的较优解具有确定的破坏作用，假如的破坏作用，假如PmPm的值太大，可能会导致算法目前处的值太大，可能会导致算法目前处于的较好的搜寻状态倒退回原来较差的状况。于的较好的搜寻状态倒退回原来较差的状况。PmPm的取值一般为的取值一般为0.0010.001至至0.10.1之间。之间。也可接受自适应方法调整算法运行过程中的也可接受自适应方法调整算法运行过程中的PmPm值。值。R R视接受的染色体编码方案而定。视接受的染色体编码方案而定。对于二进制编码方法，对于二进制编码方法，R=0,1R=0,1，而对于浮点数编码方法，而对于浮点数编码方法，R R与优化问题定义的解每一维变量的取值范围相同。与优化问题定义的解每一维变量的取值范围相同。基因取值基因取值范围范围R 4.3.2 参数设置参数设置终止条件终止条件确定算法何时停止运行，输出找到的最优解，接受何种确定算法何时停止运行，输出找到的最优解，接受何种终止条件，跟具体问题的应用有关。终止条件，跟具体问题的应用有关。可以使算法在达到最大进化代数时停止，最大进化代数可以使算法在达到最大进化代数时停止，最大进化代数一般可设置为一般可设置为10010001001000，依据具体问题可对该建议值作，依据具体问题可对该建议值作相应的修改。相应的修改。也可以通过考察找到的当前最优解是否达到误差要求来也可以通过考察找到的当前最优解是否达到误差要求来限制算法的停止。限制算法的停止。或者是算法在持续很长的一段进化时间内所找到的最优或者是算法在持续很长的一段进化时间内所找到的最优解没有得到改善时，算法可以停止。解没有得到改善时，算法可以停止。适应值评价适应值评价影响算法对种群的选择，恰当的评估函数应当能够对染影响算法对种群的选择，恰当的评估函数应当能够对染色体的优劣做出合适的区分，保证选择机制的有效性，色体的优劣做出合适的区分，保证选择机制的有效性，从而提高群体的进化实力。从而提高群体的进化实力。评估函数的设置同优化问题的求解目标有关。评估函数的设置同优化问题的求解目标有关。评估函数应满足较优染色体的适应值较大的规定。评估函数应满足较优染色体的适应值较大的规定。为了更好地提高选择的效能，可以对评估函数做出确定为了更好地提高选择的效能，可以对评估函数做出确定的修正。的修正。目前主要的评估函数修正方法有：线性变换；乘幂变换；目前主要的评估函数修正方法有：线性变换；乘幂变换；指数变换等。指数变换等。4.3.2 参数设置参数设置1、最、最优优保存策略保存策略找出当前群体中适找出当前群体中适应应度最高的个体和适度最高的个体和适应应度最低的个体度最低的个体若当前群体中最佳个体的适若当前群体中最佳个体的适应应度比度比总总的迄今的迄今为为止的最好止的最好个体的适个体的适应应度度还还要高，要高，则则以当前群体中最佳个体作以当前群体中最佳个体作为为新的新的迄今迄今为为止的最好个体。止的最好个体。用迄今用迄今为为止的最好个体替止的最好个体替换换掉当前群体中的最差个体。掉当前群体中的最差个体。最最优优保存策略可保保存策略可保证证迄今迄今为为止所得到的最止所得到的最优优个体不被交叉、个体不被交叉、变变异等操作所破坏，是异等操作所破坏，是遗传遗传算法收算法收敛敛性的一个重要保性的一个重要保证证条条件。件。简洁简洁使某个局部最使某个局部最优优个体不易被淘汰掉反而快速个体不易被淘汰掉反而快速扩扩散，从散，从而使算法的全局搜而使算法的全局搜寻实寻实力下降。力下降。该该方法要与其它一些方法要与其它一些选择选择操作方法操作方法协协作起来运用才有良好作起来运用才有良好效果。效果。4.3.3 动态策略和自适应策略动态策略和自适应策略2、自适、自适应遗传应遗传算法算法自适自适应遗传应遗传算法（算法（Adaptive GA，AGA）的交叉概率和）的交叉概率和变变异概率能随适异概率能随适应应度自度自动变动变更。更。当种群各个体适当种群各个体适应应度度趋趋于一于一样样或或趋趋于局部最于局部最优时优时，使交叉，使交叉概率和概率和变变异概率增加，而当群体适异概率增加，而当群体适应应度比度比较较分散分散时时，使交，使交叉概率和叉概率和变变异概率削减。同异概率削减。同时对时对于适于适应值应值高于群体平均适高于群体平均适应值应值的个体，的个体，对应对应于于较较低的交叉概率和低的交叉概率和变变异概率，使异概率，使该该解解得以得以爱护进爱护进入下一代；而低于平均适入下一代；而低于平均适应值应值的个体，的个体，对应对应于于较较高的交叉概率和高的交叉概率和变变异概率，使异概率，使该该解被淘汰掉。解被淘汰掉。4.3.3 动态策略和自适应策略动态策略和自适应策略2、自适自适应遗传应遗传算法算法4.3.3 动态策略和自适应策略动态策略和自适应策略3、小生境、小生境遗传遗传算法算法遗传遗传算法中模算法中模拟拟小生境的方法主要有：小生境的方法主要有：（1）基于）基于预选择预选择（Preselection）的小生境）的小生境实现实现方法方法Cavicchio于于1970年提出年提出该该方法，其基本思想：方法，其基本思想：仅仅当新当新产产生的子代个体的适生的子代个体的适应应度超度超过过其父代个体的适其父代个体的适应应度度时时，所，所产产生出的子代个体才能替生出的子代个体才能替换换其父代个体而其父代个体而遗传遗传到下一代到下一代群体中，否群体中，否则则父代个体仍保留到下一代群体中。父代个体仍保留到下一代群体中。这这种方种方法事法事实实上只替上只替换换掉了一些掉了一些编码结编码结构相像的个体，故能有构相像的个体，故能有效效维维持群体的多持群体的多样样性。性。4.3.3 动态策略和自适应策略动态策略和自适应策略3、小生境、小生境遗传遗传算法算法（2）基于排）基于排挤挤（Crowding）的小生境）的小生境实现实现方法方法De Jong于于1975年提出年提出该实现该实现方法。排方法。排挤挤的思想源于在一的思想源于在一个有限的生存空个有限的生存空间间中，各种不同的生物中，各种不同的生物为为了能持了能持续续生存，生存，必需相互必需相互竞竞争各种有限的生存争各种有限的生存资资源。其基本思想是：源。其基本思想是：设设置一排置一排挤挤因子因子CF，由群体中随机，由群体中随机选选取的取的1/CF个个体个个体组组成排成排挤挤成成员员，然后依据新，然后依据新产产生的个体与排生的个体与排挤挤成成员员的相像的相像性来排性来排挤挤掉一些与排掉一些与排挤挤成成员员相相类类似的个体。似的个体。这这里，个体里，个体之之间间的相像性可用个体的相像性可用个体编码编码串之串之间间的海明距离来度量。的海明距离来度量。随着排随着排挤过挤过程的程的进进行，群体中的个体行，群体中的个体渐渐渐渐被分被分类类，从而，从而形成各个小的生存坏境，并形成各个小的生存坏境，并维维持了群体的多持了群体的多样样性。性。4.3.3 动态策略和自适应策略动态策略和自适应策略4、遗传遗传-灭变灭变算法算法即在即在遗传遗传算法的基算法的基础础上，模上，模拟拟自然界的自然界的灭变现灭变现象，当推象，当推断断连续连续数代最佳个体没有任何数代最佳个体没有任何进进化，或者各个体已化，或者各个体已过过于于近似近似时时，即可，即可实实施施灭变灭变。灭变灭变方法很多，可以突然增大方法很多，可以突然增大变变异概率或异概率或对对不同个体不同个体实实施不同施不同规规模的突模的突变变，以，以产产生不生不同数目的大量后代等。用同数目的大量后代等。用灭变灭变方法可以打破原有的基因方法可以打破原有的基因的的垄垄断断优势优势，增加基因的多，增加基因的多样样性，性，创创建有生命力的新个建有生命力的新个体。体。4.3.3 动态策略和自适应策略动态策略和自适应策略4.3.4 混合遗传算法混合遗传算法爬山法爬山法模拟退火算法模拟退火算法最速下降法最速下降法其它其它局部搜寻算法局部搜寻算法遗传算法遗传算法4.3.4 混合遗传算法混合遗传算法并行组合模拟退火算法并行组合模拟退火算法并行模拟退火遗传算法并行模拟退火遗传算法贪欲遗传算法贪欲遗传算法遗传比率切割算法遗传比率切割算法遗传爬山法遗传爬山法引入局部改善操作的混合遗传算法引入局部改善操作的混合遗传算法免疫遗传算法免疫遗传算法并行计算并行计算单指令流多数据流计算机单指令流多数据流计算机多指令流多数据流计算机多指令流多数据流计算机并行计算网络并行计算网络串行计算串行计算单指令流单数据流处理器单指令流单数据流处理器4.3.5 并行遗传算法并行遗传算法并行遗传算法并行遗传算法标准型并行方法标准型并行方法分解型并行方法分解型并行方法标准型并行方法标准型并行方法分解型并行方法分解型并行方法子群体进化信息交换问题子群体进化信息交换问题分解型并行方法分解型并行方法u交换的时间交换的时间 u交换的方式交换的方式 u交换的内容交换的内容 典型的并行遗传算法的群体模型典型的并行遗传算法的群体模型u岛屿模型岛屿模型 u踏脚石模型踏脚石模型 u邻居模型邻居模型 图像处理和模式识别图像处理和模式识别优化与调度优化与调度机器学习机器学习智能限制智能限制其它其它人工生命人工生命自动程序设计自动程序设计应用应用4.4 遗传算法的应用遗传算法的应用