文档介绍：人 工 智 能
*
第5章 计算智能 2 Computational Intelligence
进化计算
人工生命
*
进化计算包括：
遗传算法 genetic algorithms,GA
进化策略 evo用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索；
4  遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作，
遗传算法
*
2. 遗传算法的框图
1 初始化种群;
2 计算种群上每个个体的适应度值;
3 按由个体适应度值所决定的某个规则选
择将进入下一代的个体;
4 按概率Pc进行交叉操作;
5 按概率Pm进行变异操作;
6 若没有满足某种停止条件,则转第 2 步,
否则进入下一步，
7 输出种群中适应度值最优的染色体作为问题的满意解或最优解，
遗传算法
*
初始化种群
变异操作
计算适应度值
选择操作
交叉操作
最优解输出
终止条件
算法框图 返回
遗传算法
否
是
开始
结束
1
2
3
4
5
6
7
*
遗传算法的一般结构表示
Procedure: Genetic Algorithms
begin
t ← 0;
initialize P t ;evaluate P t ;
while not termination condition do
begin
recombine P t to yield C t ;
evaluate C t ;
select P t+1 from P t and C t ;
t ← t+1;
end
end
遗传算法
*
3. 遗传算法求解举例
遗传算法
设
用SGA求
遗传算法归纳为五个基本组成部份
方案表示
种群初始化
适应度函数
遗传操作
算法参数
*
SGA及其模式定理
回顾：
1 GA的基本原理与算法框架；
2 GA的基本遗传算子；
问题：
1 基本遗传算法 SGA 的算法步骤；
2 GA的计算实例；
3 GA有效性的理论证明；
遗传算法
*
SGA的算法步骤
遗传算法
1 编码： 随机产生一个由确定长度的特征字符串组成的初始种群，
2 进化：对该字符串种群迭代的执行下面的步①和步② ,直到满足停止标准：
① 计算种群中每个个体字符串的适应值；
② 应用复制、交叉和变异等遗传算子产生下一代种群，
3 解码：把在后代中出现的最好的个体字符串指定为遗传算法的执行结果,这个结果可以表示问题的一个解，
*
产生初始种群
计算每个个体的适应值
GEN:=GEN+1
依概率选择遗传操作
执行复制
选择一个个体
i:=i+1
选择两个个体
选择一个个体
执行变异
i:=0
复制到新种群
i:=i+1
将两个后代插入新种群
插入到新种群
执行杂交
指定结果
是
否
是
否
变异
复制
交叉
结束
GEN:=0
是否满足停止准则
i=M
遗传算法
*
SGA的伪代码描述
Procedure: Simple Genetic Algorithms
begin
t ← 0;
initialize P t ;evaluate P t ;
while not termination condition do
begin
recombine P t to yield C t ;
P t ← C t ;
evaluate P t ;
t ← t+1;
end
end
遗传算法
*
一个简单的计算实例
例：极大值问题 max f x =x2,x 0,31
1. 编码：5位二进制数；
2. 初始群体：群体规模为4个个体,随机产生；
假设为：01101,11000,01000,10011
3. 适应度计算： 适应值直接取 f x
4. 选择复制产生下一代群体； 选择概率按适应值大小采用轮盘赌的随机策略
遗传算法
31
0
f=x2
个体编号
初始群体
基因译码
适应度计算
f