进化控制介绍

1、第五章 进化控制目 录引言GA的基本概念Darwin进化论及进化系统模型Mendel的遗传学说GA的基本概念与术语GA的原理GA的目的GA的基本原理GA的算法过程2目 录GA的应用GA在函数优化中的应用进化控制简介进化控制应用举例35.1 引言生物的进化是一个奇妙的优化过程,它通过选择淘汰,突然变异,基因遗传等规律产生适应环境变化的优良物种.例如,在人类的进化过程中,通过“物竞天择、适者生存”自然的选择和淘汰,人类的身、心不断得到进化,逐渐进化成为这地球上的具有最高等智慧的主宰者.在这个进化过程中,不仅人的身体得到进化,而且人的智慧、智能也在得到进化.因此,生物的进化过程其实也是一种智能的进化

2、、优化过程,也是一种智能行为.“物竞天择、适者生存”中蕴涵了智能的光辉、蕴涵了优化的思想.4人是怎样进化的?从鱼到人的进化过程/discovery/life/200608/10/t20060810_8087469.shtml5遗传算法(Genetic Algorithm,GA)就是根据生物进化思想而启发得出的一种智能理论和方法.它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法,是通过对生物进化的归纳和模拟得到的一种仿生算法.GA在本质上是一种不依赖具体问题的直接搜索方法,是一种具有普适性的优化方法.GA的发展历程为:1965年,Michigan大学的Holland首次提出了人

3、工遗传操作的重要性,并把这些应用于自然系统和人工系统中.1967年,J.D.Bagley在他的论文中首次提出了GA这一术语与概念,并讨论了GA在自动博弈中的应用.5.1 引言61970年,Cavicchio把GA应用于模式识别中.第一个把GA应用于函数优化的是Hollstien.而GA的理论和方法的系统性研究开始于1975年,这一开创性工作是由J.H.Holland所实行.这一年是GA研究的历史上十分重要的一年.Holland在他的著名专著Adaptation in Natural and Artificial Systems中系统地阐述了GA的基本理论和方法,并提出了对GA的理论研究和发展极

4、为重要的模式理论(schemata theory).该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性.5.1 引言7同年,DeJong完成了他的重要论文遗传自适应系统的行为分析.他在该论文中所做的研究工作可看作是GA发展过程中的一个里程碑,这是因为他把Holland的模式理论与他的计算使用结合起来.1989年Goldberg对GA从理论上,方法上和应用上作了系统的总结.1990年代以来,以GA为代表的进化类算法及计算智能理论和算法得到极大重视.1994年在美国召开了第一届世界计算智能大会,欣起了进化类算法研究和应用的热潮.5.1 引言8GA与其它优化方法相比,具有如下特点:GA不是直接

5、作用在参变量集上, 而是利用参变量集的某种编码;GA不是从单个点, 而是在群体中从多个点开始搜索;GA利用适应值信息, 无需导数或其它辅助信息;因此对优化问题(函数)的限制较弱,灵活,通用性(普适性)强,有着较广泛的应用领域.GA利用概率转移规则, 而非确定性规则.GA在解空间内不是盲目的穷举或完全随机测试，而是一种启发式搜索，效率优于其它算法。5.1 引言9GA的优点:较容易的和其它方法结合避免陷入局部最优解即使在较短的有限时间内,也能获得较好的次优解、满意解.鲁棒性佳对优化问题的初始条件(状态)依赖性小。 抗干扰性强。具有并行计算的特点，可提高计算速度5.1 引言10GA的不足:No gu

6、arantee for optimal solution within finite timeWeak theoretical basisGA能解决的问题:优化NP完全高度复杂的非线性问题5.1 引言11近年,GA在各应用领域中得到极大重视,并广泛应用于各领域的优化、搜索、问题求解中,并在模式识别、NN、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用.5.1 引言125.2 GA的基本概念GA的基本思想是基于达尔文(Darwin)进化论和门德尔(Mendel)的遗传学说的,下面将分别介绍:Darwin进化论及进化系统模型Mendel的遗传学说GA的基本概念与术

7、语135.2.1 Darwin进化论及进化系统模型Charles DarwinAll environments have finite resources (i.e., can only support a limited number of individuals)它认为每一物种在发展中越来越适应环境.Darwin(1809-1882, Father of the evolution theory)进化论最重要的是适者生存(Survival of the fittest)原理.14物种每个个体的基本特征由后代所继承,但后代又会产生一些异于父代的新变化.在环境变化时,只有那些能适应环境的个体特

8、征方能保留下来.5.2.1 Darwin进化论及进化系统模型155.2.1 Darwin进化论及进化系统模型生物进化过程(循环图):初始群体淘汰体竞争初始种群繁殖变异新的群体16自Darwin以来的新进化学说强调:个体是基本的选择目标;随机过程在进化中起重大作用,遗传变异大部分是偶然现象;进化是在适应中变化的,形式多样,不仅是基因的变化;选择是概率型的,而不是决定型的.5.2.1 Darwin进化论及进化系统模型175.2.2 Mendel遗传学说Gregor Mendel它认为遗传以密码方式存在细胞中,并以基因形式包含在染色体内.每个基因有特殊的位置并控制某种特殊性质;所以,每个基因产生的个

9、体对环境具有某种适应性.Mendel(1822-1884, Father of genetics)遗传学说最重要的是基因遗传原理.185.2.2 Mendel遗传学说基因突变和基因杂交可产生更适应于环境的后代.经过存优去劣的自然淘汰,适应性高的基因结构得以保存下来.195.2.3 GA的基本概念与术语基于达尔文的进化论与孟德尔的遗传学说,可得到如下生物进化的原则生物进化过程的发生需要四个基本条件:存在由多个生物个体组成的种群;生物个体之间存在着差异,或群体具有多样性;生物能够自我繁殖;不同个体具有不同的环境生存能力,具有优良基因结构的个体繁殖能力强,反之则弱.205.2.3 GA的基本概念与术

10、语生物群体的进化机制包括三种基本形式:自然选择 杂交突变另外,外界对生物的评价反映了生物的生存价值和机会. 受到生物进化过程的启迪,模拟生物进化的优化方法GA得到重视并迅速发展.215.2.3 GA的基本概念与术语由于GA是由进化论和遗传学机理而产生的直接搜索优化方法,故而在这个算法中要用到各种进化和遗传学的概念.这些概念如下:串群体群体规模基因与基因位置基因特征值适应度225.2.3 GA的基本概念与术语A. 串(String)它是个体(Individual)的基因表示形式,本质为如何表示解.在算法中常采用给定长度的二进制串,其特点操作简便.如串S=1011根据具体问题也可采用特定的适宜于问

11、题处理的编码方式,如实数编码D进制, D=3,8,16,序列编码:例如TSP的路径表达自适应编码-长度可调节235.2.3 GA的基本概念与术语B. 群体(Population)个体的集合称为群体,串是群体的元素.A population is a set of possible solutions.GA之所以具有良好的优化性能和智能行为,除开交叉和变异等遗传操作具有独到的优化能力,正是由于其优化过程是针对群体而非仅仅针对单个个体进行.对群体的优化除保证子代群体能够继承父代群体的优势特征之外,重要的其在一定程度上保证所搜索到的解具有某种全局性.群体进化行为在一定程度上可避免个体进化和优化的局部

12、性、非单调性等.245.2.3 GA的基本概念与术语C. 群体规模(Population Size)群体规模指群体中个体的数量.由于GA的优化是针对群体进行的,因此群体规模是非常重要的一个参数Many researchers suggest population sizes between 25 and 100. 255.2.3 GA的基本概念与术语D. 基因(Gene)与基因位置(Gene Position)基因是串中的元素,基因用于表示个体的特征.基因位置是指一个基因在串中的位置,有时也简称基因位.基因位置对应于遗传学中的地点(Locus).例如有一个串S=1011,则其中的1,0,1,1

13、这4个元素分别称为基因.基因位置由串的左向右计算,例如在串S=1011中,0的基因位置是2.265.2.3 GA的基本概念与术语E. 基因特征值(Gene Feature)在用串表示整数时,基因的特征值与二进制数的权一致;例如在串S=1011中,基因位置3中的1,它的基因特征值为2;基因位置1中的1,它的基因特征值为8.275.2.3 GA的基本概念与术语F. 适应度(Fitness)表示某一个体对于环境的适应程度,是GA进行优化的指标函数.在优化过程中,通过适应度可以进行个体优劣的比较,可以进行个体的筛选,以产生子代群体,或选择个体参加交叉和变异等遗传操作.一般,适应度函数定义为0,1之间的

14、实数.适应度函数值越大,表示该个体越适应环境(问题),就越优.因此GA是对适应度函数求极大优化.285.2.3 GA的基本概念与术语GA还有一些其它的概念,这些概念在介绍GA的原理和执行过程时,再进行说明.295.3 GA的原理GA把问题的解表示成“染色体”,在算法中也即是以二进制编码的串.并且,在执行GA之前,给出一群“染色体”,也即是假设解.然后,把这些假设解置于问题的“环境”中,并按适者生存的原则,从中选择出较适应环境的“染色体”进行复制,再通过交叉,变异过程产生更适应环境的新一代“染色体”群.这样,一代一代地进化,最后就会收敛到最适应环境的一个“染色体”上,它就是问题的最优解.305.

15、3 GA的原理下面分别介绍:GA的目的GA的基本原理GA的算法过程315.3.1 GA的目的典型的遗传算法(canonical genetic algorithm, CGA)通常用于解决下面这一类的静态最优化问题:考虑对于一群长度为L的二进制编码bi,i=1,2,n;有bi0,1L (1)给定目标函数f,有f(bi),并且0f(bi)求满足下式maxf(bi)|bi0,1L (2)的bi.325.3.1 GA的目的很明显,GA是一种最优化方法,它通过进化和遗传机理,从给出的原始解群中,不断进化产生新的解,最后收敛到一个特定的串bi处,即求出最优解.335.3.2 GA的基本原理长度为L的n个二

16、进制串bi(i=1,2,n)组成了GA的初解群,也称为初始群体.在每个串中,每个二进制位就是个体染色体的基因.根据进化术语,对群体执行的操作有三种:选择与再生重组与交叉变异345.3.2 GA的基本原理A. 选择(Selection)与再生(Reproduction)选择是根据适者生存原则从群体中选择出较适应环境的个体以生产子代.在选择时,以适应度为选择原则.适应度准则体现了适者生存,不适应者淘汰的自然法则.这些选中的个体用于繁殖下一代.故有时也称这一操作为再生(reproduction).由于在选择用于繁殖下一代的个体时,是根据个体对环境的适应度而决定其繁殖量的,故而有时也称为非均匀再生(d

17、ifferential reproduction).355.3.2 GA的基本原理早期的GA算法产生的新一代均是从父代的个体经交叉与变异产生的子代中由基于选择概率的选择算子选择产生的.这种选择策略使得进化过程可能似的优化的解被丢弃,产生退化.实践证明使用保留父代群体中最佳个体模型至子代的GA比基本GA的性能有明显的改进,该GA成为保留最优个体遗传算法.365.3.2 GA的基本原理下面主要讨论基于适应度函数产生的选择概率来选择的方法- Proportionate-based selection一般在GA的选择中,由个体的适应度函数值计算相应的选择概率,并按照轮盘赌的方式选择需要进行遗传运算的个

18、体(参加遗传操作的父亲和母亲).设目标函数为f,则f(bi)称为个体bi的适应度.相应地,个体bi的选择概率为选择概率一般用于选择下一代(子代)群体,以及参加交叉和变异操作的个体.在选择参加交叉和变异操作的个体时采用轮盘赌的方式,如下图所示375.3.2 GA的基本原理图2 随机选择遗传操作的轮盘赌385.3.2 GA的基本原理选择方法: （a）从适应度大小出发(四舍五入概念). 定义:选择概率 ,选择 的个数:n* . (b)从相对适应度出发选择. 定义: 相对适应度, 平均适应度, 分析: 直接从相对适应度出发,四舍五入取整选择.395.3.2 GA的基本原理显然,从式(3)可知:A. 适

19、应度较高的个体,繁殖下一代的数目较多.反之适应度较小的个体,繁殖下一代的数目较少;甚至被淘汰.B. 适应度较高的个体有较多的机会参与交叉和变异等遗传操作.这样,就产生了对环境适应能力较强的后代.对于问题求解角度来讲,就是选择出和最优解较接近的中间解.405.3.2 GA的基本原理B. 重组(Recombination)与交叉(Crossover)这是在选中用于繁殖下一代的个体中,对两个不同的个体的相同位置的基因进行交换,从而产生新的个体.415.3.2 GA的基本原理对于选中用于繁殖下一代的个体,按选择概率以轮盘赌的方式随机地选择两个个体作为父代,并随机选取相同的基因位置,按交叉概率Pc,在选

20、中的位置实行交换.这个过程反映了随机信息交换;目的在于产生新的基因组合,也即产生新的个体.交叉时,可实行单点交叉、多点交叉及一致交叉(Uniform Crossover).从理论上讲,多点交叉可以由多次单点交叉实现.对于多点交叉算子,随着交叉点数的增加会降低GA的性能42例如有2个父代个体S1=100|101 S2=010|111若随机选择它们的左边3位进行交叉操作,则产生的子代为S1=010|101 S2=100|1115.3.2 GA的基本原理下面介绍具体的交叉算子算法:(1) 二进制单点交叉算子. 单点交叉过程可图示如下:435.3.2 GA的基本原理单点交叉算子的过程为:BeginRe

21、peat 产生的子代个体数=n从父代群体中根据各个体的选择概率，采用轮盘赌方式选择2个参与交叉的父代个体产生（0，1）间的随机数s若s小于等于交叉概率Pc,则随机产生交叉位Lc对2个父代个体在交叉位Lc进行交叉操作,生成2个子代个体EndEnd44例如有2个父代个体S1=10010101 S2=01110100若屏蔽字为1101110,则产生的子代为S1=101101005.3.2 GA的基本原理(2) 二进制一致(Uniform Crossover)交叉算子. 所谓一致交叉,即对给定的屏蔽字,若屏蔽字的某位为1,则子代的该位继承父亲;若为0,则子代的该位继承母亲.屏蔽字交叉过程可图示如下:4

22、55.3.2 GA的基本原理对选择算子选作交叉的父代,是否进行交叉运算,以交叉概率Pc决定。一般而言,交叉概率Pc取值为0.250.75.465.3.2 GA的基本原理C. 变异(Mutation)变异是根据生物遗传中基因变异的原理,按选择概率以轮盘赌的方式随机地选择一个个体作为父代,并随机选取基因位置以变异概率Pm对某些个体的某些基因位执行异向转化.在变异时,对执行变异的串的对应基因位求反.产生变异时就是把它变成0;反亦反之.变异概率Pm与生物变异极小的情况一致,所以,Pm的取值较小,一般取0.010.2.475.3.2 GA的基本原理下面介绍具体的变异算子算法:二进制变异算子.变异过程可图

23、示如下:例如有父代个体S=101011对其的第1,4位置的基因进行变异,则有S=001111485.3.2 GA的基本原理变异算子的过程为:BeginRepeat 对所有交叉算子产生的新子代的个体数产生（0，1）间的随机数s若s小于等于变异概率Pm,则随机产生变异位Lm对个体i在变异位Lm进行变异操作,生成新子代个体EndEnd495.3.2 GA的基本原理对变异算子的作用,有如下讨论单靠变异不能在求解中得到好处.但是,它能保证算法过程不会产生无法进化的单一群体.在所有的个体趋向一样时,交叉是无法产生新的个体的,这时只能靠变异产生新的个体,以保持群体的多样性,避免早熟.也就是说,变异增加了全局

24、优化的特质.虽然变异概率的增大也会增加群体的多样性,但它却降低了GA的性能,并且随着变异概率的增大,GA的性能越来越接近于随机搜索算法的性能.505.3.2 GA的基本原理除前面讨论的变异算子外,还有如下常用的变异算子多点变异随机变异区间内均匀随机取515.3.3 GA的算法过程基于上述GA的原理和基因操作,可总结出GA的基本过程.GA的算法流程如右图所示；其相应的算法如下所示.525.3.3 GA的算法过程GA算法choose an intial populationdetermine the fitness of each individualperform selectionrepeat

25、perform crossover at crossover probability Pcperform mutation at crossover probability Pmdetermine the fitness of each individualperform selectionuntil some stopping criterion applies535.3.3 GA的算法过程在GA的初始化过程,主要的工作为决定GA的各参数与初始群体.需确定的GA的主要参数有:群体规模交叉概率变异概率对初始群体,通常以随机方法产生.为保证群体的多样性,以及不遗漏某些基因的遗传因子,初始群体的离

26、散度应较大.问题的最优解将通过这些初始假设解进化而求出.545.3.3 GA的算法过程选择、交叉和变异是GA的三种基本操作.群体正是在这三种操作的交替运行过程中,得到进化(优化),提升智能.群体进化的结束的标志是群体的某种性能指标达到预先定义的某种结束准则.这里所指的某种结束准则一般是指个体的适应度达到给定的阈值;或者个体的适应度的变化率为零.下图显示出选择、交叉和变异这三种运算是如何交替迭代进行的.555.3.3 GA的算法过程图3 GA原理565.3.3 GA的算法过程当最优个体的适应度达到给定的阈值,或者最优个体的适应度和群体适应度不再上升时,则算法的迭代过程收敛、算法结束.否则,用经过

27、选择、交叉、变异所得到的新一代群体取代上一代群体,并返回到第2步即选择操作处继续循环执行.图3中表示了GA的执行过程.575.4 GA的应用GA在很多领域都得到应用,如函数优化、NN学习、方程求解、控制工程、系统工程、计算机科学等领域.在GA应用中,应先明确其特点和关键问题,才能对这种算法深入了解,灵活应用,以及进一步研究开发.下面介绍:GA在函数优化中的应用58考虑如下实函数的优化命题GA在函数优化中的应用其中x为n维优化变量向量.在利用GA对式(4)所示的函数优化命题进行运算时,需考虑的问题是:适应度函数由于上述函数优化命题为求极小,因此,在转换成适应度函数时,可采取以下两种方法.59GA

28、在函数优化中的应用1）转化成最大化问题,且保证非负性。 (目标函数) C为人为设定的足够大的正数。 2）若能保证g(x)是正的,则 注意：若问题本身是最大化,但不能保证g(x)非负性60GA在函数优化中的应用个体编码对该优化命题,可采用二进制编码或实数编码.若采用实数编码,则可将变量向量x的每一变量分量变换成02L-1间的二进制数(其中L为每个变量分量对应的二进制串的长度).然后将各变量分量所对应的二进制串按次序或某种规则排列策划功能成GA中的串.61GA在函数优化中的应用群体规模、交叉和变异概率对如何选取群体规模、交叉和变异概率这些GA所需要的参数,目前还没有能得到非常具体的选取方法,只有一

29、些经验性质的指导原则.针对具体的优化问题,需要作具体分析,以及还要依赖于使用者的所掌握的经验和技巧.对交叉和变异概率的选取,有研究人员提出一些自适应选取策略,在一定程度上有助于GA的应用.但是在GA的优化机理缺乏严格研究的情况下,自适应策略的效果也未有严格的分析和证明.62GA在函数优化中的应用下面简单讨论函数优化的GA 算例.算例 用CGA求解如下函数优化问题在该算例中,为简单便于说明起见,选择:个体编码长度为5位二进制群体个数为4适应度函数直接为函数值交叉概率1.0,变异概率0.75(通常变异概率应非常小)GA计算结果为63GA在函数优化中的应用初始群体与第一次选择编号群体变量函数值x2选

30、择百分比期望复制数目实际复制数目1234011011100001000100111324819169576643610.14440.49230.05470.30850.57781.96920.21881.23421201和平均值最大值1170292.557610.25000.4923411.969241264GA在函数优化中的应用第一次交叉编号交配池交配对交配位置新的群体变量函数值x212340110 | 111 | 0001100 | 010 | 0111,32,4420110011001110111000012252716144625729256和平均值最大值(随机产生)(随机产生)175

31、443972965GA在函数优化中的应用第一次变异编号交配池变异位置新的群体变量函数值x212340110 | 0110 | 01110111 | 000043无10111011101110110000014292701968417290和平均值最大值(随机产生)1766441.584166GA在函数优化中的应用第二次选择编号群体变量函数值x2选择百分比期望复制数目实际复制数目123401110111011101100000142927019684172900.11100.47620.412800.44391.90481.651200220和平均值最大值1766441.584110.25000.4762411.904841267GA在函数优化中的应用第二次交叉编号交配池交配对交配位置新的群体变量函数值x21234111 | 011 | 1101110 | 111 | 10111,32,4311111111101110011101131292527961841625729和平均值最大值(随机产生)(随机产生)315678996168进化控制原理与系统结构进化控制及基