文档介绍：第四章遗传算法的高级实现技术
7/5/2017
1
主要内容
倒位算子
二倍体与显性操作算子
变长度染色体遗传算法
小生境遗传算法
混合遗传算法
7/5/2017
2
倒位算子
定义:什么是倒位操作?
所谓倒位操作(Inverse Operation)是指颠倒个体编码串随机指定的二个基因座之间的基因排列顺序,从而形成一个新的染色体。
7/5/2017
3
倒位算子
具体操作过程:
①在个体编码串中随机指定二个基因座之后的位置为倒位点;
②以倒位概率颠倒这二个倒位点之间的基因排列顺序。
1
2
3
1
2
3
7/5/2017
4
倒位算子
对二进制编码个体进行倒位操作的示例:
A:1 1 0 ┊ 0 1 0 0 1 ┊ 1 0
A’:1 1 0 ┊ 1 0 0 1 0 ┊ 1 0
倒位点1
倒位点2
倒位操作
倒位操作改变了个体编码串的部分基因排列顺序,其目的主要是为了能够使遗传算法更有利于生成较好的模式。
7/5/2017
5
倒位算子
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
21
23
27
28
29
30
31
32
33
34
35
36
37
38
39
S
G
倒位算子应用实例
7/5/2017
6
倒位算子
用遗传算法进行机器人路径规划时,可取机器人移动过程中所经过栅格标号的顺序排列来作为一个个体(一条行走路线)的表现形式,如下所示即表示一条行走路线:
PATH:0——3——9——13——29——39(虚线)
若在上述行走路线的第二个路径和第三个路径点之间进行倒位操作,可得到一条新的路线:
PATH: 0——9——3——13——29——39(实线)
7/5/2017
7
二倍体与显性操作算子
二倍体结构的生物基础
生物学中,二倍体是指含有二个同源基因组(染色体)的个体。
二倍体是由两个同源染色体构成的,其中的每一个染色体都含有相同功能的基因信息。
7/5/2017
8
二倍体结构的生物基础
二倍体结构中各个基因有显性基因和隐性基因之分,这二类基因使个体所呈现出的表现型由下述规则来决定(显性规则):
在每个基因座上,当两个同源染色体其中之一的基因是显性时,则该基因所对应的性状表现为显性;而仅当两个同源染色体中对应基因皆为隐性时,该基因所对应的性状才表现为隐性。
A b c D e f G
A b C D e f G
二倍体结构
A b C D e f G
个体表现型
7/5/2017
9
二倍体结构的生物基础
二倍体的二个重要特性:
1)二倍体的记忆能力,它使得生物能够记忆以前经历过的环境及变化,使得生物的遗传进化过程能够快速地适应环境的变化。这个特点在遗传算法中的应用意义就在于,使用二倍体结构的遗传算法能够解决动态环境下的复杂系统优化问题,而常规的遗传算法却不能很好地应用于动态环境,它难于跟踪环境的动态变化过程。
2)显性操作的鲁棒性,它使得即使随机选择了适应度不高的个体,而在显性操作的作用下,能够用其另一同源染色体对其进行校正,从而避免这个有害选择所带来的不利之处。这个特点应用于遗传算法中,。
7/5/2017
10