优化设计方法:第二章 遗传算法基本理论_第1页
优化设计方法:第二章 遗传算法基本理论_第2页
优化设计方法:第二章 遗传算法基本理论_第3页
优化设计方法:第二章 遗传算法基本理论_第4页
优化设计方法:第二章 遗传算法基本理论_第5页
已阅读5页,还剩70页未读, 继续免费阅读

付费下载

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

遗传算法的基本理论优化设计课件枚举法

枚举出可行解集合内的所有可行解,以求出精确最优解。对于连续函数,该方法要求先对其进行离散化处理,这样就有可能产生离散误差而永远达不到最优解。另外,当枚举空间比较大时,该方法的求解效率比较低,有时甚至在目前最先进的计算工具上都无法求解。搜索方法启发式算法寻求一种能产生可行解的启发式规则,以找到一个最优解或近似最优解。该方法的求解效率虽然比较高,但对每一个需要求解的问题都必须找出其特有的启发式规则,这个启发式规则无通用性,不适合于其他问题。搜索算法寻求一种搜索算法,该方法在可行解集合的一个子集内进行搜索工作,以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解,但若适当的应用一些启发知识,就可在近似解的质量和求解的效率上达到一种较好的平衡。随着问题种类的不同,以及问题规模的扩大,要寻求到一种能以有限的代价来解决上述最优化问题的通用方法仍是一个难题。而遗传算法却为我们解决这类问题提供了一个有效的途径和通用框架,开创了一种新的全局优化搜索方法。2.1遗传算法的生物学基础生物在自然界的生存和繁衍,显示出了其对自然环境的优异自适应能力。受其启发,人们致力于对生物各种生存特性的机理研究和行为模拟,为人工自适应系统的设计和开发提供了广阔的前景。遗传算法(geneticalgorithms,简称Gas)就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟,遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。

2.2遗传算法的简介遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Hollend教授提出。起源于60年代对自然和人工自适应系统的研究。70年代DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算试验。在一系列研究工作的基础上,80年代由Goldbery进行归纳总结,形成了遗传算法的基本框架。

2.2.1遗传算法概要对于一个求函数最大值的优化问题(求函数最小值也类同),一般可以描述为下述数学规划模型:

maxf(X)(1-1)

s.t.X∈R

(1-2)

RU(1-3)式中,X=[x1,x2,x3,……xn]T为决策变量,f(X)为目标函数,式(1-2)、(1-3)为约束条件,U是基本空间,R是U的一个子集。满足约束条件的解X称为可行解,集合R表示由所有满足约束条件的解所组成的一个集合,叫做可行解集合。它们的关系如图1-1:

对于上述最优化问题,目标函数和约束条件种类繁多,有的是线性的,有的非线性的;有的是连续的,有的是离散的;有的是单峰值的,有的是多峰值的。随着研究的深入,人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能,也不现实,因此求出其近似最优解或满意解是人们主要着眼点之一。总的来说,求优解或近似最优解的方法主要有3种:枚举法、启发式算法和搜索算法。

遗传算法的发展遗传算法起源于对生物系统所进行的计算机模拟研究。早在本世纪40年代,就有学者开始研究如何利用计算机进行生物模拟的技术,他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。进入60年代后,美国密执安大学的Holland教授及其学生们受到这种生物模拟技术的启发,创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术——遗传算法。下面是在遗传算法的发展过程中一些关键人物所做出的一些主要贡献。

(1)J.H.Holland60年代,Holland认识到了生物的遗传和自然进化现象与人工自适应系统的相似关系,运用生物遗传和进化的思想来研究自然和人工自适应系统的生成以及它们与环境的关系,提出在研究和设计人工自适应系统时,可以借鉴生物遗传的机制,以群体的方法进行自适应搜索,并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。

70年代初,Holland教授提出了遗传算法的基本定理——模式定理,从而奠定了遗传算法的理论基础。模式定理揭示出了群体中的优良个体(较好的模式)的样本数将以指数级规律增长,因而从理论上保证了遗传算法是一个可以用来寻求最优可行解的优化过程。1975年,Holland出版了第一本系统论述遗传算法和人工自适应系统的专著《自然系统和人工系统的自适应性》。80年代,Holland教授实现了第一个基于遗传算法的机器学习系统——分类器系统(简称CS),开创了基于遗传算法的机器学习的新概念,为分类器系统构造出了一个完整的框架。(2)J.D.Bagley1967年,Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词,并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、显性、倒位等遗传算子,在个体编码上使用了双倍体的编码方法。这些都与目前遗传算法中所使用的算子和方法相类似。他还敏锐地意识到了在遗传算法执行的不同阶段可以使用不同的选择率,这将有利于防止遗传算法的早熟现象,从而创立了自适应遗传算法的概念。

(3)K.A.DeJong1975年,DeJong在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验,树立了遗传算法的工作框架,得到了一些重要且具有指导意义的结论。例如,对于规模在50~100的群体,经过10~20代的进化,遗传算法都能以很高的概率找到最优或近似最优解。他推荐了在大多数优化问题中都较试用的遗传算法的参数,还建立了著名的DeJong五函数测试平台,定义了评价遗传算法性能的在线指标和离线指标。

(4)D.J.Goldberg1989年,Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》。该书系统总结了遗传算法的主要研究成果,全面而完整地论述了遗传算法的基本原理及其应用。可以说这本书奠定了现代遗传算法的科学基础,为众多研究和发展遗传算法的学者多瞩目。(5)L.Davis1991年,Davis编辑出版了《遗传算法手册》一书,书中包括了遗传算法在科学计算、工程技术和社会经济中的大量应用实例。这本书为推广和普及遗传算法的应用起到了重要的指导作用。

(6)J.R.Koza1992年,Koza将遗传算法应用于计算机程序的优化设计及自动生成,提出了遗传编程(简称GP)的概念。他将一段LISP语言程序作为个体的基因型,把问题的解编码为一颗树,基于遗传和进化的概念,对由树组成的群体进行遗传运算,最终自动生成性能较好的计算机程序。Koza成功地把他提出的遗传编程的方法应用于人工智能、机器学习、符号处理等方面。遗传算法(GA)最重要的基本理论是模式定理[4-7]、积木块假设[6,8]以及隐并行性定理[4-7]模式定理(SchemataTheorem)模式定理是由Holland在1971年提出的,它是GA的基本定理。它将GA的运算过程理解为模式运算过程,并从模式运算的角度解释GA的性能特点。模式是描述字符串集的模板,反映字符串集中串的某些位置上存在的相似性。在本节的叙述中,仅就二进制编码的情况进行讨论。定义2.1基于三值字符集{0,1,*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。例如,模式S=01*0*描述了所有在位置1和位置4上为0,在位置2上为1的字符串,该模式描述的字符串集合为{01000,01001,01101,01101}。也就是:S=01*0*={01000,01001,01101,01101}事实上,模式的概念使得我们可以简明地描述具有相似结构特点的个体编码字符串。在引入模式的概念后,遗传算法的本质就是对模式所进行的一系列运算,遗传运算过程中的个体通过模式联系起来。通过这些遗传运算,一些比较差的模式逐渐被淘汰,而一些较好的模式逐步被遗传和进化。在进行遗传算法的理论分析时,往往需要定量地估计模式运算。因此,有必要引入以下两个概念:模式阶和模式定义长度。定义2.2模式H中确定位置的个数称为模式的模式阶(SchemataOrder),记作O(H)。模式H中第一个确定位置和最后一个确定位置之间的距离称为模式的定义长度(SchemataDefiningLength),记作δ(H)。根据定义2.2,O(101*0)=4,δ(101*0)=4;O(0**1*)=2,δ(0**1*)=3。而对于H=****1、H=****0**之类的模式,由于他们只有一个确定位置,所以我们规定它们的定义长度为1,如δ(****0**)=1。330当字符串的长度确定时,模式的阶数越高,与该模式相匹配的样本数目就越少,该模式的确定性也就越高。而模式的定义长度越大,则在遗传运算中,该模式被遗传运算破坏的概率越大,生存概率越小。定理2.1模式定理(SchemataTheorem)在遗传算子选择、交叉和变异的作用下,具有低阶、短定义长度以及平均适应度高于种群平均适应度的模式在子代中将得以指数级增长。模式定理保证了遗传优化过程中较优解的样本呈指数级增长,在一定意义上可以解释基本遗传算法的优化本质,同时也给遗传算法的应用提供了指导作用。积木块假设与欺骗问题模式定理说明,低阶、定义长度短、平均适应度高的模式被交叉切断的可能性低,随着世代交替其数量将增加。这种类型的模式称为积木块(BuildingBlock)。定义2.3(积木块)具有低阶、短定义长度以及高适应度的模式称作积木块。假设2.1(积木块假设)积木块在遗传算子的作用下相互结合,能生成高阶、长定义长度、高平均适应度的模式,并最终生成全局最优解。模式定理说明了积木块的样本数呈指数级增长,亦即说明了用遗传算法寻求最优样本的可能性;而积木块假设说明了用遗传算法求解各种问题的基本思想,即通过积木块之间的相互拼接能够产生出问题更好的解,表明遗传算法具有全局寻优能力,能够寻求到最优样本。到目前为止,上述假设并未得到完整而严密的数学证明,但大量的实践对这一假设提供了强有力的支持。如果一个问题的编码满足积木块假设,那么用遗传算法求解的效率较高,否则用遗传算法求解的效率较低。应用实践表明,存在一类用遗传算法难以求解的问题,称为“GA-难”问题。属于“GA-难”的问题一般包括有孤立的最优点,在搜索过程中,低阶积木块错误地引导搜索过程,不能发现高阶积木块,通过欺骗遗传算法,使其进化过程偏离最优解,最终使遗传算法发散,这种现象称为欺骗。实际上,目前尚未没有解决这类问题的较好的方法,也无法判断一个问题包含欺骗的多少与问题相对于遗传算法的难易程度。不过,现实中遇到的各种应用问题中,遗传算法大部分是适用的。隐并行性定理在遗传算法的运行过程中,每代都处理了个个体,但由于一个个体编码串中隐含有多种不同的模式,所以算法实际上却处理了更多的模式。以二进制编码为例,一定长度的编码串隐含有多种模式,这样,规模为的种群中就可能隐含种不同的模式。但由模式定理可知,并不是所有的模式都能以较大的概率被保存下来进行处理。Holland在分析了有效模式(即那些按指数级递增的模式)的数目后,得到了隐并行性定理。

隐并行性定理意味着,每一代遗传算法处理个个体的同时,却获得了对个模式的并行处理,并且无须额外的存储量。这种并行处理过程有别于一般意义下的并行算法的运行过程,是包含在处理过程内部的一种隐含并行性。通过这种隐含并行性,使得我们可以快速地搜索出一些比较好的模式。编码策略遗传算法得一个显著特点是它交替地在编码空间和解空间中工作,它在编码空间对个体进行遗传运算,而在解空间对解进行评价和选择。Holland模式定理建议采用二进制编码,并给出了最小字符集编码规则。为了克服早熟现象,Schraodolph等提出了动态变量编码,通过对Jong的5个函数进行测试,发现动态变量编码比普通二进制编码的优化效果好得多。实数编码具有精度高、便于大空间搜索的优点,越来越受到重视。有学者还研究了二进制和十进制编码的搜索能力强,但前者不能保持种群稳定性。目前关于采用何种编码策略仍然存在许多争议。一派根据模式定理,建议尽量用少的字符进行编码;另一派以数值优化计算的方便和精度为准,采用一个基因一个参数的方法,并把相应的基因运算改造成合适实数运算的形式[9]。编码问题遗传算法应用中一个重要的问题,也是一个很复杂的问题。针对一个具体应用问题,如何设计一种完美的编码方案一直是遗传算法的应用难点之一,也是遗传算法的一个重要研究方向。Jong曾提出了两条操作性较强的实用编码规则[4]。规则一(有意义积木块编码规则):应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案。规则二(最小字符集编码规则):应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。规则一是基于模式定理和积木块假设的,可以理解成应使用易于生成适应度较高的个体的编码方案。从应用的角度看,把握和应用问题空间相对应积木块的编码结构是十分困难的,但在编码设计时还是应该检查一下编码串中相关位位置之间的距离。而规则二提供了一种更为实用的编码原则,说明了为何偏爱于使用二进制编码方法的原因。事实上,理论分析表明,与其他编码字符集相比,二进制编码方案能包含最大的模式数,从而使得遗传算法在确定规模的种群中能够处理最多的模式。Jong提出的这两条规则对设计编码方案具有指导意义。然而,在处理实际问题时,必须对编码方案,遗传算子等统一考虑,以寻求一种对问题的描述最为方便、遗传运算效率最高的编码方案。下面讨论两种最常用的编码方法:二进制编码和实数编码。二进制编码方法当变量不止一个分量时,我们可以对各变量分别进行编码,然后合并成一个长串。解码时,分别根据其对应的子串进行解码即可。二进制编码方法有如下一些优点:(1)编码、解码操作简单易行,交叉、变异等遗传运算便于实现;(2)符合最小字符集编码规则,便于利用模式定理对算法进行理论分析。但是,在求解连续优化问题时,它存在以下的缺点:(1)相邻整数的二进制编码可能具有较大的Hamming距离,例如15和16的二进制表示为01111和10000,因此,算法要从15改进到16则必须改变所有的位。这种缺陷将降低遗传算子的搜索效率。二进制编码的这一缺点称为Hamming悬崖。(2)二进制编码时,一般要先给出求解的精度以确定串长,而一当精度确定后,就很难在算法执行过程中进行调整。从而使算法缺乏微调的功能。若在算法一开始就选取较高的精度,那么串长就很大,这样也将降低算法的效率。(3)在求解高维优化问题时,二进制编编码串将非常之长,从而使得算法的搜索效率很低。实数编码方法为了克服二进制编码的缺点,对于问题的变量是实向量的情形,可以直接采用实数形式进行编码。所谓实数编码方法,是指个体的每个基因值用某一范围内的一个实数来表示,个体的编码长度等于其决策变量的个数。试验证明,对于大部分数值优化问题,通过一些专门设计的遗传算子的引入,采用实数编码比采用二进制编码时算法的平均效率更高。实数方法有如下一些优点:(1)适合于在遗传算法中表示范围较大的数;(2)适合于精度要求较高的遗传算法;(3)便于较大空间的遗传搜索;(4)改善了遗传算法的计算复杂性,提高了运算效率;(5)便于遗传算法与经典优化方法的混合使用;(6)便于设计针对问题的专门知识的知识型遗传算子;(7)便于处理复杂的决策变量约束条件。适应度函数适应度评价是通过适应度函数来对个体质量的一种测量,是进化过程中自然选择的唯一依据。遗传算法中,有很多方法定义适应度函数,一般情况下,会使用目标函数或者目标函数的变换形式来定义。适应度评价是选择运算的依据,适应度函数的设计直接影响到遗传算法的性能,所以确定适当的适应度函数是遗传优化取得成功的必要条件之一。最优化问题可以分为两大类,一类是求目标函数的全局最大值,另一类是求目标函数的全局最小值。对于这两类优化问题,可以通过目标函数f(x)适当的变换,得到适应度函数F(x)。遗传算法中,种群的进化过程就是以种群中各个个体的适应度为依据,通过一个反复迭代过程,不断地寻求出适应度较大的个体,最终就可得到问题的最优解或近似最优解。在应用遗传算法时,有可能出现一些不利于进化的情况,主要表现为进化的过早收敛或停滞现象。如果种群中出现了超级个体,该个体的适应度大大超过种群的平均适应度,则按照适应度比例进行选择时,该个体很快就会在种群中占绝对的比例。从而导致算法较早地收敛到一个局部最优点,这种现象称为过早收敛(PrematureConvergence)。如果在搜索过程的后期,虽然种群中存在足够的多样性,但种群的平均适应度可能会接近种群的最优适应度。在这种情况下,种群中实际上已经不存在竞争,从而搜索目标也难以得到改善,这种现象称为停滞现象(Stagnation)。为了防止进化过程中出现过早收敛或停滞现象,改变算法性能的方法之一就是对适应度进行调整,即通过变换改变原适应度的比例关系,常用的比例变换有线性变换、幂函数变换和指数函数变换等。另外,在实际的应用过程中,许多最优化问题是带有条件约束的。为了保证优化满足给定的约束条件,可以通过引入惩罚机制[10]来实现。遗传算子不同的编码方法和不同的遗传算子构成了各种不同的遗传算法。但这些算法都是通过对生物遗传和进化过程中选择、交叉、变异机理的模仿,来完成对问题最优解的自适应搜索过程。下面对这三个基本遗传算子分别进行介绍。1、选择算子选择算子是决定父代种群中哪些个体、并能以多大的可能性被挑选来复制或遗传到下一代的遗传算子,它模拟的是“优胜劣汰、适者生存”的自然进化原理。它建立在对个体适应度评价的基础上,实质是从种群中选择性能优良的个体,淘汰性能较差的个体,把性能优良的个体直接遗传到下一代,或通过交叉产生新的个体。目前常用的选择策略有赌盘选择策略、排序选择策略和最优保存选择策略等。(1)赌盘选择(2)排序选择排序选择是指根据适应度大小顺序对种群中个体排序,按照这个排序来分配各个个体的选择概率。适应度越大的概率,其选择概率越大。然后基于这些概率用赌盘选择的方法来选择个体。这种选择策略能比较有效地避免过早收敛和停滞现象。(3)最优保存选择最优保存策略的基本思想是把当前种群中适应度最高的个体不参与交叉运算和变异运算,直接保留到下一代。这种策略的优点是进化过程中,最优解不会被破坏。但是也隐含了局部最优个体的遗传基因会急速增加而使进化有可能限于局部解,也就是说,其全局搜索能力差。除了上述三种选择策略,此外还有确定采样选择、无回放随机选择、无回放余数随机选择、随机联赛选择等。各种方法具有不同的选择性能和优缺点,在实际应用中,应根据问题的具体情况,选择适当的策略。2、交叉算子所谓交叉运算,是指对两个相互配对的个体按某种方式相互交换其部分基因,从而形成两个新的个体。交叉算子是遗传算法中起核心作用的算子。交叉运算使遗传算法的搜索能力大大提高。根据编码策略的不同,将有不同的交叉方法。下面分别叙述几种比较常用于二进制编码或实数编码的交叉算子。(1)点式交叉点式交叉算子又分为单点交叉,双点交叉和多点交叉,适用于二进制编码。单点交叉又称简单交叉,其操作是在个体编码串中随机设定一个交叉点,将父代个体在该点前或后的两个子串互相交换,生成两个新个体。双点交叉设置两个交叉点,将两个交叉点之间的子串互换。多点交叉是单点交叉和双点交叉的推广,即在个体串中随机设置了多个交叉点,然后进行基因交换。一般不要太多使用多点交叉算子,因为它又可能破坏一些好的模式。事实上,随着交叉点数的增多,个体的结构被破坏的可能性野逐渐增大,这样就很难有效地保存较好的模式,从而影响遗传算法的性能。(2)均匀交叉(3)算术交叉3、变异算子变异算子指的是对种群中的个体串的某些基因上的基因值作变动。遗传算法导入变异的目的有两个。一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子以接近最优解邻域时,利用变异算子的局部搜索能力可以加速向最优解收敛。二是使遗传算法维持种群多样性,以防止出现早熟收敛。在二进制编码时的变异算子非常简单,只是以一定的变异概率将所选个体的位取反。即若是1,则取0;若是0,则取1。这种变异方法非常简单,称为基本变异。另外,还有一种用于二进制编码的变异算子称为逆转算子。它通过在个体编码串中随机挑选两个逆转点,然后将两个逆转点间的基因值以逆转概率逆向排序。逆转操作的真正目的并不在变异,而是实现一种重新排序操作。在不影响个体特征的前提下,提高积木块的繁殖率。即把对形成积木块有用的某些分离较远的基因通过重排序调到相距较近的位置。在实数编码时,比较常用的两种变异方法是均匀性变异和非均匀性变异。均匀性变异指分别用符合某一范围内均匀分布的随机数,以某一较小的概率来替换个体编码串中各个基因上的原有基因值。均匀性变异运算特别适合应用于遗传算法的初期运行阶段,它使得搜索点可以在整个搜索空间内自由地移动,从而可以增加种群的多样性,使算法处理更多的模式。在均匀性变异中,变异算子的作用与进化代数没有直接关系。从而,当遗传算法进化到一定代数后,由于缺乏局部搜索,导致很难获得收益。非均匀性变异在进化的初期,变异的范围相对较大,而随着进化的推进,变异范围越来越小,它重点搜索原个体附近的微小区域。控制参数在设计遗传算法时,一方面需要针对具体问题选择适当的编码方案及相应的遗传算子;另一方面需要选择算法的控制参数。参数的不同选取常常会对算法的性能产生较大的影响。这些控制参数主要包括编码长度,种群规模,交叉概率,变异概率和终止进化代数等。(1)编码长度使用二进制编码时,编码长度通常由对问题的求解精度决定;使用实数编码时,编码长度与

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论