Artificial Intelligence 第5章计算智能(2): 进化计算 人工生命
第5章 计算智能(2): 进化计算 人工生命
令进化计算包括: 遗传算法( genetic algorithms,GA) ◇进化策略( evolution strategies) 令进化编程( evolutionary rogramming) 遗传编程( genetic programming) 令人类不满足于模仿生物进化行为,希望能 (够建立具有自然生命特征的人造生命和人 造生命糸统。 令人工生命是人工智能和计算智能的一个新 (的研究热点
2 ❖进化计算包括： ❖遗传算法(genetic algorithms，GA) ❖进化策略(evolution strategies) ❖进化编程(evolutionary rogramming) ❖遗传编程(genetic programming) ❖人类不满足于模仿生物进化行为，希望能 够建立具有自然生命特征的人造生命和人 造生命系统。 ❖人工生命是人工智能和计算智能的一个新 的研究热点
51遗传算法 令遺传算法是模仿生物遗传学和自然选 择机理,通过人工方式所构造的一类 优化披索算法,是对生物进化过程进 行的一种数学仿真,是进化计算的最 C重要的形式。 令遗传算法为那些唯以找到传统数学模 型的难题指出了一个解决方法。 进化计算和遗传算油借鉴了生物科学。 中的某些知识,这也体现了人工智能 这一交叉学科的特点
3 5.1 遗传算法 ❖遗传算法是模仿生物遗传学和自然选 择机理，通过人工方式所构造的一类 优化搜索算法，是对生物进化过程进 行的一种数学仿真，是进化计算的最 重要的形式。 ❖遗传算法为那些难以找到传统数学模 型的难题指出了一个解决方法。 ❖进化计算和遗传算法借鉴了生物科学 中的某些知识，这也体现了人工智能 这一交叉学科的特点
5.1遗传算法 511遗传算法的基本机狸 霍兰德的遗传算法通帝称为简草遗传算 法(SGA)。现以此作为讨论主要对象, 加上适应的改进,亲分析遗传算法的结 构和机理。 令编码与解码 心适应度函数 遗传操作
4 5.1.1 遗传算法的基本机理 ❖霍兰德的遗传算法通常称为简单遗传算 法（SGA）。现以此作为讨论主要对象， 加上适应的改进，来分析遗传算法的结 构和机理。 ❖编码与解码 ❖适应度函数 ❖遗传操作 5.1 遗传算法
5.1遗传算法 5,2遭传算法的求解步騵 1.遗传算渎的特点 (1)遗传算是对参数集合的编码而非针对参数 (本身进行进化; (②)遗传算法是从闷题解的编码组开始而非从单 个解开始披索 (3)遗传算法利用目标函数的适应度这一信息而 (非利用导数或其名辅助信息来指导披索; 4)遗传算法利用选择、交叉、变异等算子而不 是利用确定性规则进行随机操作
5 5.1.2 遗传算法的求解步骤 1. 遗传算法的特点 (1) 遗传算法是对参数集合的编码而非针对参数 本身进行进化； (2) 遗传算法是从问题解的编码组开始而非从单 个解开始搜索； (3) 遗传算法利用目标函数的适应度这一信息而 非利用导数或其它辅助信息来指导搜索； (4) 遗传算法利用选择、交叉、变异等算子而不 是利用确定性规则进行随机操作。 5.1 遗传算法
5.1遗传算法 2遗传算法的框图(图5,2) (1)初始化群体; ()计算群体上每个个体的应度值;C5 (3)按由个体适应度值所决定的甚个规则选 择将进入下一代的个体 (4)按概率P进行交叉操作 (5)按概率P进行突吏振作 (6)若没有满足某种停止条件,则转第(2)步 否则进入下一步。 (⑦)輪出群体中适应度值最优的樂色体作为问题的 满意解或录优解
6 2. 遗传算法的框图(图5.2) (1) 初始化群体; (2) 计算群体上每个个体的适应度值; (3) 按由个体适应度值所决定的某个规则选 择将进入下一代的个体; (4) 按概率Pc进行交叉操作; (5) 按概率Pc进行突变操作; (6) 若没有满足某种停止条件，则转第(2)步， 否则进入下一步。 (7) 输出群体中适应度值最优的染色体作为问题的 满意解或最优解。 5.1 遗传算法
5.1遗传算法 开始「 初始化种群 计算适应度值 选择操作 交叉操作 变异操作 终止条件 初始化种群 图52算法框图
7 初始化种群 变异操作 计算适应度值 选择操作 交叉操作 初始化种群 终止条件 开始 图5.2 算法框图 5.1 遗传算法
5.1遗传算法 一般遗传算法的主要步骠如下: (1)随机产生一个由确定长度的特征字 符串组成的初始群体。 (2)对该字符串群体迭代的执行下面的 步①和②,直到端足停止标准: ①计算群体中每个个体字符串的适应值; (②应用复制、交叉和异等遗传算子产生 下一代群体。 (3)把在后代中出现的最好的个体字符 串指定为遗传算謗的执行结果,这个 结果可以表示问题的一个解。 8
8 一般遗传算法的主要步骤如下： (1) 随机产生一个由确定长度的特征字 符串组成的初始群体。 (2) 对该字符串群体迭代的执行下面的 步①和②，直到满足停止标准： ① 计算群体中每个个体字符串的适应值； ② 应用复制、交叉和变异等遗传算子产生 下一代群体。 (3) 把在后代中出现的最好的个体字符 串指定为遗传算法的执行结果，这个 结果可以表示问题的一个解。 5.1 遗传算法
5.1遗传算法 GEN: =0 产生初始群体 是否满足停止准则是 指定结果 否 计算每个个体的适应值 C结束 i:=0 GEN: =GEN+I 是 i=M? 否 复制 依概率选择遗传操作 交叉 变异 选择一个个体 选择两个个体 选择一个个体 执行复制 i:=i+1 执行变异 L复制到新群体」 匚执行杂交 插入到新群体 将两个后代插入新群体 i:=i+1 9
9 产生初始群体 是否满足停止准则 计算每个个体的适应值 GEN:=GEN+1 i=M? 依概率选择遗传操作 执行复制 选择一个个体 i:=i+1 选择两个个体 选择一个个体 执行变异 i:=0 GEN:=0 复制到新群体 i:=i+1 将两个后代插入新群体 执行杂交 插入到新群体 指定结果 结束 是 否 是 否 复制 交叉 变异 5.1 遗传算法
5.1遗传算法 遗传算法的一般结构表示 .g 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) 8 select P(t+1) from P(t)and c(t; t←t1 end end 10
10 遗传算法的一般结构表示 ❖ 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 5.1 遗传算法