2-2计算智能技术-进化算法.ppt

演化计算
Clark Cao USTC
1
内容
概述
进化系统理论的形式模型
达尔文进化算法
遗传算法
遗传算法的理论基础
遗传算法的改进
进化策略
进化规划
2
1 概述
进化计算是通过模拟自然界中生物进化机制进行搜索的一种算法。
3
发展历史
进化计算的研究起源于20世纪50年代。
1965年,Holland首次提出了人工遗传操作的重要性,并把这些应用于自然系统和人工系统中。
大约在同一时期:
Rechenberg和Schwefel提出了进化策略。
Fogel提出了进化规划。
4
发展历史
1967年,Bagley在他的论文中首次提出了遗传算法这一术语,并讨论了遗传算法在自动博弈中的应用。
1970年,hio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是Hollstien。
5
发展历史
1975年是遗传算法研究的历史上十分重要的一年。这一年,Holland出版了他的著名专著《自然系统和人工系统的适应性》该书系统地阐述了遗传算法的基本理论和方法,并提出了对遗传算法的理论研究和发展极为重要的模式理论(schemata theory),该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。
同年,DeJong完成了他的重要论文《遗传自适应系统的行为分析》。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑,这是因为他把Holland的模式理论与他的计算使用结合起来。
6
发展历史
1989 Goldberg对遗传算法从理论上,方法上和应用上作了系统的总结。
1990年,Koza提出了遗传程序设计(ic Programming)的概念。(用于搜索解决特定问题的最适计算机程序)
7
遗传算法与自然进化的比较
自然界
染色体
基因
等位基因(allele)
染色体位置(locus)
基因型(genotype)
表型(phenotype)
遗传算法
字符串
字符,特征
特征值
字符串位置
结构
参数集,译码结构
8
新达尔文进化理论的主要论点
个体是基本的选择目标;
随机过程在进化中起重大作用, 遗传变异大部分是偶然现象;
基因型变异大部分是重组的产物, 特别是突变;
逐渐进化可能与表型不连续有关;
不是所有表型变化都是自然选择的必然结果;
进化是在适应中变化的, 形式多样, 不仅是基因的变化;
选择是概率型的, 而不是决定型的。
9
进化计算的三大主流板块
Holland提出的遗传算法(ic Algorithm)。
Rechenberg和Schwefel提出的进化策略(Evolutionary Strategies)。
Fogel提出的进化规划(Evolutionary Programming),又称为进化程序设计。
本章将着重介绍遗传算法,对进化策略和进化规划只作简单介绍。
10