第九章 基因算法.ppt

《第九章 基因算法.ppt》由会员分享，可在线阅读，更多相关《第九章 基因算法.ppt（75页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第九章第九章 基因算法基因算法一、概述一、概述一、概述一、概述AnEAisaniterativeprocedurewhichevolvesapopulationofindividualsEachindividualisacandidatesolutiontoagivenproblemEachindividualisevaluatedbyafitness function,whichmeasuresthequalityofitscandidatesolutionAteachiteration(generation):ThebestindividualsareselectedGeneticoper

2、atorsareappliedtoselectedindividualsinordertoproducenewindividuals(offspring)NewindividualsareevaluatedbyfitnessfunctionBasicIdeasofEvolutionaryAlgorithms(EAs)BasicFlowChartofEAscreateinitialpopulationcomputefitnessselectbestindividuals(basedonfitness)modifybestindividuals,producingoffspringcomputef

3、itnessofoffspringNstop?YReturnbestindividual(solution)一、概述一、概述What is evolution?Evolutionisagradualprocessofchangeinthegeneticcompositionofapopulation,asaresultofnaturalselectionactingongeneticvariationamongindividualsBasic Elements of an Evolutionary Process:ReproductionwithinheritanceGeneticvariat

4、ion(usuallyproducedbyrandommodifications)Naturalselection(survivalofthefittest)Evolutionary Biology一、概述一、概述 遗传学遗传学 GA 染色体（染色体（Chromosome）数据、数组、位串数据、数组、位串 基因（基因（gene）位位 等位基因（等位基因（allele）特性值特性值 基因座（基因座（locus）串中位置串中位置 基因型（基因型（genotype）解结构（基因空间）解结构（基因空间）表现型（表现型（phenotype）解结构（问题空间）解结构（问题空间）遗传算法是模拟遗传选择，优胜

5、劣汰，适者生存的生物进化过程的计算模型。它是由美国Michigan 大学的J.Holland教授于1975年首先提出的。遗传和变异是决定生物进化的内在因素。生物体通过对基因的复制和交叉的操作使其性状的遗传得到选择和控制，使生物界的物种能够保持相对的稳定；同时，通过基因组合、基因变异等操作产生丰富多样的新性状，新物种，推动了生物的进化和发展。GA是一种新的全局优化随机搜索算法。GA搜索不依赖梯度信息，简单通用、鲁棒性强，适合并行分布处理，应用范围广，尤其适用于解决传统方法难以解决的复杂和非线性问题。二、遗传算法二、遗传算法初始群体评估每个个体选择交叉结束是否优解？开始解编码评估函数遗传操作标准的

6、遗传算法标准的遗传算法是具有是具有“生成生成 +检测检测（generate-and-testgenerate-and-test）迭代过程的搜索算法。迭代过程的搜索算法。遗传算法通过遗传算法通过迭代进化，迭代进化，从一群初始解找到所期望从一群初始解找到所期望的解的解新群体变异遗传算法（遗传算法（SGA）l 爬山法或梯度法仅能到达爬山法或梯度法仅能到达局部最优解局部最优解GA versus“Traditional”search/optimization algorithmsl模拟退火算法允许以一定模拟退火算法允许以一定的概率降低到较小的适应的概率降低到较小的适应度，从而获得越过低谷，度，从而获得越

7、过低谷，爬上全局高峰的机会爬上全局高峰的机会二、遗传算法二、遗传算法l GAGA或或EAsEAs 是一种多点并行分布式全局优化搜索算法是一种多点并行分布式全局优化搜索算法二、遗传算法二、遗传算法 多点并行搜索多点并行搜索 基本上不用搜索空间的知识，仅用适应度函数来评估。适应度函数不受基本上不用搜索空间的知识，仅用适应度函数来评估。适应度函数不受 连续可谓的约束，对定义域可以任意设置。对适应函数唯一要求是输出连续可谓的约束，对定义域可以任意设置。对适应函数唯一要求是输出 为正，以便比较。为正，以便比较。GA GA不是直接处理问题参数，而是对参数集进行编码后进行处理。为此，不是直接处理问题参数，而

8、是对参数集进行编码后进行处理。为此，GA GA可直接对结构对象进行操作。如集合、序、列、矩阵、树、图、链和可直接对结构对象进行操作。如集合、序、列、矩阵、树、图、链和 表等一维或二维甚至三维结构对象，扩大了应用范围。表等一维或二维甚至三维结构对象，扩大了应用范围。通过对权矩阵的操作，通过对权矩阵的操作，GAGA可以对可以对NNNN的权甚至结构进行优化。的权甚至结构进行优化。通过对集合的操作，通过对集合的操作，GAGA可以实现规则集或知识库的自适应优化可以实现规则集或知识库的自适应优化通过对树的操作，通过对树的操作，GAGA可得到用于分类的最佳决策树。可得到用于分类的最佳决策树。GA GA不是采

9、用确定规则，而是采用概率的搜索规则。但是，不是采用确定规则，而是采用概率的搜索规则。但是，GAGA不是一种盲不是一种盲 目搜索方法，而是有明确的搜索方向。目搜索方法，而是有明确的搜索方向。增量式进化增量式进化遗传算法的特点遗传算法的特点二、遗传算法二、遗传算法尤其当：其他各种方法太慢或过于复杂求解的问题类似于GA已成功应用的问题搜索空间太大且包含相当多的局部解多目标优化变化环境或噪声环境GA应用：应用：二、遗传算法二、遗传算法三、SGAEncodingtechnique(gene,chromosome)Initializationprocedure(creation)Evaluationfun

10、ction(environment)Selectionofparents(reproduction)Geneticoperators(mutation,crossover)Parametersettings(practice and art)SGA中的关键要素13三、SGASGASGA采用二进制编码，这是最简单也较常用的个体表示采用二进制编码，这是最简单也较常用的个体表示方法方法Chromosomescouldbe:Bitstrings(0101.1100)Realnumbers(43.2-33.1.0.089.2)Permutationsofelement(E11E3E7.E1E15)Lis

11、tsofrules(R1R2R3.R22R23)Programelements(geneticprogramming).anydatastructure.nRepresentation（encoding）三、SGAEvaluationEvaluatedgenerationgenerationnEvaluation：GAGA基本上不用外部信息，仅用适应度函数来评估每个个体。基本上不用外部信息，仅用适应度函数来评估每个个体。评估时需要评估时需要decodingdecoding，即把，即把genotypegenotype解转换为解转换为phenotypephenotype解，以便利用评估函数或适应函

12、数。解，以便利用评估函数或适应函数。X(=39)Coding and decoding解（个体）在问题空间和遗传空间的转换，即解（个体）在问题空间和遗传空间的转换，即phenotypephenotype 解和解和genotypegenotype解之间的转换解之间的转换。三、SGA利用赌轮（roulette wheel）法fitnessproportionateexpectedno.ofrepresentativesofeachindividualisproportionaltoitsfitnessn选择（Selection）三、SGAf1f2f3f4f5f6f7n=7roulette whee

13、l三、SGA根据概率的大小将将圆盘分为 n个扇形，每个扇形的大小为选择时转动轮盘，参考点r落到扇形i则选择个体i。从一对父辈产生一对子辈单点交叉交叉概率pctypicallyinrange0.5,1.0Crossover是GA最本质的遗传算子:在进化中，能加速搜索能形成schemata的有效组合(subsolutionsondifferentchromosomes)nCrossover(recombination)三、SGAOne-Point Cross-Over三、SGAparentsChildrenbitwisemutationprobabilityofmutation:pmequalpr

14、obabilityforeachgene/bittypicallychosentobesmallrang:0.001,0.1fewmutationsperindividualdependsonnatureofproblemnMutation三、SGABefore:(11110110)After:(11100110)Before:(1.38-69.4326.440.1)After:(1.38-67.5326.440.1)三、SGAExamples:三、SGArepresentation eachchromosomecontain8”genes”,codingforlettersfitness-f

15、unctionfitnessbethenumberofcorrectletters example2：problem:correctly spelling“SEQUENCE”with GACrossoverandmutation三、SGATypically,the populations average fitness will initially increase rapidly,and then gradually converge四、四、GA的理论概述的理论概述 模式模式(schema)(schema)基于字符集基于字符集0,1,0,1,*所产生的能描述具有某些结构所产生的能描述具有某些

16、结构相似性的相似性的0 0，1 1字符串字符串 例：模式例：模式H 0*1 H 0*1 描述了具有相似结构的四个个体描述了具有相似结构的四个个体 0 000001 1，0 001011 1，0 011111 1，0 010101 1显然，一个个体可有包含多个模式，一个模式可显然，一个个体可有包含多个模式，一个模式可 以存在于多个个体中，以存在于多个个体中，如果说最优个体（解）对应一个明确的字符串或模如果说最优个体（解）对应一个明确的字符串或模式，那么遗传算子作用就是使群体中的个体模式不式，那么遗传算子作用就是使群体中的个体模式不断地向优解逼近。断地向优解逼近。模式阶模式阶(schema ord

17、er)(schema order)模式模式H H中有确定值的基因座个数称为模式中有确定值的基因座个数称为模式H H的阶的阶 O(H)O(H)如：如：模式模式011*1*011*1*的阶数的阶数O(H)=4 O(H)=4 模式模式0*0*的阶数的阶数O(H)=1O(H)=1 显然，一个模式的阶数越低，其生存能力越强显然，一个模式的阶数越低，其生存能力越强 定义距定义距(defining length)(defining length)模式模式H H中第一个有确定值的基因座和最后一个有确定值中第一个有确定值的基因座和最后一个有确定值 的基因座之间的距离的基因座之间的距离(H)(H)如：如：模式模式

18、011*1*011*1*的定义距的定义距(H)=4 (H)=4 模式模式0*0*的的定义距定义距(H)=0(H)=0 显然，一个模式的阶数越低，其生存能力越强显然，一个模式的阶数越低，其生存能力越强四、四、GA的理论概述的理论概述遗传算子对模式的影响遗传算子对模式的影响 着眼某个模式着眼某个模式H H，考虑遗传操作（再生、交叉和变异），考虑遗传操作（再生、交叉和变异）对包含该模式的个体数的影响对包含该模式的个体数的影响再生（再生（reproduction)reproduction)或选择（或选择（selection)selection)设第设第k k代中，包含代中，包含H H的个体数为的个体数

19、为m(H,km(H,k););这些个体的这些个体的平均适应度为平均适应度为f(H,kf(H,k),),群体中所有个体的平均适应度群体中所有个体的平均适应度为为 ，则基于平均适应度选择法得到选择或再生，则基于平均适应度选择法得到选择或再生的个体数期望值为：的个体数期望值为：What will happen if only selection is used in GAs?四、四、GA的理论概述的理论概述交叉交叉(crossover)设交叉概率为 ，由于交叉使包含H的个体被破坏的概率为：交叉结果也会有未被破坏的包含H的个体保留下来。此外，交叉也 会生成包含相同H的新个体。为此，经交叉操作后包含H的

20、个体数期 望值为:变异变异(mutation)(mutation)设变异概率为 ，经变异操作后包含H的个体数的期望值为：The crossover and mutation can generate new and possibly better individuals,they can also destroy good individuals.Do you have any idea to avoid this problem?四、四、GA的理论概述的理论概述模式定理模式定理(schema theorem)(schema theorem)Short,loworder,aboveaverag

21、eschemataaremultipliedexponentiallyinsubsequentgenerationsofageneticalgorithmshort,loworderandaboveaverageschema(goodschemata)arecalledbuildingblocks.Buildingblockswillbemultipliedveryquicklyduringevolution.UsingGAs,wecanalwaysgetgoodindividualscontaininggoodbuildingblocks考虑到群体平均适应度的作用，此式不能递归使用考虑到群体

22、平均适应度的作用，此式不能递归使用未能说明优化未能说明优化仅适用于仅适用于SGASGA四、四、GA的理论概述的理论概述Bycrossover,weexchangetheblocksthatdefinegoodsolutions:SchemaTheorem:withtheevaluationofagenotypewealsoimplicitlyevaluateallitscomponentsaboutO(n3)(Hollands estimate)schemataprocessedsuccessfullyimplicitparallelismeventhoughateachgenerationc

23、omputationproportionaltosizeofthepopulation(O(n)isperformedoneofthemainreasonsforsuccessofGAs隐并行性（隐并行性（implicit parallelism）四、四、GA的理论概述的理论概述积木块假设积木块假设(building block hypothesis)(building block hypothesis)低阶、短距且平均适应度高的模块称谓积木块低阶、短距且平均适应度高的模块称谓积木块 积积木木块块在在遗遗传传操操作作下下相相互互组组合合能能逐逐步步形形成成高高阶阶、长长距距且且平平均均适适应应

24、度度高高的的模模块块，最最终终生生成成最最优优解解或准最优解或准最优解仅仅是假设，但对于初始群体的产生有参考价仅仅是假设，但对于初始群体的产生有参考价值。值。四、四、GA的理论概述的理论概述五、五、GA算法分析算法分析编码编码l遗传算法主要是通过遗传操作对群遗传算法主要是通过遗传操作对群体中具有某种结构形式的个体进行体中具有某种结构形式的个体进行重组处理，形成并优化积木块以逐重组处理，形成并优化积木块以逐渐逼近最优解。渐逼近最优解。l通过编码和译码操作，解在两个空通过编码和译码操作，解在两个空间转换间转换l编码策略和交叉策略是互为依存的。编码策略和交叉策略是互为依存的。恰当的设计编码和交叉方法

25、对于恰当的设计编码和交叉方法对于GAGA的有效运作是十分重要的的有效运作是十分重要的l积木块原则积木块原则：编码应易于生成与所编码应易于生成与所求问题相关的短距、低阶积木快求问题相关的短距、低阶积木快l最小字符集原则：最小字符集原则：编码应采用最小编码应采用最小字符集字符集GA空间遗传空间12c12c比较一下二值编码和非二值编码（在A-Z26个字符和1-66个数字组成的字符集上），仍然以求f=x最大值为例X值二进制码非二值码适应度132481901101110000100010011N Y I T16957664561 二进制码个体的相似性易于观测，每位可提供最多的二进制码个体的相似性易于观测

26、，每位可提供最多的模式数，这是最小字符集编码原则的优点，符合遗传操作模式数，这是最小字符集编码原则的优点，符合遗传操作的特点的特点五、五、GA算法分析算法分析编码编码五、五、GA算法分析算法分析编码编码 binarycoding 优点：优点：简单易行；符合最小字符集编码原则；模式定理仅对二进简单易行；符合最小字符集编码原则；模式定理仅对二进 制编码有效制编码有效 缺点：缺点：映射误差；不能直接反映所求问题的本身结构特征映射误差；不能直接反映所求问题的本身结构特征多参数映射编码多参数映射编码 在优化求解中常常会遇到多参数优化问题。在优化求解中常常会遇到多参数优化问题。可以把每个参数进行二进制编码

27、得到子串，再把子串连成一个完整可以把每个参数进行二进制编码得到子串，再把子串连成一个完整 的染色体，每个子串可有不同的串长度的染色体，每个子串可有不同的串长度l l 和参数范围和参数范围 注意离散化操作：注意离散化操作：注意映射的编码精度：注意映射的编码精度：Graycoding for binarycoding,Hammingdistancebetweenconsecutiveintegersmaybe1example:5bitbinaryrepresentation：14:0111015:0111116:10000Probabilityofchanging15into16byindepen

28、dentbitflips(mutation)isnotsameaschangingitinto14Graycodingsolvesproblem.example:3-bitGrayCode Integer 0 1 2 3 4 5 6 7 binary000001010011100101110111 gray000001011010110111101100(Hammingdistance1)二值编码：问题空间的相邻解在编码空间并不相邻不利于解的搜索格雷码：问题空间的相邻解在编码空间相邻有利于解的搜索五、五、GA算法分析算法分析编码编码 可变染色体长度编码可变染色体长度编码 自然界生物进化过程中，

29、越是高等生物其染色体越长，由此可自然界生物进化过程中，越是高等生物其染色体越长，由此可 见，染色体的长度是可变的。见，染色体的长度是可变的。GoldbergGoldberg提出的提出的mGA(Messy GA)mGA(Messy GA)的的 编码方法就融入了这种机制。编码方法就融入了这种机制。mGAmGA的遗传操作与的遗传操作与SGASGA思想一致，但方法不同。思想一致，但方法不同。mGAmGA在应用上很有在应用上很有 特色。特色。能直接反映所求问题的本身结构特征的二维或多维编能直接反映所求问题的本身结构特征的二维或多维编 码，树结构编码等码，树结构编码等 如图像恢复、神经网络进化和程序进化等

30、问题的求解如图像恢复、神经网络进化和程序进化等问题的求解 可以克服：个体的表示很难反映求解问题的结构或层次可以克服：个体的表示很难反映求解问题的结构或层次 需要特定的编码译码技术需要特定的编码译码技术 不易表示高层次知识及相应的学习系统不易表示高层次知识及相应的学习系统五、五、GA算法分析算法分析编码编码Binary-codedandReal-coded实数编码实数编码五、五、GA算法分析算法分析编码编码1.海明悬崖（Hammingcliffs）：相邻整数的二进制编码可能具有较大的Hamming距离.2.需要首先给出求解的精度以确定串长,并且很难在算法的执行的过程中进行调整,从而使算法缺乏微调

31、的功能,降低算法的效率.3.在求解高维优化问题时,二进制编码的将非常的长,从而使算法的效率降低.二进制编码的缺点五、五、GA算法分析算法分析编码编码1.实数编码是连续参数优化问题的直接的自然描述,不存在编码解码的过程.2.提高算法解的精度和运算速度,特别是在搜速空间较大时更为明显.3.避免编码中带来的附加问题,如海明悬崖(Hammingcliffs)等,便于和其他搜索技术结合.实数编码的优点五、五、GA算法分析算法分析编码编码五、五、GA算法分析算法分析群体设定群体设定编码设计后的任务是初始群体的设定，其关键问题是群体规模。其中编码设计后的任务是初始群体的设定，其关键问题是群体规模。其中要考虑

32、：要考虑：初始群体如何设定？多大规模？初始群体如何设定？多大规模？进化过程中各代的群体规模如何维持？进化过程中各代的群体规模如何维持？初始群体的设定初始群体的设定 GAGA中初始群体中的个体是随机产生的，也可以根据先验知识设定初中初始群体中的个体是随机产生的，也可以根据先验知识设定初始群体始群体 群体中个体的多样性群体中个体的多样性 模式定理告诉我们，若群体规模为模式定理告诉我们，若群体规模为M M，GAGA可操作的模式数为可操作的模式数为M,M,并在并在此基础上不断形成和优化积木块，直到最优解。此基础上不断形成和优化积木块，直到最优解。显然，显然，M M越大，越大，GAGA操作的模式越多，生

33、成有意义的积木块的机会越高。操作的模式越多，生成有意义的积木块的机会越高。换句话说，换句话说，群体规模越大，群体中个体的多样性越高，陷入局部解群体规模越大，群体中个体的多样性越高，陷入局部解的危险就越小的危险就越小 群体规模太大的弊病群体规模太大的弊病计算效率计算效率由于个体被选择的概率大多采用适应度比例选择法，当规模太大时，由于个体被选择的概率大多采用适应度比例选择法，当规模太大时，大多数个体会被淘汰，仅少量的高适应度个体生存下来，影响配对大多数个体会被淘汰，仅少量的高适应度个体生存下来，影响配对和交叉繁殖。和交叉繁殖。群体规模太小的弊病群体规模太小的弊病会使会使GAGA的搜索空间有限，引起

34、未成熟收敛的搜索空间有限，引起未成熟收敛(premature convergence)(premature convergence)结论：结论：规模设定是一个规模设定是一个tradeofftradeoff问题问题 可以证明，在二进制编码的前提下，为满足隐并行性，群体的个数可以证明，在二进制编码的前提下，为满足隐并行性，群体的个数只要设定为只要设定为 即可。这个数目很大，一般设定为几十即可。这个数目很大，一般设定为几十几百几百进化过程中，群体规模未必保持在相同规模，但一般情况下都保持进化过程中，群体规模未必保持在相同规模，但一般情况下都保持不变不变五、五、GA算法分析算法分析群体设定群体设定GA

35、基本上不用外部信息，仅用适应度函数基本上不用外部信息，仅用适应度函数作为依据作为依据GA的适应度函数不受连续可微的约束，且的适应度函数不受连续可微的约束，且定义域可为任意集合，唯一要求是定义域可为任意集合，唯一要求是可计算可计算出能加以比较的非负结果出能加以比较的非负结果。此特点使。此特点使GA应应用范围很广。用范围很广。具有相同编码的解应有相同的适应度具有相同编码的解应有相同的适应度需要译码后再进行适应度评估需要译码后再进行适应度评估五、五、GA算法分析算法分析适应度函数设计适应度函数设计 目标函数映射为适应度函数目标函数映射为适应度函数许多应用中，目标函数可直接作为适应度函数，但是，有些情

36、况下需许多应用中，目标函数可直接作为适应度函数，但是，有些情况下需将目标函数作变换，以得到适应度函数。将目标函数作变换，以得到适应度函数。最小化问题：最小化问题：将费用函数等最小化函数将费用函数等最小化函数g(x)g(x)转化为适应度函数转化为适应度函数其他情况 可以是一个合适的值，也可采用迄今为止进化过程中可以是一个合适的值，也可采用迄今为止进化过程中g(x)g(x)的最大值或当前群体中的最大值或当前群体中g(x)g(x)的最大值的最大值 最大化问题：最大化问题：将利润函数等最大化函数将利润函数等最大化函数u(x)u(x)转化为适应度函数转化为适应度函数其他情况 可以是合适的输入值，也可以是

37、当前一代或前可以是合适的输入值，也可以是当前一代或前K K代中代中u(x)u(x)的最小值的最小值 适应度函数标定适应度函数标定(scaling)(scaling)在应用在应用GAGA尤其用尤其用GAGA处理小规模群体时常常会出现一些处理小规模群体时常常会出现一些 不利于优化的现象和结果：不利于优化的现象和结果：l进化初期的未成熟收敛现象：基于比例选择策略，一进化初期的未成熟收敛现象：基于比例选择策略，一些异常个体竞争力太强而处于主宰地位些异常个体竞争力太强而处于主宰地位 解决办法：降低异常个体的竞争力，即适应度解决办法：降低异常个体的竞争力，即适应度l进化后期的随机漫游现象：群体的平均适应度

38、已接近进化后期的随机漫游现象：群体的平均适应度已接近最佳个体的适应度，此时，个体间竞争力减弱最佳个体的适应度，此时，个体间竞争力减弱 解决办法：提高个体间竞争力，即适应度解决办法：提高个体间竞争力，即适应度五、五、GA算法分析算法分析适应度函数设计适应度函数设计 线性标定：线性标定：设原适应度函数为设原适应度函数为f,f,标定后为标定后为f:f=af+b f:f=af+b 其中，其中，a,b a,b 设定要满足设定要满足：和为了控制原适应度最大的为了控制原适应度最大的个体可贡献子孙数。个体可贡献子孙数。通常取通常取为了保证在以后的选择处为了保证在以后的选择处理中平均每个个体可贡献理中平均每个个

39、体可贡献一个期待的子孙到下一代一个期待的子孙到下一代五、五、GA算法分析算法分析适应度函数设计适应度函数设计 A 正常线性定标B 出现负适应度地线性定标一些坏个体适应度远小于群体平均适应一些坏个体适应度远小于群体平均适应度和最大适应度，且度和最大适应度，且群体群体平均适应度又平均适应度又比较接近最大适应度时，为了拉开他比较接近最大适应度时，为了拉开他们，使低适应度经定标后变成负值们，使低适应度经定标后变成负值 截断截断(sigma truncation)(sigma truncation)消除负适应度：消除负适应度：是群体适应度的标准方差，每代要计算方差 1c3 幂定标幂定标(power la

40、w scaling)(power law scaling)较少使用，K与求解问题相关五、五、GA算法分析算法分析适应度函数设计适应度函数设计3.适应度函数与适应度函数与GA迭代停止条件迭代停止条件 当最优解的适应度值已知或准最优解的适应度下限可以确定时，当最优解的适应度值已知或准最优解的适应度下限可以确定时，可用作迭代停止条件可用作迭代停止条件 否则，若发现群体中个体的进化已趋于稳定，即发现一定比例的否则，若发现群体中个体的进化已趋于稳定，即发现一定比例的个体具有完全相同的适应度，则停止迭代个体具有完全相同的适应度，则停止迭代4.适应度函数与问题的约束条件适应度函数与问题的约束条件 GAGA仅

41、靠适应度来评估和引导搜索，不能明确表示约束条件。仅靠适应度来评估和引导搜索，不能明确表示约束条件。对策：适应度函数考虑惩罚或代价对策：适应度函数考虑惩罚或代价 约束优化问题约束优化问题 非约束问题非约束问题 此类问题还可在编码和遗传操作设计方面采取一定措施此类问题还可在编码和遗传操作设计方面采取一定措施五、五、GA算法分析算法分析适应度函数设计适应度函数设计六、六、GA算法分析算法分析选择操作选择操作遗传操作包括三个遗传算子：遗传操作包括三个遗传算子：选择；选择；交叉；交叉；变异变异都是随机化操作，但有别于一般的随机化操作，是有都是随机化操作，但有别于一般的随机化操作，是有向的随机操作对进化的

42、效果有很大影响向的随机操作对进化的效果有很大影响具体的方法或策略随具体问题的不同而不同，本质上具体的方法或策略随具体问题的不同而不同，本质上与问题的编码直接有关与问题的编码直接有关 选择算子选择算子 选择操作是建立在适应度评估基础上，目的是把好的选择操作是建立在适应度评估基础上，目的是把好的个体直接选择遗传到下一代或者通过配对交叉产生新个体直接选择遗传到下一代或者通过配对交叉产生新的个体再遗传到下一代的个体再遗传到下一代 选择选择(selection)(selection)又称为再生又称为再生(reproduction)(reproduction)选择概率选择概率 P Ps s五、五、GA算法

43、分析算法分析选择操作选择操作 fitness proportional method （适应度比例方法）（适应度比例方法）设群体大小为n，个体i的适应度为 ,则i被选择的概率为：最佳个体保存法最佳个体保存法(elitist model)(elitist model)Considerthebestindividualitselfasaschemawhichisgood,butlongandhighorder,andcanbedestroyedeasilybycrossoverandmutation.Thus,GAsmayneverbeabletofindthebestindividualElit

44、estrategycanbeusedtopreservethebestindividualobtaineduptonow 把群体中适应度最高的个体不参与配对交叉而直接复制到下一代。把群体中适应度最高的个体不参与配对交叉而直接复制到下一代。该方法使得某一代的最优解不被交叉和变异操作所破坏，但这也隐该方法使得某一代的最优解不被交叉和变异操作所破坏，但这也隐含了一个危机，即局部最优个体的遗传基因会急速增加而使进化可含了一个危机，即局部最优个体的遗传基因会急速增加而使进化可能陷于局部优解。因此该方法更适合单峰性质空间的搜索，而不是能陷于局部优解。因此该方法更适合单峰性质空间的搜索，而不是多峰性质空间的

45、搜索。多峰性质空间的搜索。为此，为此，该方法须与其他选择方法结合使用，以避免可能产生局部优该方法须与其他选择方法结合使用，以避免可能产生局部优解解五、五、GA算法分析算法分析选择操作选择操作linear rank selectionFindthefitnessSorttheindividualsaccordingtotheirfitnessProbabilityforsurvivalisalinearfunctionoftherank五、五、GA算法分析算法分析选择操作选择操作EExponential rank selectionFindthefitnessSorttheindividuals

46、accordingtotheirfitnessProbabilityforsurvivalisanexponentialfunctionoftherankIngeneral,rankselectionmightbebetterthanrouletteselectionItismoretimeconsumingbecausesortisused五、五、GA算法分析算法分析选择操作选择操作 Truncation selection(Truncation selection(截断选择）截断选择）FindthefitnessSorttheindividualsRemovebadindividualsF

47、illtheblankwithnewindividualsThisselectionmethodisgoodalthoughsimpleGoodindividualswillnotbeincreasedbyselectionaloneDiversitycanbekept五、五、GA算法分析算法分析选择操作选择操作 Tournament selection（联赛选择）（联赛选择）FindthefitnessChoosenindividualsniscalledthetournamentsize，usually,n=2or3Copythebestoneofthenindividualstothen

48、extgenerationRepeatthisforPopSizetimesTournamentselectiondoesnotneedsort五、五、GA算法分析算法分析选择操作选择操作五、五、GA算法分析算法分析交叉操作交叉操作生物进化过程中起核心作用的是生物遗传基因的替换重组生物进化过程中起核心作用的是生物遗传基因的替换重组（交叉），因此（交叉），因此交叉操作是遗传操作中的核心算子交叉操作是遗传操作中的核心算子 交叉算子的设计要点交叉算子的设计要点 交叉算子的设计一般与所求具体问题有关，但均须满足若干交叉算子的设计一般与所求具体问题有关，但均须满足若干设计要点设计要点:n任何交叉算子须保

49、证优秀个体的性状能得到遗传继承。任何交叉算子须保证优秀个体的性状能得到遗传继承。n要满足上述要求，交叉算子设计须与编码设计协调，即所谓要满足上述要求，交叉算子设计须与编码设计协调，即所谓编码编码-交叉设计交叉设计n对于占主流的二值编码而言，各种交叉算子都包含：对于占主流的二值编码而言，各种交叉算子都包含：从经选择形成的配对库从经选择形成的配对库(mating pool)(mating pool)中，随中，随机机配对个体，按预先设配对个体，按预先设定的交叉概率定的交叉概率 来决定是否对每对进行交叉操作来决定是否对每对进行交叉操作随机设定交叉点，对点前或点后的部分结构进行交换随机设定交叉点，对点前

50、或点后的部分结构进行交换 主要交叉算子主要交叉算子 一点交叉一点交叉个体个体A 1001|A 1001|111111-1001 1001000000 新个体新个体AA 个体个体B 0011|B 0011|000000-0011 0011111111 新个体新个体BB 二点交叉二点交叉 个体个体A 10A 10|110110|11-11-10 1001001011 11 新个体新个体AA 个体个体B 00B 00|010010|00-00-00 0011011000 00 新个体新个体BB 多点交叉多点交叉 前两种交叉的推广，不常采用，因为它更接近于前两种交叉的推广，不常采用，因为它更接近于 随