第4章-遗传算法.ppt

1、第四章遗传算法，Contents，算法简介，1，4.1遗传算法简介，遗传算法是什么？遗传算法(Genetic Algorithm，GA)是进化计算的一个分支，是模拟自然界生物进化过程的随机搜索算法。遗传算法的来源是什么？是谁提出来的？GA思想源于自然选择“自然选择”和“适者生存”的进化规律，通过模拟生物进化中的自然选择和交配变异，探索问题的全局最佳解决方法。美国密歇根大学教授约翰h霍兰首次提出。目前广泛应用于各种工程领域的优化问题。4.1.1基本原理，遗传算法，生物进化生命从地球出生开始漫长的生物进化过程，低水平简单的生物类型逐渐发展成高级复杂的生物类型。这个过程已经通过对古生物、胚胎学、比较

2、解剖学等的研究证明。生物进化的原因自古以来就有多种解释，其中被广泛接受的是达尔文的自然选择理论。4.1.1的基本原理，自然选择说，生物要想生存，就必须进行生存斗争。生存斗争有种内斗争、种间斗争、生物和武器环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易生存，留给后代有利变异的机会更多，具有不利变异的个体容易淘汰，产生后代的机会也少得多。因此，在生存斗争中获胜的个人对环境的适应性比较强。达尔文在生存斗争中消除赤字生存和不安的这种过程被称为自然选择。达尔文的自然选择学说表明遗传和变异是影响生物进化的本质因素。4.1.1基本原理，4.1.1基本原理，4.1.1基本原理，生物进化过程，基因

3、重组过程，1，也称为模式定义模式块(building block)，是描述一系列子集的相似模板。定义1模式：在群体中编码的某些位置具有相似结构的染色体集。例如：染色体的编码是由0或1组成的二进制序列，模式01*0表示代码字符串中以01开头和以0结尾的相应染色体集。4.1.1基本原理、图案清理、图案样例和图案*1010110与以下两个字符串匹配：01010101110 110101110和图案* 1010110匹配以下四个字符串：010100110 01010110 110110，4.1.1基本原理，定义两个图案的顺序是图案中出现的“0”和“1”的数字，并以o(s)记录。具有给定值的基因数。例如

4、：模式“0 * * * *”的阶数为1，模式“10*1*”的阶数为3。定义三种模式的长度是阵列中第一个确定位置和最后一个确定位置之间出现的距离，记录为。例如：模式“01 * * * *”的长度为1，模式“0*1”的长度为4。遗传算法的本质是通过选择、交叉、突变等搜索模式，在群体中指数增长低顺序、定义长度小、平均适应值高于群体平均适应值的模式。也就是说，随着进化的进行，更好的染色体数迅速增加。模式定理证明了遗传算法找到最优解的可能性。但是，算法不能保证必须找到全局优化。4.1.1基本原理，2，构造块假设：低阶、较小定义长度和平均适宜值表示高于组平均适应值的模式。积木块假定在遗传算法运行期间，积木

5、块受遗传运算符的影响，接近可相互结合的新的、更好的积木，最终接近全局最优解决方案。构造块假设补充了模式定理，表明遗传算法具有寻找全局最优解的能力。目前的研究不能对积木假设是否成立提供严格的判断和证明，但很多实验和应用为积木假设提供了支持。，4.1.1基本原理，4.1.2研究进展，GA研究内容和方向，与GA相关的重要学术杂志和国际会议，重要学术杂志evolutilonary computation IEEE transactions on evolutilonary computation重要国际会议iii 第一代人口生成，适者生存，解码后近似最优解决方案，4.1.4基本过程，4.2遗传算法过程

6、，流程结构染色体编码组初始化自适应值评估选择运算符配对运算符算法流程图和伪代码应用示例函数优化问题算法的执行步骤图，也称为简单遗传算法的基本遗传算法(Simple Genetic Algorithm:SGA) 染色体编码方法：首先要将问题的答案空间编码，以便用遗传算法操作。更常用的是二进制编码方法，现在使用非冗馀编码的情况也越来越多。基本遗传算法的组成部分，染色体编码，二进制编码方法浮点编码方法，0000000，1111111，使用生成随机数的方法初始化染色体的每个一维变量的值。初始化染色体的时候，要仔细观察染色体是否符合优化问题的有效解法的定义。如果在进化开始的时候，保证早期群体已经是某种程

7、度上的优秀群体，那么算法就能有效地提高寻找全局最优解决方案的能力。组初始化，评估函数用于评估每条染色体的适应性，以区分优劣。评估函数在解决函数优化问题时，经常根据问题的优化目标来确定，例如，使用问题定义目标函数作为评估函数的原型。遗传算法中适应值越大的染色体越优秀。因此，对于求解最大值的几个数值优化问题，可以直接应用由问题定义的函数表达式。但是，对于其它优化问题，定义为问题的目标函数表达式必须经过一定的转换。适应值评估，选择运算符，轮盘选择算法，fi是个人的适应能力；Fsum是人口的总适应度。Pi是单个I的选择概率。设置轮选择的详细说明流程顺序汇总组中个人的适合性、其累计值、n个组和最后一个累

8、计值Sn。0，生成均匀分布在Sn段的随机数r。如果依次比较Si和r，则第一次出现大于或等于r的Si的相应单独I将被选择为复制对象。重复步骤2和3，直到满足所需的复制对象数。在交配操作符、染色体交配阶段，如果每个染色体的随机(0，1)小于Pc，则意味着该染色体可以进行交配操作(其中随机(0，1)在0，1之间均匀分布的随机数)，否则染色体不参与交配。根据Pc交配的概率，两个选定的染色体进行交配，交换每个基因的一部分，产生两个新的子代染色体。具体工作是随机制作有效的交配位置，以交换染色体在其交配位置的所有基因。交配运算符，单点交叉，两点交叉，染色体的变异作用于基因，对交配后新群体中染色体的每个基因，

9、根据变异概率Pm判定基因是否变异。如果Random(0，1)小于Pm，则更改该基因的值(其中Random(0，1)是在0，1之间均匀分布的随机数)。否则，基因将保持不变。，变异运算符，4，执行参数n:组大小，即组中包含的对象数。t:由遗传算法终止的进化代数。Pc:交叉概率，通常为0.40.99。Pm:可变概率，通常为0.00010.1。遗传算法流程图和伪代码，问题的解决-组攀登，进化算法的问题解决过程是持续攀登过程，登山模拟，搜索空间，随机生成初始解决方案，登山模拟，搜索空间，持续交叉变异和选择，登山效果，登山模拟，搜索空间，持续交叉登山的模拟，搜索空间，通过不断的交叉变异和选择实现登山的效果

10、，登山的模拟，搜索空间，最终达到最佳，4.2.2应用案例，示例4.1已知函数，在这里使用遗传算法实现y的，max。执行阶段、运算符选择参数设置动态策略和自适应策略混合遗传算法并行遗传算法、4.3遗传算法的改进、遗传算法的诸多优点，但是目前存在的问题仍然很多，如早熟现象、接近最优解决方案时收敛速度慢等。很多专家的持续研究，致力于促进遗传算法的发展，深入研究编码方法、控制参数的确定、选择和交叉方法，引入提高遗传算法性能的动态策略和适应策略，提出多种变体的遗传算法(VCGA)，简单地说，4.3遗传算法的改进，4.3.1运算符的选择，影响算法的搜索能力和执行效率。n设置越大，应用一次进化的模式就越多，

11、可以确保群体的多样性，提高算法的搜索能力，但由于组内染色体数较多，只能增加算法计算量，降低算法的执行效率。如果将n设置得小，计算量就会减少，但在每个进化中，减少了组包含更好染色体的能力。n的设置通常为20100。影响算法的计算量和交配变异操作的效果。l的设置与优化问题密切相关，通常由问题定义的解决方案的形式和选择的编码方法决定。对于二进制编码方法，染色体长度l根据解决方案的值范围和指定的精度要求选择大小。对于浮点编码方法，染色体的长度l等于问题定义的解决方案的维数d。Goldberg等公司除了提出染色体长度的特定编码方法外，还提出了染色体长度不固定的可变长度染色体遗传算法Messy GA。4.

12、3.2设定参数，确定参与交配的进化过程人口的平均染色体数。值通常介于0.4和0.99之间。也可以使用自适应方法调整算法运行过程中的交配概率。增加群体进化的多样性，决定进化过程中在群体中引起变异的基因的平均数量。Pm的值不能太大。变异对发现的更好的解决方案起一定的破坏作用，因此如果Pm值太大，算法当前处于更好的搜索状态，则可能会返回到原始状态不好的状态。Pm的值通常介于0.001和0.1之间。也可以使用自适应方法在算法运行过程中调整Pm值。r取决于使用的染色体编码系统。对于二进制编码方法，R=0，1；对于浮点编码方法，R等于由优化问题定义的每个一维变量的值范围。设置4.3.2参数，确定算法在应用

13、特定问题时停止工作的时间，在输出中发现的最佳解决方案，以及使用的终止条件。可以使算法在达到最大进化代数时停止，最大进化代数通常可以设置为1001000，该值可以根据特定问题适当地修改。还可以通过检查找到的当前最佳解决方案是否达到错误要求来控制算法的停止。或者，如果算法在长期进化期间发现的最佳解决方案没有得到改善，则算法可能会停止运行。影响算法在人口选择上，适当的评价函数要适当区分染色体的优劣，确保选择机制的有效性，以提高群体的进化力。评价函数的设置与优化问题的解决目标有关。评价函数必须满足更好染色体的适应值更大的规定。要提高选择的性能，可以稍微修改计算函数。当前主要评估函数修改方法如下：线性变

14、换；动力转换；指数转换等。4.3.2参数设置，1，最佳保留策略查找当前组的最高级别的适应和最低级别的对象，如果当前组的最佳对象的适应度最高，则使用当前组的最佳对象作为新的最佳对象，高于到目前为止最佳对象的适应度。用迄今为止最好的对象替换当前群体中最差的对象。最优保留策略是遗传算法收敛性的重要保证条件，确保到目前为止得到的最优对象不会因交叉、变异等操作而受损。通过使特定区域的最佳对象快速扩散，而不是轻易消除，降低了算法的全局搜索能力。此方法必须与其他选择操作方法结合使用，才能获得良好的效果。4.3.3动态策略和自适应策略，2，自适应遗传算法自适应遗传算法(AGA)的交叉概率和变异概率可以根据自适

15、应度自动改变。如果群体的个体适应度一致或局部最优倾向，则提高交叉概率和变异概率，如果群体适应度分布，则降低交叉概率和变异概率。此外，对于适应值高于组的平均适应值的对象，对应于低交叉概率和变异概率，以便相应的解决方案保护到下一代。低于平均自适应值的对象对应于较高的相交概率和变异概率，此解决方案被消除。4.3.3动态策略和自适应策略，2，自适应遗传算法，4.3.3动态策略和自适应策略，3，生态位遗传算法遗传算法中模拟生态位的方法主要为：(1)基于预选的间隙实施方法Cavicchio 1970年的建议，基本思路：结果子实体只有在新创建的子实体的适应性超过父实体的适应性时，才能替换父实体以后代的身份继承，否则父实体将保留为以下子组：这种方法实际上只替换了编码结构相似的部分实体，可以有效地保持群体的多样性。4.3.3动态策略和适应策略，3，基于小生