第四章：遗传算法精选文档.ppt

《第四章：遗传算法精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章：遗传算法精选文档.ppt（113页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、而且而且人的智慧、智人的智慧、智能能也在得到进化也在得到进化.因此因此,生物的进化过程其实也是一种智能的进化、优化过程生物的进化过程其实也是一种智能的进化、优化过程,也是一种智能行为也是一种智能行为.“.“物竞天择、适者生存物竞天择、适者生存”中蕴涵了智能的光中蕴涵了智能的光辉、蕴涵了优化的思想辉、蕴涵了优化的思想.本讲稿第三页，共一百一十三页n遗传算法遗传算法(Genetic Algorithm,GA)(Genetic Algorithm,GA)就是根据生物进化思就是根据生物进化思想而启发得出的一种智能理论和方法想而启发得出的一种智能理论和方法.它是基于进化过程中的信息遗传机制和优胜劣汰的自

4、然选择它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法原则的搜索算法,是通过对生物进化的归纳和模拟得到的一种是通过对生物进化的归纳和模拟得到的一种仿生算法仿生算法.GAGA在本质上是一种不依赖具体问题的直接搜索方法在本质上是一种不依赖具体问题的直接搜索方法,是一种具是一种具有普适性的优化方法有普适性的优化方法.nGAGA的发展历程为的发展历程为:19651965年年,Michigan,Michigan大学的大学的HollandHolland首次提出了人工遗传操作的重首次提出了人工遗传操作的重要性要性,并把这些应用于自然系统和人工系统中并把这些应用于自然系统和人工系统中.196

5、71967年年,J.D.Bagley,J.D.Bagley在他的论文中首次提出了在他的论文中首次提出了GAGA这一术语与概这一术语与概念念,并讨论了并讨论了GAGA在自动博弈中的应用在自动博弈中的应用.4.1 4.1 引言引言本讲稿第四页，共一百一十三页19701970年年,Cavicchio,Cavicchio把把GAGA应用于模式识别中应用于模式识别中.第一个把第一个把GAGA应用于函数优化的是应用于函数优化的是Hollstien.Hollstien.而而GAGA的理论和方法的系统性研究开始于的理论和方法的系统性研究开始于19751975年年,这一开这一开创性工作是由创性工作是由J.H.H

6、ollandJ.H.Holland所实行所实行.n这一年是这一年是GAGA研究的历史上十分重要的一年研究的历史上十分重要的一年.nHollandHolland在他的著名专著在他的著名专著Adaptation in Natural and Adaptation in Natural and Artificial SystemsArtificial Systems中系统地阐述了中系统地阐述了GAGA的基本理论和方的基本理论和方法法,并提出了对并提出了对GAGA的理论研究和发展极为重要的模式理的理论研究和发展极为重要的模式理论论(schemata theory).(schemata theory).

7、n该理论首次确认了结构重组遗传操作对于获得隐并行该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性性的重要性.4.1 4.1 引言引言本讲稿第五页，共一百一十三页同年同年,DeJong,DeJong完成了他的重要论文完成了他的重要论文遗传自适应系统遗传自适应系统的行为分析的行为分析.n他在该论文中所做的研究工作可看作是他在该论文中所做的研究工作可看作是GAGA发展过程中的一个发展过程中的一个里程碑里程碑,这是因为他把这是因为他把HollandHolland的模式理论与他的计算使的模式理论与他的计算使用结合起来用结合起来.19891989年年GoldbergGoldberg对对GAGA从理

8、论上从理论上,方法上和应用上作了方法上和应用上作了系统的总结系统的总结.19901990年代以来年代以来,以以GAGA为代表的进化类算法及计算智能理为代表的进化类算法及计算智能理论和算法得到极大重视论和算法得到极大重视.1994.1994年在美国召开了第一届年在美国召开了第一届世界计算智能大会世界计算智能大会,欣起了进化类算法研究和应用欣起了进化类算法研究和应用的热潮的热潮.4.1 4.1 引言引言本讲稿第六页，共一百一十三页nGAGA与其它优化方法相比与其它优化方法相比,具有如下特点具有如下特点:GAGA不是直接作用在参变量集上不是直接作用在参变量集上,而是利用参变量集的而是利用参变量集的某

9、种编码某种编码;GAGA不是从单个点不是从单个点,而是在群体中从多个点开始搜索而是在群体中从多个点开始搜索;GAGA利用适应值信息利用适应值信息,无需导数或其它辅助信息无需导数或其它辅助信息;n因此对优化问题因此对优化问题(函数函数)的限制较弱的限制较弱,灵活灵活,通用性通用性(普适性普适性)强强,有着较广泛的应用领域有着较广泛的应用领域.GAGA利用概率转移规则利用概率转移规则,而非确定性规则而非确定性规则.GAGA在解空间内不是盲目的穷举或完全随机测试，而在解空间内不是盲目的穷举或完全随机测试，而是一种启发式搜索，效率优于其它算法。是一种启发式搜索，效率优于其它算法。4.1 4.1 引言引

10、言本讲稿第七页，共一百一十三页nGAGA的优点的优点:较容易的和其它方法结合较容易的和其它方法结合避免陷入局部最优解避免陷入局部最优解n即使在较短的有限时间内即使在较短的有限时间内,也能获得较好的次优解、满意也能获得较好的次优解、满意解解.鲁棒性佳鲁棒性佳n对优化问题的初始条件对优化问题的初始条件(状态状态)依赖性小。依赖性小。n 抗干扰性强。抗干扰性强。具有并行计算的特点，可提高计算速度具有并行计算的特点，可提高计算速度4.1 4.1 引言引言本讲稿第八页，共一百一十三页nGAGA的不足的不足:No guarantee for optimal solution within finite N

11、o guarantee for optimal solution within finite timetimeWeak theoretical basisWeak theoretical basisnGAGA能解决的问题能解决的问题:优化优化NPNP完全完全高度复杂的非线性问题高度复杂的非线性问题4.1 4.1 引言引言本讲稿第九页，共一百一十三页n近年近年,GA,GA在各应用领域中得到极大重视在各应用领域中得到极大重视,并广泛应用于各领并广泛应用于各领域的优化、搜索、问题求解中域的优化、搜索、问题求解中,并在并在模式识别、模式识别、NNNN、图像处理、图像处理、机器学习、机器学习、工业优化控

12、制、工业优化控制、自适应控制、自适应控制、生物科学、生物科学、社会科学社会科学等方面都得到应用等方面都得到应用.4.1 4.1 引言引言本讲稿第十页，共一百一十三页n当前在当前在AIAI研究中研究中,人们认为人们认为“GAGA、自适应系统、自适应系统、细胞自动机、混沌理论与细胞自动机、混沌理论与AIAI一样一样,都是对今后十都是对今后十年的计算技术有重大影响的关键技术年的计算技术有重大影响的关键技术”.4.1 4.1 引言引言本讲稿第十一页，共一百一十三页4.2 GA4.2 GA的基本概念的基本概念nGAGA的的基基本本思思想想是是基基于于达达尔尔文文(Darwin)(Darwin)进进化化论

13、论和和门门德尔德尔(Mendel)(Mendel)的遗传学说的的遗传学说的,下面将分别介绍下面将分别介绍:DarwinDarwin进化论及进化系统模型进化论及进化系统模型MendelMendel的遗传学说的遗传学说GAGA的基本概念与术语的基本概念与术语本讲稿第十二页，共一百一十三页4.2.1 Darwin4.2.1 Darwin进化论及进化系统模型进化论及进化系统模型Charles DarwinAll environments have All environments have finite resources(i.e.,can finite resources(i.e.,can only

14、 support a limited only support a limited number of individuals)number of individuals)它它认认为为每每一一物物种种在在发发展展中中越越来来越越适适应环境应环境.nDarwin(Darwin(1809-1882,1809-1882,Father Father o of the f the evevololutiutio on then theo oryry)进化论最重要的进化论最重要的是是适者生存适者生存(Survival of the(Survival of the fittest)fittest)原理原理.

15、本讲稿第十三页，共一百一十三页物物种种每每个个个个体体的的基基本本特特征征由由后后代代所所继继承承,但但后后代代又又会会产生一些异于父代的新变化产生一些异于父代的新变化.在在环环境境变变化化时时,只只有有那那些些能能适适应应环环境境的的个个体体特特征征方方能能保留下来保留下来.4.2.1 Darwin4.2.1 Darwin进化论及进化系统模型进化论及进化系统模型本讲稿第十四页，共一百一十三页4.2.1 Darwin4.2.1 Darwin进化论及进化系统模型进化论及进化系统模型生物进化过程生物进化过程(循环图循环图):):初始群体淘汰体竞争初始种群繁殖变异新的群体本讲稿第十五页，共一百一十三

16、页n自自DarwinDarwin以来的新进化学说强调以来的新进化学说强调:个体是基本的选择目标个体是基本的选择目标;随随机机过过程程在在进进化化中中起起重重大大作作用用,遗遗传传变变异异大大部部分分是是偶偶然然现象现象;进进化化是是在在适适应应中中变变化化的的,形形式式多多样样,不不仅仅是是基基因因的的变变化化;选择是概率型的选择是概率型的,而不是决定型的而不是决定型的.4.2.1 Darwin4.2.1 Darwin进化论及进化系统模型进化论及进化系统模型本讲稿第十六页，共一百一十三页4.2.2 Mendel4.2.2 Mendel遗传学说遗传学说Gregor Mendel它它认认为为遗遗传

17、传以以密密码码方方式式存存在在细细胞胞中中,并并以以基基因因形形式式包含在染色体内包含在染色体内.每每个个基基因因有有特特殊殊的的位位置置并并控控制制某某种种特特殊殊性性质质;所所以以,每每个个基基因因产产生生的的个个体体对对环环境境具有某种适应性具有某种适应性.nMendel(Mendel(1822-1884,1822-1884,Father Father o of f genetics)genetics)遗传学说最重要的是遗传学说最重要的是基因遗传原理基因遗传原理.本讲稿第十七页，共一百一十三页4.2.2 Mendel4.2.2 Mendel遗传学说遗传学说基因突变和基因杂交可产生更适应于

18、环境的后代基因突变和基因杂交可产生更适应于环境的后代.经经过过存存优优去去劣劣的的自自然然淘淘汰汰,适适应应性性高高的的基基因因结结构构得得以以保存下来保存下来.本讲稿第十八页，共一百一十三页4.2.3 GA4.2.3 GA的基本概念与术语的基本概念与术语n基基于于达达尔尔文文的的进进化化论论与与孟孟德德尔尔的的遗遗传传学学说说,可可得得到到如下生物进化的原则如下生物进化的原则生物进化过程的发生需要四个基本条件生物进化过程的发生需要四个基本条件:n存在由多个生物个体组成的种群存在由多个生物个体组成的种群;n生物个体之间存在着差异生物个体之间存在着差异,或群体具有多样性或群体具有多样性;n生物能

19、够自我繁殖生物能够自我繁殖;n不不同同个个体体具具有有不不同同的的环环境境生生存存能能力力,具具有有优优良良基基因因结结构构的的个个体体繁殖能力强繁殖能力强,反之则弱反之则弱.本讲稿第十九页，共一百一十三页4.2.3 GA4.2.3 GA的基本概念与术语的基本概念与术语生物群体的进化机制包括三种基本形式生物群体的进化机制包括三种基本形式:n自然选择自然选择 n杂交杂交n突变突变n另外另外,外界对生物的评价反映了生物的生存价值和机会外界对生物的评价反映了生物的生存价值和机会.受受到到生生物物进进化化过过程程的的启启迪迪,模模拟拟生生物物进进化化的的优化方法优化方法GAGA得到重视并迅速发展得到重

20、视并迅速发展.本讲稿第二十页，共一百一十三页4.2.3 GA4.2.3 GA的基本概念与术语的基本概念与术语n由由于于GAGA是是由由进进化化论论和和遗遗传传学学机机理理而而产产生生的的直直接接搜搜索索优优化化方方法法,故故而而在在这这个个算算法法中中要要用用到到各各种种进进化化和和遗遗传学的概念传学的概念.这些概念如下这些概念如下:n串串n群体群体n群体规模群体规模n基因与基因位置基因与基因位置n基因特征值基因特征值n适应度适应度本讲稿第二十一页，共一百一十三页4.2.3 GA4.2.3 GA的基本概念与术语的基本概念与术语A.A.串串(String)(String)它它是是个个体体(Ind

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

22、opulation)(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)群体规模指群体中个体的数量群体规模指群体中个体的数量.由由于于GAGA的的优优化化是是针针对对群群体体进进

24、行行的的,因因此此群群体体规规模模是是非常重要的一个参数非常重要的一个参数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的基本概念与术语的基本概念与

28、术语nGAGA还还有有一一些些其其它它的的概概念念,这这些些概概念念在在介介绍绍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典典型型的的遗遗传传算算法法(canonicalgenetic

30、algorithm,CGA)通通常常用于解决下面这一类的静态最优化问题用于解决下面这一类的静态最优化问题:考虑对于一群长度为考虑对于一群长度为L的二进制编码的二进制编码bi,i=1,2,n;有有bi 0,1L(1)给定目标函数给定目标函数f,有有f(bi),并且并且0f(bi)0)和ci(0)(i=1,2,n)，背包的总容量假设为v(v0)，如何选择哪些物品装入背包使得所装物品价值最大？该问题的模型可表示为如下的0-1规划问题：n背包问题是个典型的NP完全问题，目前还不存在多项式时间的算法。4.4.4 GA4.4.4 GA在组合优化中的应用在组合优化中的应用本讲稿第八十三页，共一百一十三页n编

31、码格式：例如x=1100000000表示仅装第1和第2种物品n适应度度量：n选择算子：赌盘选择（与适应值成比例选择）n交叉算子：混合单点交叉n变异算子：混合点变异n进化参数：种群规模，终止进化代数，交叉概率，变异概率=50，500，0.6，0.054.4.4 GA4.4.4 GA在组合优化中的应用在组合优化中的应用本讲稿第八十四页，共一百一十三页4.4.4 GA4.4.4 GA在组合优化中的应用在组合优化中的应用n其它如其它如8 8皇后问题皇后问题,即即在在n*nn*n格格的的国国际际象象棋棋棋棋盘盘上上放放置置n n个个皇皇后后,使使得得任任意意两两个个皇皇后后不不能能互互相相攻攻击击,即即

32、任任何何行行、列列、对对角角线线上上不不得得有有两两个个或或两两个个以上的皇后以上的皇后.n这这样样的的格格局局称称为为问问题题的的一个解一个解.本讲稿第八十五页，共一百一十三页4.4.4 GA4.4.4 GA在组合优化中的应用在组合优化中的应用n还还有有前前面面提提到到得得TSPTSP组组合合优优化化问问题题。注注意意非非法法解的解决。解的解决。本讲稿第八十六页，共一百一十三页4.5 GA4.5 GA的理论分析的理论分析qGAGA源源于于自自然然选选择择和和生生物物遗遗传传学学,相相对对于于其其鲜鲜明明的的生生物物基基础础,GA,GA的理论基础公认是不完善的的理论基础公认是不完善的.GAGA

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

34、可以称为定理可以称为GAGA进化动力学的基本定理进化动力学的基本定理.模式定理构成了求解优化问题时模式定理构成了求解优化问题时GAGA具备发现全局最优具备发现全局最优解的充分条件解的充分条件,也是分析也是分析GAGA的进化行为的基本理论的进化行为的基本理论,也称也称为模式理论为模式理论.本讲稿第八十八页，共一百一十三页4.5 GA4.5 GA的理论分析的理论分析通过基于模式理论的进化动力学分析通过基于模式理论的进化动力学分析,我们可我们可以发现以发现GAGA所能求解的问题的范围所能求解的问题的范围,找出找出GAGA的不的不足之处足之处,进而可能对其进行改进进而可能对其进行改进.本讲稿第八十九页

35、，共一百一十三页4.5 GA4.5 GA的理论分析的理论分析n遗传算法的理论基础是遗传算法的二进制表达式遗传算法的理论基础是遗传算法的二进制表达式及模式的含义。及模式的含义。下面简单介绍模式的概念及模式定理下面简单介绍模式的概念及模式定理.它的有关内容如下它的有关内容如下:n模式概念模式概念n模式的阶和长度模式的阶和长度n复制对群体适应值的影响复制对群体适应值的影响n交叉对模式的影响交叉对模式的影响n变异对模式的影响变异对模式的影响nHollandHolland模式定理模式定理本讲稿第九十页，共一百一十三页4.5 GA4.5 GA的理论分析的理论分析A.模式概念模式概念定义模式的好处是使我们容

36、易描述串的相似性。一个基因串用符号集0,1,*表示,则称为一个模式;n其中*是通配符,可以是0或1.即模式是含有通配符(*)的一类字符串的通式表达,例如:nH=1*0*是一个模式.n模式*10101110与以下两个字符串匹配:010101110 110101110n而模式 *1010110 与以下四个字符串匹配:010100110 010101110110100110 110101110本讲稿第九十一页，共一百一十三页4.5 GA4.5 GA的理论分析的理论分析B.模式的阶和长度模式的阶和长度模式中0和1的个数称为模式的阶,并用o(H)表示.模式中第1位数字(非通配符*)和最后位数字间的距离称

37、为模式的长度,并用(H)表示.对于模式H=1*0*,有o(H)=2,(H)=4.n对于模式H=*0*1*0*,有o(H)=3,(H)=6.本讲稿第九十二页，共一百一十三页4.5 GA4.5 GA的理论分析的理论分析C.复制对群体适应值的影响复制对群体适应值的影响假定在给定的时间步t,一个特定的模式s在群体P(t)中包含m个代表串,记为m=m(s,t)。首先,我们暂不考虑交叉和变异操作。n每个串根据适应值的大小获得不同的复制概率。n串i的复制概率为:本讲稿第九十三页，共一百一十三页4.5 GA4.5 GA的理论分析的理论分析则在群体P(t+1)中,模式s的代表串的数量的期望值为:其中 (s,t)

38、表示模式s在t时刻的所有代表串的适应值的均值,称为模式s的适应值。n (t)表示群体P(t)中所有个体的适应值的平均值。上式表明,模式s的代表串的数目随时间增长的幅度正比于模式s的适应值与群体平均适应值的比值。n即:适应值高于群体平均值的模式在下一代的代表串数目将会增加,而适应值低于群体平均值的模式在下一代的代表串数目将会减少。本讲稿第九十四页，共一百一十三页4.5 GA4.5 GA的理论分析的理论分析假设模式的适应值为(1+c)(t),其中c是一个常数,则上式可写为:n上式表明,在平均适应值之上(之下)的模式,将会按指数增长(衰减)的方式被复制。本讲稿第九十五页，共一百一十三页4.5 GA4

39、.5 GA的理论分析的理论分析n复制的结果并没有生成新的模式。复制的结果并没有生成新的模式。因而因而,为了探索搜索空间中的未搜索部分为了探索搜索空间中的未搜索部分,需要利需要利用交叉和变异操作。用交叉和变异操作。下面分别探索交叉和变异对模式的影响。下面分别探索交叉和变异对模式的影响。本讲稿第九十六页，共一百一十三页4.5 GA4.5 GA的理论分析的理论分析D.交叉对模式的影响交叉对模式的影响考虑模式s1=“*1*0”和s2=“*10*”间的交叉,可以发现n交叉会改变模式的一部分,模式的长度越长,被破坏的概率越大。本讲稿第九十七页，共一百一十三页4.5 GA4.5 GA的理论分析的理论分析假定

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

41、1)的期望值为上式忽略了一项较小的交叉相乘项。由此我们得到一个关于GA优化性能的重要定理-模式定理(Schema Theorem)。本讲稿第一百页，共一百一十三页4.5 GA4.5 GA的理论分析的理论分析pHollandHolland模式定理模式定理模模式式定定理理 低低阶阶,短短长长度度,高高适适应应值值的的模模式式在在群群体体遗遗传过程中将会按指数规律增加传过程中将会按指数规律增加.根根据据模模式式定定理理，随随着着遗遗传传算算法法的的再再生生、交交叉叉、变变异异等等操操作作一一代代接接一一代代地地进进行行，那那些些短短的的，低低阶阶的的，高高适适应应值值的的模模式式将将越越来来越越多多

42、，最最后后得得到到的的串串即即是是这这些些模模式式的的组组合合。因因而而可可期期望望算算法法性性能能越越来来越越得得到改善，并最终向全局的最优点发展。到改善，并最终向全局的最优点发展。本讲稿第一百零一页，共一百一十三页遗传算法用于神经网络的权值优化：在神经遗传算法用于神经网络的权值优化：在神经网络用于系统建模和控制时，它要利用神经网络网络用于系统建模和控制时，它要利用神经网络的函数估计及分类功能。设计神经网络的关键是的函数估计及分类功能。设计神经网络的关键是如何确定神经网络的结构和连接权系数。它实质如何确定神经网络的结构和连接权系数。它实质上也是一个优化问题，其优化的目标是使得所设上也是一个优

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

44、代计算后，将码串解码为权值构成新的神经网络，通过对所有训练样本进行计算得到神经网络输出的网络，通过对所有训练样本进行计算得到神经网络输出的均方误差从而确定每个个体的适应度。经过若干代计算，均方误差从而确定每个个体的适应度。经过若干代计算，神经网络将进化到误差全局最小。神经网络将进化到误差全局最小。4.6遗传算法在智能控制中的应用遗传算法在智能控制中的应用本讲稿第一百零三页，共一百一十三页例例4.1倒立摆的遗传神经网络控制。设被控对象为图示的单倒立摆系统倒立摆的遗传神经网络控制。设被控对象为图示的单倒立摆系统其动力学方程为其动力学方程为4.6遗传算法在智能控制中的应用遗传算法在智能控制中的应用本

45、讲稿第一百零四页，共一百一十三页6.4遗传算法在智能控制中的应用遗传算法在智能控制中的应用控控制制系系统统采采用用下下图图所所示示结结构构，其其中中NNC为为神神经经网网络络控控制制器器，该该控控制制器器的的输输入入为为、x、，输输出出为为控控制制量量u。控控制制器器采采用用3层层前前馈馈神神经经网络实现，网络实现，为了避免陷入局部极小，采用遗传算法确定网络的权值为了避免陷入局部极小，采用遗传算法确定网络的权值。本讲稿第一百零五页，共一百一十三页1）神经网络控制器的结构设计）神经网络控制器的结构设计神经网络输入层有神经网络输入层有4个节点，分别对应于个节点，分别对应于4个输入分量个输入分量、x

46、、；输出层设；输出层设1个节点，对应于控制量个节点，对应于控制量u；隐层设；隐层设10个节点。个节点。6.4遗传算法在智能控制中的应用遗传算法在智能控制中的应用2）遗传算法训练）遗传算法训练对神经网络的所有权值和阈值采用对神经网络的所有权值和阈值采用10进制编码，每个参数的变化范进制编码，每个参数的变化范围为围为-10，10，种群规模为，种群规模为n=50，交叉概率为，交叉概率为=0.9，变异概率为，变异概率为=0.03。遗传算法的适配值取倒立摆系统的稳定时间遗传算法的适配值取倒立摆系统的稳定时间T（系统稳定指摆角不超过（系统稳定指摆角不超过15）。）。本讲稿第一百零六页，共一百一十三页遗传算

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

48、种群；(5)重复重复(2)(3)，直到取得满意解。，直到取得满意解。6.4遗传算法在智能控制中的应用遗传算法在智能控制中的应用本讲稿第一百零七页，共一百一十三页4.7 GA4.7 GA的发展展望的发展展望qGAGA从从6060年代末至今已经有年代末至今已经有3030余年的发展历程余年的发展历程,在在理论分析、理论分析、遗传策略、遗传策略、算法设计及算法设计及应用上应用上 都都取取得得巨巨大大成成就就,成成为为近近年年在在智智能能理理论论与与优优化化理理论论领领域域的的一一个个非非常常重重要要的的方方法法,促促进进了了智智能能理理论论与与优优化化理理论论领领域域的发展的发展.本讲稿第一百零八页，

49、共一百一十三页4.7 GA4.7 GA的发展展望的发展展望qGAGA所所追追求求的的是是当当前前群群体体产产生生比比现现有有个个体体更更好好个个体体的的能能力力,即即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