文献综述-雄性偏向的遗传算法的改进研究.doc

专业文献综述题 目: 遗传算法综述 姓 名: 学 院: 信息科技学院 专 业: 计算机科学与技术 班 级: 计科121 学 号: 指导教师: 职称: 副教授 2015年 6月 24 日南京农业大学教务处制遗传算法综述摘要：遗传算法是通过模拟生物界的自然遗传进化规律得到的随机化搜索方法。它具有较好的全局性，高鲁棒性和可扩展性，较高的随机性，以及潜在的并行性等不同优点，近年来，在求解复杂优化问题中表现出了巨大的潜力并且在相关产业领域的有了较为成功的应用,因此受到了国内外学者的广泛关注。同时，针对其存在的早熟问题，较差的局部搜索能力等缺点做出改善也成为了众多学者研究的方向。本文介绍了遗传算法的基本原理与技术，回顾了遗传算法的起源、发展，阐述了该算法目前存在的问题，对简单展望了其未来发展情况。关键词：遗传算法；搜索；编码；进化Summary of the Genetic AlgorithmsWang yuetianAbstract： Genetic algorithms are stochastic search methods of genetic evolution through natural biological laws of simulation obtained. It has distinct advantages better overall, high robustness and scalability, high randomness and potential parallelism, in recent years, in solving complex optimization problems showed great potential and in the relevant With more successful application industries, and therefore subject to the attention of scholars. Meanwhile, for the precocious its problems, the disadvantage of poor local search ability make improvements has become a research direction of many scholars. This article describes the basic principles of genetic algorithms and techniques, review the origin of the genetic algorithm development, describes the algorithm existing problems, prospects for its future development simple situation.Key words: Genetic Algorithms；Search；Encoding；Evolution引言：大自然的智慧是无穷的，生物进化人类发展到现在本身就是神奇的，无数应用仿生学而成功解决了问题的先例告诉我们，自然界的事物存在与发展是我们解决问题可以借鉴的素材库。随着计算机技术的发展，计算机应用领域也越来越广泛，随之而来的是所要解决问题的复杂性也在攀升，正是在这样的一种情形下，当传统搜索算法在解决复杂和非线性问题陷入问题瓶颈时，遗传算法逐渐发展了起来。遗传算法（Genetic Algorithm 简称GA）是一种通过模拟自然进化过程的搜素算法。60年代中期，美国Michigan大学J.Holland教授提出借鉴生物自然遗传的基本原理应用于自然和人工系统的自适应研究，随后他的学生Bagley首次提出了遗传算法一词。1975年Holland教授出版了标志着遗传算法诞生的“Adaptation in natural and artificial systems“,后经 DeJong、Goldberg等人不断的补充归纳，总结形成了一类系统的模拟进化算法 1 3 。算法主要思想是通过模拟自然界物种进化（适者生存，优胜劣汰遗传机制）来形成的一种过程搜索最优解的算法。自其诞生以来，就引起了国内外众多学者的关注 4。1遗传算法的基本原理与技术综合文献来看，到目前为止，遗传算法的研究主要包括三个领域5 :遗传算法的理论与技术;用遗传算法进行优化;用遗传算法进行分类系统的机器学习。作为遗传算法研究的基础，遗传算法的理论与技术研究主要包括编码、遗传算子，适应度评价，参数选择，收敛性分析等方面。1.1基本原理遗传算法是模拟自然环境下生物的遗传和进化过程来解决问题的，是一种自适应全局优化搜索方法，它采用了自然进化模型。概括来讲，遗传算法的整个过程是从一个初始解（称为种群）开始的，种群由问题的潜在解集中随机选择产生。经过基因编码的一定数目的个体组成了初始种群，实际上每个个体是问题的一个解（称为染色体）。之后借助于自然遗传学的遗传算子进行组合交叉和变异，生成下一代染色体,即后代。按照适者生存和优胜劣汰的自然进化原理，在每一代，根据问题域中个体的适应度大小选择个体，产生出代表新的解集的种群。新产生种群与上一代种群合并后,作为下一代群体,再继续进化,这样经过若干代之后，逐代演化产生出越来越好的近似解，这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解或次优解。1.2编码问题编码也就是将实际空间问题转化成为遗传基因型的过程，这是因为遗传算法并不能直接处理实际问题，必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。也可以称作(问题的)表示(representation)。编码是遗传算法要解决的首要问题。Holland提出的编码方式是二进制编码1，也即用二进制字符集0,1产生通常的0,1字符串来表示问题，由于其操作简单便于实现，也便于利用模式定理分析，二进制编码成为了最常用的的方法。但是遗传算法的随机特性导致了其在连续问题中局部搜索能力较差，一些其他的改进编码方式也出现了，常见有格雷码编码，实数编码，符号编码，动态编码，复数编码等。格雷码编码6方法对二进制编码方法的一种变形，其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的,其余码位都完全相同。实数编码即用实数来表示个体的每个基因值。在解决一些多维、高精度要求的连续函数优化问题，能较好地缩小映射误差等不利，方便引入与问题相关的启发式信息来增加算法的搜索能力。提高了遗传算法的精度要求6，较大空间的搜素效果好。在设计专门问题的算子时十分方便贴合。符号编码也称为非数值编码，是指用没有数值含义的符号来表示染色体编码串中的基因值。这些符号本身是字符也可以是数字。使用这一方法可以非常方便地把问题领域的知识结合到遗传算法的设计和和实现当中来。动态编码即动态相似度参数零件族编码，该编码方法通过相似性、自身相似基因比动态划分零件族，极大地降低了问题求解的时间复杂度7。复数编码通过采用向量的方式来解决二维问题。利用复数的模与实自变量对应，用实部和虚部两个变量来表示一个自变量，挖掘群体中个体的多样性，减少局部收敛。这一方法也可以推广到多维问题的求解中去。1.3遗传算子遗传算法是基于生物遗传学的，而自然界物种的自然选择，遗传进化规则可以概括为繁衍，杂交和突变。于是，模拟该过程的选择，交叉，变异三种基本操作算子构成了遗传算法强大搜索能力的核心。（1） 选择算子选择算子有时又称为再生算子(reproduction operator)。是“优胜劣汰”操作的具体实现，选择操作的依据是个体的适应度评价结果。即根据适应度从群体中选择优胜的个体，淘汰劣质个体。其目的是把优化的个体(或解)直接遗传到下一代，避免基因缺失，同时提高全局收敛性和计算效率。总得来讲，目前常用的选择算子有轮盘赌选择法，随机联赛选择法，排序选择方法，最佳个体保存方法等。轮盘赌选择法又称为适应度比例法，即按照适应度值来选择个体，是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为fi，则i 被选择的概率为 。随机联赛选择法的基本思想则更强调随机性，具体方法是从群体中任意选择部分个体，把适应度最高的个体留到下一代。反复执行这个过程，直到保存到的个体数达到预先设定的数目为止。最佳个体保存方法将当前种群的最优个体不经交叉变异，直接保存到下一代，并用它来代替交叉变异后的适应度最低个体。这样可以保证最优个体不被破坏，保证了遗传算法 的收敛性。从而增强了算法的全局搜索能力。（2） 交叉算子生物学中的基因交叉是产生新基因型的关键，同理，交叉操作也是遗传算法自适应产生问题的解的主要方式，大大提高了遗传算法的搜素能力。其具体实现是把两个互相配对的父代个体按某种方式将其部分结构加以替换重组,从而产生新的个体。这也是遗传算法的可区别的重要特征。交叉操作按交叉率将个体随机地交换基因，从而产生新的基因型，期望将有益基因组合在一起，以增加求得到最优解的可能。交叉算子一般均需要包括：随机将个体配对，并按预先设定的交叉概率来判断是否需要交叉，对需要交叉的个体设定交叉点，并将点前后部分结构进行交换。交叉操作有很多种方法，Potts等人概括出了 17种 8 。最简单的是单点交叉，即简单交叉，这种方法中，交叉点随机设置，相互交换两个配对个体的部分结构，生成两个新个体。同理，双点交叉即是随机设置两个交叉点，交换它们之间的部分基因。相对于这种按点部分交叉方式，还有两种按位交叉方式，一种是均匀交叉，即两个互相配对的个体的每一位基因都以相同的概率进行交换,从而形成两个新个体。另一种是算术交叉，其基本思想是由两个个体的线性组合而产生出新的个体。具体数学描述为：在两个个体 A、B 之间进行算术交叉,则交叉运算后生成的两个新个体 X =A+(1-)B、Y =B +(1-)A。（3） 变异算子基因突变是生物遗传界产生新基因的方式，其随机性是现在物种多样性的重要原因。在遗传算法中，变异是增加算法局部随机搜索能力的关键。变异的基本操作是将群体中随机个体的一个或多个基因座上的基因值用其等位基因来替换。由于变异的存在，当遗传算法通过交叉运算逐渐接近最优解邻域时，变异算子的局部随机搜索能力细化并加速了逼近最优解。同时通过与交叉算子的配合，平衡了遗传算法全局和局部的搜素能力。变异算子一般需要先确定变异点位置，而后按设定好的变异概率对其进行变异操作。基本位变异算子是指在群体中随机挑选一个或多个基因座作为变异点，然后对它们的基因值做变异(按变异概率P)。相对于基本位的点操作，均匀变异是将个体中每个基因座都进行了替换，该算子也可称作一致变异，它是分别用某一范围内均匀分布的随机数 , 并按某一较小的概率来替换的，它使变异点在整个求解空间内自由移动，特别适合遗传算法的初期运行阶段。 高斯变异与均匀变异类似，只是用成正态分布的随机数来进行替换（正态分布的均值为、方差为2）。相对于以上在单染色体上进行的变异操作，二元变异算子能较好地客服早熟收敛问题，这种方法需要两条染色体参与 ,变异后生成两条新个体中的各个基因分别取原染色体对应基因值的同或/异或，它有效提高了运算速度。1.4适应度评价自然遗传进化论的适应度，代表了个体对环境的适应能力和繁殖后代能力，是优胜劣汰的评价标准。在遗传算法中，适应度评价是得出个体性能主要指标的基本方法。遗传算法的适应度函数也叫评价函数，一般均用问题求解的目标函数来进行。针对不同问题，结合其要求本身，设计不同的函数方法来建立优化目标函数并进行优化。评价函数是搜索算法性能的关键。在求解有约束的优化问题时 , 一般利用罚函数方法将目标函数和约束条件沿群体进化过程方向设计建立成一个无约束的优化目标函数，然后对其进行相应转换，得到合适的适应度函数 。同时要注意的是，适应度必须非负 10 。 1.5收敛性分析遗传算法的收敛性分析也就是对算法程序中止条件的分析。通常将种群适应函数的最大值或均值趋于最优解时，种群状态逐渐稳定作为标准。即当最优个体的适应度达到给定的阈值或不再上升，群体适应度不再上升，或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100-500代。依不同的研究方法及所应用的数学工具 , 收敛性分析可分为 Vose-Liepins 模型 、Markov链模型和公理化模型等11 。2遗传算法的问题与发展2.1存在的问题J.Holland教授所提出的GA通常为简单遗传算法（SGA）。在其提出之后,遗传算法的研究引起了国内外学者的关注，也在重点领域中进行了实际操作检验。虽然遗传算法在这些领域中都有成功的应用，但其自身也存在不足，如局部搜索能力差、存在未成熟收敛和随机游走等现象，导致算法的收敛性差，求解耗时长等问题。这些不足阻碍了遗传算法的推广应用。为了克服这些问题，越来越多的研究人员致力于遗传算法的改进。概括来讲，遗传算法还存在着这样一些问题：1、早熟。也是影响最严重的问题，即算法对新空间的探索能力是有限的，容易收敛到局部最优解。2、大量计算。涉及到大量个体的计算，当问题复杂时，时间复杂度上涨，计算时间过长。3、处理规模小。目前对于维数较高的问题，还是很难处理和优化的。4、难于处理非线性约束。对非线性约束的处理，大部分算法都是添加惩罚因子解决，增加了开销。5、稳定性差。遗传算法属于随机类算法，需要多次运算，结果的可靠性差，不一定能稳定的得到解。2.2发展随着越来越多的研究人员对遗传算法问题的研究深入，并致力于找到改善解决方法，多种多样的改进算法被提出来，经过验证具有较好的效果且比较常见的改进算法有混合遗传算法，并行遗传算法，协同进化算法，基于免疫的遗传算法，精英策略遗传算法等等：作为进化算法的主要方法之一，遗传算法与其他几种具有较好局部优化效果的算法进行结合，可以得到多种混合算法。例如, Ackley 推荐的遗传爬山法;Mathefoud 提出的遗传模拟退火算法;Miller 等提出的对于 NP 难问题的优化问题,采用遗传算法中增加局部改善运算等等。由于互补性，混合遗传算法常有较好的平衡能力。针对遗传算法在解决实际问题时,种群规模往往较大，需要进行大量操作运算的个体较多,尤其是要对大量的个体进行适应度评价,使得算法的进行过程异常缓慢,难以达到要求,因而并行计算的应用受到了重视。对遗传算法进行并行处理的具有极大的可挖掘性,于是产生了多种基于并行计算机或局域网的并行遗传算法。这些并行遗传算法主要从下列四个方面对其进行改进和发展。(1)个体适应度评价的并行性 (2)整个群体中各个个体的适应度评价的并行性 (3)群体产生过程的并行性(4)基于群体分组的并行性与遗传算法相同，协同进化也是根据自然界协同进化的现象发展出来的全局优化算法。传统遗传算法只考虑个体进化水平，仅以个体适应度作为评价标准，忽视了种群与环境，种群与种群之前的进化关系对个体进化产生的影响，因此在收敛性方面存在着一定不足 12。相对而言，综合考虑了种群之间，种群与个体，个体之间关系对个体之间的生存能力影响的协同进化算法，在收敛效果、收敛时间、寻优能力上都具有较好的改善效果。3遗传算法的前景展望随着计算机技术的发展，和对遗传算法的不断改进和拓展，遗传算法的有效应用领域在逐渐扩充，遗传算法的研究和应用非常具有新引力的前景：一是在机器学习领域的应用，这一新的研究课题把遗传算法扩展到了具有独特规则生成功能机器学习算法。对于解决人工智能中知识获取和知识优化的难题带来了希望。二是遗传算法正日益和神经网络、模糊识别以及混沌理论等其它智能计算方法相互渗透和结合，这对发展和建立新的智能计算技术将具有重要的意义。三是与人工生命的研究领域不断渗透。对于人工模拟自然界的生命现象有着重要作用，遗传算法本身就是从自然中提炼得到，回归到自然的模拟当中，尤其是对于自然界生命遗传进化的模拟。一定会具有良好的效果。此外，随着自然界生物遗传规则和进化奥秘的不断揭示，遗传算法本身的改进和完善也有着广阔的前景和明确的方向。参考文献：1 Holland.JH .Adaptation in natural and artificial systems M . AnnArbor:University of Michigan Press,1975.2 Dejongka. The analysis of the behavior of a class of genetic adaptive systems D .AnnArbor:University of Michigan, 1975.3 Goldbergde Genetic algorithms in search,optimizat