文档介绍：最优化算法讲课课件
第1页，共41页，编辑于2022年，星期六
主要内容
倒位算子
二倍体与显性操作算子
变长度染色体遗传算法
小生境遗传算法
混合遗传算法
*
，星期六
二倍体结构在遗传算法中的实现方案
0
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
0M 0m 1M 1m
0M
0m
1M
1m
单基因座显性映射方法
双基因座显性映射方法
图 1
图 2
*
*
第12页，共41页，编辑于2022年，星期六
二倍体结构在遗传算法中的实现方案
使用双倍体的遗传算法的算法结构与基本遗传算法的算法结构相类似，不同之处在于：
(1) 显性性状也能进化，所以同源染色体之间也需进行交叉操作。
(2) 变异操作需要考虑隐性性状；
(3) 对个体进行交叉、变异运算之后，要进行显性操作。
*
*
第13页，共41页，编辑于2022年，星期六
二倍体结构在遗传算法中的实现方案
算法DiploidyGA
① 初始化，并设置进化代数计数器初值：t=1。
② 随机产生具有二倍体结构的初始群体P(0)。
⑤ 对初始群体P(0)进行显性操作。
④ 评价初始群体P(0)中各个个体的适应度。
⑦ 交叉操作：P’(t)←Crossover[p(t)]。由每两个随机配对的二倍体个体进行交叉操作时，共可产生四个单倍体个体。
⑥ 变异操作：P’’(t)←Mutation[p’(t)]。在对群体中的各个个体进行变异操作时，需要考虑隐性基因的作用。
⑦ 对群体P’’(t)进行显性操作。
⑧ 评价群体P’’(t)中各个个体的适应度。
⑨ 个体选择、复制操作：P(t+1)←Reproduction [P(t)∪P’’（t）]
⑩ 终止条件判断。若不满足终止条件，则: t←t+1，转到第⑤步，继续进行进化操作过程；若满足终止条件．则:输出当前最优个体，算法结束。
*
*
第14页，共41页，编辑于2022年，星期六
变长度染色体遗传算法
在遗传算法的实际应用中，有时为简要地描述问题的解，也需要使用不同长度的编码串。
结点1和结点6之间的连通路线，可用以下二种方法来描述：
*
*
第15页，共41页，编辑于2022年，星期六
变长度染色体遗传算法
(1)用二进制编码来表示各个结点是否在连通路线上，其中1表示在连通路线上，0表示不在连通路线上。此时可使用等长度的编码串来表示连通路线，如：
PATH1：1 1 0 0 1 1
PATH2：1 1 1 1 1 1
(2)用连通路线所经过结点的顺序排列来表示该条连通路线，如：
PATH1：1→2 → 5 → 6
PATH2：1 → 2 → 3 → 4 → 5 → 6
*
*
第16页，共41页，编辑于2022年，星期六
变长度染色体遗传算法的编码与解码
编码
将常规遗传算法的染色体编码串中各基因座位置及相应基因值组成一个二元组，把这个二元组按一定顺序排列起来，就组成了变长度染色体的一种通用染色体编码方式。一般它可表示为:
ik是所描述的基因在原常规染色体中的基因座编号，vk为对应的基因值。
*
*
第17页，共41页，编辑于2022年，星期六
变长度染色体遗传算法的编码与解码
若常规遗传算法中一个个体的基因型是：
X：1 0 0 1 0 1
其染色体长度为L＝6。使用变长度染色体编码，该个体就可表示为：
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)(5，0)(6，1)
前者称为过剩指定，后者称为缺省指定。而当个体的所有基因都能在编码串中得到唯一的描述时，这种描述称为正常指定。
*
*
第18页，共41页，编辑于2022年，星期六
变长度染色体遗传算法的编码与解码
解码
正常指定没有问题。过剩指定或缺省指定，可按下述规则来进行解码处理：
(1)描述过剩时的解码方法。规定取最左边的二元组来进行解码。
例如，对于变长度染色体遗传算法中的个体
Xm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)(3，1)(1，0)
它在常规遗传算法中所对应的个体为：
X：1 0 0 1 0 1
*
*
第19页，共41页，编辑于2022年