遗传算法综述

遗传算法综述摘要：遗传算法(geneticalgorithms，GA)是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，适用于处理传统搜索方法难以解决的复杂和非线性优化问题。遗传算法可广泛应用于组合优化、机器学习、自适应控制、设计和人工生命等领域，是21世纪有关智能计算中的重要技术之一。本文通过对相关论文的查阅和整理，对遗传算法的研究现状和发展趋势进行了综述并谈论了一些自己的看法。关键词：遗传算法研究现状发展趋势引言：遗传算法是模拟遗传选择和自然淘汰的生物进化过程的计算模型，由美国Michigan大学的Holland教授于1969年提出，后经DeJong、Goldberg等人归纳总结，形成一种新的全局优化搜索算法[1]。遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。1、遗传算法的基本原理与传统搜索算法不同,遗传算法从一组随机产生的初始解,称为群体,开始搜索过程。群体中的每个个体是问题的一个解,称为染色体。这些染色体在后续迭代中不断进化,称为遗传。遗传算法主要通过交叉、变异、选择运算实现。交叉或变异运算生成下一代染色体,称为后代。染色体的好坏用适应度来衡量。根据适应度的大小从上一代和后代中选择一定数量的个体,作为下一代群体,再继续进化,这样经过若干代之后,算法收敛于最好的染色体,它很可能就是问题的最优解或次优解。“遗传算法中使用适应度这个概念来度量群体中的各个个体的在优化计算中有可能到达最优解的优良程度。度量个体适应度的函数称为适应度函数。适应度函数的定义一般与具体求解问题有关”[2]。遗传算法包含两个数据转换操作，一个是从表现型到基因型的转换，将搜索空间的参数或解转换成遗传空间中的染色体或个体，这个过程称为编码（coding）。另一个是从基因型到表现型的转换，即将个体转化成搜索空间中的参数，这个过程称为译码（decode）。图1展示了遗传算法的运行过程。图1遗传算法的运行过程示意图2、遗传算法的研究现状2.1遗传算法研究方向[3]在遗传算法的研究中，目前主要有三类研究方向：⑴研究遗传算法本身的理论基础。⑵用遗传算法作为工具解决工程问题。主要是进行优化，关心的是能否在传统方法上有所提高。在工程实践中的遗传算法应用主要是利用了其并行性和全局搜索的特点来进行优化。⑶用遗传算法研究进化现象，一般涉及到人工生命等复杂性科学领域。2.2遗传算法研究数据对比文献[4]通过对2008—2010年三年内遗传算法研究方面发表在EI源刊上的文章分布情况的分析，分别从研究内容和应用领域两个方面进行了统计，得到如下的统计图：图2遗传算法研究对比分析文献[5]则通过对2002—2006年国内学者及工程技术人员在综述、函数优化、组合优化、生产调度、自动控制、机器人学、图像处理、人工生命、遗传编程、机器学习、数据挖掘11个方面对近五年国内发表在中文核心期刊上、与遗传算法有关的论文进行了分类，得到如下对比分析图：图32002-2006年国内遗传算法研究现状分析通过对这些图的分析，我们可以得到以下推论：（1）从研究内容来看，涉及物种多样性、测试函数、遗传算子、参数确定等研究内容的文章占据较大数量，欺骗问题和编码问题有关所占的比重不大；（2）从应用领域来看，针对遗传算法在生产调度及机器人学方面进行研究的文章占多数，在自动控制、组合优化和图像处理方面的研究也占很大一部分比例。有关遗传算法在函数优化、机器学习、人工生命、数据挖掘方面研究所涉及的文章不是很多，遗传编程方面被忽视。（3）通过遗传算法方面的研究情况进行对比分析得出，遗传算法在函数优化和组合优化方面进行研究的文章每年几乎都是最多的，而生产调度及自动控制等实际应用领域的研究成果较少，这说明了现阶段我国的学者仍将研究的重心放在遗传算法的理论研究上。遗传算法在数据挖掘和机器学习领域进行研究的文章不多，但在研究成果中所占的比重逐年增长。3、遗传算法的发展趋势遗传算法作为一种搜索算法，其基本框架已经形成，在各种问题的求解和应用中展现了它的特点和魅力，下面概述遗传算法现阶段研究课题的几个主要方面：3.1优化搜索方法的研究优化问题的求解在遗传算法研究中占很大比重。尽管遗传算法比其他传统搜索方法有更强的鲁棒性，但它更擅长全局搜索而局部搜索能力却不足。为此，除了要进一步改进基本理论和方法外，还要采用和神经网络、模拟退火或专家系统等其他方法相结合的策略[6]。许多研究结果表明，采用这种混合模型可有效提高遗传算法的局部搜索能力，从而进一步改善其收敛速度和解的品质。3.2遗传算法的并行分布处理伴随遗传算法应用的深入发展，并行分布遗传算法及其实现的研究也变得十分重要。遗传算法由于其群体性操作，所以本质上具有很好的并行分布处理特性。尤其是遗传算法中各个体的适应度计算可独立进行而彼此间无需任何通信，所以并行处理效率是很高的。但是，标准的遗传算法除适应度计算外，“几乎所有的遗传操作都是建立在全局统计处理的基础上，这意味着在整个进化过程中，这种全局统计处理所引起的通信开销依然是不可忽视的”[7]。因此，设计有效的并行遗传算法及相应的实现系统对于遗传算法的理论研究和应用研究都是十分重要而迫切的任务。文献[8]即给出了一种适用于大规模变量的并行遗传算法。3.3量子遗传算法研究量子遗传算法是在遗传算法中引入量子计算的概念,是20世纪90年代新兴的研究领域。目前，这一领域的研究主要集中在两类模型上：“一类是基于量子多宇宙特征的多宇宙量子衍生遗传算法(QuantumInspiredGeneticAlgorithm)，另一类是基于量子比特和量子态登加特性的遗传量子算法(GeneticQuantumAlgorithm,GQA)”[9]。最近几年量子遗传算法在算法机理和性能方面以及在算法的种群改进、编码扩展、算子创新、算法融合等应用方面均取得进展，但此算法在函数优化中迭代次数多、容易陷入局部最优解的问题仍亟待解决。文献[10]即给出了一种改进的量子遗传算法研究。3.4生物进化与遗传算法的研究从生物进化的角度看，现在的遗传算法理论框架尚处于核糖核酸的水平，模拟从RNA向DNA的进化过程和机制，从而完善和提高遗传算法的性能是值得注意的研究课题。3.5遗传算法在自动控制领域中的应用许多控制领域问题,当考虑到系统优化、自适应、自学习以及自组织等方面的要求时,多存在很多常规方法难以奏效的困难。而遗传算法在自动控制领域中的应用已经得到了良好效果。如遗传算法进行“航空控制系统的优化、使用遗传算法设计空间交会控制器以及运用遗传算法进行人工神经网络的结构优化设计和权值学习等”[11]都显示出了遗传算法在自动控制领域中应用的可能性，未来可以在这个领域发挥更大的作用。总结：综上所述我们可以看到遗传算法正逐步从理论走向实际，并且越来越贴近我们的实际生活。随着遗传算法理论研究的不断深入，其自身的发展将得到进一步完善，另外遗传算法自身的“开放性决定了它与其它算法相结合应用并会在计算速度上有大的突破，届时遗传算法在各个应用领域必将发挥重大作用”[12]，希望这一天可以尽早到来。参考文献：[1]HOLLANDJH.Adaptationinnaturalandartificialsystems[M].AnnArbor：UniversityofMichiganPress，1975[2]吉根林《遗传算法研究综述》第21卷第2期2004年2月计算机应用与软件（ComputerApplicationsandSoftwareVol121,No12Feb1,2004）[3]张达《遗传算法及其发展状况研究》计算机科学2004Vo1.31N2.10(增刊)[4]马永杰，云文霞《遗传算法研究进展》第29卷第4期2012年4月计算机应用与软件中图分类号:TP18文献标志码:A文章编号:1001-3695(2012)04-1201-06[5]葛继科，邱玉辉，吴春明，等．遗传算法研究综述［J］．计算机应用研究，2008，25(10):2911-2916．[6]PowllD.TongS,SkolnikM.EnGENEous:DomainIndependent,MachineforDesignOp－timization[J].ProcofICGA-89,1989.[7]StenderJ(Ed).ParallelGeneticAlgorithms[J].TheoryandApplication.ISOPress,1993.[8]李东潘志松《一种适用于大规模变量的并行遗传算法研究》《计算机科学》2012年07期【分类号】：TP18[9]梁昌勇柏桦蔡美菊等《量子遗传算法研究进展》计算机应用研究(ApplicationResearchofComputers)2012年07期[10]王竹荣杨波等《一种改进的量子遗传算法研究》西安理工大学学报（JournalofXi’anUniversityofTechnology）2012年02期[11]龚玲《遗传算法在自动控制领域中的应用综述》无线互联科技2013年06期[12]张国民《遗传算法的综述》科技视界(Science&TechnologyVision)2013年09期