进化计算与遗传算法—人工智能课程讲解

《进化计算与遗传算法—人工智能课程讲解》由会员分享，可在线阅读，更多相关《进化计算与遗传算法—人工智能课程讲解（86页珍藏版）》请在金锄头文库上搜索。

1、1 第十二章 进化计算与遗传算法 徐从富 浙江大学人工智能研究所 2003年11月 2 本章主要参考文献： 1 陈国良, 王煦法 等. 遗传算法及其应用. 人民邮电出版社, 1996. 2 王正志, 薄涛. 进化计算. 国防科技大学出版社, 2000. 3 张颖, 刘艳秋. 软计算方法. 科学出版社, 2002. pp69-108. 4 史忠植. 高级人工智能. 科学出版社, 1998. pp249-270. 5 史忠植. 知识发现. 清华大学出版社, 2002. pp265-294. 6 Mitchell, T. M.著, 曾华军等译. 机器学习. 机械工业出版社, 2003. pp179-

2、196. 7 贺前华, 韦岗, 陆以勤. 基因算法研究进展. 电子学报, 1998, 26(10): 118-122, 103. 3 内容 12.1 概述 12.2 进化系统理论的形式模型 12.3 达尔文进化算法 12.4 分类器系统 12.5 桶链算法 12.6 遗传算法 12.7 并行遗传算法 12.8 分类器系统Boole 12.9 规则发现系统 12.10 进化策略 12.11 进化程序设计 4 12.1 概述 12.1.1 背景 人们对很多高度非线性问题的内部机理还很不清楚 ： 智能模拟 非线性优化 图像识别，等等。 要解决上述问题，就需要一些具有自组织、自适 应能力的大规模并行算

3、法，模拟生物或自然现象就 成为AI中的一种自然而又重要的研究方向。因此产 生了如下新方法： 人工神经网络 遗传算法、进化计算，等等。 5 生物进化的主要特点： 进化的结果非常复杂 进化的过程非常简单：繁殖、变异、竞争、选择 基于自然选择的软件设计方法解决传统方法中存 在的如下最大障碍：需要事先描述问题的全部特点， 并说明针对问题的特点，程序应采取的措施。 利用进化机理，人们可以“培育”程序，去解决那 些结构尚不清楚的问题。 12.1.1 背景（续） 6 遗传算法和进化计算的基本思想：来源于生物 进化过程, 它是基于进化过程中的信息遗传机制和优 胜劣汰的自然选择原则的搜索算法（以字符串表示 状态

4、空间）。遗传算法用概率搜索过程在该状态空 间中搜索，产生新的样本。 遗传算法和进化计算是一种通用的问题求解方 法，它采用某种编码技术来表示各种复杂的结构， 并将每个编码称为一个个体。算法维持一个一定数 目的编码集合，称为种群，并通过对种群中的每个 个体进行某些遗传操作（如变异、交叉、选择等） 来模拟进化过程，最终获得一些具有较高性能指标 的编码。 12.1.3 基本思想 7 发展历史 遗传算法的发展历史： 1965年，Holland首次提出了人工遗传操作 的重要性，并把这些应用于自然系统和人 工系统中。 1967年，Bagley在他的论文中首次提出了 遗传算法（Genetic Algorith

5、m，简称GA） 这一术语，并讨论了遗传算法在自动博弈 中的应用。 1970年，Cavicchio把遗传算法应用于模式 识别中。第一个把遗传算法应用于函数优 化的是Hollstien。 8 发展历史（续） 1975年是遗传算法研究的历史上十分重要的一年。这 一年，Holland出版了他的著名专著“Adaptation in Natural and Artificial Systems”(自然和人工系统的自 适应性)该书系统地阐述了遗传算法的基本理论和 方法，并提出了对遗传 算法的理论研究和发展极为重 要的模式理论论（Schemata Theory），该理论首次确认 了结构重组遗传 操作对于获得隐

6、并行性的重要性。 同年，DeJong完成了他的重要论文“An Analysis of the Behavior of a Class of Genetic Adaptive Systems”(遗遗 传传自适应应系统统的行为为分析)。他在该论文中所做的 研究工作可看作是遗传算法发展过程中的一个里程碑 ，这是因为他把Holland的模式理论与他自己的实验结 合起来。 9 发展历史（续） 1988年Mayr提出新达尔文进化理论。 1989年Goldberg对遗传 算法从理论、方法和应用上 作了系统的总结. 10 特 点 特点： 通用 鲁棒 次优解、满意解 遗传算法能解决的问题： 优化 NP完全问题

7、NP难解问题 高度复杂的非线性问题 11 进化计算和遗传算法的主要应用领域： 应用领域说 明 控制 规划 设计 组合优化 图像处理 信号处理 机器人 人工生命 瓦斯管道控制、防避导弹控制、机器人控制 生产规划、并行机任务分配 VLSI部局、通信网络设计、喷气发动机设计 TSP问题、背包问题、图划分问题 模式识别、特征抽取 滤波器设计 路径规划 生命的遗传进化 12 遗传算法与自然进化的比较 自然界 染色体 基因 等位基因(allele) 染色体位置(locus) 基因型(genotype) 表型(phenotype) 遗传算法 字符串 字符，特征 特征值 字符串位置 结构 参数集，译码结构 1

8、3 面向执行的学习系统 任务子系统 学习子系统 任务检测器 任务效应器 执行效应器执行检测器 14 新达尔文进化理论的主要论点 1) 个体是基本的选择目标; 2) 随机过程在进化中起重大作用, 遗传变异大 部分是偶然现象; 3) 基因型变异大部分是重组的产物, 特别是突 变; 4) 逐渐进化可能与表型不连续有关; 5) 不是所有表型变化都是自然选择的必然结 果; 6) 进化是在适应中变化的, 形式多样, 不仅是 基因的变化; 7) 选择是概率型的, 而不是决定型的。 15 12.2 进化系统理论的形式模型 进化在个体群体中起作用。1974年Waddington指 出基因型和表型之间关系的重要性

9、。群体禁止异构环 境。但是“后成环境”是多维空间。表型是基因型和环 境的产物。然后表型通过异构“选择环境”发生作用。 【注】：这种多维选择环境与后成环境空间是不 同的。现在，适应性是表型空间和选择环境空间的产 物。它经常被取作一维，表示多少子孙对下一代作出 贡献。 基于上述思想，1989年Muhlenbein和Kindermann 提出了一种称为进化系统理论的形式模型。 16 进化系统理论的形式模型 进化的主要过程 后生环境遗传操作符选择环境 gp 17 进化系统理论的形式模型 其中，g 是基因型 p 是表型 基因gi的可能值称为等位基因。 在门德尔(Mendel)遗传学中，假设每个基因有 有

10、限个等位基因。 18 进化系统理论的形式模型 这个变换函数给出了模型，说明表型的发展是通 过基因与环境的交互作用而实现的。 变换过程是高度非线性的。 19 进化系统理论的形式模型 质质量函数q给出了具体选择环 境ESi下表型的质量 ， 其定义如下： 质量函数定义适应应度，用于达尔文选择。目前主要 有三种通用模型，即 门门德尔遗传遗传 学 遗传遗传 生态态学 进进化配子 20 门德尔遗传学 在门门德尔遗传遗传 学中，基因型被详细模型化，而表 型和环境几乎被忽略；在遗传遗传 生态态学中恰好相反；进 化配子论是从社会生物学导出的模型。 首先，讨论门 德尔遗传学的选择模型。为简单 起见 ，假设一个基因

11、具有n个等位基因a1,an。二倍基因型以 元组(ai, aj)为特征。定义pi,j为总群体中基因型(ai, aj)的频频 度。假设基因型与表型相等。质量函数给每个表型赋值 。 q (ai, aj) = qi,j qi,j可被解释为出生率减去死亡率。 21 门德尔遗传学 假设 pi,j是下一代表型(ai, aj)的频度。然后达尔文 选择选择 根据选择方程调整表型的分布: 其中，Q是群体的平均适应度。 22 门德尔遗传学 设 pi 是群体中等位基因的频率。如果 pi,j = pi pj 那么，可得基因型空间GS中的一个选择方程为： 23 门德尔遗传学 这个离散的选择方程可以用连续方程近似: 如果

12、qi,j = qj,i, 那么这个离散的选择方程可以用连 续方程近似: 24 门德尔遗传学 这个方程很容易被证明: 这个结果称作Fisher基本定理。它说明平均适 应应度随适应应度的差别别呈正比例增加。实际上，全部 可能的基因型仅有一部分实现。这就是遗传遗传 操纵纵子 探索基因型空间的任务，其个体数目相当小。这些 操纵子是群体遗传变 异性的来源。最重要的操纵子 是突变和重组。 25 12.3 达尔文进化算法 根据定量遗传学，达尔文进化算法采用简单的突 变/选择动力学。达尔文算法的一般形式可以描述如 下： 其中， ：是一代的双亲数目， ：为子孙数目， ：称作“混杂”数，若双亲混合其基因，则 =

13、2。 【注】：仅当是最好的个体才允许产生子孙。 逗号“,”表示双亲们没有选择，加号“+”表 示双 亲有选择。 26 12.3 达尔文进化算法 1) 建立原始种体。 2) 通过突变建立子孙。 3) 选择： 4) 返回到步骤(1)。 27 12.4 分类器系统 Holland和他的同事提出了一种分类器系统的认 知模型,其中的规则不是规则集, 而是遗传算法操纵 的内部实体。 下图给出了分类器系统的一般结构, 它由三层动 作构成,即执行子系统、信用赋值子系统和发现子系 统。 28 分类器系统 （1）执执行子系统统处在最低层, 直接与环境进行交互。它 与专家系统相同,由产生式规则构成。但是, 它们是通过

14、消息 传传送,高度并行工作。这类规则 称作分类类器。 （2）分类器系统中的学习, 要求环境提供反馈, 确认所 希望的状态是否达到。系统将评价这些规则的有效性, 这些 活动 常常称作信用赋值赋值 。有些特定算法专门用来实现信用赋值, 例如, 桶链算法。 （3）最后一层层是发现发现 子系统统, 该该系统统必须产须产 生新的规则规则 , 取代当前用处处不大的规则规则 。通过过系统统累积积的经验产经验产 生规则规则 。系 统统根据适应值应值 , 使用遗传遗传 算法选择选择 、重组和取代规则。 29 分类器系统 分类器系统的一般结构 发现 遗传算法 信用赋值 桶链 执行 分类器系统 消息来自 输入接口

15、支付 消息送出 输出接口 （目标） 来自内部监控器的消息 30 分类器系统 分类器系统是平行执行、消息传递和基于规则的系统。 在简单的方案中,消息采用规定的字母, 全部为固定长度。 全部规则采用条件/动作形式。每个条件规定必须满足的 信息, 每个动作规定当条件满足时所发送的消息。 为了方便, 假设消息采用长度为l的二进制字符串 记录, 字符采用子集1, 0, #。 31 规则与消息 产生式规则：IF THEN 约定：条件的长度是固定的，用二进制数表示。 定义： If sj = 1 or sj = 0, then mj = sj If sj = #, then mj can be either 1 or 0. 32 规则与消息 满足要求的全部消息构成子集, 即每个子集是在消 息空间的一个超平面。分类器系统是由一组分类器 C1, C2, CN、一个消息表、输入接口、输出接 口构成。每部分的主要功能如下: (1) 输入接口将当前环境状态翻译成标准消息。 (2) 分类器根据规则, 规定系统处理消息的过程。 (3) 消息表包含当前全部消息。 (4) 输出接口将结果消息翻译成效应器动作, 修改环境