1、遗传算法及在神遗传算法及在神经网络中的应用经网络中的应用目 录n引言引言nGAGA的基本概念的基本概念DarwinDarwin进化论及进化系统模型进化论及进化系统模型MendelMendel的遗传学说的遗传学说GAGA的基本概念与术语的基本概念与术语nGAGA的原理的原理GAGA的目的的目的GAGA的基本原理的基本原理GAGA的算法过程的算法过程目 录nGAGA的应用的应用GAGA的特点的特点GAGA应用的关键应用的关键GAGA在函数优化中的应用在函数优化中的应用GAGA在组合优化中的应用在组合优化中的应用nGAGA的理论分析的理论分析nGAGA在智能控制中的应用在智能控制中的应用n遗传算法优
2、化神经网络遗传算法优化神经网络n遗传神经网络应用设计遗传神经网络应用设计nGAGA的发展展望的发展展望n参考文献参考文献7.1 7.1 引言引言n生物的进化是一个奇妙的优化过程生物的进化是一个奇妙的优化过程,它通过选择淘它通过选择淘汰汰,突然变异突然变异,基因遗传等规律产生适应环境变化的基因遗传等规律产生适应环境变化的优良物种优良物种.例如例如,在人类的进化过程中在人类的进化过程中,通过通过“物竞天择、适者生存物竞天择、适者生存”自然的选择和淘汰自然的选择和淘汰,人类的身、心不断得到进化人类的身、心不断得到进化,逐渐进逐渐进化成为这地球上的具有最高等智慧的主宰者化成为这地球上的具有最高等智慧的
3、主宰者.在这个进化过程中在这个进化过程中,不仅人的身体得到进化不仅人的身体得到进化,而且而且人的智人的智慧、智能慧、智能也在得到进化也在得到进化.因此因此,生物的进化过程其实也是一种智能的进化、优化生物的进化过程其实也是一种智能的进化、优化过程过程,也是一种智能行为也是一种智能行为.“物竞天择、适者生存物竞天择、适者生存”中蕴中蕴涵了智能的光辉、蕴涵了优化的思想涵了智能的光辉、蕴涵了优化的思想.n遗传算法遗传算法(Genetic(Genetic Algorithm,GAAlgorithm,GA)就是根据生物进就是根据生物进化思想而启发得出的一种智能理论和方法化思想而启发得出的一种智能理论和方法
4、.它是基于进化过程中的信息遗传机制和优胜劣汰的自然它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法选择原则的搜索算法,是通过对生物进化的归纳和模拟得是通过对生物进化的归纳和模拟得到的一种仿生算法到的一种仿生算法.GAGA在本质上是一种不依赖具体问题的直接搜索方法在本质上是一种不依赖具体问题的直接搜索方法,是一是一种具有普适性的优化方法种具有普适性的优化方法.nGAGA的发展历程为的发展历程为:19651965年年,Michigan,Michigan大学的大学的HollandHolland首次提出了人工遗传操首次提出了人工遗传操作的重要性作的重要性,并把这些应用于自然系统和人工
5、系统中并把这些应用于自然系统和人工系统中.19671967年年,J.D.BagleyJ.D.Bagley在他的论文中首次提出了在他的论文中首次提出了GAGA这一术这一术语与概念语与概念,并讨论了并讨论了GAGA在自动博弈中的应用在自动博弈中的应用.7.1 7.1 引言引言19701970年年,CavicchioCavicchio把把GAGA应用于模式识别中应用于模式识别中.第一个把第一个把GAGA应用于函数优化的是应用于函数优化的是HollstienHollstien.而而GAGA的理论和方法的系统性研究开始于的理论和方法的系统性研究开始于19751975年年,这一开创性工作是由这一开创性工作
6、是由J.H.HollandJ.H.Holland所实行所实行.n这一年是这一年是GAGA研究的历史上十分重要的一年研究的历史上十分重要的一年.nHollandHolland在他的著名专著在他的著名专著Adaptation in Natural Adaptation in Natural and Artificial Systemsand Artificial Systems中系统地阐述了中系统地阐述了GAGA的基的基本理论和方法本理论和方法,并提出了对并提出了对GAGA的理论研究和发展极为的理论研究和发展极为重要的模式理论重要的模式理论(schemata theory).(schemata t
7、heory).n该理论首次确认了结构重组遗传操作对于获得隐并该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性行性的重要性.7.1 7.1 引言引言同年同年,DeJongDeJong完成了他的重要论文完成了他的重要论文遗传自适应遗传自适应系统的行为分析系统的行为分析.n他在该论文中所做的研究工作可看作是他在该论文中所做的研究工作可看作是GAGA发展过程发展过程中的一个里程碑中的一个里程碑,这是因为他把这是因为他把HollandHolland的模式理论的模式理论与他的计算使用结合起来与他的计算使用结合起来.19891989年年GoldbergGoldberg对对GAGA从理论上从理论上,方
8、法上和应用上方法上和应用上作了系统的总结作了系统的总结.19901990年代以来年代以来,以以GAGA为代表的进化类算法及计算为代表的进化类算法及计算智能理论和算法得到极大重视智能理论和算法得到极大重视.1994.1994年在美国召年在美国召开了第一届世界计算智能大会开了第一届世界计算智能大会,欣起了进化类算欣起了进化类算法研究和应用的热潮法研究和应用的热潮.7.1 7.1 引言引言nGAGA与其它优化方法相比与其它优化方法相比,具有如下特点具有如下特点:GAGA不是直接作用在参变量集上不是直接作用在参变量集上,而是利用参变而是利用参变量集的某种编码量集的某种编码;GAGA不是从单个点不是从单
9、个点,而是在群体中从多个点开始而是在群体中从多个点开始搜索搜索;GAGA利用适应值信息利用适应值信息,无需导数或其它辅助信息无需导数或其它辅助信息;n因此对优化问题因此对优化问题(函数函数)的限制较弱的限制较弱,灵活灵活,通用性通用性(普普适性适性)强强,有着较广泛的应用领域有着较广泛的应用领域.GAGA利用概率转移规则利用概率转移规则,而非确定性规则而非确定性规则.GAGA在解空间内不是盲目的穷举或完全随机测试，在解空间内不是盲目的穷举或完全随机测试，而是一种启发式搜索，效率优于其它算法。而是一种启发式搜索，效率优于其它算法。7.1 7.1 引言引言nGAGA的优点的优点:较容易的和其它方法
10、结合较容易的和其它方法结合避免陷入局部最优解避免陷入局部最优解n即使在较短的有限时间内即使在较短的有限时间内,也能获得较好的次优解、也能获得较好的次优解、满意解满意解.鲁棒性佳鲁棒性佳n对优化问题的初始条件对优化问题的初始条件(状态状态)依赖性小。依赖性小。n 抗干扰性强。抗干扰性强。具有并行计算的特点，可提高计算速度具有并行计算的特点，可提高计算速度7.1 7.1 引言引言nGAGA的不足的不足:No guarantee for optimal solution within No guarantee for optimal solution within finite timefinite
11、 timeWeak theoretical basisWeak theoretical basisnGAGA能解决的问题能解决的问题:优化优化NPNP完全完全高度复杂的非线性问题高度复杂的非线性问题7.1 7.1 引言引言n近年近年,GA,GA在各应用领域中得到极大重视在各应用领域中得到极大重视,并广泛应用并广泛应用于各领域的优化、搜索、问题求解中于各领域的优化、搜索、问题求解中,并在并在模式识别、模式识别、NNNN、图像处理、图像处理、机器学习、机器学习、工业优化控制、工业优化控制、自适应控制、自适应控制、生物科学、生物科学、社会科学社会科学等方面都得到应用等方面都得到应用.7.1 7.1
12、引言引言n当前在当前在AIAI研究中研究中,人们认为人们认为“GAGA、自适应系、自适应系统、细胞自动机、混沌理论与统、细胞自动机、混沌理论与AIAI一样一样,都是都是对今后十年的计算技术有重大影响的关键对今后十年的计算技术有重大影响的关键技术技术”.7.1 7.1 引言引言7.2 GA7.2 GA的基本概念的基本概念nGAGA的基本思想是基于达尔文的基本思想是基于达尔文(Darwin)(Darwin)进化论进化论和门德尔和门德尔(Mendel)(Mendel)的遗传学说的的遗传学说的,下面将分别下面将分别介绍介绍:DarwinDarwin进化论及进化系统模型进化论及进化系统模型MendelM
13、endel的遗传学说的遗传学说GAGA的基本概念与术语的基本概念与术语7.2.1 Darwin7.2.1 Darwin进化论及进化系统模型进化论及进化系统模型Charles 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)它认为每一物种在发展中越来它认为每一物种在
14、发展中越来越适应环境越适应环境.nDarwin(Darwin(1809-1882,1809-1882,Father Father o of f the the evevololutiutio on then theo oryry)进化论最进化论最重要的是重要的是适者生存适者生存(Survival of(Survival of the fittest)the fittest)原理原理.物种每个个体的基本特征由后代所继承物种每个个体的基本特征由后代所继承,但后代但后代又会产生一些异于父代的新变化又会产生一些异于父代的新变化.在环境变化时在环境变化时,只有那些能适应环境的个体特征只有那些能适应环境的
15、个体特征方能保留下来方能保留下来.7.2.1 Darwin7.2.1 Darwin进化论及进化系统模型进化论及进化系统模型7.2.1 Darwin7.2.1 Darwin进化论及进化系统模型进化论及进化系统模型生物进化过程生物进化过程(循环图循环图):):初始群体淘汰体竞争初始种群繁殖变异新的群体n自自DarwinDarwin以来的新进化学说强调以来的新进化学说强调:个体是基本的选择目标个体是基本的选择目标;随机过程在进化中起重大作用随机过程在进化中起重大作用,遗传变异大部分遗传变异大部分是偶然现象是偶然现象;进化是在适应中变化的进化是在适应中变化的,形式多样形式多样,不仅是基因不仅是基因的变
16、化的变化;选择是概率型的选择是概率型的,而不是决定型的而不是决定型的.7.2.1 Darwin7.2.1 Darwin进化论及进化系统模型进化论及进化系统模型7.2.2 Mendel7.2.2 Mendel遗传学说遗传学说Gregor Mendel它认为遗传以密码方式它认为遗传以密码方式存在细胞中存在细胞中,并以基因形并以基因形式包含在染色体内式包含在染色体内.每个基因有特殊的位置每个基因有特殊的位置并控制某种特殊性质并控制某种特殊性质;所所以以,每个基因产生的个体每个基因产生的个体对环境具有某种适应性对环境具有某种适应性.nMendel(Mendel(1822-1884,1822-1884,
17、Father Father o of genetics)f genetics)遗传学说最重遗传学说最重要的是要的是基因遗传原理基因遗传原理.7.2.2 Mendel7.2.2 Mendel遗传学说遗传学说基因突变和基因杂交可产生更适应于环境的后基因突变和基因杂交可产生更适应于环境的后代代.经过存优去劣的自然淘汰经过存优去劣的自然淘汰,适应性高的基因结适应性高的基因结构得以保存下来构得以保存下来.7.2.3 GA7.2.3 GA的基本概念与术语的基本概念与术语n基于达尔文的进化论与孟德尔的遗传学说基于达尔文的进化论与孟德尔的遗传学说,可可得到如下生物进化的原则得到如下生物进化的原则生物进化过程的
18、发生需要四个基本条件生物进化过程的发生需要四个基本条件:n存在由多个生物个体组成的种群存在由多个生物个体组成的种群;n生物个体之间存在着差异生物个体之间存在着差异,或群体具有多样性或群体具有多样性;n生物能够自我繁殖生物能够自我繁殖;n不同个体具有不同的环境生存能力不同个体具有不同的环境生存能力,具有优良基因结具有优良基因结构的个体繁殖能力强构的个体繁殖能力强,反之则弱反之则弱.7.2.3 GA7.2.3 GA的基本概念与术语的基本概念与术语生物群体的进化机制包括三种基本形式生物群体的进化机制包括三种基本形式:n自然选择自然选择 n杂交杂交n突变突变n另外另外,外界对生物的评价反映了生物的生存
19、价值和机外界对生物的评价反映了生物的生存价值和机会会.受到生物进化过程的启迪受到生物进化过程的启迪,模拟生物进化模拟生物进化的优化方法的优化方法GAGA得到重视并迅速发展得到重视并迅速发展.7.2.3 GA7.2.3 GA的基本概念与术语的基本概念与术语n由于由于GAGA是由进化论和遗传学机理而产生的直是由进化论和遗传学机理而产生的直接搜索优化方法接搜索优化方法,故而在这个算法中要用到各故而在这个算法中要用到各种进化和遗传学的概念种进化和遗传学的概念.这些概念如下这些概念如下:n串串n群体群体n群体规模群体规模n基因与基因位置基因与基因位置n基因特征值基因特征值n适应度适应度7.2.3 GA7
20、.2.3 GA的基本概念与术语的基本概念与术语A.A.串串(String)(String)它是个体它是个体(Individual)(Individual)的基因表示形式的基因表示形式,本质为本质为如何表示解如何表示解.在算法中常采用给定长度的二进制串在算法中常采用给定长度的二进制串,其特点操其特点操作简便作简便.根据具体问题也可采用特定的适宜于问题处理根据具体问题也可采用特定的适宜于问题处理的编码方式的编码方式,如如n实数编码实数编码nD D进制进制,D D=3,8,16,=3,8,16,n序列编码序列编码:例如例如TSPTSP的路径表达的路径表达n自适应编码自适应编码-长度可调节长度可调节7
21、.2.3 GA7.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、对群体而非仅仅针对单个个体进行个个体进行.对群体的优化除保证子代群体能够继承父代群对群体的优化除保证子代群体能够继承父代群体的优势特征之外体的优势特征之外,重要的其在一定程度上保证重要的其在一定程度上保证所搜索到的解具有某种全局性所搜索到的解具有某种全局性.群体进化行为在一定程度上可避免个体进化和群体进化行为在一定程度上可避免个体进化和优化的局部性、非单调性等优化的局部性、非单调性等.7.2.3 GA7.2.3 GA的基本概念与术语的基本概念与术语C.C.群体规模群体规模(Population Size)(Population Size)群体规模指群体中个体的数量群体规模指群体中个体的数量.由
23、于由于GAGA的优化是针对群体进行的的优化是针对群体进行的,因此群体规模因此群体规模是非常重要的一个参数是非常重要的一个参数Many researchers suggest population sizes Many researchers suggest population sizes between 25 and 100.between 25 and 100.7.2.3 GA7.2.3 GA的基本概念与术语的基本概念与术语D.D.基因基因(Gene)(Gene)与基因位置与基因位置(Gene Position)(Gene Position)基因基因是串中的元素是串中的元素,基因用于表示个
24、体的特征基因用于表示个体的特征.基因位置基因位置是指一个基因在串中的位置是指一个基因在串中的位置,有时也简有时也简称基因位称基因位.n基因位置对应于遗传学中的地点基因位置对应于遗传学中的地点(Locus).(Locus).例如有一个串例如有一个串S=1011,S=1011,则其中的则其中的1,0,1,11,0,1,1这这4 4个元个元素分别称为基因素分别称为基因.n基因位置由串的左向右计算基因位置由串的左向右计算,例如在串例如在串S=1011S=1011中中,0,0的的基因位置是基因位置是2.2.7.2.3 GA7.2.3 GA的基本概念与术语的基本概念与术语E.E.基因特征值基因特征值(Ge
25、ne Feature)(Gene Feature)在用串表示整数时在用串表示整数时,基因的特征值与二进制数的基因的特征值与二进制数的权一致权一致;例如在串例如在串S=1011S=1011中中,基因位置基因位置3 3中的中的1,1,它的基因它的基因特征值为特征值为2;2;基因位置基因位置1 1中的中的1,1,它的基因特征值为它的基因特征值为8.8.7.2.3 GA7.2.3 GA的基本概念与术语的基本概念与术语F.F.适应度适应度(Fitness)(Fitness)表示某一个体对于环境的适应程度表示某一个体对于环境的适应程度,是是GAGA进行优进行优化的指标函数化的指标函数.在优化过程中在优化过
26、程中,通过适应度可以进行个体优劣的通过适应度可以进行个体优劣的比较比较,可以进行个体的筛选可以进行个体的筛选,以产生子代群体以产生子代群体,或或选择个体参加交叉和变异等遗传操作选择个体参加交叉和变异等遗传操作.一般一般,适应度函数定义为适应度函数定义为0,10,1之间的实数之间的实数.n适应度函数值越大适应度函数值越大,表示该个体越适应环境表示该个体越适应环境(问题问题),),就越优就越优.n因此因此GAGA是对适应度函数求极大优化是对适应度函数求极大优化.7.2.3 GA7.2.3 GA的基本概念与术语的基本概念与术语nGAGA还有一些其它的概念还有一些其它的概念,这些概念在介绍这些概念在介
27、绍GAGA的的原理和执行过程时原理和执行过程时,再进行说明再进行说明.7.3 GA7.3 GA的原理的原理nGAGA把问题的解表示成把问题的解表示成“染色体染色体”,在算法中也在算法中也即是以二进制编码的串即是以二进制编码的串.并且并且,在执行在执行GAGA之前之前,给出一群给出一群“染色体染色体”,也即也即是假设解是假设解.然后然后,把这些假设解置于问题的把这些假设解置于问题的“环境环境”中中,并并按适者生存的原则按适者生存的原则,从中选择出较适应环境的从中选择出较适应环境的“染色体染色体”进行复制进行复制,再通过交叉再通过交叉,变异过程产变异过程产生更适应环境的新一代生更适应环境的新一代“
28、染色体染色体”群群.这样这样,一代一代地进化一代一代地进化,最后就会收敛到最适应最后就会收敛到最适应环境的一个环境的一个“染色体染色体”上上,它就是问题的最优解它就是问题的最优解.7.3 GA7.3 GA的原理的原理n下面分别介绍下面分别介绍:GAGA的目的的目的GAGA的基本原理的基本原理GAGA的算法过程的算法过程7.3.1 GA7.3.1 GA的目的的目的n典型的遗传算法典型的遗传算法(canonical genetic algorithm,CGA)通常用于解决下面这一类的静态最优化问题通常用于解决下面这一类的静态最优化问题:考 虑 对 于 一 群 长 度 为考 虑 对 于 一 群 长
29、度 为 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 xv7.4.4 GA7.4.4 GA在组合优化中的应用在组合优化中的应用n编码格式：例如x=1100000000表示仅装第1
30、和第2种物品n适应度度量：n选择算子：赌盘选择（与适应值成比例选择）n交叉算子：混合单点交叉n变异算子：混合点变异n进化参数：种群规模，终止进化代数，交叉概率，变异概率=50，500，0.6，0.0512|0,1,1,2,nniHxx xxxin1()niiif xc x7.4.4 GA7.4.4 GA在组合优化中的应用在组合优化中的应用7.4.4 GA7.4.4 GA在组合优化中的应用在组合优化中的应用n其它如其它如8 8皇后问题皇后问题,即即在在n n*n n格的国际象棋棋格的国际象棋棋盘上放置盘上放置n n个皇后个皇后,使使得任意两个皇后不能得任意两个皇后不能互相攻击互相攻击,即任何行、
31、即任何行、列、对角线上不得有列、对角线上不得有两个或两个以上的皇两个或两个以上的皇后后.n这样的格局称为问题这样的格局称为问题的一个解的一个解.7.4.4 GA7.4.4 GA在组合优化中的应用在组合优化中的应用n还有前面提到得还有前面提到得TSPTSP组合优化问题。注意组合优化问题。注意非法解的解决。非法解的解决。A B C D E F J H G J 7.5 GA7.5 GA的理论分析的理论分析qGAGA源于自然选择和生物遗传学源于自然选择和生物遗传学,相对于其鲜明的生物相对于其鲜明的生物基础基础,GA,GA的理论基础公认是不完善的的理论基础公认是不完善的.GAGA的基础理论主要以收敛性分
32、析为主的基础理论主要以收敛性分析为主,即群体收即群体收敛到优化问题的全局最优解的概率敛到优化问题的全局最优解的概率.理论分析主要是基于模式理论的收敛性分析理论分析主要是基于模式理论的收敛性分析,称称之为之为GAGA的进化动力学理论的进化动力学理论.7.5 GA7.5 GA的理论分析的理论分析 n基于某种具体运算形式的基于某种具体运算形式的GAGA的进化行为分析的进化行为分析构成了进化动力学理论的基本内容构成了进化动力学理论的基本内容.由由HollandHolland提出的模式提出的模式(Schema,(Schema,又译图式又译图式)定理可定理可以称为以称为GAGA进化动力学的基本定理进化动力
33、学的基本定理.模式定理构成了求解优化问题时模式定理构成了求解优化问题时GAGA具备发现全局具备发现全局最优解的充分条件最优解的充分条件,也是分析也是分析GAGA的进化行为的基本的进化行为的基本理论理论,也称为模式理论也称为模式理论.7.5 GA7.5 GA的理论分析的理论分析通过基于模式理论的进化动力学分析通过基于模式理论的进化动力学分析,我们我们可以发现可以发现GAGA所能求解的问题的范围所能求解的问题的范围,找出找出GAGA的不足之处的不足之处,进而可能对其进行改进进而可能对其进行改进.7.5 GA7.5 GA的理论分析的理论分析n遗传算法的理论基础是遗传算法的二进制表遗传算法的理论基础是
34、遗传算法的二进制表达式及模式的含义。达式及模式的含义。下面简单介绍模式的概念及模式定理下面简单介绍模式的概念及模式定理.它的有关内容如下它的有关内容如下:n模式概念模式概念n模式的阶和长度模式的阶和长度n复制对群体适应值的影响复制对群体适应值的影响n交叉对模式的影响交叉对模式的影响n变异对模式的影响变异对模式的影响nHollandHolland模式定理模式定理7.5 GA7.5 GA的理论分析的理论分析A.模式概念模式概念定义模式的好处是使我们容易描述串的相似性。一个基因串用符号集0,1,*表示,则称为一个模式;n其中*是通配符,可以是0或1.即模式是含有通配符(*)的一类字符串的通式表达,例
35、如:nH=1*0*是一个模式.n模式*10101110与以下两个字符串匹配:010101110 110101110n而模式 *1010110 与以下四个字符串匹配:010100110 010101110110100110 1101011107.5 GA7.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.7.5 GA7.5 GA的理论分析的理论分析
36、C.复制对群体适应值的影响复制对群体适应值的影响假定在给定的时间步t,一个特定的模式s在群体P(t)中包含m个代表串,记为m=m(s,t)。首先,我们暂不考虑交叉和变异操作。n每个串根据适应值的大小获得不同的复制概率。n串i的复制概率为:njijfifp1)()(7.5 GA7.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)中所有个体的适应
37、值的平均值。f上式表明,模式s的代表串的数目随时间增长的幅度正比于模式s的适应值与群体平均适应值的比值。n即:适应值高于群体平均值的模式在下一代的代表串数目将会增加,而适应值低于群体平均值的模式在下一代的代表串数目将会减少。7.5 GA7.5 GA的理论分析的理论分析假设模式的适应值为(1+c)(t),其中c是一个常数,则上式可写为:f1)1()0,()1(),()()()1(),()1,(tcsmctsmtftfctsmtsmEn上式表明,在平均适应值之上(之下)的模式,将会按指数增长(衰减)的方式被复制。7.5 GA7.5 GA的理论分析的理论分析n复制的结果并没有生成新的模式。复制的结果
38、并没有生成新的模式。因而因而,为了探索搜索空间中的未搜索部分为了探索搜索空间中的未搜索部分,需要需要利用交叉和变异操作。利用交叉和变异操作。下面分别探索交叉和变异对模式的影响。下面分别探索交叉和变异对模式的影响。7.5 GA7.5 GA的理论分析的理论分析D.交叉对模式的影响交叉对模式的影响考虑模式s1=“*1*0”和s2=“*10*”间的交叉,可以发现n交叉会改变模式的一部分,模式的长度越长,被破坏的概率越大。7.5 GA7.5 GA的理论分析的理论分析假定模式s在交叉后不被破坏的概率为ps,则:1)(1lsps若交叉概率为pc,则s不被破坏的概率为1)(1lsppcs所以,在考虑交叉时,模
39、式s在群体P(t+1)中的数目m(s,t+1)的期望值为:1)(1)(),(),()1,(lsptftsftsmtsmEc7.5 GA7.5 GA的理论分析的理论分析E.变异对模式的影响变异对模式的影响变异算子以概率pm随机地改变个体某一位的值。n只有当o(s)个确定位(即确定为0或1,而非通配符*)的值不被破坏时,模式s才不被破坏。模式s在变异后不被破坏的概率:()1o ssmppPm+b123,WWW124,BBB7.7 遗传算法优化神经网络（）二进制编码网络参数的二进制编码图：7.7 遗传算法优化神经网络（）实数编码 网络参数的实数编码图：7.7 遗传算法优化神经网络实数编码GA优化NN
40、结构和参数的算法步骤如下:1）给定网络的输入、输出样本集；）对网络的参数进行编码构成染色体；）选择遗传操作，选择，交叉和变异及其运行参数；）设定种群规模并随机产生个染色体；）由输入样本经网络传输产生对应于个染色体的网络输出；）根据选择的适应度函数计算方式来计算每个染色体的适应度；）依据适应度在遗传空间进行选择操作；）进行交叉、变异操作产生新一代群体；）返回步骤5），直到满足性能要求，最后获得网络的参数。7.7 遗传算法优化神经网络遗传操作 在各种选择方法中除了排挤方法以外，其它选择方法对于实数编码GA都是适用的。如适应度比例方法、最佳个体保存方法等。实数编码GA通常采用算术交叉法。变异方式可根
41、据所解决问题的特点进行合理选择。适应度函数 目标函数可选为：2111()()2qsmttktJy ky k=骣=-桫邋适应度函数形式：()1mmfitJd-=+()y k：期望输出()y k：网络当前输出 7.8 遗传神经网络应用设计 n遗传神经网络设计的基本方法 当利用NN解决某一问题时，首先要根据该问题的特点，选择适合的NN模型。确定好使用的网络模型后，接下来就要进行网络的设计。其设计部分主要包括：确定网络的拓扑结构、网络的连接权值及阈值等。利用GA 可以搜索到以上问题的最优解。n遗传神经网络应用设计实例 设计一个遗传BP网络，来逼近非线性函数。函数的输入输出为：P=-1:.05:1，T=
42、sin(pi*P)。7.8 遗传神经网络应用设计画出函数曲线：figure(1);P=-1:.05:1;T=sin(pi*P);plot(P,T);%画出函数曲线7.8 遗传神经网络应用设计（）首先要利用GA优化该BP网络的拓扑结构，采用二进制编码，Matlab代码如下：clc;clear all;tic%计算程序运行时间，和计算程序运行时间，和toc连用，连用，tic表示开始，表示开始，toc表示结束表示结束NIND=40;%种群规模种群规模MAXGEN=100;%最大运行代数最大运行代数GGAP=0.9;%代沟代沟trace=zeros(1,MAXGEN);%用于存储训练误差用于存储训练误
43、差Chrom=crtbp(NIND,10);%创建初始种群创建初始种群gen=0;%代计数器代计数器ObjV=(objv2s(Chrom,40);while genMAXGEN,FitnV=ranking(ObjV);SelCh=select(sus,Chrom,FitnV,GGAP);7.8 遗传神经网络应用设计SelCh=recombin(xovsp,SelCh,0.7);SelCh=mut(SelCh);ObjVSel=(objv2s(SelCh,36);Chrom ObjV=reins(Chrom,SelCh,1,1,ObjV,ObjVSel);gen=gen+1;Jm index=m
44、in(ObjV);%记录最优目标函数值的变化记录最优目标函数值的变化 trace(gen,1)=Jm;if(gen=1)t(gen,1)=toc;elset(gen,1)=toc+t(gen-1,1);endendLy=Chrom(index,:);%训练结束后，记录最优个体训练结束后，记录最优个体figure(2);plot(1:100,trace);%画出训练误差变化曲线画出训练误差变化曲线7.8 遗传神经网络应用设计（）下面为被调用函数。将每个染色体解码成一个网络结构，分别计算在该结构下，网络的测试输出与期望输出的误差值，该组误差值被返回到主程序中，用以衡量每个染色体性能的好坏，从而选出
45、性能优良的染色体，经过GA的不断进化，最终获得网络拓扑结构。nfunction Ye=objvs(Chr,m)nP=-1:.05:1;nT=sin(pi*P);nfor k=1:mn if(Chr(k,1)=0)&(Chr(k,2)=0)%只有一个隐含层只有一个隐含层n x1=23*Chr(k,6)+22*Chr(k,5)+21*Chr(k,4)+20*Chr(k,3);n%该隐含层神经该隐含层神经元个数元个数 n if x1=0n x1=10;n end7.8 遗传神经网络应用设计nnet=newff(minmax(P),x1,1,tansig,purelin);%创建创建BP网络网络n e
46、lsen x1=23*Chr(k,6)+22*Chr(k,5)+21*Chr(k,4)+20*Chr(k,3);n x2=23*Chr(k,10)+22*Chr(k,9)+21*Chr(k,8)+20*Chr(k,7);nif x1=0n x1=10;n endn if x2=0n x2=8;n endn net=newff(minmax(P),x1,x2,1,purelin,tansig,purelin);%创建创建BP网络网络n endn Y(k,:)=sim(net,P);n Ye(k)=sum(Y(k,:)-T).2);n k=k+1;n end7.8 遗传神经网络应用设计运行100代
47、的误差下降曲线 7.8 遗传神经网络应用设计 优化结束后，Ly中保存获得的最优解。在matlab命令窗口中输入Ly，按回车键的如下结果：Ly=0 0 1 1 0 0 0 1 0 0 Ly中前两位是网络层数的编码，由前面的规定可知，隐含层数为1，则Ly中的第3到第第六位表示该隐含层的节点数，为：。由此便获得了网络的拓扑结构。0*2 00*2 11*2 21*2 312+=7.8 遗传神经网络应用设计 利用GA优化该BP网络的权值和阈值，传递函数分别为tansig和purelin，所以不需要优化形状参数。采用实数编码，Matlab代码如下：clc;clear all;FieldDR=-20-20-
48、20-20-20-20-20-20-20-20-20-20-1-1-1-1-1-1-1-1-1-1-1-1-20-20-20-20-20-20-20-20-20-20-20-20-1;20 20 20 20 20 20 20 20 20 20 20 20 1 1 1 1 1 1 1 1 1 1 1 1 20 20 20 20 20 20 20 20 20 20 20 20 1;%权值和阈值的取值范围权值和阈值的取值范围 Chrom=crtrp(40,FieldDR);%产生产生40个初始群体个初始群体MAXGEN=200;%最大运行代数最大运行代数GGAP=0.9;%代勾代勾gen=0;%代计
49、数器代计数器Jm=1;tracec=zeros(MAXGEN,1);%用于存储训练误差用于存储训练误差ObjV=objv2b(Chrom,40);%调用调用obj2b函数计算当前群体的目标函数函数计算当前群体的目标函数值值7.8 遗传神经网络应用设计nwhile(gen0)n ticn FitnV=ranking(ObjV);n maxfit index=max(FitnV);n Selch=select(sus,Chrom,FitnV,GGAP);%代勾是代勾是0,9,Chrom经选择后经选择后 是是36个个体个个体n Selch=recombin(reclin,Selch,0.7);%进行
50、算术交叉进行算术交叉n Selch=mutate(mutbga,Selch,FieldDR,0.01);%变异变异n ObjVSel=objv2b(Selch,36);%求目标函数值求目标函数值n Chrom ObjV=reins(Chrom,Selch,1,1,ObjV,ObjVSel);%重构组成重构组成40个个体个个体n gen=gen+1;n Jm index=min(ObjV);%记录最优目标函数值的变化记录最优目标函数值的变化n tracec(gen,1)=Jm;n if(gen=1)n t(gen,1)=toc;n elsen t(gen,1)=toc+t(gen-1,1);n
