文档介绍：第5章计算智能(2):
进化计算
人工生命
中南大学智能系统与智能软件研究所
进化计算包括:
遗传算法(ic algorithms,GA)
进化策略(evolution strategies)
进化编程(evolutionary rogramming)
遗传编程(ic programming)
人类不满足于模仿生物进化行为,希望能够建立具有自然生命特征的人造生命和人造生命系统。
人工生命是人工智能和计算智能的一个新的研究热点。
2
遗传算法
遗传算法是模仿生物遗传学和自然选择机理,通过人工方式所构造的一类优化搜索算法,是对生物进化过程进行的一种数学仿真,是进化计算的最重要的形式。
遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。
进化计算和遗传算法借鉴了生物科学中的某些知识,这也体现了人工智能这一交叉学科的特点。
3
遗传算法的基本机理
霍兰德的遗传算法通常称为简单遗传算法(SGA)。现以此作为讨论主要对象,加上适应的改进,来分析遗传算法的结构和机理。
编码与解码
适应度函数
遗传操作
遗传算法
4
遗传算法的求解步骤
1. 遗传算法的特点
(1) 遗传算法是对参数集合的编码而非针对参数本身进行进化;
(2) 遗传算法是从问题解的编码组开始而非从单个解开始搜索;
(3) 遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索;
(4) 遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。
遗传算法
5
2. 遗传算法的框图()
(1) 初始化群体;
(2) 计算群体上每个个体的适应度值;
(3) 按由个体适应度值所决定的某个规则选
择将进入下一代的个体;
(4) 按概率Pc进行交叉操作;
(5) 按概率Pc进行突变操作;
(6) 若没有满足某种停止条件,则转第(2)步,
否则进入下一步。
(7) 输出群体中适应度值最优的染色体作为问题的
满意解或最优解。
遗传算法
6
初始化种群
变异操作
计算适应度值
选择操作
交叉操作
初始化种群
终止条件
开始
算法框图
遗传算法
7
一般遗传算法的主要步骤如下:
(1) 随机产生一个由确定长度的特征字符串组成的初始群体。
(2) 对该字符串群体迭代的执行下面的步①和②,直到满足停止标准:
①计算群体中每个个体字符串的适应值;
②应用复制、交叉和变异等遗传算子产生下一代群体。
(3) 把在后代中出现的最好的个体字符串指定为遗传算法的执行结果,这个结果可以表示问题的一个解。
遗传算法
8
产生初始群体
是否满足停止准则
计算每个个体的适应值
i=M?
GEN:=GEN+1
依概率选择遗传操作
执行复制
选择一个个体
i:=i+1
选择两个个体
选择一个个体
执行变异
i:=0
GEN:=0
复制到新群体
i:=i+1
将两个后代插入新群体
插入到新群体
执行杂交
指定结果
结束
是
否
是
否
变异
复制
交叉
遗传算法
9
遗传算法的一般结构表示
Procedure: ic Algorithms
begin
t ← 0;
initialize P(t);evaluate P(t);
while (not termination condition ) do
begin
bine P(t) to yield C(t);
evaluate C(t);
select P(t+1) from P(t) and C(t);
t ← t+1;
end
end
遗传算法
10