《优化算法讲》PPT课件

《《优化算法讲》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章遗传算法的高级实现技术7/16/20211主要内容4.1倒位算子4.2二倍体与显性操作算子4.3变长度染色体遗传算法4.4小生境遗传算法4.5混合遗传算法7/16/202124.1倒位算子4.1.1定义：什么是倒位操作？所谓倒位操作（InverseOperation）是指颠倒个体编码串随机指定的二个基因座之间的基因排列顺序，从而形成一个新的染色体。7/16/202134.1倒位算子4.1.2具体操作过程:①在个体编码串中随机指定二个基因座之后的位置为倒位点；②以倒位概率颠倒这二个倒位点之间的基因排列顺序。1231237/16/202144.1倒位算子对二进制编码

2、个体进行倒位操作的示例：A：110┊01001┊10A’：110┊10010┊10倒位点1倒位点2倒位操作倒位操作改变了个体编码串的部分基因排列顺序，其目的主要是为了能够使遗传算法更有利于生成较好的模式。7/16/202154.1倒位算子0123456789101112131415161718212327282930313233343536373839SG4.1.3倒位算子应用实例7/16/202164.1倒位算子用遗传算法进行机器人路径规划时，可取机器人移动过程中所经过栅格标号的顺序排列来作为一个个体（一条行走路线）的表现形式，如下所示即表示一条行走路线：PATH：

3、0——3——9——13——29——39（虚线）若在上述行走路线的第二个路径和第三个路径点之间进行倒位操作，可得到一条新的路线：PATH:0——9——3——13——29——39（实线）7/16/202174.2二倍体与显性操作算子4.2.1二倍体结构的生物基础生物学中，二倍体是指含有二个同源基因组(染色体)的个体。二倍体是由两个同源染色体构成的，其中的每一个染色体都含有相同功能的基因信息。7/16/202184.2.1二倍体结构的生物基础二倍体结构中各个基因有显性基因和隐性基因之分，这二类基因使个体所呈现出的表现型由下述规则来决定（显性规则）：在每个基因座上，当两个同源

4、染色体其中之一的基因是显性时，则该基因所对应的性状表现为显性；而仅当两个同源染色体中对应基因皆为隐性时，该基因所对应的性状才表现为隐性。AbcDefGAbCDefG二倍体结构AbCDefG个体表现型7/16/202194.2.1二倍体结构的生物基础二倍体的二个重要特性：1）二倍体的记忆能力，它使得生物能够记忆以前经历过的环境及变化，使得生物的遗传进化过程能够快速地适应环境的变化。这个特点在遗传算法中的应用意义就在于，使用二倍体结构的遗传算法能够解决动态环境下的复杂系统优化问题，而常规的遗传算法却不能很好地应用于动态环境，它难于跟踪环境的动态变化过程。2）显性操作的鲁棒

5、性，它使得即使随机选择了适应度不高的个体，而在显性操作的作用下，能够用其另一同源染色体对其进行校正，从而避免这个有害选择所带来的不利之处。这个特点应用于遗传算法中，能有利于提高遗传算法的运算效率．维护好的搜索群体。7/16/2021104.2.2二倍体结构在遗传算法中的实现方案Hollstien提出了二倍体与显性操作的双基因座显性映射方法：每个二进制基因用两个基因来描述，一个称为函数基因，取通常含义的0或1值；另一个称为修饰基因，取值为M或m，其中M表示显性基因，m表示隐性基因。随后，Hollstien将这种映射关系简化为单基因座显性映射方法。Holland对这种单基

6、因座的显性映射描述方法进行了改进。描述基因的字符集为{0,1,10}，其中10为隐性的1，1为显性的1。7/16/2021114.2.2二倍体结构在遗传算法中的实现方案00000001001101110M0m1M1m0M0m1M1m单基因座显性映射方法双基因座显性映射方法图1图27/16/2021124.2.2二倍体结构在遗传算法中的实现方案使用双倍体的遗传算法的算法结构与基本遗传算法的算法结构相类似，不同之处在于：(1)显性性状也能进化，所以同源染色体之间也需进行交叉操作。(2)变异操作需要考虑隐性性状；(3)对个体进行交叉、变异运算之后，要进行显性操作。7/16/

7、2021134.2.2二倍体结构在遗传算法中的实现方案算法DiploidyGA①初始化，并设置进化代数计数器初值：t=1。②随机产生具有二倍体结构的初始群体P(0)。⑤对初始群体P(0)进行显性操作。④评价初始群体P(0)中各个个体的适应度。⑦交叉操作：P’(t)←Crossover[p(t)]。由每两个随机配对的二倍体个体进行交叉操作时，共可产生四个单倍体个体。⑥变异操作：P’’(t)←Mutation[p’(t)]。在对群体中的各个个体进行变异操作时，需要考虑隐性基因的作用。⑦对群体P’’(t)进行显性操作。⑧评价群体P’’(t)中各个个体的适应