遗传算法及其应用毕业设计论文.docx

上传人:豆**** 文档编号:29960413 上传时间:2022-08-02 格式:DOCX 页数:70 大小:779.08KB
返回 下载 相关 举报
遗传算法及其应用毕业设计论文.docx_第1页
第1页 / 共70页
遗传算法及其应用毕业设计论文.docx_第2页
第2页 / 共70页
点击查看更多>>
资源描述

《遗传算法及其应用毕业设计论文.docx》由会员分享,可在线阅读,更多相关《遗传算法及其应用毕业设计论文.docx(70页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、遗传算法及其应用摘 要遗传算法是一种模拟自然界生物进化的搜索算法,由于它的简单易行、鲁棒性强,尤其是其不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程,从而使它的应用范围极为广泛,并且己在众多领域得到了实际应用,取得了许多令人瞩目的成果,引起了广大学者和工程人员的关注。 在简要的介绍了遗传算法的发展历史和研究现状及其生物学、数学基础后,文中引出了遗传算法的基本概念和原理、分析了遗传算法的基本实现技术。如:编码、适应度函数、遗传算法的三大遗传操作、参数规则等。最后在介绍了遗传算法程序设计原则的基础上,编程实现了遗传算法在图像识别中的应用,在实践中检验了遗传算法的实际效果。 关键词:遗传算

2、法,适应度函数,图像识别ABSTRACT The genetic algorithm is a kind of searching method which simulates the natural evolution. It is simple and easy to implement, especially it do not need the special field knowledge, so it has been using in very broad fields. Now the genetic algorithm has got a lot of fruits, and

3、 more and more scholars begin to pay attention on it. After brief introducted the genetic algorithm and studyed the history of the development status and biology, mathematical basis, we brought out the basic genetic algorithm concepts and principles, analysised the genetic algorithm to achieve the b

4、asic technology. Such as: coding, fitness function, genetic algorithm of the three major genetic manipulation, and other parameters of the rules. Finally, introduced a genetic algorithm procedures based on the principles of design, programming a genetic algorithm in the application of image recognit

5、ion, in practice, we test the practical effects of genetic algorithm.Key word:genetic algorithm,Fitness function,image recognition引言 当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代,生命科学与工程科学的交叉、渗透和相互促进是其中的一个典型例子,也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。制造机器智能一直是人类的梦想,人们为此付出了巨大的努力。近年来,随着人工智能应用领域的不断拓广,传统的基于符号处理机制的人工

6、智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题已变得越来越突出,这些困难甚至使某些学者对人工智能提出了强烈批判,对人工智能的可能性提出了质疑。在人工智能领域中,有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。因此,研究能在搜索过程中自动获得和积累有关搜索空间的知识,并能自适应地控制搜索过程,从而得到最优解或准优解的通用搜索算法一直是令人瞩目的课题。遗传算法就是在这种背景下产生并经实践证明特别有效的算法。 遗传算法(Genetic Algorithm GA)是近年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想是基于Darwin的进化论和Mendel的遗传学说

7、。该算法由密执安大学教授Holland及其学生于1975年创建。自1985年以来。国际上已召开了多次遗传算法的学术会议和研讨会。国际遗传算法学会组织召开的ICGA(International Conference on Genetic Algorithms)会议FOGA(Workshop -on Foundation of Genetic Algorithms)会议。为研究和应用遗传算法提供了国际交流的机会。 作为一种通用的问题求解方法,遗传算法采用简单的编码技术来表示各种复杂的结构,并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择,来指导学习和确定搜索的方向。近年来,遗传算法已被成

8、功地应用于工业、经济管理、交通运输、工业设计等不同领域。解决了许多问题。例如:可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。67第一章 绪论1.1遗传算法的发展历史与研究现状 20世纪60年代,美国Michigan大学的John Holland教授开始研究自然和人工系统的自适应行为,在这些研究中,他试图发展一种用于创造通用程序和机器的理论,使得通用程序和机器具有适应任意环境的能力。他意识到用群体方法搜索以及选择、交换等操作策略的重要性。在六十年代中期至七十年代末期,基于语言智能和逻辑数学智能的传统人工智能十分兴盛,而基于自然进化的思想则遭到怀疑和反对,

9、Holland及其数位博士生仍坚持了这一方向的研究。Bagley发明“遗传算法”一词,并发表了第一篇有关遗传算法应用的论文,在他开创性的博士论文中采用双倍体编码,发展了与目前类似的复制、交换、突变、显性、倒位等基因操作,他还敏锐地察觉到防止早熟收敛的机理,并发展了自组织遗传算法的概念。与此同时,Rosen-berg在他的博士论文中进行了单细胞生物群体的计算机仿真研究,对以后函数优化的研究颇有启发,并发展了自适应交换策略。Cavicohio 1970年研究了基于遗传算法的子程序选择和模式识别问题,在模式识别问题上,采用整数编码,检索空间很大,他提出了以预选择策略保证群体多样性,对遗传算法参数进行

10、中心控制的方法。同年,Weinberg研究了生物体的计算机仿真,他的贡献在于提出运用多层遗传算法来进行遗传算法的参数自优化。1968至1971年,Holland提出了重要的模式理论,建议采用二进制编码。与前面几位博士不同,Holland首次采用二进制编码来研究函数优化问题,并指出了运用Gray码的一些优点,他研究了从生物系统引申出的各种不同的选择和配对策略。1972年,Frantz的博士论文中研究了许多新的问题,如基因非线性(异位显性)现象,基因迁移操作及多点交换操作等,由于没有设计出诸如GAeception之类合适的非线性优化问题,实验结果并不具备说服力。这一年,Holland的模式理论也渐

11、趋成熟,但在编码策略上出现了至今仍执争论的二派,一派根据模式定理建议用尽量少的符号编码,一派以数值优化计算的方便和精度为准采用一个基因一个参数的方法,并把相应的基因操作改造成适合实数操作的形式,Bosworth,Zoo和Zeigler是后者的开创者。1975年竖立了遗传算法发展史上的两块里程碑,一是Holland出版了经典著作Adaptation in Nature andArtificial System,该书是作者十几年间许多思想及其实现的结晶,详细阐述了遗传算法的理论,并为其奠定了数学基础,发展了一整套模拟生物自适应系统的理论;二是De Jong完成了具有指导意义的博士论文An Anal

12、ysis of the Behavior of a Class of Genetic Adaptive System,他深入领会了模式定理并做了大量严格的计算实验,给出了明确的结论,他还建立了著名的De Jong五函数测试平台,定义了性能评价标准,并以函数优化为例,对遗传算法的六种方案的性能及机理进行了详细实验和分析,他的工作成为后继者的范例并为以后的广泛应用奠定了坚实的基础。为克服De Jong的轮盘赌(随机)选择操作中的随机误差,Brindle于1981年在她的博士论文中研究了六种复制策略。 进入八十年代,随着以符号系统模仿人类智能的传统人工智能暂时陷入困境,神经网络、机器学习和遗传算法等

13、从生物系统底层模拟智能的研究重新复活并获得繁荣。Goldberg在遗传算法研究中起着继往开来的作用,他在1983年的博士论文中第一次把遗传算法用于实际的工程系统煤气管道的优化,从此,遗传算法的理论研究更为深入和丰富,应用研究更为广泛和完善,自1985年起,遗传算法及其应用国际会议每二年召开一次,有关人工智能的会议和刊物上大多有遗传算法的专题,Goldberg的课本,及其他学者的专著的出版有力地推动了遗传算法的传播。 进入九十年代,以不确定性、非线性、时间不可逆为内涵,以复杂问题为对象的科学新范式得到学术界普遍认同,如广义进化综合理论。由于遗传算法能有效地求解属于NPC类型的组合优化问题及非线性

14、多模型、多目标的函数优化问题,从而得到了多学科的广泛重视,一些学者也认识到求解复杂问题最优解是不现实的,故而寻求满意解,而遗传算法是最佳工具之一,生物进化的历史比任何数学证明都强有力,问题是遗传算法在吸收遗传学、进化论及分子生物学最新成果和在实验得到证明和证伪的同时本身也在进化。目前,遗传算法引起包括数学、物理、化学、生物学、计算机科学等领域的科学家的极大兴趣。遗传算法的研究领域和内容十分的广泛,如遗传算法的设计与分析,遗传算法的理论基础及其在各个领域的应用。随着理论的深入研究和应用领域的不断拓展,遗传算法必将取得更大的发展。1.2 遗传算法的生物学基础1.2.1 生物的进化过程 19世纪50

15、年代。英国生物学家达尔文根据他对世界各地生物的考察结果和人工选择实验。提出了“生物进化论”。1859年达尔文发表了物种起源巨著。提出了以自然选择为基础的生物进化论学说。根据达尔文的进化论,生物进化的发展来源于三种动力:遗传、变异和选择。 遗传就是子代总是保持和亲代的相似性,遗传性是一切生物所共有的特征。正是这种遗传性,使得生物能够把它的特性、性状传给后代,并在后代中保持相似。现代遗传学研究表明,生物都具有遗传性。遗传学的建立和发展有力地推动和促进了进化论,变异是子代和亲代有某些不相似的现象。即子代永远不会和亲代完全一样,变异是一切事物所具有的共同特征,是生物个体之间相互区别的基础。引起变异的原

16、因主要是生活条件的影响,器官使用的不同及杂交。变异性为生物的进化发展创造了条件,选择决定了生物进化的方向,所谓选择是指生物具有保留和淘汰的特性,选择分为人工选择和自然选择。人工选择是在人为环境下把对人有利的生物保留下,把对人不利的个体淘汰掉;自然选择就是指生物在自然界的生存环境中适者生存,世界上所有形形色色的生物都是在自然选择的影响下、在悠久的岁月中形成的。自然选择的过程是通过生存斗争的过程来实现生存斗争的结果,优胜劣汰。这样就保证了生物去适应环境,通过不断地自然选择,那些有利于生存的变异就遗传下去,日积月累越来越大,逐步产生了新的物种。 生物的各项生命活动都有他的物质基础。生物的遗传和变异也

17、不例外。遗传物质的主要载体为染色体。研究表明,染色体主要有脱氧核糖核酸和蛋白质,其中脱氧核糖核酸在染色体中含量稳定,结构相对稳定,能够自我复制,前后保持一定的连续性,能够产生可遗传的变异。因此它是主要的遗传物质。生物的性状遗传主要是通过染色体传递给后代。因此,基因是控制生物性状的遗传物质的功能和结构单位。生物变异与遗传一样,也是很复杂的,由遗传物质引起的变异称为遗传变异。它有三种来源:基因重组、基因变异和基因突变。基因重组是控制不同性状的基因的重新组合;基因变异是指基因内部的化学变化;基因突变的产生是在一定外界环境条件和生物内部因素的作用下,基因的分子结构发生改变的结果。每种生物染色体无论结构

18、和数目都是相对恒定的。但在自然条件和人为条件的影响下染色体结构和数目都可以发生变化, 染色体数目的改变是染色体变异的一个重要方面。遗传算法正是借鉴生物自然选择和遗传机制的随机搜索算法。它之所以能够增强解决问题的能力,是因为自然演化过程本质就是一个学习与优化的过程。遗传算法通过模拟“优胜劣汰,适者生存”的规律激励好的结构,通过模拟孟德尔的遗传变异理论在迭代过程中保持已有的结构,同时寻找更好的结构。1.2.2 生物学对遗传算法的启示 生物是在遗传的过程中保持物种性状的,而变异是生物在综合作用过程中不断向前发展和进化的动力,选择通过遗传和变异起作用,变异为选择提供资料。遗传巩固与积累选择资料,而选择

19、则能控制变异与遗传的方向。使变异和遗传向着适应环境的方向发展。虽然生物进化论揭示了生物长期自然选择的进化发展规律。然而科学家从中受到了启迪,进化论的自然选择过程蓄含一种搜索和优化的先进思想。而将这种思想用于工程技术领域发展起来的遗传算法,为解决许多传统的优化问题提供了许多途径。1.3 遗传算法的数学基础遗传算法之所以能在众多优化问题中得到广泛应用且效果较好,必然有其理论上的机理。Holland提出的模式定理和积木块假设即是遗传算法的理论基础。模式定理作为描述遗传算法动力学机理的基本定理,奠定了遗传算法的数学基础。1.3.1模式理论 定义1.1:模式是表示一些相似的模块,它描述了在某些位置上具有

20、相似结构特征的个体在编码串的一个子集。 为不失一般性,考虑二值字符集0,1,由此可产生通常的0,1字符串,为了方便描述一个模式,增加一个通配符“*”,也称为无关符,用它来表示不确定字符,它既可代表字符集中的0,也可代表字符集中的1,并且可在字符集中的任意位置,这样,二值字符集0,1就扩展成三值字符集0,1,*。引入模式的概念后,我们可以看到一个串实际上隐含着多个模式,一个模式可以隐含在多个串中,不同的串之间通过模式而相互联系。 定义1.2:在模式H中具有确定基因值的位置数目称为该模式的模式阶(Schema Order),记为O(H) 。如模式011 * 1*的模式阶为4,模式0*的模式阶为1。

21、显然,一个模式的阶数越高,其样本个数越少,因而确定性越高。 定义1.3:模式H中第一个确定基因值的位置和最后一个确定基因值的位置之间的距离称为该模式的模式定义长度(Schema Defining Length)或模式定义距,记为S(H)。如模式011 * 1*的定义距为4,而模式0*的定义距为0。 在研究交叉算子对模式的作用时可以发现:对于单点交叉算子,模式1*0比模式10*更易被破坏,这两个模式具有相同的阶,为了描述这一性质,我们引入了模式定义距。 定理1.1(模式定理):在遗传算子选择、交叉和变异的作用下,具有低阶、短模式距以及平均适应度高于种群平均适应度的模式在子代中以指数级增长。模式定

22、理从模式角度论证了N个初始种群在经过选择、交叉、变异算子后模式H的变化: (1.1)其中,表示第代种群中模式所能匹配的样本的数量, ()、分别表示第代所有模式的平均适应度与种群平均适应度,表示串的长度,、分别表示交叉概率与变异概率。 定理中的三项分别说明了GA运算中选择、交叉和变异对种群中模式数量的影响: (1)模式的增长(减少),即样本数量的增加(减少),依赖于模式的平均适应度与群体适应度之比,那些平均适应度高于种群平均适应度的将在下一代中得以增长,而那些平均适应度低于种群平均适应度的将在下一代中减少;(2)具有短模式距的模式经过交叉后样本的数量越多;(3)具有低阶的模式经过变异后的生存率越

23、大,它大约为:。 从定理可以简单地分析一下交叉概率PC和变异概率Pm的作用,当其它值不变时,PC、Pm越小,则模式在下一代(代)群体中的个体数量越大,即个体趋向相似和一致,新个体的数量减少,从而使搜索范围减小,能快速收敛但也容易产生“早熟”现象;PC、Pm增大,群体多样性增强,搜索范围扩大,但有可能破坏群体中好的模式,使收敛速度变慢。因此,在实际应用时,可参照该定理设置或调整PC、Pm的值。 作为指导遗传算法的基本理论,模式定理同时还对遗传算法作了如下的启示: (1)编码中 根据模式定理,遗传过程中存活的都是长度短、阶次低、适应度高的模式,因此编码时应使所研究的主要性质用一长度短、阶次低的模式

24、表示;而次要性质用其它模式表示。因为二进制字符串拥有的内涵(模式数目)比较大,编码时尽量使用二进制或字符变化少的字符串。 (2)交叉操作中当亲代的优良模式介于字符串首尾之间时,如果采用一点交叉方式,它必然被破坏,在子代中就没法保留其优良模式,而相反,若采用两点交叉,其子代个体不仅保留原来亲代个体1的优良模式,而且兼容亲代个体2的优良模式,从而形成比原来更优良的模式。因此,在遗传算法中常使用该交叉方式,尤其是当字符串长度比较大的时候。1.3.2 积木块假设 符合模式定理的这类模式在GA中非常有用,我们将它定义为积木块。GA模拟了生物的进化机制,模式定理则提供了一种解释这种机理的数学工具。 定义1

25、.4:具有低阶、短模式距以及高适应度的模式称为积木块。 积木块假设:低阶、短定义距、高平均适应度的模式(积木块)在遗传算子作用下,相互结合,能生成高阶、长距、高平均适应度的模式,最终生成全局最优解。 模式定理保证了较优的模式(GA的较优解)的样本呈指数级增长,从而满足了寻找最优解的必要性,即GA存在着寻找到全局最优解的可能性;而积木块假设指出了遗传算法具备寻找到全局最优解的能力,即积木块在遗传算子的作用下,能生成高阶、长距、高平均适应度的模式,最终生成全局最优解。 积木块假设被认为是解释GA寻优原理的较完善的理论,它对GA在理论上的深入研究提供了较好的基础,并为GA性能的改进和应用的拓展提供了

26、理论指导。虽然积木块假设还未被理论证明,只是称为假说,但大量的实践都支持这一假说,实际应用领域表明其成功之处,如平滑多峰问题,带干扰多峰问题,组合优化等问题。可见,大量的实践都证明了遗传算法的适用性。1.3.3 遗传算法的收敛性 由模式定理知道了一个给定模式遗传算子作用在下一代中出现的期望比例,但由此还不能知道算法的收敛性。通过建立遗传算法搜索的马尔可夫模型,可证明算法的强收敛性。 定义1.5:两个模式Sa和Sb是非重叠的,当且仅当他们所定义的子集合不相交时,即SaSb=时,他们非重叠。 例如模式00*与01*是非重叠的。定义1.6:两个模式Sa和Sb是位置等价的,当且仅当 (1.2) 例如,

27、模式0*1*和1*0*是位置等价的;模式00*和1*0*不是位置等价的。定义1.7:设是一个非重叠的且位置等价的模式集合,令字母集0,*被映射到整数0,字母L被映射到整数1,则模式族函数 :Z + 定义为: (1.3) 例如,(*011)=3。定义1.8:设Sa ,Sb,令字母集0,*,被映射到整数0,则模式距离函数: Z + 为 (1.4) 其中=,是异或算子。定义1.9:对任意S,设 =0,1,2,-1是S上位置指标的集合,则所有可能交叉段的集合记为 (1.5)定义1.10:设,, ,广义交叉算子C:Z 定义为 (1.6) 其中对,当 ,Z, ,=,=;其他情况下=, = 。 定义1.11

28、:对于任意, , Oab通过所有可能的广义交叉算子作用在模式 ,所得到的模式集合。引理1.1:对某个,如果如果(,Z) =,则(1) (1.7)(2) (1.8) (3) (1.9)其中函数h表示两个模式间的Hamming距离,即两个模式间不同位的数目。 1.4 遗传算法的应用领域遗传算法提供了一种求解复杂系统优化问题的通用框架,它不依赖于问题的具体领域,对问题的种类有很强的鲁棒性,所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域:(l)函数优化。函数优化是遗传算法的经典应用领域,也是对遗传算法进行性能评价的常用算例。很多人构造出了各种各样的复杂形式的测试函数,有连续函数也有离散函数,

29、有凸函数也有凹函数,有低维函数也有高维函数,有确定函数也有随机函数,有单峰值函数也有多峰值函数等。用这些几何特性各具特色的函数来评价遗传算法的性能,更能反映算法的本质效果。而对于一些非线性、多模型、多目标的函数优化问题,用其他优化方法较难求解,而遗传算法却可以方便地得到较好的结果。(2)组合优化。随着问题规模的增大,组合优化问题的搜索空间也急剧扩大,有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题,人们已意识到应把主要精力放在寻求其满意解上,而遗传算法是寻求这种满意解的最佳工具之一。实践证明,遗传算法对于组合优化中的NP类问题非常有效。例如:遗传算法已经在求解旅行商

30、问题、背包问题、装箱间题、图形划分问题等方面得到成功的应用。(3)生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难以精确求解,即使经过一些简化之后可以进行求解,也会因简化得太多而使得求解结果与实际相差甚远。而目前在现实生产中也主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效工具,在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到广泛有效的应用。 (4)自动控制。在自动控制领域中有很多与优化相关的问题需要求解,遗传算法已在其中得到了初步的应用,并显示出了良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基

31、于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等,都显示出了遗传算法在这些领域中应用的可能性。 (5)机器人学。机器人是一类复杂的难以精确建模的人工系统,而遗传算法的起源就来自于对人工自适应系统的研究,所以机器人学理所当然地成为遗传算法的一个重要应用领域。例如:遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到研究和应用。 (6)人工生命。人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能

32、力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系,基于遗传算法的进化模型是研究人工生命现象的重要基础理论。虽然人工生命的研究尚处于启蒙阶段,但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力,并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成,遗传算法为人工生命的研究提供了一个有效的工具,人工生命的研究也必将促进遗传算法的进一步发展。 (7)遗传编程。Koza发展了遗传编程的概念,他使用了以LISB语言所表示的编码方法,基于对一种树型结构所进行的遗传操作来自动生成计算机程序。虽然遗传编程的理论尚未成熟,应用也有一些限制,但它已

33、成功地应用于人工智能、机器学习等领域。(8)机器学习。学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习,特别是分类器系统,在很多领域中都得到了应用。如遗传算法被用于学习模糊控制规则,利用遗传算法来学习隶属度函数,能更好地改进了模糊系统的性能。基于遗传算法的机器学习可用来调整人工神经网络的连接权,也可用于人工神经网络的网络结构优化设计,分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。 第二章 遗传算法简介2.1 遗传算法的基本概念遗传算法是对人类自然演化过程的模拟。人类的自然演化过程是进化过程,这种进化过程发生在染色体上;自然选择使适应值好的染色体比那些适应值差的染

34、色体有更多的繁殖机会;变异可以使子代染色体不同于父代染色体;通过两个父代染色体的结合与重组可以产生全新的染色体。染色体的选择、变异与重组进程是无记忆的。将这些概念反映在数学上就形成了遗传算法的基本概念。个体和个体空间:所谓l个体X,即是长度为l的0和1字符串,简称个体;l称作个体的链长,l个体的全体记作S=(0,1)l,称为个体空间。按照遗传学的术语,个体也称作染色体(chromosome),个体的分量称作基因(gene),分量的取值称作等位基因(allele)。种群和种群空间:所谓N种群是N个个体组成的集合(个体允许重复),简称种群。N称作种群规模,称=(X1,X2, ,XN),XiS(iN

35、)为N种群空间。 对于一个种群,由于是由个体构成的,因此它是个体空间的一部分,即是个体空间的一个子集。我们可以记为,当用时,视为一个子集,当用时,表示中不重复的个体是中的一个子集。这时和都不视为向量。如果视可表示为矩阵形式,如: (2.1)其中每一行代表一个个体,第i行表示第i个个体。对于链长为l种群规模为N的种群可以表示为Nl阶矩阵。 (2.2)其中 为一个个体。表示第i个个体第j个基因取值。适应值函数:对于一个个体产生的效益称为适应值。适应值函数是个体空间S到正实数空间的映射,即适应值函数为:。选择算子:选择算子即是在一个种群中选择一个个体,它是随机映射: (2.3)特别地,按照概率规则

36、(2.4)选择个体的方式称为适应值选择算子。其中表示种群中的个体的适应值,0。对于=1称为比例选择算子,简记为。容易看到适应值选择算子依赖于种群,它是种群上的一个概率分布,即对于种群=(X1, X2, XN)有概率分布 (2.5)即构成概率分布向量 (2.6)其中满足以下条件: 0 () 称0()为上的一维概率分布。 从选择算子的执行过程,适应值大的个体易被选择,适应值小的个体易被淘汰,这样经过不断地选择使适应值大的个体不断重复出现,使一个种群可能变为齐次种群。但是选择算子只是在一个固定的种群中进行选择;选择的结果不可能跑到种群之外。对于种群之外更好的个体是不可能被选择得到的,选择的结果依赖于

37、初始种群。母体和母体空间: 所谓母体即是一对个体(X1,X2),其中 XiS (i=1,2)所有母体的全体称为母体空间,即 S2=( X1,X2);X1,X2S (2.7) 杂交算子:杂交算子是母体空间到个体空间的映射,记作 Ts : S2S (2.8) (l)单点杂交算子:等概率的随机确定一个基因位置作为杂交点,再把一对母体两个个体从杂交点分成前后两个部分,交换两个个体的后半部分得到两个新个体,取第一个个体为杂交结果。 (2)单点随机杂交算子:等概率的随机确定一个基因位置作为杂交点,再把一对母体两个个体从杂交点分为前后两个部分,以概率Pc交换两个个体的后半部分,得到两个新个体,取第一个个体为

38、杂交结果。称Pc为杂交概率。 如果确定两个基因位置将一对母体两个个体分成三部分,交换中间部分,称为双点杂交算子。同样有双点杂交与双点随机杂交之分。(3)均匀随机杂交算子:独立地以概率Pc把母体的第一个个体的相应的分量交换为第二母体的相应分量,从而得到杂交结果。 变异算子:变异算子是个体空间到个体空间的随机映射,其作用方式为独立地以概率Pm改变个体分量取值。Pm称作变异概率。基于生物学上的考虑,一般认为杂交是自然演化的主要机制,变异为自然演化的背景,它们分别承担遗传与变异两种功能。因此在具体应用过程中,杂交概率一般取值较大,在0.6与0.9之间。而变异概率取值较小、一般在0.001与0.01之间

39、。遗传算法的基本概念构成了遗传算法的基本模型。对于一个实际问题,首先是将问题转化为遗传算法的基本概念。一旦用遗传算法的基本概念来表达实际问题,问题的求解过程就不再依赖于实际问题本身。2.2遗传算法的基本原理遗传算法类似于自然进化,通过作用于染色体上的基因寻找好的染色体来求解问题。与自然界相似,遗传算法对求解问题的本身一无所知,它所需要的仅是对算法所产生的每个染色体进行评价,并基于适应值来选择染色体,使适应性好的染色体有更多的繁殖机会。在遗传算法中,通过随机方式产生若干个所求解问题的数字编码,即染色体,形成初始群体;通过适应度函数给每个个体一个数值评价,淘汰低适应度的个体,选择高适应度的个体参加

40、遗传操作,经过遗传操作后的个体集合形成下一代新的种群,从而对这个新种群进行下一轮进化。这就是遗传算法的基本原理。下面是遗传算法的基本思想:(1) 初始化群体;(2) 计算群体上每个个体的适应度值;(3) 按由个体适应度值所决定的某个规则,选择将进入下一代的个体;(4) 按概率Pc进行交叉操作;(5) 按概率Pc进行突变操作;(6) 没有满足某种停止条件,则转第(2)步,否则进入(7);(7) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。程序的停止条件最简单的有如下二种:完成了预先给定的进化代数则停止;种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。应

41、用遗传算法求解应用问题时,需要根据应用问题构造遗传算法,遗传算法中的各种选择算子、交叉算子、变异算子,遗传算法的构造过程如图 2.1所示。实际应用中的优化问题都含有一定的约束条件,在遗传算法中处理约束条件常用的方法有搜索空间限定法、可行解变换法、罚函数法。搜索空间限定法的思想是在搜索空间中将个体与解空间中可行解之间建立一一对应的关系;可行解变换法的思想是在由个体基因型到个体表现型的变换中增加满足约束条件的处理过程;罚函数法的思想是对解空间中无对应可行解的个体计算其适应度时处以一个罚函数降低适应度,减少此个体遗传到下一代的机会。另外,在遗传算法的研究和应用中,开发出了多种高级实现技术,利用这些技

42、术可以有效的利用遗传算法解决广泛的应用问题。 最优化问题描述 解空间 确定决策变量、优化条件 建立优化模型 第一步 第二步 目标函数f(X) 个体表现型X确定适应度转换规则 解码方法 编码方法 适应度F(X) 个体基因型X 第三步 第四步 第五步 设计遗传算子 第六步 确定运行参数 第七步 遗传算法 遗传空间 图2.1 遗传算法的构造过程2.3 遗传算法的特征 为解决各种优化计算问题,人们提出了各种各样的优化算法,如单纯形法、梯度法、动态规划法、分枝定界法等。这些优化算法各有各的长处,各有各的适用范围,也各有各的限制。 搜索算法的共同特征为: (1)首先组成一组候选解; (2)依据某些适应性条

43、件测算这些候选解的适应度; (3)根据适应度保留某些候选解,放弃其他候选解; (4)对保留的候选解进行某些操作,生成新的候选解。 在遗传算法中,上述几个特征以一种特殊的方式组合在一起:基于染色体群的并行搜索,带有猜测性质的选择操作、交叉操作和变异操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。遗传算法是一类可用于复杂系统优化计算的搜索算法,与其他一些优化算法相比,它主要有下述几个特点 : 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算,但遗传算法不是直接以决策变量的值而是以决策变量的某种形式的编码为运算对象。这种对决策变量的编码处理方式,使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念,可以模仿自然界中生物的遗传和进化等机理,也使得我们可以方便地应用遗传操作算子。特别是对一些无数值概念或很难有数值概念,而只有代码概念的优化间题,编码处理方式更显示出了其独持的优越性。 遗传算法直接以目标函数值作为搜索信息。传统的优化算法不仅需要利用目标函数值,而且往往需要目标函数的导数值等其他一些辅助信

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 小学资料

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁