第四章：遗传算法精选课件.ppt

1、目 录n引言引言nGAGA的基本概念的基本概念DarwinDarwin进化论及进化系统模型进化论及进化系统模型MendelMendel的遗传学说的遗传学说GAGA的基本概念与术语的基本概念与术语nGAGA的原理的原理GAGA的目的的目的GAGA的基本原理的基本原理GAGA的算法过程的算法过程目 录nGAGA的应用的应用GAGA的特点的特点GAGA应用的关键应用的关键GAGA在函数优化中的应用在函数优化中的应用GAGA在组合优化中的应用在组合优化中的应用nGAGA的理论分析的理论分析nGAGA在智能控制中的应用在智能控制中的应用nGAGA的发展展望的发展展望n参考文献参考文献4.1 4.1 引言

2、引言n生物的进化是一个奇妙的优化过程生物的进化是一个奇妙的优化过程,它通过选择淘它通过选择淘汰汰,突然变异突然变异,基因遗传等规律产生适应环境变化的基因遗传等规律产生适应环境变化的优良物种优良物种.例如例如,在人类的进化过程中在人类的进化过程中,通过通过“物竞天择、适者生存物竞天择、适者生存”自然的选择和淘汰自然的选择和淘汰,人类的身、心不断得到进化人类的身、心不断得到进化,逐渐进逐渐进化成为这地球上的具有最高等智慧的主宰者化成为这地球上的具有最高等智慧的主宰者.在这个进化过程中在这个进化过程中,不仅人的身体得到进化不仅人的身体得到进化,而且而且人的智人的智慧、智能慧、智能也在得到进化也在得到

3、进化.因此因此,生物的进化过程其实也是一种智能的进化、优化生物的进化过程其实也是一种智能的进化、优化过程过程,也是一种智能行为也是一种智能行为.“.“物竞天择、适者生存物竞天择、适者生存”中蕴中蕴涵了智能的光辉、蕴涵了优化的思想涵了智能的光辉、蕴涵了优化的思想.n遗传算法遗传算法(Genetic Algorithm,GA)(Genetic Algorithm,GA)就是根据生物进就是根据生物进化思想而启发得出的一种智能理论和方法化思想而启发得出的一种智能理论和方法.它是基于进化过程中的信息遗传机制和优胜劣汰的自然它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法选择原则的搜索算

4、法,是通过对生物进化的归纳和模拟得是通过对生物进化的归纳和模拟得到的一种仿生算法到的一种仿生算法.GAGA在本质上是一种不依赖具体问题的直接搜索方法在本质上是一种不依赖具体问题的直接搜索方法,是一是一种具有普适性的优化方法种具有普适性的优化方法.nGAGA的发展历程为的发展历程为:19651965年年,Michigan,Michigan大学的大学的HollandHolland首次提出了人工遗传操首次提出了人工遗传操作的重要性作的重要性,并把这些应用于自然系统和人工系统中并把这些应用于自然系统和人工系统中.19671967年在他的论文中首次提出了年在他的论文中首次提出了GAGA这一术语与概念这一

5、术语与概念,并并讨论了讨论了GAGA在自动博弈中的应用在自动博弈中的应用.4.1 4.1 引言引言19701970年年,Cavicchio,Cavicchio把把GAGA应用于模式识别中应用于模式识别中.第一个把第一个把GAGA应用于函数优化的是应用于函数优化的是Hollstien.Hollstien.而而GAGA的理论和方法的系统性研究开始于的理论和方法的系统性研究开始于19751975年年,这一开创性工作是由所实行这一开创性工作是由所实行.n这一年是这一年是GAGA研究的历史上十分重要的一年研究的历史上十分重要的一年.nHollandHolland在他的著名专著在他的著名专著Adaptat

6、ion in Natural Adaptation in Natural and Artificial Systemsand Artificial Systems中系统地阐述了中系统地阐述了GAGA的基的基本理论和方法本理论和方法,并提出了对并提出了对GAGA的理论研究和发展极为的理论研究和发展极为重要的模式理论重要的模式理论(schemata theory).(schemata theory).n该理论首次确认了结构重组遗传操作对于获得隐并该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性行性的重要性.4.1 4.1 引言引言同年同年,DeJong,DeJong完成了他的重要论文完成了

7、他的重要论文遗传自适应遗传自适应系统的行为分析系统的行为分析.n他在该论文中所做的研究工作可看作是他在该论文中所做的研究工作可看作是GAGA发展过程发展过程中的一个里程碑中的一个里程碑,这是因为他把这是因为他把HollandHolland的模式理论的模式理论与他的计算使用结合起来与他的计算使用结合起来.19891989年年GoldbergGoldberg对对GAGA从理论上从理论上,方法上和应用上方法上和应用上作了系统的总结作了系统的总结.19901990年代以来年代以来,以以GAGA为代表的进化类算法及计算为代表的进化类算法及计算智能理论和算法得到极大重视智能理论和算法得到极大重视.1994

8、.1994年在美国召年在美国召开了第一届世界计算智能大会开了第一届世界计算智能大会,欣起了进化类算欣起了进化类算法研究和应用的热潮法研究和应用的热潮.4.1 4.1 引言引言nGAGA与其它优化方法相比与其它优化方法相比,具有如下特点具有如下特点:GAGA不是直接作用在参变量集上不是直接作用在参变量集上,而是利用参变而是利用参变量集的某种编码量集的某种编码;GAGA不是从单个点不是从单个点,而是在群体中从多个点开始而是在群体中从多个点开始搜索搜索;GAGA利用适应值信息利用适应值信息,无需导数或其它辅助信息无需导数或其它辅助信息;n因此对优化问题因此对优化问题(函数函数)的限制较弱的限制较弱,

9、灵活灵活,通用性通用性(普普适性适性)强强,有着较广泛的应用领域有着较广泛的应用领域.GAGA利用概率转移规则利用概率转移规则,而非确定性规则而非确定性规则.GAGA在解空间内不是盲目的穷举或完全随机测试，在解空间内不是盲目的穷举或完全随机测试，而是一种启发式搜索，效率优于其它算法。而是一种启发式搜索，效率优于其它算法。4.1 4.1 引言引言nGAGA的优点的优点:较容易的和其它方法结合较容易的和其它方法结合避免陷入局部最优解避免陷入局部最优解n即使在较短的有限时间内即使在较短的有限时间内,也能获得较好的次优解、也能获得较好的次优解、满意解满意解.鲁棒性佳鲁棒性佳n对优化问题的初始条件对优化

10、问题的初始条件(状态状态)依赖性小。依赖性小。n 抗干扰性强。抗干扰性强。具有并行计算的特点，可提高计算速度具有并行计算的特点，可提高计算速度4.1 4.1 引言引言nGAGA的不足的不足:No guarantee for optimal solution within No guarantee for optimal solution within finite timefinite timeWeak theoretical basisWeak theoretical basisnGAGA能解决的问题能解决的问题:优化优化NPNP完全完全高度复杂的非线性问题高度复杂的非线性问题4.1 4.1

11、 引言引言n近年近年,GA,GA在各应用领域中得到极大重视在各应用领域中得到极大重视,并广泛应用并广泛应用于各领域的优化、搜索、问题求解中于各领域的优化、搜索、问题求解中,并在并在模式识别、模式识别、NNNN、图像处理、图像处理、机器学习、机器学习、工业优化控制、工业优化控制、自适应控制、自适应控制、生物科学、生物科学、社会科学社会科学等方面都得到应用等方面都得到应用.4.1 4.1 引言引言n当前在当前在AIAI研究中研究中,人们认为人们认为“GAGA、自适应系、自适应系统、细胞自动机、混沌理论与统、细胞自动机、混沌理论与AIAI一样一样,都是都是对今后十年的计算技术有重大影响的关键对今后十

12、年的计算技术有重大影响的关键技术技术”.4.1 4.1 引言引言4.2 GA4.2 GA的基本概念的基本概念nGAGA的基本思想是基于达尔文的基本思想是基于达尔文(Darwin)(Darwin)进化论进化论和门德尔和门德尔(Mendel)(Mendel)的遗传学说的的遗传学说的,下面将分别下面将分别介绍介绍:DarwinDarwin进化论及进化系统模型进化论及进化系统模型MendelMendel的遗传学说的遗传学说GAGA的基本概念与术语的基本概念与术语4.2.1 Darwin4.2.1 Darwin进化论及进化系统模型进化论及进化系统模型Charles DarwinAll environme

13、nts have All environments have finite resources(i.e.,finite resources(i.e.,can only support a limited can only support a limited number of individuals)number of individuals)它认为每一物种在发展中越来它认为每一物种在发展中越来越适应环境越适应环境.nDarwin(Darwin(1809-1882,1809-1882,Father Father o of f the evthe evololutiutio on then th

14、eo oryry)进化论最进化论最重要的是重要的是适者生存适者生存(Survival of(Survival of the fittest)the fittest)原理原理.物种每个个体的基本特征由后代所继承物种每个个体的基本特征由后代所继承,但后代但后代又会产生一些异于父代的新变化又会产生一些异于父代的新变化.在环境变化时在环境变化时,只有那些能适应环境的个体特征只有那些能适应环境的个体特征方能保留下来方能保留下来.4.2.1 Darwin4.2.1 Darwin进化论及进化系统模型进化论及进化系统模型4.2.1 Darwin4.2.1 Darwin进化论及进化系统模型进化论及进化系统模型生

15、物进化过程生物进化过程(循环图循环图):):初始群体淘汰体竞争初始种群繁殖变异新的群体GA从串集开始搜索,覆盖面大,利于全局择优,具有较好的全局性.这样,一代一代地进化,最后就会收敛到最适应环境的一个“染色体”上,它就是问题的最优解.每个串根据适应值的大小获得不同的复制概率。其相应的算法如下所示.3 GA在函数优化中的应用变异概率Pm与生物变异极小的情况一致,所以,Pm的取值较小,一般取0.3 GA的基本概念与术语(3)GA自身参数设定3 GA在函数优化中的应用S2 Stearns,Steven C and Hoekstra,Rolf.遗传算法可以用于神经网络的设计。基因位置是指一个基因在串中

16、的位置,有时也简称基因位.由于在选择用于繁殖下一代的个体时,是根据个体对环境的适应度而决定其繁殖量的,故而有时也称为非均匀再生(differential reproduction).bi0,1L (1)都取得巨大成就,成为近年在智能理论与优化理论领域的一个非常重要的方法,促进了智能理论与优化理论领域的发展.n自自DarwinDarwin以来的新进化学说强调以来的新进化学说强调:个体是基本的选择目标个体是基本的选择目标;随机过程在进化中起重大作用随机过程在进化中起重大作用,遗传变异大部分遗传变异大部分是偶然现象是偶然现象;进化是在适应中变化的进化是在适应中变化的,形式多样形式多样,不仅是基因不仅

17、是基因的变化的变化;选择是概率型的选择是概率型的,而不是决定型的而不是决定型的.4.2.1 Darwin4.2.1 Darwin进化论及进化系统模型进化论及进化系统模型4.2.2 Mendel4.2.2 Mendel遗传学说遗传学说Gregor Mendel它认为遗传以密码方式它认为遗传以密码方式存在细胞中存在细胞中,并以基因形并以基因形式包含在染色体内式包含在染色体内.每个基因有特殊的位置每个基因有特殊的位置并控制某种特殊性质并控制某种特殊性质;所所以以,每个基因产生的个体每个基因产生的个体对环境具有某种适应性对环境具有某种适应性.nMendel(Mendel(1822-1884,1822-

18、1884,Father Father o of genetics)f genetics)遗传学说最重遗传学说最重要的是要的是基因遗传原理基因遗传原理.4.2.2 Mendel4.2.2 Mendel遗传学说遗传学说基因突变和基因杂交可产生更适应于环境的后基因突变和基因杂交可产生更适应于环境的后代代.经过存优去劣的自然淘汰经过存优去劣的自然淘汰,适应性高的基因结适应性高的基因结构得以保存下来构得以保存下来.4.2.3 GA4.2.3 GA的基本概念与术语的基本概念与术语n基于达尔文的进化论与孟德尔的遗传学说基于达尔文的进化论与孟德尔的遗传学说,可可得到如下生物进化的原则得到如下生物进化的原则生物

19、进化过程的发生需要四个基本条件生物进化过程的发生需要四个基本条件:n存在由多个生物个体组成的种群存在由多个生物个体组成的种群;n生物个体之间存在着差异生物个体之间存在着差异,或群体具有多样性或群体具有多样性;n生物能够自我繁殖生物能够自我繁殖;n不同个体具有不同的环境生存能力不同个体具有不同的环境生存能力,具有优良基因结具有优良基因结构的个体繁殖能力强构的个体繁殖能力强,反之则弱反之则弱.4.2.3 GA4.2.3 GA的基本概念与术语的基本概念与术语生物群体的进化机制包括三种基本形式生物群体的进化机制包括三种基本形式:n自然选择自然选择 n杂交杂交n突变突变n另外另外,外界对生物的评价反映了

20、生物的生存价值和机外界对生物的评价反映了生物的生存价值和机会会.受到生物进化过程的启迪受到生物进化过程的启迪,模拟生物进化模拟生物进化的优化方法的优化方法GAGA得到重视并迅速发展得到重视并迅速发展.4.2.3 GA4.2.3 GA的基本概念与术语的基本概念与术语n由于由于GAGA是由进化论和遗传学机理而产生的直是由进化论和遗传学机理而产生的直接搜索优化方法接搜索优化方法,故而在这个算法中要用到各故而在这个算法中要用到各种进化和遗传学的概念种进化和遗传学的概念.这些概念如下这些概念如下:n串串n群体群体n群体规模群体规模n基因与基因位置基因与基因位置n基因特征值基因特征值n适应度适应度4.2.

21、3 GA4.2.3 GA的基本概念与术语的基本概念与术语A.A.串串(String)(String)它是个体它是个体(Individual)(Individual)的基因表示形式的基因表示形式,本质为本质为如何表示解如何表示解.在算法中常采用给定长度的二进制串在算法中常采用给定长度的二进制串,其特点操其特点操作简便作简便.根据具体问题也可采用特定的适宜于问题处理根据具体问题也可采用特定的适宜于问题处理的编码方式的编码方式,如如n实数编码实数编码nD D进制进制,D D=3,8,16,=3,8,16,n序列编码序列编码:例如例如TSPTSP的路径表达的路径表达n自适应编码自适应编码-长度可调节长

22、度可调节4.2.3 GA4.2.3 GA的基本概念与术语的基本概念与术语B.B.群体群体(Population)(Population)个体的集合称为群体个体的集合称为群体,串是群体的元素串是群体的元素.nA population A population is a set is a set of possible solutions.of possible solutions.GAGA之所以具有良好的优化性能和智能行为之所以具有良好的优化性能和智能行为,除开除开交叉和变异等遗传操作具有独到的优化能力交叉和变异等遗传操作具有独到的优化能力,正正是由于其优化过程是针对群体而非仅仅针对单是由于其优

23、化过程是针对群体而非仅仅针对单个个体进行个个体进行.对群体的优化除保证子代群体能够继承父代群对群体的优化除保证子代群体能够继承父代群体的优势特征之外体的优势特征之外,重要的其在一定程度上保证重要的其在一定程度上保证所搜索到的解具有某种全局性所搜索到的解具有某种全局性.群体进化行为在一定程度上可避免个体进化和群体进化行为在一定程度上可避免个体进化和优化的局部性、非单调性等优化的局部性、非单调性等.4.2.3 GA4.2.3 GA的基本概念与术语的基本概念与术语C.C.群体规模群体规模(Population Size)(Population Size)群体规模指群体中个体的数量群体规模指群体中个体

24、的数量.由于由于GAGA的优化是针对群体进行的的优化是针对群体进行的,因此群体规模因此群体规模是非常重要的一个参数是非常重要的一个参数Many researchers suggest population sizes Many researchers suggest population sizes between 25 and 100.between 25 and 100.4.2.3 GA4.2.3 GA的基本概念与术语的基本概念与术语D.D.基因基因(Gene)(Gene)与基因位置与基因位置(Gene Position)(Gene Position)基因基因是串中的元素是串中的元素,基因

25、用于表示个体的特征基因用于表示个体的特征.基因位置基因位置是指一个基因在串中的位置是指一个基因在串中的位置,有时也简有时也简称基因位称基因位.n基因位置对应于遗传学中的地点基因位置对应于遗传学中的地点(Locus).(Locus).例如有一个串例如有一个串S=1011,S=1011,则其中的则其中的1,0,1,11,0,1,1这这4 4个元个元素分别称为基因素分别称为基因.n基因位置由串的左向右计算基因位置由串的左向右计算,例如在串例如在串S=1011S=1011中中,0,0的的基因位置是基因位置是2.2.4.2.3 GA4.2.3 GA的基本概念与术语的基本概念与术语E.E.基因特征值基因特

26、征值(Gene Feature)(Gene Feature)在用串表示整数时在用串表示整数时,基因的特征值与二进制数的基因的特征值与二进制数的权一致权一致;例如在串例如在串S=1011S=1011中中,基因位置基因位置3 3中的中的1,1,它的基因它的基因特征值为特征值为2;2;基因位置基因位置1 1中的中的1,1,它的基因特征值为它的基因特征值为8.8.4.2.3 GA4.2.3 GA的基本概念与术语的基本概念与术语F.F.适应度适应度(Fitness)(Fitness)表示某一个体对于环境的适应程度表示某一个体对于环境的适应程度,是是GAGA进行优进行优化的指标函数化的指标函数.在优化过程

27、中在优化过程中,通过适应度可以进行个体优劣的通过适应度可以进行个体优劣的比较比较,可以进行个体的筛选可以进行个体的筛选,以产生子代群体以产生子代群体,或或选择个体参加交叉和变异等遗传操作选择个体参加交叉和变异等遗传操作.一般一般,适应度函数定义为适应度函数定义为0,10,1之间的实数之间的实数.n适应度函数值越大适应度函数值越大,表示该个体越适应环境表示该个体越适应环境(问题问题),),就越优就越优.n因此因此GAGA是对适应度函数求极大优化是对适应度函数求极大优化.4.2.3 GA4.2.3 GA的基本概念与术语的基本概念与术语nGAGA还有一些其它的概念还有一些其它的概念,这些概念在介绍这

28、些概念在介绍GAGA的的原理和执行过程时原理和执行过程时,再进行说明再进行说明.4.3 GA4.3 GA的原理的原理nGAGA把问题的解表示成把问题的解表示成“染色体染色体”,在算法中也在算法中也即是以二进制编码的串即是以二进制编码的串.并且并且,在执行在执行GAGA之前之前,给出一群给出一群“染色体染色体”,也即也即是假设解是假设解.然后然后,把这些假设解置于问题的把这些假设解置于问题的“环境环境”中中,并并按适者生存的原则按适者生存的原则,从中选择出较适应环境的从中选择出较适应环境的“染色体染色体”进行复制进行复制,再通过交叉再通过交叉,变异过程产变异过程产生更适应环境的新一代生更适应环境

29、的新一代“染色体染色体”群群.这样这样,一代一代地进化一代一代地进化,最后就会收敛到最适应最后就会收敛到最适应环境的一个环境的一个“染色体染色体”上上,它就是问题的最优解它就是问题的最优解.4.3 GA4.3 GA的原理的原理n下面分别介绍下面分别介绍:GAGA的目的的目的GAGA的基本原理的基本原理GAGA的算法过程的算法过程4.3.1 GA4.3.1 GA的目的的目的n典型的遗传算法典型的遗传算法(canonical genetic algorithm,CGA)通常用于解决下面这一类的静态最优化问题通常用于解决下面这一类的静态最优化问题:考 虑 对 于 一 群 长 度 为考 虑 对 于 一

30、 群 长 度 为 L 的 二 进 制 编 码的 二 进 制 编 码bi,i=1,2,n;有有bi0,1L (1)给定目标函数给定目标函数f,有有f(bi),并且并且0f(bi)0)和ci(0)(i=1,2,n)，背包的总容量假设为v(v0)，如何选择哪些物品装入背包使得所装物品价值最大？该问题的模型可表示为如下的0-1规划问题：n背包问题是个典型的NP完全问题，目前还不存在多项式时间的算法。1211max(,).0,1,1,2,nniiiiniiif x xxc xst xinw xv4.4.4 GA4.4.4 GA在组合优化中的应用在组合优化中的应用n编码格式：例如x=1100000000表

31、示仅装第1和第2种物品n适应度度量：n选择算子：赌盘选择（与适应值成比例选择）n交叉算子：混合单点交叉n变异算子：混合点变异n进化参数：种群规模，终止进化代数，交叉概率，变异概率=50，500，0.0512|0,1,1,2,nniHxx xxxin1()niiif xc x4.4.4 GA4.4.4 GA在组合优化中的应用在组合优化中的应用4.4.4 GA4.4.4 GA在组合优化中的应用在组合优化中的应用n其它如其它如8 8皇后问题皇后问题,即即在在n n*n n格的国际象棋棋格的国际象棋棋盘上放置盘上放置n n个皇后个皇后,使使得任意两个皇后不能得任意两个皇后不能互相攻击互相攻击,即任何行

32、、即任何行、列、对角线上不得有列、对角线上不得有两个或两个以上的皇两个或两个以上的皇后后.n这样的格局称为问题这样的格局称为问题的一个解的一个解.4.4.4 GA4.4.4 GA在组合优化中的应用在组合优化中的应用n还有前面提到得还有前面提到得TSPTSP组合优化问题。注意组合优化问题。注意非法解的解决。非法解的解决。A B C D E F J H G J 4.5 GA4.5 GA的理论分析的理论分析q GAGA源于自然选择和生物遗传学源于自然选择和生物遗传学,相对于其鲜明的生物相对于其鲜明的生物基础基础,GA,GA的理论基础公认是不完善的的理论基础公认是不完善的.GAGA的基础理论主要以收敛

33、性分析为主的基础理论主要以收敛性分析为主,即群体收即群体收敛到优化问题的全局最优解的概率敛到优化问题的全局最优解的概率.理论分析主要是基于模式理论的收敛性分析理论分析主要是基于模式理论的收敛性分析,称称之为之为GAGA的进化动力学理论的进化动力学理论.4.5 GA4.5 GA的理论分析的理论分析 n基于某种具体运算形式的基于某种具体运算形式的GAGA的进化行为分析的进化行为分析构成了进化动力学理论的基本内容构成了进化动力学理论的基本内容.由由HollandHolland提出的模式提出的模式(Schema,(Schema,又译图式又译图式)定理可定理可以称为以称为GAGA进化动力学的基本定理进化

34、动力学的基本定理.模式定理构成了求解优化问题时模式定理构成了求解优化问题时GAGA具备发现全局具备发现全局最优解的充分条件最优解的充分条件,也是分析也是分析GAGA的进化行为的基本的进化行为的基本理论理论,也称为模式理论也称为模式理论.4.5 GA4.5 GA的理论分析的理论分析通过基于模式理论的进化动力学分析通过基于模式理论的进化动力学分析,我们我们可以发现可以发现GAGA所能求解的问题的范围所能求解的问题的范围,找出找出GAGA的不足之处的不足之处,进而可能对其进行改进进而可能对其进行改进.4.5 GA4.5 GA的理论分析的理论分析n遗传算法的理论基础是遗传算法的二进制表遗传算法的理论基

35、础是遗传算法的二进制表达式及模式的含义。达式及模式的含义。下面简单介绍模式的概念及模式定理下面简单介绍模式的概念及模式定理.它的有关内容如下它的有关内容如下:n模式概念模式概念n模式的阶和长度模式的阶和长度n复制对群体适应值的影响复制对群体适应值的影响n交叉对模式的影响交叉对模式的影响n变异对模式的影响变异对模式的影响nHollandHolland模式定理模式定理4.5 GA4.5 GA的理论分析的理论分析A.模式概念模式概念定义模式的好处是使我们容易描述串的相似性。一个基因串用符号集0,1,*表示,则称为一个模式;n其中*是通配符,可以是0或1.即模式是含有通配符(*)的一类字符串的通式表达

36、,例如:nH=1*0*是一个模式.n模式*10101110与以下两个字符串匹配:010101110 110101110n而模式 *1010110 与以下四个字符串匹配:010100110 010101110110100110 1101011104.5 GA4.5 GA的理论分析的理论分析B.模式的阶和长度模式的阶和长度模式中0和1的个数称为模式的阶,并用o(H)表示.模式中第1位数字(非通配符*)和最后位数字间的距离称为模式的长度,并用(H)表示.对于模式H=1*0*,有o(H)=2,(H)=4.n对于模式H=*0*1*0*,有o(H)=3,(H)=6.4.5 GA4.5 GA的理论分析的理论

37、分析C.复制对群体适应值的影响复制对群体适应值的影响假定在给定的时间步t,一个特定的模式s在群体P(t)中包含m个代表串,记为m=m(s,t)。首先,我们暂不考虑交叉和变异操作。n每个串根据适应值的大小获得不同的复制概率。n串i的复制概率为:njijfifp1)()(4.5 GA4.5 GA的理论分析的理论分析则在群体P(t+1)中,模式s的代表串的数量的期望值为:(,)(,)(,)(,1)(,)()()m s tnf s tf s tE m s tm s tf tf t 其中 (s,t)表示模式s在t时刻的所有代表串的适应值的均值,称为模式s的适应值。fn (t)表示群体P(t)中所有个体的

38、适应值的平均值。f上式表明,模式s的代表串的数目随时间增长的幅度正比于模式s的适应值与群体平均适应值的比值。n即:适应值高于群体平均值的模式在下一代的代表串数目将会增加,而适应值低于群体平均值的模式在下一代的代表串数目将会减少。4.5 GA4.5 GA的理论分析的理论分析假设模式的适应值为(1+c)(t),其中c是一个常数,则上式可写为:f1)1()0,()1(),()()()1(),()1,(tcsmctsmtftfctsmtsmEn上式表明,在平均适应值之上(之下)的模式,将会按指数增长(衰减)的方式被复制。4.5 GA4.5 GA的理论分析的理论分析n复制的结果并没有生成新的模式。复制的

39、结果并没有生成新的模式。因而因而,为了探索搜索空间中的未搜索部分为了探索搜索空间中的未搜索部分,需要需要利用交叉和变异操作。利用交叉和变异操作。下面分别探索交叉和变异对模式的影响。下面分别探索交叉和变异对模式的影响。4.5 GA4.5 GA的理论分析的理论分析D.交叉对模式的影响交叉对模式的影响考虑模式s1=“*1*0”和s2=“*10*”间的交叉,可以发现n交叉会改变模式的一部分,模式的长度越长,被破坏的概率越大。4.5 GA4.5 GA的理论分析的理论分析假定模式s在交叉后不被破坏的概率为ps,则:1)(1lsps若交叉概率为pc,则s不被破坏的概率为1)(1lsppcs所以,在考虑交叉时

40、,模式s在群体P(t+1)中的数目m(s,t+1)的期望值为:1)(1)(),(),()1,(lsptftsftsmtsmEc4.5 GA4.5 GA的理论分析的理论分析E.变异对模式的影响变异对模式的影响变异算子以概率pm随机地改变个体某一位的值。n只有当o(s)个确定位(即确定为0或1,而非通配符*)的值不被破坏时,模式s才不被破坏。模式s在变异后不被破坏的概率:()1o ssmppPm1,可近似地表示为1()smppo s 4.5 GA4.5 GA的理论分析的理论分析因此,考虑交叉和变异时,模式s在群体P(t+1)中的数目m(s,t+1)的期望值为()(,1)(,)()11()1()()

41、(,)1()1cmcmf sE m s tm s tfspp o slf ssm s tpp o slf上式忽略了一项较小的交叉相乘项。由此我们得到一个关于GA优化性能的重要定理-模式定理(Schema Theorem)。4.5 GA4.5 GA的理论分析的理论分析p HollandHolland模式定理模式定理 模式定理模式定理 低阶低阶,短长度短长度,高适应值的模式在群体高适应值的模式在群体遗传过程中将会按指数规律增加遗传过程中将会按指数规律增加.根据模式定理，随着遗传算法的再生、交叉、根据模式定理，随着遗传算法的再生、交叉、变异等操作一代接一代地进行，那些短的，低变异等操作一代接一代地进

42、行，那些短的，低阶的，高适应值的模式将越来越多，最后得到阶的，高适应值的模式将越来越多，最后得到的串即是这些模式的组合。因而可期望算法性的串即是这些模式的组合。因而可期望算法性能越来越得到改善，并最终向全局的最优点发能越来越得到改善，并最终向全局的最优点发展。展。遗传算法用于神经网络的权值优化：在神遗传算法用于神经网络的权值优化：在神经网络用于系统建模和控制时，它要利用神经网经网络用于系统建模和控制时，它要利用神经网络的函数估计及分类功能。设计神经网络的关键络的函数估计及分类功能。设计神经网络的关键是如何确定神经网络的结构和连接权系数。它实是如何确定神经网络的结构和连接权系数。它实质上也是一个

43、优化问题，其优化的目标是使得所质上也是一个优化问题，其优化的目标是使得所设计的神经网络功能具有尽可能好的函数估计及设计的神经网络功能具有尽可能好的函数估计及分类功能。遗传算法可以用于神经网络的设计。分类功能。遗传算法可以用于神经网络的设计。4.6 遗传算法在智能控制中的应用遗传算法在智能控制中的应用 将神经网络中所有神经元的连接权值编码成二进制将神经网络中所有神经元的连接权值编码成二进制码串或实数码串表示的个体，随机生成这些码串的初始码串或实数码串表示的个体，随机生成这些码串的初始群体，即可进行常规的遗传算法优化计算。群体，即可进行常规的遗传算法优化计算。每进行一代计算后，将码串解码为权值构成

44、新的神每进行一代计算后，将码串解码为权值构成新的神经网络，通过对所有训练样本进行计算得到神经网络输经网络，通过对所有训练样本进行计算得到神经网络输出的均方误差从而确定每个个体的适应度。经过若干代出的均方误差从而确定每个个体的适应度。经过若干代计算，神经网络将进化到误差全局最小。计算，神经网络将进化到误差全局最小。4.6 遗传算法在智能控制中的应用遗传算法在智能控制中的应用例例4.1 倒立摆的遗传神经网络控制。设被控对象为图示的单倒立摆倒立摆的遗传神经网络控制。设被控对象为图示的单倒立摆系统系统2222)(cos)(3/4(sin)(cossin)(mllmMdtdmlugmMdtdmMdtdd

45、tdmludtxdcossin)(22222其动力学方程为其动力学方程为4.6 遗传算法在智能控制中的应用遗传算法在智能控制中的应用6.4 遗传算法在智能控制中的应用遗传算法在智能控制中的应用控制系统采用下图所示结构，其中控制系统采用下图所示结构，其中NNC为神经网络控制器，该控制为神经网络控制器，该控制器的输入为器的输入为、x、，输出为控制量，输出为控制量u。控制器采用。控制器采用3层前馈神经层前馈神经网络实现，网络实现，为了避免陷入局部极小，采用遗传算法确定网络的权值为了避免陷入局部极小，采用遗传算法确定网络的权值。x 1）神经网络控制器的结构设计）神经网络控制器的结构设计 神经网络输入层

46、有神经网络输入层有4个节点，分别对应于个节点，分别对应于4个输入分量个输入分量、x、；输出层设；输出层设1个节点，对应于控制量个节点，对应于控制量u；隐层设；隐层设10个节点。个节点。x 6.4 遗传算法在智能控制中的应用遗传算法在智能控制中的应用2）遗传算法训练）遗传算法训练 对神经网络的所有权值和阈值采用对神经网络的所有权值和阈值采用10进制编码，每个参数的进制编码，每个参数的变化范围为变化范围为-10，10，种群规模为，种群规模为n=50，交叉概率为，变异概，交叉概率为，变异概率为率为。遗传算法的适配值取倒立摆系统的稳定时间。遗传算法的适配值取倒立摆系统的稳定时间T（系统稳定（系统稳定指

47、摆角不超过指摆角不超过15）。）。mPcP遗传算法用于神经网络的权值优化，其具体过程如下：遗传算法用于神经网络的权值优化，其具体过程如下：(1)采用某种编码方案对每个权值进行编码，随机产生一组权值采用某种编码方案对每个权值进行编码，随机产生一组权值编码；编码；(2)计算神经网络的误差函数，确定其适应度的函数值，误差值计算神经网络的误差函数，确定其适应度的函数值，误差值越大，适配值越小；越大，适配值越小；(3)选择若干适配值大的个体直接遗传给下一代，其余按适配值选择若干适配值大的个体直接遗传给下一代，其余按适配值确定的概率遗传；确定的概率遗传；(4)利用交叉、变异等操作处理当前种群，产生下一代种

48、群；利用交叉、变异等操作处理当前种群，产生下一代种群；(5)重复重复(2)(3)，直到取得满意解。，直到取得满意解。6.4 遗传算法在智能控制中的应用遗传算法在智能控制中的应用4.7 GA4.7 GA的发展展望的发展展望q GAGA从从6060年代末至今已经有年代末至今已经有3030余年的发展历程余年的发展历程,在在 理论分析、理论分析、遗传策略、遗传策略、算法设计及算法设计及 应用上应用上 都取得巨大成就都取得巨大成就,成为近年在智能理论与优化理成为近年在智能理论与优化理论领域的一个非常重要的方法论领域的一个非常重要的方法,促进了智能理论与优促进了智能理论与优化理论领域的发展化理论领域的发展

49、.4.7 GA4.7 GA的发展展望的发展展望q GAGA所追求的是当前群体产生比现有个体更好个体的能力所追求的是当前群体产生比现有个体更好个体的能力,即即GAGA的可进化性或称群体可进化性的可进化性或称群体可进化性.因此因此,GA,GA的理论和方法研究也就围绕着这一目标展开的理论和方法研究也就围绕着这一目标展开.关于下面五个问题的回答关于下面五个问题的回答,就成为就成为GAGA理论研究的主要方理论研究的主要方向向:GAGA如何更好地模拟复杂系统的适应性过程和进化行如何更好地模拟复杂系统的适应性过程和进化行为为?GAGA在优化问题求解中怎样才能具备全局收敛性在优化问题求解中怎样才能具备全局收敛

50、性?GAGA的搜索效率如何评价的搜索效率如何评价?遗传策略的设计和参数控制的理论基础是什么遗传策略的设计和参数控制的理论基础是什么?GAGA与其他算法如何结合与其他算法如何结合?参考文献参考文献B1 Bck,T.“Evolutionary Algorithms in Theory and Practice”Oxford University Press,New York,1996B2 Bck,T.,Hammel,U.,and Schwefel,H.-P.(1997).“Evolutionary Computation:Comments on the History and Current St