进化控制介绍

1、第五章第五章 进化控制进化控制目 录n引言引言nGAGA的基本概念的基本概念DarwinDarwin进化论及进化系统模型进化论及进化系统模型MendelMendel的遗传学说的遗传学说GAGA的基本概念与术语的基本概念与术语nGAGA的原理的原理GAGA的目的的目的GAGA的基本原理的基本原理GAGA的算法过程的算法过程2目 录nGAGA的应用的应用GAGA在函数优化中的应用在函数优化中的应用n进化控制简介进化控制简介n进化控制应用举例进化控制应用举例35.1 5.1 引言引言n生物的进化是一个奇妙的优化过程生物的进化是一个奇妙的优化过程, ,它通过选择淘它通过选择淘汰汰, ,突然变异突然变异

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

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

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

5、中首次提出了在他的论文中首次提出了GAGA这一术这一术语与概念语与概念, ,并讨论了并讨论了GAGA在自动博弈中的应用在自动博弈中的应用. .5.1 5.1 引言引言619701970年年,Cavicchio,Cavicchio把把GAGA应用于模式识别中应用于模式识别中. .第一个把第一个把GAGA应用于函数优化的是应用于函数优化的是Hollstien.Hollstien.而而GAGA的理论和方法的系统性研究开始于的理论和方法的系统性研究开始于19751975年年, ,这一开创性工作是由这一开创性工作是由J.H.HollandJ.H.Holland所实行所实行. .n这一年是这一年是GAGA

6、研究的历史上十分重要的一年研究的历史上十分重要的一年. .nHollandHolland在他的著名专著在他的著名专著Adaptation in Natural Adaptation in Natural and Artificial Systemsand Artificial Systems中系统地阐述了中系统地阐述了GAGA的基的基本理论和方法本理论和方法, ,并提出了对并提出了对GAGA的理论研究和发展极为的理论研究和发展极为重要的模式理论重要的模式理论(schemata theory).(schemata theory).n该理论首次确认了结构重组遗传操作对于获得隐并该理论首次确认了结构

7、重组遗传操作对于获得隐并行性的重要性行性的重要性. .5.1 5.1 引言引言7同年同年,DeJong,DeJong完成了他的重要论文完成了他的重要论文遗传自适应遗传自适应系统的行为分析系统的行为分析. .n他在该论文中所做的研究工作可看作是他在该论文中所做的研究工作可看作是GAGA发展过程发展过程中的一个里程碑中的一个里程碑, ,这是因为他把这是因为他把HollandHolland的模式理论的模式理论与他的计算使用结合起来与他的计算使用结合起来. .19891989年年GoldbergGoldberg对对GAGA从理论上从理论上, ,方法上和应用上方法上和应用上作了系统的总结作了系统的总结.

8、 .19901990年代以来年代以来, ,以以GAGA为代表的进化类算法及计算为代表的进化类算法及计算智能理论和算法得到极大重视智能理论和算法得到极大重视.1994.1994年在美国召年在美国召开了第一届世界计算智能大会开了第一届世界计算智能大会, ,欣起了进化类算欣起了进化类算法研究和应用的热潮法研究和应用的热潮. .5.1 5.1 引言引言8nGAGA与其它优化方法相比与其它优化方法相比, ,具有如下特点具有如下特点: :GAGA不是直接作用在参变量集上不是直接作用在参变量集上, , 而是利用参变而是利用参变量集的某种编码量集的某种编码; ;GAGA不是从单个点不是从单个点, , 而是在群

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

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

11、al solution within finite timefinite timeWeak theoretical basisWeak theoretical basisnGAGA能解决的问题能解决的问题: :优化优化NPNP完全完全高度复杂的非线性问题高度复杂的非线性问题5.1 5.1 引言引言11n近年近年,GA,GA在各应用领域中得到极大重视在各应用领域中得到极大重视, ,并广泛应用并广泛应用于各领域的优化、搜索、问题求解中于各领域的优化、搜索、问题求解中, ,并在并在模式识别、模式识别、NNNN、图像处理、图像处理、机器学习、机器学习、工业优化控制、工业优化控制、自适应控制、自适应控制

12、、生物科学、生物科学、社会科学社会科学等方面都得到应用等方面都得到应用. .5.1 5.1 引言引言125.2 GA5.2 GA的基本概念的基本概念nGAGA的基本思想是基于达尔文的基本思想是基于达尔文(Darwin)(Darwin)进化论进化论和门德尔和门德尔(Mendel)(Mendel)的遗传学说的的遗传学说的, ,下面将分别下面将分别介绍介绍: :DarwinDarwin进化论及进化系统模型进化论及进化系统模型MendelMendel的遗传学说的遗传学说GAGA的基本概念与术语的基本概念与术语135.2.1 Darwin5.2.1 Darwin进化论及进化系统模型进化论及进化系统模型C

13、harles DarwinAll environments 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

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

15、系统模型155.2.1 Darwin5.2.1 Darwin进化论及进化系统模型进化论及进化系统模型生物进化过程生物进化过程( (循环图循环图):):初始群体淘汰体竞争初始种群繁殖变异新的群体16n自自DarwinDarwin以来的新进化学说强调以来的新进化学说强调: :个体是基本的选择目标个体是基本的选择目标; ;随机过程在进化中起重大作用随机过程在进化中起重大作用, ,遗传变异大部分遗传变异大部分是偶然现象是偶然现象; ;进化是在适应中变化的进化是在适应中变化的, ,形式多样形式多样, ,不仅是基因不仅是基因的变化的变化; ;选择是概率型的选择是概率型的, ,而不是决定型的而不是决定型的.

16、 .5.2.1 Darwin5.2.1 Darwin进化论及进化系统模型进化论及进化系统模型175.2.2 Mendel5.2.2 Mendel遗传学说遗传学说Gregor Mendel它认为遗传以密码方式它认为遗传以密码方式存在细胞中存在细胞中, ,并以基因形并以基因形式包含在染色体内式包含在染色体内. .每个基因有特殊的位置每个基因有特殊的位置并控制某种特殊性质并控制某种特殊性质; ;所所以以, ,每个基因产生的个体每个基因产生的个体对环境具有某种适应性对环境具有某种适应性. .nMendel(Mendel(1822-1884, 1822-1884, Father Father o of

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

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

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

20、与基因位置n基因特征值基因特征值n适应度适应度225.2.3 GA5.2.3 GA的基本概念与术语的基本概念与术语A. A. 串串(String)(String)它是个体它是个体(Individual)(Individual)的基因表示形式的基因表示形式, ,本质为本质为如何表示解如何表示解. .在算法中常采用给定长度的二进制串在算法中常采用给定长度的二进制串, ,其特点操其特点操作简便作简便. .如串如串S=1011S=1011根据具体问题也可采用特定的适宜于问题处理根据具体问题也可采用特定的适宜于问题处理的编码方式的编码方式, ,如如n实数编码实数编码nD D进制进制, , D D=3,8

21、,16,=3,8,16,n序列编码序列编码: :例如例如TSPTSP的路径表达的路径表达n自适应编码自适应编码- -长度可调节长度可调节235.2.3 GA5.2.3 GA的基本概念与术语的基本概念与术语B. B. 群体群体(Population)(Population)个体的集合称为群体个体的集合称为群体, ,串是群体的元素串是群体的元素. .nA population A population is a set is a set of possible solutions.of possible solutions.GAGA之所以具有良好的优化性能和智能行为之所以具有良好的优化性能和智能行

22、为, ,除开除开交叉和变异等遗传操作具有独到的优化能力交叉和变异等遗传操作具有独到的优化能力, ,正正是由于其优化过程是针对群体而非仅仅针对单是由于其优化过程是针对群体而非仅仅针对单个个体进行个个体进行. .对群体的优化除保证子代群体能够继承父代群对群体的优化除保证子代群体能够继承父代群体的优势特征之外体的优势特征之外, ,重要的其在一定程度上保证重要的其在一定程度上保证所搜索到的解具有某种全局性所搜索到的解具有某种全局性. .群体进化行为在一定程度上可避免个体进化和群体进化行为在一定程度上可避免个体进化和优化的局部性、非单调性等优化的局部性、非单调性等. .245.2.3 GA5.2.3 G

23、A的基本概念与术语的基本概念与术语C. C. 群体规模群体规模(Population Size)(Population Size)群体规模指群体中个体的数量群体规模指群体中个体的数量. .由于由于GAGA的优化是针对群体进行的的优化是针对群体进行的, ,因此群体规模因此群体规模是非常重要的一个参数是非常重要的一个参数Many researchers suggest population sizes Many researchers suggest population sizes between 25 and 100.between 25 and 100. 255.2.3 GA5.2.3 GA

24、的基本概念与术语的基本概念与术语D. D. 基因基因(Gene)(Gene)与基因位置与基因位置(Gene Position)(Gene Position)基因基因是串中的元素是串中的元素, ,基因用于表示个体的特征基因用于表示个体的特征. .基因位置基因位置是指一个基因在串中的位置是指一个基因在串中的位置, ,有时也简有时也简称基因位称基因位. .n基因位置对应于遗传学中的地点基因位置对应于遗传学中的地点(Locus).(Locus).例如有一个串例如有一个串S=1011,S=1011,则其中的则其中的1,0,1,11,0,1,1这这4 4个元个元素分别称为基因素分别称为基因. .n基因位置

25、由串的左向右计算基因位置由串的左向右计算, ,例如在串例如在串S=1011S=1011中中,0,0的的基因位置是基因位置是2.2.265.2.3 GA5.2.3 GA的基本概念与术语的基本概念与术语E. E. 基因特征值基因特征值(Gene Feature)(Gene Feature)在用串表示整数时在用串表示整数时, ,基因的特征值与二进制数的基因的特征值与二进制数的权一致权一致; ;例如在串例如在串S=1011S=1011中中, ,基因位置基因位置3 3中的中的1,1,它的基因它的基因特征值为特征值为2;2;基因位置基因位置1 1中的中的1,1,它的基因特征值为它的基因特征值为8.8.27

26、5.2.3 GA5.2.3 GA的基本概念与术语的基本概念与术语F. F. 适应度适应度(Fitness)(Fitness)表示某一个体对于环境的适应程度表示某一个体对于环境的适应程度, ,是是GAGA进行优进行优化的指标函数化的指标函数. .在优化过程中在优化过程中, ,通过适应度可以进行个体优劣的通过适应度可以进行个体优劣的比较比较, ,可以进行个体的筛选可以进行个体的筛选, ,以产生子代群体以产生子代群体, ,或或选择个体参加交叉和变异等遗传操作选择个体参加交叉和变异等遗传操作. .一般一般, ,适应度函数定义为适应度函数定义为0,10,1之间的实数之间的实数. .n适应度函数值越大适应

27、度函数值越大, ,表示该个体越适应环境表示该个体越适应环境( (问题问题),),就越优就越优. .n因此因此GAGA是对适应度函数求极大优化是对适应度函数求极大优化. .285.2.3 GA5.2.3 GA的基本概念与术语的基本概念与术语nGAGA还有一些其它的概念还有一些其它的概念, ,这些概念在介绍这些概念在介绍GAGA的的原理和执行过程时原理和执行过程时, ,再进行说明再进行说明. .295.3 GA5.3 GA的原理的原理nGAGA把问题的解表示成把问题的解表示成“染色体染色体”, ,在算法中也在算法中也即是以二进制编码的串即是以二进制编码的串. .并且并且, ,在执行在执行GAGA之

28、前之前, ,给出一群给出一群“染色体染色体”, ,也即也即是假设解是假设解. .然后然后, ,把这些假设解置于问题的把这些假设解置于问题的“环境环境”中中, ,并并按适者生存的原则按适者生存的原则, ,从中选择出较适应环境的从中选择出较适应环境的“染色体染色体”进行复制进行复制, ,再通过交叉再通过交叉, ,变异过程产变异过程产生更适应环境的新一代生更适应环境的新一代“染色体染色体”群群. .这样这样, ,一代一代地进化一代一代地进化, ,最后就会收敛到最适应最后就会收敛到最适应环境的一个环境的一个“染色体染色体”上上, ,它就是问题的最优解它就是问题的最优解. .305.3 GA5.3 GA

29、的原理的原理n下面分别介绍下面分别介绍: :GAGA的目的的目的GAGA的基本原理的基本原理GAGA的算法过程的算法过程315.3.1 GA5.3.1 GA的目的的目的n典型的遗传算法典型的遗传算法(canonical genetic algorithm, CGA)通常用于解决下面这一类的静态最优化问题通常用于解决下面这一类的静态最优化问题:考 虑 对 于 一 群 长 度 为考 虑 对 于 一 群 长 度 为 L 的 二 进 制 编 码的 二 进 制 编 码bi,i=1,2,n;有有bi0,1L (1)给定目标函数给定目标函数f,有有f(bi),并且并且0f(bi) 求满足下式求满足下式max

30、f(bi)|bi0,1L (2)的的bi.325.3.1 GA5.3.1 GA的目的的目的n很明显很明显,GA,GA是一种最优化方法是一种最优化方法, ,它通过进化和它通过进化和遗传机理遗传机理, ,从给出的原始解群中从给出的原始解群中, ,不断进化产不断进化产生新的解生新的解, ,最后收敛到一个特定的串最后收敛到一个特定的串b bi i处处, ,即即求出最优解求出最优解. .335.3.2 GA5.3.2 GA的基本原理的基本原理n长度为长度为L L的的n n个二进制串个二进制串b bi i( (i=i=1,2,1,2, ,n n) )组成组成了了GAGA的初解群的初解群, ,也称为初始群体

31、也称为初始群体. .在每个串中在每个串中, ,每个二进制位就是个体染色体的基每个二进制位就是个体染色体的基因因. .根据进化术语根据进化术语, ,对群体执行的操作有三种对群体执行的操作有三种: :n选择与再生选择与再生n重组与交叉重组与交叉n变异变异345.3.2 GA5.3.2 GA的基本原理的基本原理A. A. 选择选择(Selection)(Selection)与再生与再生(Reproduction)(Reproduction)n选择是根据适者生存原则从群体中选择出较适应环选择是根据适者生存原则从群体中选择出较适应环境的个体以生产子代境的个体以生产子代. .在选择时在选择时, ,以适应度

32、为选择原则以适应度为选择原则. .适应度准则体现了适者生存适应度准则体现了适者生存, ,不适应者淘汰的自然法则不适应者淘汰的自然法则. .这些选中的个体用于繁殖下一代这些选中的个体用于繁殖下一代. .n故有时也称这一操作为再生故有时也称这一操作为再生(reproduction).(reproduction).由于在选择用于繁殖下一代的个体时由于在选择用于繁殖下一代的个体时, ,是根据个体对环是根据个体对环境的适应度而决定其繁殖量的境的适应度而决定其繁殖量的, ,故而有时也称为非均匀故而有时也称为非均匀再生再生(differential reproduction).(differential r

33、eproduction).355.3.2 GA5.3.2 GA的基本原理的基本原理早期的早期的GAGA算法产生的新一代均是从父代的个体算法产生的新一代均是从父代的个体经交叉与变异产生的子代中由基于选择概率的经交叉与变异产生的子代中由基于选择概率的选择算子选择产生的选择算子选择产生的. .n这种选择策略使得进化过程可能似的优化的解被丢这种选择策略使得进化过程可能似的优化的解被丢弃弃, ,产生退化产生退化. .n实践证明使用保留父代群体中最佳个体模型至子代实践证明使用保留父代群体中最佳个体模型至子代的的GAGA比基本比基本GAGA的性能有明显的改进的性能有明显的改进, ,该该GAGA成为成为保留最

34、保留最优个体遗传算法优个体遗传算法. .365.3.2 GA5.3.2 GA的基本原理的基本原理n下面主要讨论基于适应度函数产生的选择概率来选择的方法- Proportionate-based selectionn一般在GA的选择中,由个体的适应度函数值计算相应的选择概率,并按照轮盘赌的方式选择需要进行遗传运算的个体(参加遗传操作的父亲和母亲).设目标函数为f,则f(bi)称为个体bi的适应度.相应地,个体bi的选择概率为)3()()(1njjiibfbfbP 选中 选择概率一般用于选择下一代(子代)群体,以及参加交叉和变异操作的个体.在选择参加交叉和变异操作的个体时采用轮盘赌的方式,如下图所

35、示375.3.2 GA5.3.2 GA的基本原理的基本原理b1b2b3b4b5b6b7b8b9b10b11图2 随机选择遗传操作的轮盘赌385.3.2 GA5.3.2 GA的基本原理的基本原理选择方法选择方法: : （a a）从适应度大小出发）从适应度大小出发( (四舍五入概念四舍五入概念).). 定义定义: :选择概率选择概率 , ,选择选择 的个的个数数:n:n* * . . (b) (b)从相对适应度出发选择从相对适应度出发选择. . 定义定义: : 相对适应度相对适应度, , 平均适应度平均适应度, , 分析分析: : )(ixPix)(ixPfxfii)(fnxffii)()()()

36、()(iiiiiixnPxfxnffxf直接从相对适应度出发,四舍五入取整选择.395.3.2 GA5.3.2 GA的基本原理的基本原理n显然显然, ,从式从式(3)(3)可知可知: :A.A. 适应度较高的个体适应度较高的个体, ,繁殖下一代的数目较多繁殖下一代的数目较多. .反之适应度较小的个体反之适应度较小的个体, ,繁殖下一代的数目较少繁殖下一代的数目较少; ;甚至被淘汰甚至被淘汰. .B.B. 适应度较高的个体有较多的机会参与交叉和变异等适应度较高的个体有较多的机会参与交叉和变异等遗传操作遗传操作. .这样这样, ,就产生了对环境适应能力较强的后代就产生了对环境适应能力较强的后代.

37、.对于问题求解角度来讲对于问题求解角度来讲, ,就是选择出和最优解较就是选择出和最优解较接近的中间解接近的中间解. .405.3.2 GA5.3.2 GA的基本原理的基本原理B. B. 重组重组( (RecombinationRecombination) )与交叉与交叉(Crossover)(Crossover)这是在选中用于繁殖下一代的个体中这是在选中用于繁殖下一代的个体中, ,对两个不对两个不同的个体的相同位置的基因进行交换同的个体的相同位置的基因进行交换, ,从而产生从而产生新的个体新的个体. .415.3.2 GA5.3.2 GA的基本原理的基本原理n对于选中用于繁殖下一代的个体对于选

38、中用于繁殖下一代的个体, ,按选择概率按选择概率以轮盘赌的方式随机地选择两个个体作为父以轮盘赌的方式随机地选择两个个体作为父代代, ,并随机选取相同的基因位置并随机选取相同的基因位置, ,按交叉概率按交叉概率P Pc c, ,在选中的位置实行交换在选中的位置实行交换. .这个过程反映了随机信息交换这个过程反映了随机信息交换; ;n目的在于产生新的基因组合目的在于产生新的基因组合, ,也即产生新的个体也即产生新的个体. .交叉时交叉时, ,可实行单点交叉、多点交叉及一致交叉可实行单点交叉、多点交叉及一致交叉( (Uniform CrossoverUniform Crossover).).n从理论

39、上讲从理论上讲, ,多点交叉可以由多次单点交叉实现多点交叉可以由多次单点交叉实现. .n对于多点交叉算子对于多点交叉算子, ,随着交叉点数的增加会降低随着交叉点数的增加会降低GAGA的的性能性能42 例如有2个父代个体S1=100|101 S2=010|111若随机选择它们的左边3位进行交叉操作,则产生的子代为S1=010|101 S2=100|1115.3.2 GA5.3.2 GA的基本原理的基本原理n下面介绍具体的交叉算子算法:(1) 二进制单点交叉算子二进制单点交叉算子. 单点交叉过程可图示如下: Parents Children 435.3.2 GA5.3.2 GA的基本原理的基本原理

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

41、位为1,则子代的该位继承父亲;若为0,则子代的该位继承母亲.屏蔽字交叉过程可图示如下: Parents Children 屏蔽字 1 0 1 1 0 0 1 0 455.3.2 GA5.3.2 GA的基本原理的基本原理n对选择算子选作交叉的父代,是否进行交叉运算,以交叉概率Pc决定。一般而言,交叉概率Pc取值为65.3.2 GA5.3.2 GA的基本原理的基本原理C. 变异变异(Mutation)n变异是根据生物遗传中基因变异的原理,按选择概率以轮盘赌的方式随机地选择一个个体作为父代,并随机选取基因位置以变异概率Pm对某些个体的某些基因位执行异向转化.在变异时,对执行变异的

42、串的对应基因位求反.n产生变异时就是把它变成0;反亦反之.变异概率Pm与生物变异极小的情况一致,所以,Pm的取值较小,一般取0.010.2.475.3.2 GA5.3.2 GA的基本原理的基本原理n下面介绍具体的变异算子算法:二进制变异算子二进制变异算子.变异过程可图示如下: 求反 Parents Children 例如有父代个体S=101011对其的第1,4位置的基因进行变异,则有S=001111485.3.2 GA5.3.2 GA的基本原理的基本原理变异算子的过程为:BeginRepeat 对所有交叉算子产生的新子代的个体数n产生（0，1）间的随机数sn若s小于等于变异概率Pm,则随机产生

43、变异位Lm对个体i在变异位Lm进行变异操作,生成新子代个体EndEnd495.3.2 GA5.3.2 GA的基本原理的基本原理n对变异算子的作用对变异算子的作用, ,有如下讨论有如下讨论单靠变异不能在求解中得到好处单靠变异不能在求解中得到好处. .n但是但是, ,它能保证算法过程不会产生无法进化的单一群它能保证算法过程不会产生无法进化的单一群体体. .n在所有的个体趋向一样时在所有的个体趋向一样时, ,交叉是无法产生新的个体交叉是无法产生新的个体的的, ,这时只能靠变异产生新的个体这时只能靠变异产生新的个体, ,以保持群体的多以保持群体的多样性样性, ,避免早熟避免早熟. .n也就是说也就是说

44、, ,变异增加了全局优化的特质变异增加了全局优化的特质. .n虽然变异概率的增大也会增加群体的多样性虽然变异概率的增大也会增加群体的多样性, ,但它却但它却降低了降低了GAGA的性能的性能, ,并且随着变异概率的增大并且随着变异概率的增大,GA,GA的性的性能越来越接近于随机搜索算法的性能能越来越接近于随机搜索算法的性能. .505.3.2 GA5.3.2 GA的基本原理的基本原理n除前面讨论的除前面讨论的变异算子外变异算子外, ,还有如下常用的变还有如下常用的变异算子异算子多点变异多点变异随机变异随机变异n区间内均匀随机取区间内均匀随机取515.3.3 GA5.3.3 GA的算法过程的算法过

45、程n基于上述基于上述GAGA的原理和的原理和基因操作基因操作, ,可总结出可总结出GAGA的基本过程的基本过程. .GAGA的算法流程如右图的算法流程如右图所示；所示；其相应的算法如下所其相应的算法如下所示示. . N Y 初始化 计算个体适应 值和选择概率 选择 交叉 变异 群体收敛否? 结束 525.3.3 GA5.3.3 GA的算法过程的算法过程GA算法算法choose an intial populationdetermine the fitness of each individualperform selectionrepeatperform crossover at crosso

46、ver probability Pcperform mutation at crossover probability Pmdetermine the fitness of each individualperform selectionuntil some stopping criterion applies535.3.3 GA5.3.3 GA的算法过程的算法过程n在在GAGA的初始化过程的初始化过程, ,主要的工作为决定主要的工作为决定GAGA的各的各参数与初始群体参数与初始群体. .需确定的需确定的GAGA的主要参数有的主要参数有: :n群体规模群体规模n交叉概率交叉概率n变异概率变异概

47、率对初始群体对初始群体, ,通常以随机方法产生通常以随机方法产生. .n为保证群体的多样性为保证群体的多样性, ,以及不遗漏某些基因的遗传因以及不遗漏某些基因的遗传因子子, ,初始群体的离散度应较大初始群体的离散度应较大. .n问题的最优解将通过这些初始假设解进化而求出问题的最优解将通过这些初始假设解进化而求出. .545.3.3 GA5.3.3 GA的算法过程的算法过程n选择、交叉和变异是选择、交叉和变异是GAGA的三种基本操作的三种基本操作. .群体正是在这三种操作的交替运行过程中群体正是在这三种操作的交替运行过程中, ,得到得到进化进化( (优化优化),),提升智能提升智能. .群体进化

48、的结束的标志是群体的某种性能指标群体进化的结束的标志是群体的某种性能指标达到预先定义的某种结束准则达到预先定义的某种结束准则. .这里所指的某种结束准则一般是指个体的适应这里所指的某种结束准则一般是指个体的适应度达到给定的阈值度达到给定的阈值; ;或者个体的适应度的变化率或者个体的适应度的变化率为零为零. .下图显示出选择、交叉和变异这三种运算是如下图显示出选择、交叉和变异这三种运算是如何交替迭代进行的何交替迭代进行的. .555.3.3 GA5.3.3 GA的算法过程的算法过程图3 GA原理565.3.3 GA5.3.3 GA的算法过程的算法过程n当最优个体的适应度达到给定的阈值当最优个体的

49、适应度达到给定的阈值, ,或者最或者最优个体的适应度和群体适应度不再上升时优个体的适应度和群体适应度不再上升时, ,则则算法的迭代过程收敛、算法结束算法的迭代过程收敛、算法结束. .否则否则, ,用经过选择、交叉、变异所得到的新一代用经过选择、交叉、变异所得到的新一代群体取代上一代群体群体取代上一代群体, ,并返回到第并返回到第2 2步即选择操步即选择操作处继续循环执行作处继续循环执行. .图图3 3中表示了中表示了GAGA的执行过程的执行过程. .575.4 GA5.4 GA的应用的应用q GAGA在很多领域都得到应用在很多领域都得到应用, ,如函数优化、如函数优化、NNNN学习、方程求解、

50、学习、方程求解、控制工程、系统工程、计算机科学等领域控制工程、系统工程、计算机科学等领域. . 在在GAGA应用中应用中, ,应先明确其特点和关键问题应先明确其特点和关键问题, ,才能对这种算才能对这种算法深入了解法深入了解, ,灵活应用灵活应用, ,以及进一步研究开发以及进一步研究开发. . 下面介绍下面介绍: : GAGA在函数优化中的应用在函数优化中的应用58q 考虑如下实函数的优化命题GAGA在函数优化中的应用在函数优化中的应用min( )(4)gxx其中x为n维优化变量向量.q 在利用GA对式(4)所示的函数优化命题进行运算时,需考虑的问题是: 适应度函数 由于上述函数优化命题为求极

51、小,因此,在转换成适应度函数时,可采取以下两种方法.59GAGA在函数优化中的应用在函数优化中的应用1 1）转化成最大化问题）转化成最大化问题, ,且保证非负性。且保证非负性。 ( (目标函数目标函数) ) C C为人为设定的足够大的正数。为人为设定的足够大的正数。 2 2）若能保证）若能保证g(x)g(x)是正的是正的, ,则则 注意：若问题本身是最大化注意：若问题本身是最大化, ,但不能保证但不能保证g(x)g(x)非负非负性性)()(maxmaxxgCxf)(1)(maxxgxf)()(maxminxgCxf0)(minxgC60GAGA在函数优化中的应用在函数优化中的应用 个体编码 对

52、该优化命题,可采用二进制编码或实数编码. 若采用实数编码,则可将变量向量x的每一变量分量变换成02L-1间的二进制数(其中L为每个变量分量对应的二进制串的长度). 然后将各变量分量所对应的二进制串按次序或某种规则排列策划功能成GA中的串.61GAGA在函数优化中的应用在函数优化中的应用 群体规模、交叉和变异概率 对如何选取群体规模、交叉和变异概率这些GA所需要的参数,目前还没有能得到非常具体的选取方法,只有一些经验性质的指导原则. 针对具体的优化问题,需要作具体分析,以及还要依赖于使用者的所掌握的经验和技巧. 对交叉和变异概率的选取,有研究人员提出一些自适应选取策略,在一定程度上有助于GA的应

53、用. 但是在GA的优化机理缺乏严格研究的情况下,自适应策略的效果也未有严格的分析和证明.62GAGA在函数优化中的应用在函数优化中的应用q 下面简单讨论函数优化的GA 算例.q 算例算例 用CGA求解如下函数优化问题31, 0)(max2xxxfxq 在该算例中,为简单便于说明起见,选择: 个体编码长度为5位二进制 群体个数为4 适应度函数直接为函数值 交叉概率1.0,变异概率0.75(通常变异概率应非常小)GA计算结果为63GAGA在函数优化中的应用在函数优化中的应用初始群体与第一次选择编号群体变量函数值x2选择百分比期望复制数目实际复制数目1234011011100001000100111

54、324819169576643610.14440.49230.05470.30850.57781.96920.21881.23421201和平均值最大值1170292.557610.25000.4923411.969241264GAGA在函数优化中的应用在函数优化中的应用第一次交叉编号交配池交配对交配位置新的群体变量函数值x212340110 | 111 | 0001100 | 010 | 0111,32,4420110011001110111000012252716144625729256和平均值最大值(随机产生)(随机产生)175443972965GAGA在函数优化中的应用在函数优化中的应

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