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

《高级人工智能第十五章进化理论107.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十五章进化计算史忠植中科院计算所2021/7/251史忠植高级人工智能内容15.1概述15.2进化系统理论的形式模型15.3达尔文进化算法15.4遗传算法15.5遗传算法的理论基础15.6遗传算法的改进15.7遗传机器学习—分类器系统15.8桶链算法15.9规则发现系统15.10进化策略15.11进化规划2021/7/252史忠植高级人工智能15.1概述进化计算是通过模拟自然界中生物进化机制进行搜索的一种算法。2021/7/253史忠植高级人工智能发展历史进化计算的研究起源于20世纪50年代。1965年，Hol

2、land首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。大约在同一时期：Rechenberg和Schwefel提出了进化策略。Fogel提出了进化规划。2021/7/254史忠植高级人工智能发展历史1967年，Bagley在他的论文中首次提出了遗传算法这一术语，并讨论了遗传算法在自动博弈中的应用。1970年，Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是Hollstien。2021/7/255史忠植高级人工智能发展历史1975年是遗传算法研究的历史上十分重要的

3、一年。这一年，Holland出版了他的著名专著《自然系统和人工系统的适应性》该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（schematatheory），该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，DeJong完成了他的重要论文《遗传自适应系统的行为分析》。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑，这是因为他把Holland的模式理论与他的计算使用结合起来。2021/7/256史忠植高级人工智能发展历史1989Goldb

4、erg对遗传算法从理论上，方法上和应用上作了系统的总结。1990年，Koza提出了遗传程序设计（GeneticProgramming）的概念。（用于搜索解决特定问题的最适计算机程序）2021/7/257史忠植高级人工智能遗传算法与自然进化的比较自然界染色体基因等位基因(allele)染色体位置(locus)基因型(genotype)表型(phenotype)遗传算法字符串字符,特征特征值字符串位置结构参数集,译码结构2021/7/258史忠植高级人工智能新达尔文五进化理论的主要论点个体是基本的选择目标;随机过程在

5、进化中起重大作用,遗传变异大部分是偶然现象;基因型变异大部分是重组的产物,特别是突变;逐渐进化可能与表型不连续有关;不是所有表型变化都是自然选择的必然结果;进化是在适应中变化的,形式多样,不仅是基因的变化;选择是概率型的,而不是决定型的。2021/7/259史忠植高级人工智能进化计算的三大主流板块Holland提出的遗传算法(GeneticAlgorithm)。Rechenberg和Schwefel提出的进化策略(EvolutionaryStrategies)。Fogel提出的进化规划(EvolutionaryP

6、rogramming)，又称为进化程序设计。本章将着重介绍遗传算法，对进化策略和进化规划只作简单介绍。2021/7/2510史忠植高级人工智能15.2进化系统理论的形式模型进化在个体群体中起作用。瓦铤顿(Waddington)指出基因型和表型之间关系的重要性(Waddington1974)。群体禁止异构环境。但是“后生环境”是多维空间。表型是基因型和环境的产物。然后表型通过异构“选择环境"发生作用。注意，这种多维选择环境与后生环境空间是不同的。现在，适应性是表型空间和选择环境空间的产物。它经常被取作一维，表示多少

7、子孙对下一代作出贡献。基于这种想法，莫楞贝(Muhlenbein)和肯德曼(Kindermann)提出了一种称为进化系统理论的形式模型(Muhlenbein1989)。2021/7/2511史忠植高级人工智能进化系统理论的形式模型进化的主要过程后生环境遗传操作符选择环境gp2021/7/2512史忠植高级人工智能进化系统理论的形式模型其中，g是基因型p是表型。基因gi的可能值称为等位基因。在门德尔(Mendel)遗传学中，假设每个基因有有限数的等位基因。2021/7/2513史忠植高级人工智能进化系统理论的形式模

8、型这个变换函数给出了模型，说明表型的发展是通过基因与环境的交互作用。变换过程是高度非线性的。2021/7/2514史忠植高级人工智能进化系统理论的形式模型质量函数q给出了具体选择环境ESi下表型的质量，其定义如下：质量定义适应度，用于达尔文选择。至今已有三种具体范例的通用模型，即门德尔遗传学遗传生态学进化配子2021/7/2515史忠植高级人工智能门德尔遗传学在门德尔遗传