第 5章 计算智能 (2):
进化计算
人工生命
2
?进化计算包括：
?遗传算法 (genetic algorithms,GA)
?进化策略 (evolution strategies)
?进化编程 (evolutionary rogramming)
?遗传编程 (genetic programming)
?人类不满足于模仿生物进化行为，希望能
够建立具有自然生命特征的人造生命和人
造生命系统。
?人工生命是人工智能和计算智能的一个新
的研究热点。
3
5.1 遗传算法
?遗传算法是模仿生物遗传学和自然选
择机理，通过人工方式所构造的一类
优化搜索算法，是对生物进化过程进
行的一种数学仿真，是进化计算的最
重要的形式。
?遗传算法为那些难以找到传统数学模
型的难题指出了一个解决方法。
?进化计算和遗传算法借鉴了生物科学
中的某些知识，这也体现了人工智能
这一交叉学科的特点。
4
5.1.1 遗传算法的基本机理
?霍兰德的遗传算法通常称为简单遗传算
法（ SGA）。现以此作为讨论主要对象，
加上适应的改进，来分析遗传算法的结
构和机理。
?编码与解码
?适应度函数
?遗传操作
5.1 遗传算法
5
5.1.2 遗传算法的求解步骤
1,遗传算法的特点
(1) 遗传算法是对参数集合的编码而非针对参数
本身进行进化；
(2) 遗传算法是从问题解的编码组开始而非从单
个解开始搜索；
(3) 遗传算法利用目标函数的适应度这一信息而
非利用导数或其它辅助信息来指导搜索；
(4) 遗传算法利用选择, 交叉, 变异等算子而不
是利用确定性规则进行随机操作 。
5.1 遗传算法
6
2,遗传算法的框图 (图 5.2)
(1) 初始化群体 ;
(2) 计算群体上每个个体的适应度值 ;
(3) 按由个体适应度值所决定的某个规则选
择将进入下一代的个体 ;
(4) 按概率 Pc进行交叉操作 ;
(5) 按概率 Pc进行突变操作 ;
(6) 若没有满足某种停止条件, 则转第 (2)步,
否则进入下一步 。
(7) 输出群体中适应度值最优的染色体作为问题的
满意解或最优解 。
5.1 遗传算法
7
初始化种群
变异操作
计算适应度值
选择操作
交叉操作
初始化种群
终止条件
开始
图 5.2 算法框图
5.1 遗传算法
8
一般遗传算法的主要步骤如下：
(1) 随机产生一个由确定长度的特征字
符串组成的初始群体 。
(2) 对该字符串群体迭代的执行下面的
步 ① 和 ②, 直到满足停止标准：
① 计算群体中每个个体字符串的适应值；
② 应用复制, 交叉和变异等遗传算子产生
下一代群体 。
(3) 把在后代中出现的最好的个体字符
串指定为遗传算法的执行结果, 这个
结果可以表示问题的一个解 。
5.1 遗传算法
9
产生初始群体
是否满足停止准则
计算每个个体的适应值
i=M?GEN:=GEN+1
依概率选择遗传操作
执行复制
选择一个个体
i:=i+1
选择两个个体 选择一个个体
执行变异
i:=0
GEN:=0
复制到新群体
i:=i+1
将两个后代插入新群体
插入到新群体执行杂交
指定结果
结束
是
否
是
否
变异复制 交叉
5.1 遗传算法
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 遗传算法
11
3,遗传算法求解举例
5.1 遗传算法
?设,用 SGA求
?参数设臵
?二进制编码
?种群大小为 4
?染色体长为 4位
)1ln ()( 2xxf ??
]15,0[),(m a x ?xxf
12
遗传算法归纳为五个基本组成部份
?方案表示
?群体初始化
?适应度函数
?遗传操作
?算法参数
5.1 遗传算法
13
5.2 进化策略
?进化策略 (Evolution Strategies,ES)是
一类模仿自然进化原理以求解参数优化
问题的算法。
?它是由雷切伯格（ Rechenberg）、施韦
费尔（ Schwefel）和彼得 ·比纳特
（ Peter Bienert）于 1964年提出的，并
在德国共同建立的。
14
5.2.1 进化策略的算法模型
?寻求与函数极值关联的实 n维矢量 x。
?随机选择父矢量的初始群体。
?父矢量 xi,i=1,…,p产生子代矢量 xi。
?对误差 (i=1,…,p)排序以选择和决定
保持哪些矢量。
?继续产生新的试验数据以及选择最小
误差矢量。
5.2 进化策略
15
5.2.2 进化策略和遗传算法的区别
?进化策略和遗传算法有着很强的相似性，
它们都是一类模仿自然进化原理的算法。
?两者也存在着区别，其中最基本的区别
是它们的研究领域不同。
?进化策略是一种数值优化的方法，它采用一
个具有自适应步长和倾角的特定爬山方法。
?遗传算法从广义上说是一种自适应搜索技术。
5.2 进化策略
16
5.3 进化编程
?进化编程 (Evolutionary Programming,EP)，
又称为进化规划（ Evolutionary Planning），
是由福格尔（ Fogel）在 1962年提出的一种模
仿人类智能的方法。
?进化编程根据正确预测的符号数来度量适应值。
通过变异，为父代群体中的每个机器状态产生
一个子代。父代和子代中最好的部分被选择生
存下来。
?它的提出是受自然生物进化机制的启发。
17
5.3.1 进化编程的机理与表示
?进化编程的过程, 可理解为从所有可能
的计算机程序形成的空间中, 搜索具有
高的适应度的计算机程序个体 。
?进化编程设计强调群体行为的变化 。 进
化编程系统的表示自然地面向任务级 。
一旦选定一种适应性表示, 就可以定义
依赖于该表示的变异操作, 在具体的父
辈行为上创建后代 。
5.3 进化编程
18
5.3.2 进化编程的步骤
进化编程分为三个步骤：
?产生出初始群体 。
?迭代完成下述子步骤, 直至满足选种标准
为止：
?执行群体中的每个程序 。
?应用变异等操作创造新程序群体 。
?在后代中适应值最高的计算机程序个体被
指定为进化编程的结果 。
5.3 进化编程
19
变异和创造子代
评估已存在的 FSM
用最好的状态机
预测和添加符号
选择父代
初始化观测顺序
是
否是否预测
初始化群体
图 5.6 进化编程的基本过程
5.3 进化编程
20
5.4 人工生命
?自然界是生命之源。自然生命千千万万，
千姿百态，千差万别，巧夺天工，奇妙无
穷。
?人工生命（ Artificial Life,AL）试图通过
人工方法建造具有自然生命特征的人造系
统。
?人工生命是生命科学、信息科学和系统科
学等学科交叉研究的产物，其研究成果必
将促进人工智能的发展。
21
5.4.1 人工生命研究的起源和发展
?人类长期以来一直力图用科学技术方法模拟自
然界，包括人脑本身。 1943年麦卡络奇和皮茨
提出了 M－ P神经学网络模型。
?人工生命的许多早期研究工作也源于人工智能。
?20世纪 70年代以来，康拉德（ Conrad）等提出
不断完善的, 人工世界, 模型。
?80年代
?90年代
5.4 人工生命
22
5.4.2 人工生命的定义和研究意义
?人工生命是一项抽象地提取控制生物现
象的基本动态原理，并且通过物理媒介
（如计算机）来模拟生命系统动态发展
过程的研究工作。
?通俗地讲，人工生命即人造的生命，非
自然的生命。然而，要对人工生命做出
严格的定义，却需要对问题进行深入研
究。
5.4 人工生命
23
人工生命系统
?1987年兰德提出的人工生命定义为：, 人
工生命是研究能够演示出自然生命系统特
征行为的人造系统, 。
?通过计算机或其它机器对类似生命的行为
进行综合研究，以便对传统生物科学起互
补作用。
?兰德在计算机上演示了他们研制的具有生
命特征的软件系统，并把这类具有生命现
象和特征的人造系统称为人工生命系统。
5.4 人工生命
24
自然生命的共同特征和现象
?自繁殖、自进化、自寻优
?自成长、自学习、自组织
?自稳定、自适应、自协调
?物质构造
?能量转换
?信息处理
5.4 人工生命
25
研究人工生命的意义
?人工生命是自然生命的模拟、延伸与扩
展，其研究开发有重大的科学意义和广
泛的应用价值。
?开发基于人工生命的工程技术新方法、新
系统、新产品
?为自然生命的研究提供新模型、新工具、
新环境
?延伸人类寿命、减缓衰老、防治疾病
?扩展自然生命，人工进化、优生优育
?促进生命、信息、系统科学的交叉与发展
5.4 人工生命
26
5.4.3 人工生命的研究内容和方法
1,人工生命的研究内容
人工生命的研究内容大致可分为两类：
(1) 构成生物体的内部系统, 包括脑, 神
经系统, 内分泌系统, 免疫系统, 遗传
系统, 酶系统, 代谢系统等 。
(2) 在生物体及其群体的外部系统, 包括
环境适应系统和遗传进化系统等 。
5.4 人工生命
27
人工生命的科学框架
?生命现象仿生系统
?生命现象的建模与仿真
?进化动力学
?人工生命的计算理论和工具
?进化机器人
?进化和学习等的结合
?人工生命的应用
5.4 人工生命
28
2,人工生命的研究方法
（ 1） 信息模型法
根据内部和外部系统所表现的生命行
为来建造信息模型 。
（ 2） 工作原理法
生命行为所显示的自律分数和非线性
行为, 其工作原理是混沌和分形, 以此
为基础研究人工生命的机理 。
5.4 人工生命
29
人工生命的研究技术途径
(1) 工程技术途径
利用计算机、自动化、微电子、精密
机械、光电通信、人工智能、神经网络
等有关工程技术方法和途径，研究开发、
设计制造人工生命。通过计算机屏幕，
以三维动画，虚拟现实的软件方法或采
用光机电一体化的硬件装臵来演示和体
现人工生命。
5.4 人工生命
30
(2) 生物科学途径
?利用生物科学方法和技术，通过人工合
成、基因控制，无性繁殖过程，培育生
成人工生命。
?由于伦理学、社会学、人类学等方面的
问题，通过生物科学途径生成的人工生
命，如克隆人引起了不少争论。需要研
究和制订相应的社会监督、国家法律和
国际公约。
5.4 人工生命
31
5.4.4 人工生命的实例
?人工脑
?波兰人工智能和心理学教授安奇 ·布勒
（ Andrzej Buller）及一些日本学者在日本
现代通讯研究所进化系统研究室对人工脑
的研究，已取得重要进展。
?计算机病毒
?计算机进程
?细胞自动机
?人工核苷酸
5.4 人工生命
32
5.5 小结
?进化计算
?遗传算法
?进化策略
?进化编程
?人工生命
?计算智能研究的最新领域之一
?重要科学意义和社会效益
?研究内容、发展前景和应用领域
进化计算
人工生命
2
?进化计算包括：
?遗传算法 (genetic algorithms,GA)
?进化策略 (evolution strategies)
?进化编程 (evolutionary rogramming)
?遗传编程 (genetic programming)
?人类不满足于模仿生物进化行为，希望能
够建立具有自然生命特征的人造生命和人
造生命系统。
?人工生命是人工智能和计算智能的一个新
的研究热点。
3
5.1 遗传算法
?遗传算法是模仿生物遗传学和自然选
择机理，通过人工方式所构造的一类
优化搜索算法，是对生物进化过程进
行的一种数学仿真，是进化计算的最
重要的形式。
?遗传算法为那些难以找到传统数学模
型的难题指出了一个解决方法。
?进化计算和遗传算法借鉴了生物科学
中的某些知识，这也体现了人工智能
这一交叉学科的特点。
4
5.1.1 遗传算法的基本机理
?霍兰德的遗传算法通常称为简单遗传算
法（ SGA）。现以此作为讨论主要对象，
加上适应的改进，来分析遗传算法的结
构和机理。
?编码与解码
?适应度函数
?遗传操作
5.1 遗传算法
5
5.1.2 遗传算法的求解步骤
1,遗传算法的特点
(1) 遗传算法是对参数集合的编码而非针对参数
本身进行进化；
(2) 遗传算法是从问题解的编码组开始而非从单
个解开始搜索；
(3) 遗传算法利用目标函数的适应度这一信息而
非利用导数或其它辅助信息来指导搜索；
(4) 遗传算法利用选择, 交叉, 变异等算子而不
是利用确定性规则进行随机操作 。
5.1 遗传算法
6
2,遗传算法的框图 (图 5.2)
(1) 初始化群体 ;
(2) 计算群体上每个个体的适应度值 ;
(3) 按由个体适应度值所决定的某个规则选
择将进入下一代的个体 ;
(4) 按概率 Pc进行交叉操作 ;
(5) 按概率 Pc进行突变操作 ;
(6) 若没有满足某种停止条件, 则转第 (2)步,
否则进入下一步 。
(7) 输出群体中适应度值最优的染色体作为问题的
满意解或最优解 。
5.1 遗传算法
7
初始化种群
变异操作
计算适应度值
选择操作
交叉操作
初始化种群
终止条件
开始
图 5.2 算法框图
5.1 遗传算法
8
一般遗传算法的主要步骤如下：
(1) 随机产生一个由确定长度的特征字
符串组成的初始群体 。
(2) 对该字符串群体迭代的执行下面的
步 ① 和 ②, 直到满足停止标准：
① 计算群体中每个个体字符串的适应值；
② 应用复制, 交叉和变异等遗传算子产生
下一代群体 。
(3) 把在后代中出现的最好的个体字符
串指定为遗传算法的执行结果, 这个
结果可以表示问题的一个解 。
5.1 遗传算法
9
产生初始群体
是否满足停止准则
计算每个个体的适应值
i=M?GEN:=GEN+1
依概率选择遗传操作
执行复制
选择一个个体
i:=i+1
选择两个个体 选择一个个体
执行变异
i:=0
GEN:=0
复制到新群体
i:=i+1
将两个后代插入新群体
插入到新群体执行杂交
指定结果
结束
是
否
是
否
变异复制 交叉
5.1 遗传算法
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 遗传算法
11
3,遗传算法求解举例
5.1 遗传算法
?设,用 SGA求
?参数设臵
?二进制编码
?种群大小为 4
?染色体长为 4位
)1ln ()( 2xxf ??
]15,0[),(m a x ?xxf
12
遗传算法归纳为五个基本组成部份
?方案表示
?群体初始化
?适应度函数
?遗传操作
?算法参数
5.1 遗传算法
13
5.2 进化策略
?进化策略 (Evolution Strategies,ES)是
一类模仿自然进化原理以求解参数优化
问题的算法。
?它是由雷切伯格（ Rechenberg）、施韦
费尔（ Schwefel）和彼得 ·比纳特
（ Peter Bienert）于 1964年提出的，并
在德国共同建立的。
14
5.2.1 进化策略的算法模型
?寻求与函数极值关联的实 n维矢量 x。
?随机选择父矢量的初始群体。
?父矢量 xi,i=1,…,p产生子代矢量 xi。
?对误差 (i=1,…,p)排序以选择和决定
保持哪些矢量。
?继续产生新的试验数据以及选择最小
误差矢量。
5.2 进化策略
15
5.2.2 进化策略和遗传算法的区别
?进化策略和遗传算法有着很强的相似性，
它们都是一类模仿自然进化原理的算法。
?两者也存在着区别，其中最基本的区别
是它们的研究领域不同。
?进化策略是一种数值优化的方法，它采用一
个具有自适应步长和倾角的特定爬山方法。
?遗传算法从广义上说是一种自适应搜索技术。
5.2 进化策略
16
5.3 进化编程
?进化编程 (Evolutionary Programming,EP)，
又称为进化规划（ Evolutionary Planning），
是由福格尔（ Fogel）在 1962年提出的一种模
仿人类智能的方法。
?进化编程根据正确预测的符号数来度量适应值。
通过变异，为父代群体中的每个机器状态产生
一个子代。父代和子代中最好的部分被选择生
存下来。
?它的提出是受自然生物进化机制的启发。
17
5.3.1 进化编程的机理与表示
?进化编程的过程, 可理解为从所有可能
的计算机程序形成的空间中, 搜索具有
高的适应度的计算机程序个体 。
?进化编程设计强调群体行为的变化 。 进
化编程系统的表示自然地面向任务级 。
一旦选定一种适应性表示, 就可以定义
依赖于该表示的变异操作, 在具体的父
辈行为上创建后代 。
5.3 进化编程
18
5.3.2 进化编程的步骤
进化编程分为三个步骤：
?产生出初始群体 。
?迭代完成下述子步骤, 直至满足选种标准
为止：
?执行群体中的每个程序 。
?应用变异等操作创造新程序群体 。
?在后代中适应值最高的计算机程序个体被
指定为进化编程的结果 。
5.3 进化编程
19
变异和创造子代
评估已存在的 FSM
用最好的状态机
预测和添加符号
选择父代
初始化观测顺序
是
否是否预测
初始化群体
图 5.6 进化编程的基本过程
5.3 进化编程
20
5.4 人工生命
?自然界是生命之源。自然生命千千万万，
千姿百态，千差万别，巧夺天工，奇妙无
穷。
?人工生命（ Artificial Life,AL）试图通过
人工方法建造具有自然生命特征的人造系
统。
?人工生命是生命科学、信息科学和系统科
学等学科交叉研究的产物，其研究成果必
将促进人工智能的发展。
21
5.4.1 人工生命研究的起源和发展
?人类长期以来一直力图用科学技术方法模拟自
然界，包括人脑本身。 1943年麦卡络奇和皮茨
提出了 M－ P神经学网络模型。
?人工生命的许多早期研究工作也源于人工智能。
?20世纪 70年代以来，康拉德（ Conrad）等提出
不断完善的, 人工世界, 模型。
?80年代
?90年代
5.4 人工生命
22
5.4.2 人工生命的定义和研究意义
?人工生命是一项抽象地提取控制生物现
象的基本动态原理，并且通过物理媒介
（如计算机）来模拟生命系统动态发展
过程的研究工作。
?通俗地讲，人工生命即人造的生命，非
自然的生命。然而，要对人工生命做出
严格的定义，却需要对问题进行深入研
究。
5.4 人工生命
23
人工生命系统
?1987年兰德提出的人工生命定义为：, 人
工生命是研究能够演示出自然生命系统特
征行为的人造系统, 。
?通过计算机或其它机器对类似生命的行为
进行综合研究，以便对传统生物科学起互
补作用。
?兰德在计算机上演示了他们研制的具有生
命特征的软件系统，并把这类具有生命现
象和特征的人造系统称为人工生命系统。
5.4 人工生命
24
自然生命的共同特征和现象
?自繁殖、自进化、自寻优
?自成长、自学习、自组织
?自稳定、自适应、自协调
?物质构造
?能量转换
?信息处理
5.4 人工生命
25
研究人工生命的意义
?人工生命是自然生命的模拟、延伸与扩
展，其研究开发有重大的科学意义和广
泛的应用价值。
?开发基于人工生命的工程技术新方法、新
系统、新产品
?为自然生命的研究提供新模型、新工具、
新环境
?延伸人类寿命、减缓衰老、防治疾病
?扩展自然生命，人工进化、优生优育
?促进生命、信息、系统科学的交叉与发展
5.4 人工生命
26
5.4.3 人工生命的研究内容和方法
1,人工生命的研究内容
人工生命的研究内容大致可分为两类：
(1) 构成生物体的内部系统, 包括脑, 神
经系统, 内分泌系统, 免疫系统, 遗传
系统, 酶系统, 代谢系统等 。
(2) 在生物体及其群体的外部系统, 包括
环境适应系统和遗传进化系统等 。
5.4 人工生命
27
人工生命的科学框架
?生命现象仿生系统
?生命现象的建模与仿真
?进化动力学
?人工生命的计算理论和工具
?进化机器人
?进化和学习等的结合
?人工生命的应用
5.4 人工生命
28
2,人工生命的研究方法
（ 1） 信息模型法
根据内部和外部系统所表现的生命行
为来建造信息模型 。
（ 2） 工作原理法
生命行为所显示的自律分数和非线性
行为, 其工作原理是混沌和分形, 以此
为基础研究人工生命的机理 。
5.4 人工生命
29
人工生命的研究技术途径
(1) 工程技术途径
利用计算机、自动化、微电子、精密
机械、光电通信、人工智能、神经网络
等有关工程技术方法和途径，研究开发、
设计制造人工生命。通过计算机屏幕，
以三维动画，虚拟现实的软件方法或采
用光机电一体化的硬件装臵来演示和体
现人工生命。
5.4 人工生命
30
(2) 生物科学途径
?利用生物科学方法和技术，通过人工合
成、基因控制，无性繁殖过程，培育生
成人工生命。
?由于伦理学、社会学、人类学等方面的
问题，通过生物科学途径生成的人工生
命，如克隆人引起了不少争论。需要研
究和制订相应的社会监督、国家法律和
国际公约。
5.4 人工生命
31
5.4.4 人工生命的实例
?人工脑
?波兰人工智能和心理学教授安奇 ·布勒
（ Andrzej Buller）及一些日本学者在日本
现代通讯研究所进化系统研究室对人工脑
的研究，已取得重要进展。
?计算机病毒
?计算机进程
?细胞自动机
?人工核苷酸
5.4 人工生命
32
5.5 小结
?进化计算
?遗传算法
?进化策略
?进化编程
?人工生命
?计算智能研究的最新领域之一
?重要科学意义和社会效益
?研究内容、发展前景和应用领域
