遗传算法讲义3_slides

《遗传算法讲义3_slides》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章遗传算法的高级实现技术3.1二倍体与显性操作算子3.1.1二倍体结构的生物基础生物学中，二倍体是指含有二个同源基因组(染色体)的个体。二倍体是由两个同源染色体构成的，其中的每一个染色体都含有相同功能的基因信息。二倍体结构中各个基因有显性基因和隐性基因之分，这二类基因使个体所呈现出的表现型由下述规则来决定（显性规则）：在每个基因座上，当两个同源染色体其中之一的基因是显性时，则该基因所对应的性状表现为显性；而仅当两个同源染色体中对应基因皆为隐性时，该基因所对应的性状才表现为隐性。显性基因在纯合子(AA)或杂合子(A或a)情况下

2、均能被表现出，而隐性基因只能在纯合子(aa)的情况下才能被表现出。二倍体的二个重要特性：1）二倍体的记忆能力，它使得生物能够记忆以前经历过的环境及变化，使得生物的遗传进化过程能够快速地适应环境的变化。这个特点在遗传算法中的应用意义就在于，使用二倍体结构的遗传算法能够解决动态环境下的复杂系统优化问题，而常规的遗传算法却不能很好地应用于动态环境，它难于跟踪环境的动态变化过程。2）显性操作的鲁律性，它使得即使随机选择了适应度不高的个体，而在显性操作的作用下，能够用其另一同源染色体对其进行校正，从而避免这个有害选择所带来的不利之处。这个

3、特点应用于遗传算法中，能有利于提高遗传算法的运算效率．维护好的搜索群体。3.1.2二倍体结构在遗传算法中的实现方案Hollstien提出了二倍体与显性操作的双基因座显性映射方法：每个二进制基因用两个基因来描述，一个称为函数基因，取通常含义的0或1值；另一个称为修饰基因，取值为M或m，其中M表示显性基因，m表示隐性基因。随后，Hollstien将这种映射关系简化为单基因座显性映射方法。Holland对这种单基因座的显性映射描述方法进行了改进。在这个单基因座显性映射方法中，描述基因的字符集为{0,1,10}，其中10为隐性的1，1为

4、显性的1。双基因座显性映射方法单基因座显性映射方法使用双倍体的遗传算法的算法结构与基本遗传算法的算法结构相类似，但也有些差别，其不同之处在于：(1)显性性状也能进化，所以同源染色体之间也需进行交叉操作。(2)变异操作需要考虑隐性性状；(3)对个体进行交叉、变异运算之后，要进行显性操作。使用双倍体的遗传算法可描述如下：算法DiploidyGA①初始化，并设置进化代数计数器初值：t=1。②随机产生具有二倍体结构的初始群体P(0)。③对初始群体P(0)进行显性操作。④评价初始群体P(0)中各个个体的适应度。⑤交叉操作：P’(t)←cr

5、ossover[p(t)]。由每两个随机配对的二倍体个体进行交又操作时，共可产生四个单倍体个体。⑥变异操作：P’’(t)←mutation[p’(t)]。在对群体中的各个个体进行变异操作时，需要考虑隐性基因的作用。⑦对群体P’’(t)进行显性操作。⑧评价群体P’’(t)中各个个体的适应度。⑨个体选择、复制操作：⑩终止条件判断。若不满足终止条件，则:t←t+1，转到第⑤步，继续进行进化操作过程；若满足终止条件．则．输出当前最优个体，算法结束。3.2变长度染色体遗传算法在生物的进化过程中，其染色体的长度并不是固定不变的，而是随着进化

6、过程也在慢慢地变化着。在遗传算法的实际应用中．有时为简要地描述问题的解，也需要使用不同长度的编码串。结点1和结点6之间的连通路线，可用以下二种方法来描述：(1)用二进制编码来表示各个结点是否在连通路线上，其中l表示在连通路线上，0表示不在连通路线上。此时可使用等长度的编码串来表示连通路线，如：PATH1：110011PATH2：111111(2)用连通路线所经过结点的顺序排列来表示该条连通路线，如：PATH1：1—2—5—6PATH2：1—2—3—4—5—6该方法使用的就是变长度的染色体编码方法。Goldberg等提出的Mess

7、yGA(简称MGA)是一种典型的变长度染色体遗传算法。3.2.1变长度染色体遗传算法的编码与解码（MessyGA）编码将常规遗传算法的染色体编码串中各基因座位置及相应基因值组成一个二元组，把这个二元组按一定顺序排列起来，就组成了变长度染色体的一种通用染色体编码方式。一般它可表示为:ik是所描述约基因在原常规染色体中的基因座编号，vk为对应的基因值。对于所需求解的问题，若使用常规遗传算法时的染色体长度固定为l，各基因值取自集合V，则有例如，若常规遗传算法中一个个体的基因型是：X：10010l其染色体长度为l＝6。使用变长度染色体编

8、码，该个体就可表示为：Xm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)在这种变长度染色体遗传算法中，允许染色体的长度可长可短。如：Xm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)(3，1)(1，0)Xm：(1，1)(3，0)(