进化算法-遗传算法.ppt

第8章进化算法一遗传算法
智能控制基础
《智能控制基础》清华大学出版社
82遗传学习原理与算法

822遗传学习算法的理论基础
823遗传学习算法的改良)

《智能控制基础》清华大学出版社
2/50
1问题的提出
今美国的 J Holland教授于1975年提出
◆在遗传学的基础上利用计算机来模拟生物的
进化过程,从而实现复杂问题的优化求解。
◆模拟生物染色体的运作(复制、交叉、变
异),是一种随机化搜索算法
《智能控制基础》清华大学出版社
3/50
步骤
群体的初始化;
评价群体中每一个体的性能;
(③选择下一代个体;
执行简单的操作算子(如交叉、变异);
5·评价下一代群体的性能
·判断终止条件满足否?若不,则转(3)继续;若满足,则
结束
《智能控制基础》清华大学出版社
4/50
需要解决的问题
◇编码机制;
◆选择机制;
心控制参数选择;
心二进制字符串的群体构成;
心适应度函数的计算
遗传算子(交叉、变异)的定义。
《智能控制基础》清华大学出版社
5/50

令编码机制( Encoding mechanism)
心适应度函数( Fitness function
令选择机制( Selection mechanisn)
令交叉算子(C
crossover
◆变异算子( Mutation
《智能控制基础》清华大学出版社
6/50
(1)编码机制
今二进制编码
■每一个位(0或1)一基因
■字符串一染色体
◆多值编码方法
实数编码
《智能控制基础》清华大学出版社
7/50
(2)适应度函数
优化问题的目标函数
◆“适应度值”的计算直接通过将目标函数经
定的线性变换映射到的[0,1]区间内的
个值。
《智能控制基础》清华大学出版社
8/50
3)选择机制
基本思想取自于自然界进化论的“适者生
存
心适应度值越高的个体,生存的数量也越高。
满足“优胜劣汰”自然法则。
令也可称为复制机制
令比例选择法( Proportionate selection scheme)
◆转轮选择法( Roulette wheel selection
Scheme):随机方法
《智能控制基础》清华大学出版社
9/50
(4)交叉算子
◆模拟有性繁殖现象
随机地从父辈集合中选取两个个体作为双亲。
设L表示一个体的字符串(染色体)长度,
随机地产生(0~L)之间的一个数d,并把此点
位置称为交叉点。交叉运算就是将双亲的基
因链在交叉点断裂,且将在交叉点之后的基
因根据交叉率的条件决定是否进行相互交换
形成下一代。
令所谓交叉率p是根据优化问题预先确定的
个0~1之间的值。通常取06~09
《智能控制基础》清华大学出版社
1050