高级人工智能第十五章进化理论107

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