《高级人工智能第十五章进化理论107精编版》由会员分享，可在线阅读，更多相关《高级人工智能第十五章进化理论107精编版（108页珍藏版）》请在金锄头文库上搜索。
1、第十五章 进化计算,中科院计算所,2020/8/15,1,史忠植 高级人工智能,内 容,15.1 概述 15.2 进化系统理论的形式模型 15.3 达尔文进化算法 15.4 遗传算法 15.5 遗传算法的理论基础 15.6 遗传算法的改进 15.7 遗传机器学习分类器系统 15.8 桶链算法 15.9 规则发现系统 15.10 进化策略 15.11 进化规划,2020/8/15,2,史忠植 高级人工智能,15.1 概述,进化计算是通过模拟自然界中生物进化机制进行搜索的一种算法。,2020/8/15,3,史忠植 高级人工智能,发展历史,进化计算的研究起源于20世纪50年代。 1965年，Holl
2、and首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。 大约在同一时期： Rechenberg和Schwefel提出了进化策略。 Fogel提出了进化规划。,2020/8/15,4,史忠植 高级人工智能,发展历史,1967年，Bagley在他的论文中首次提出了遗传算法这一术语，并讨论了遗传算法在自动博弈中的应用。 1970年，Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是Hollstien。,2020/8/15,5,史忠植 高级人工智能,发展历史,1975年是遗传算法研究的历史上十分重要的一年。这一年，Holland出版了他的著名专著自然系
3、统和人工系统的适应性该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（schemata theory），该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。 同年，DeJong完成了他的重要论文遗传自适应系统的行为分析。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑，这是因为他把Holland的模式理论与他的计算使用结合起来。,2020/8/15,6,史忠植 高级人工智能,发展历史,1989 Goldberg对遗传算法从理论上，方法上和应用上作了系统的总结。 1990年，Koza提出了遗传程序设计（Genetic Progr
4、amming）的概念。（用于搜索解决特定问题的最适计算机程序）,2020/8/15,7,史忠植 高级人工智能,遗传算法与自然进化的比较,自然界,染色体,基因,等位基因(allele),染色体位置(locus),基因型(genotype),表型(phenotype),遗传算法,字符串,字符,特征,特征值,字符串位置,结构,参数集,译码结构,2020/8/15,8,史忠植 高级人工智能,新达尔文五进化理论的主要论点,个体是基本的选择目标; 随机过程在进化中起重大作用, 遗传变异大部分是偶然现象; 基因型变异大部分是重组的产物, 特别是突变; 逐渐进化可能与表型不连续有关; 不是所有表型变化都是自然
5、选择的必然结果; 进化是在适应中变化的, 形式多样, 不仅是基因的变化; 选择是概率型的, 而不是决定型的。,2020/8/15,9,史忠植 高级人工智能,进化计算的三大主流板块,Holland提出的遗传算法(Genetic Algorithm)。 Rechenberg和Schwefel提出的进化策略(Evolutionary Strategies)。 Fogel提出的进化规划(Evolutionary Programming)，又称为进化程序设计。 本章将着重介绍遗传算法，对进化策略和进化规划只作简单介绍。,2020/8/15,10,史忠植 高级人工智能,15.2 进化系统理论的形式模型,进
6、化在个体群体中起作用。瓦铤顿(Waddington)指出基因型和表型之间关系的重要性(Waddington 1974)。群体禁止异构环境。但是“后生环境”是多维空间。表型是基因型和环境的产物。然后表型通过异构“选择环境发生作用。注意，这种多维选择环境与后生环境空间是不同的。现在，适应性是表型空间和选择环境空间的产物。它经常被取作一维，表示多少子孙对下一代作出贡献。 基于这种想法，莫楞贝(Muhlenbein) 和肯德曼 (Kindermann)提出了一种称为进化系统理论的形式模型(Muhlenbein 1989)。,2020/8/15,11,史忠植 高级人工智能,进化系统理论的形式模型,进化的
7、主要过程,后生环境,遗传操作符,选择环境,g,p,2020/8/15,12,史忠植 高级人工智能,进化系统理论的形式模型,其中，g 是基因型 p 是表型。 基因gi的可能值称为等位基因。 在门德尔(Mendel)遗传学中，假设每个基因有有限数的等位基因。,2020/8/15,13,史忠植 高级人工智能,进化系统理论的形式模型,这个变换函数给出了模型，说明表型的发展是通过基 因与环境的交互作用。 变换过程是高度非线性的。,2020/8/15,14,史忠植 高级人工智能,进化系统理论的形式模型,质量函数q给出了具体选择环境ESi下表型的质量， 其定义如下：,质量定义适应度，用于达尔文选择。至今已有
8、三种具体范例的通用模型，即 门德尔遗传学 遗传生态学 进化配子,2020/8/15,15,史忠植 高级人工智能,门德尔遗传学,在门德尔遗传学中，基因型被详细模型化，而表型和 环境几乎被忽略。在遗传生态学中恰好相反。 进化配子论是从社会生物学导出的模型。,首先让我们讨论门德尔遗传学的选择模型。为了简单起见，我们假设一个基因具有n 等位基因a1,an。 二倍基因型以元组(ai,aj)为特征。 我们定义 pi,j 为总群体中基因型(ai,aj) 的频度。假设基因型与表型相等。质量函数给每个表型赋值。 q(ai,aj) = qi,j qi,j 可以被解释为出生率减去死亡率,2020/8/15,16,史
9、忠植 高级人工智能,门德尔遗传学,假设 pi,j是下一代表型(ai,aj) 的频度。然后达尔文 选择根据选择方程调整表型的分布:,是群体的平均适应度。,2020/8/15,17,史忠植 高级人工智能,门德尔遗传学,设 pi 是群体中等位基因的频率。如果 pi,j = pi pj 那么，我们得到在 GS中的一个选择方程为,2020/8/15,18,史忠植 高级人工智能,门德尔遗传学,这个离散的选择方程可以用连续方程近似:,如果 qi,j = qj,i, 那么,2020/8/15,19,史忠植 高级人工智能,门德尔遗传学,这个方程很容易被证明:,这个结果称作菲希尔(Fisher)基本定理。它说明平
10、均适应度随适应度的差别呈正比例增加。实际上，全部可能的基因型仅有一部分实现。这就是遗传操纵子探索基因型空间的任务，其个体数目相当小。这些操纵子是群体遗传变异性的来源。最重要的操纵子是突变和重组。,2020/8/15,20,史忠植 高级人工智能,15.3 达尔文进化算法,根据定量遗传学，达尔文进化算法采用简单 的突变/选择动力学。 达尔文算法的一般形式可以描述如下：,是一代的双亲数目， 为子孙数目。 整数 称作“混杂”数。 如果两个双亲混合他们的基因，则 = 2。仅 是最好的个体才允许产生子孙。 逗号表示双亲们没有选择，加号表示双亲有选择。,2020/8/15,21,史忠植 高级人工智能,15.
11、3 达尔文进化算法,建立原始种体。 通过突变建立子孙。 选择： 返回到步骤(1)。,2020/8/15,22,史忠植 高级人工智能,遗传算法思想来源于生物进化过程, 它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法(以字符串表示状态空间)。遗传算法用概率搜索过程在该状态空间中搜索，产生新的样本。,15.4 遗传算法,2020/8/15,23,史忠植 高级人工智能,遗传算法的特点,特点： 通用 鲁棒 次优解、满意解 遗传算法能解决的问题： 优化 NP完全 NP难 高度复杂的非线性问题,2020/8/15,24,史忠植 高级人工智能,遗传算法,遗传算法先将搜索结构编码为字符串形式
12、, 每个字符串结构被称为个体。 然后对一组字符串结构(被称为一个群体)进行循环操作。每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。 类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。,2020/8/15,25,史忠植 高级人工智能,遗传算法,与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。 在遗传算法中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体给予一个数值评价
13、，称为适应度，取消低适应度的个体，选择高适应度的个体参加操作。 常用的遗传算子有复制、杂交、变异和反转。,2020/8/15,26,史忠植 高级人工智能,遗传算法与传统优化算法的主要不同,遗传算法不是直接作用在参变量集上, 而是利用参变量集的某种编码; 遗传算法不是从单个点, 而是在群体中从一个点开始搜索; 遗传算法利用适应值信息, 无需导数或其它辅助信息; 遗传算法利用概率转移规则, 而非确定性规则。,2020/8/15,27,史忠植 高级人工智能,遗传算法的准备工作,确定表示方案; 确定适应值的度量; 确定控制该算法的参数和变量; 确定怎样指定结果及程序运行结束的标准。,2020/8/15
14、,28,史忠植 高级人工智能,基本遗传算法,基本遗传算法(Simple Genetic Algorithm:SGA)又称为简单遗传算法，只使用选择算子、交叉算子和变异算子这三种基本的遗传算子。其遗传操作简单、容易理解，是其它遗传算法的雏形和基础。 基本遗传算法的构成要素： 1、染色体编码方法：首先必须对问题的解空间进行编码，使之能用遗传算法进行操作。较常用的是二进制编码方法，现在使用非二进制编码的也逐渐增多。 2、适应度函数（fitness function，又称为适应值适值函数）用来评价一个染色体的好坏。,2020/8/15,29,史忠植 高级人工智能,基本遗传算法的构成要素,3、遗传算子
15、选择算子(selection) ：又称为复制算子。按照某种策略从父代中挑选个体进入下一代，如使用比例选择、轮盘式选择。 交叉算子(crossover)：又称为杂交算子。将从群体中选择的两个个体，按照某种策略使两个个体相互交换部分染色体，从而形成两个新的个体。如使用单点一致交叉。 变异算子(mutation)：按照一定的概率（一般较小），改变染色体中某些基因的值。,2020/8/15,30,史忠植 高级人工智能,杂交操作举例,1,0,2,2,0,2,0,1,No Offspring,Pt. of interchange Crossover,Parents,Offspring,1110#0#,1#
16、0111#,0001#11#,010#1000,#00#11,0#01#10#,#100100,100#0111,6,17,1,1110#11#,0001#0#,0001#11#,#00#11,#00#11,0#01#10#,000#0111,1#01#10#,2020/8/15,31,史忠植 高级人工智能,变异操作,简单的变异操作过程如下: 每个位置的字符变量都有一个变异概率, 各位置互相独立。通过随机过程选择发生变异的位置： 产生一个新结构 , 其中 是从对应位置 的字符变量的值域中随机选择的一个取值。 可以同样得到。,2020/8/15,32,史忠植 高级人工智能,反转操作,简单反转操作的步骤如下: 从当前群体中随机选择一个结构 从中随机选择两个数i和j, 并定义 i = mini,j, j=maxi,j; 颠倒a中位置i、j之间的部分, 产生新的结构,2020/8/15,33,史忠植 高级人工智能,基本遗传算法的构成要素,4、运行参数 N：群体大小，即群
