遗传算法综述

遗传算法综述遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。在阅读了一些相关资料后，我整理出这篇综述，将通过五个部分来介绍遗传算法以及其在计算机科学领域的相关应用、一、起源和发展分支尝试性地将生物进化过程在计算机中模拟并用于优化问题求解开始于20世纪50年代末，其目的是将生物进化的思想引入许多工程问题中而成为一种优化工具，这些开拓性的研究工作形成了遗传算法的雏形。但当时的研究进展缓慢，收效甚微。原因是由于缺少一种通用的编码方式，人们只有通过变异才能改变基因结构，而无法使用交叉，因而增加了迭代次数。同时算法本身需要较大的计算量，当时的计算机速度便无法满足要求，因而限制了这一仿生过程技术的迅速发展。20世纪60年代中期，Holland在Fraser和Bremermann等人研究成果的基础上提出了位串编码技术，这种编码技术同时适用于变异操作和交叉操作。遗传算法的真正产生源于20世纪60年代末到70年代初，美国Michigan大学的Holland教授在设计人工适应系统中开创性地使用了一种基于自然演化原理的搜索机制，并于1975年出版了著名的专著“AdaptationinNaturalandArtificialSystems”，这些有关遗传算法的基础理论为遗传算法的发展和完善奠定了的基础。同时，Holland教授的学生DeJong首次将遗传算法应用于函数优化中，设计了遗传算法执行策略和性能评价指标，他挑选的5个专门用于遗传算法数值实验的函数至今仍被频繁使用，而他提出的在线(on-line)和离线(off-line)指标则仍是目前衡量遗传算法优化性能的主要手段。在Holland教授和他的学生与同事DeJong进行大量有关遗传算法的开创性工作的同时，德国柏林工业大学的Rechenberg和Schwefel等在进行风洞实验时，为了对描述物体形状的参数进行优化以获得更好的实验数据，将变异操作引入计算模型中，获得了意外的优良效果。实验后，经过进一步系统地研究，形成了进化策略(evolutionarystrategies,ES)。1962年，Fogel等人在设计有穷状态自动机(finitestatemachine,FSM)时借用进化和思想对一组FSM进行进化，提出了一种模仿人类智能的方法，称为进化编程(evolutionaryprogramming,EP)，也叫进化规划(evolutionaryplanning)，随后将其应用于数值优化及神经网络的训练问题中。这两种算法和遗传算法以及遗传编程(geneticprogramming,GP)一起构成了目前进化计算的四大分支，它们从不同层次、不同角度模拟自然演化的规律，以达到求解实际问题的目的。而进化计算则与人工神经网络、模糊理论一起形成一个新的研究方向，即计算智能。计算智能以生物进化的观点认识和模拟智能，以数据为基础，通过进化过程建立联系而进行问题求解。人工智能已从传统的基于符号主义向以神经网络为代表的连接主义和以进化计算为代表的进化主义方向发展，形成了新的研究方法。遗传算法被提出之后立即受到了各国学者的广泛关注，有关遗传算法的研究成果不断涌现。1968年Holland提出了著名的模式(schema)定理；1975年DeJong首先尝试将遗传算法用于函数优化，提出了5个测试函数用以测试遗传算法的优化性能；1981年Bethke应用Walsh函数分析模式；1983年Wetzel用遗传算法解决了NP难问题旅行商问题(TSP)；1985年Schaffer利用多种群遗传算法研究解决了多目标优化问题；1987年Goldberg等人提出了借助共享函数的小生境遗传算法。1989年，Goldberg出版专著“GeneticAlgorithminSearch,Optimization,andMachinelearning”，对遗传算法的研究产生了非常大的影响。1992年，Michalewicz出版另一部具有极大影响力的著作“GeneticAlgorithmDataStructureEvolutionaryProgramming”。从20世纪80年代中期起，遗传算法和进化计算到达一个研究高潮，以遗传算法和进化计算为主题的国际学术会议在世界各地定期召开。1985年，第一届国际遗传算法会议(internationalconferenceongeneticalgorithms,ICGA)在美国卡耐基·梅隆大学召开，以后每两年召开一届。此外，进化规划年会(annualconferenceonevolutionaryprogramming,ACEP)于1992年在美国的加州召开第一届会议，以后每隔两年召开一届；进化计算会议(IEEEconferenceonevolutionarycomputation)也于1994年开始定期召开。相关的国际学术会议还有很多。[1]目前遗传算法的主要分支有CHC算法、自适应遗传算法、小生境遗传算法、双倍体遗传算法以及双种群遗传算法。二、重要人物和经典文章对于遗传算法带来重要影响的人物和相关文献如下：1．J.D.Bagley，1967年在其博士论文中首次提出“遗传算法（GeneticAlgorithms）”一词。2．Fogel等出版了《基于模拟进化的人工智能》，系统阐述了进化规划的思想。3．R.B.Hollstien，在他的博士论文中首次把遗传算法用于函数优化。4．Holland，于1975年出版了他的著名专著《自然系统和人工系统的自适应》（AdaptationinNaturalandArtificialSystems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schematheory）。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。5．K.A.DeJong，在1975年完成了他的博士论文《一类遗传自适应系统的行为分析》（AnAnalysisoftheBehaviorofaClassofGeneticAdaptiveSystem）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管DeJong和Hollstien一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generationgap）等新的遗传操作技术。可以认为，DeJong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。6．Smith教授，1980年首次将遗传算法应用于机器学习领域,并研制出一种称作分类器(Classifier)的系统。7．Goldberg，撰写了《遗传算法在搜索优化和机器学习中的应用》一书,对GA的原理及应用做了比较详细、全面的论述。该书至今仍是遗传算法研究中广泛适用的经典之作。8．D.E.Goldberg，出版了专著《搜索、优化和机器学习中的遗传算法》（GeneticAlgorithmsinSearch,Optimization,andMachineLearning）。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。9．美国斯坦福大学的Koza，基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计(geneticprogramming,GP)方法，成功地解决了许多问题。他的专著《遗传程序设计:基于自然选择法则的计算机程序设计》”。1994年，他又出版了《遗传程序设计，第二册:可重用程序的自动发现》深化了遗传程序设计的研究，使程序设计自动化展现了新局面。10．L.Davis编辑出版了《遗传算法手册》（HandbookofGeneticAlgorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。11.1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacencybasedcrossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。12.1992年，Michalewicz出版具有极大影响力的著作“GeneticAlgorithmDataStructureEvolutionaryProgramming”。三、算法结构如下图所示。[2][3]四、最新研究成果对于优化问题求解的任何搜索算法而言，其收敛性具有重要的理论意义。因此，遗传算法的收敛性一直是理论研究的一个重要方面。近几年，在遗传算法全局收敛性的分析方面取得了突破，运用的工具主要是Markov链。欺骗问题也是遗传算法的一个研究热点。根据2008—2010年三年内遗传算法研究方面发表在EI源刊上的文章分布情况，分别从研究内容和应用领域两个方面进行统计，结果如图1所示。[4]由图1可以得到如下结论:a)从研究内容来看，涉及物种多样性、测试函数、遗传算子、参数确定等研究内容的文章占据较大数量;b)从应用领域来看，针对遗传算法在生产调度及机器人学方面进行研究的文章占多数，在自动控制、组合优化和图像处理方面的研究也占很大一部分比例。有关遗传算法在函数优化、机器学习、人工生命、数据挖掘及遗传编程方面研究所涉及的文章不是很多。遗传算法在函数优化和组合优化方面进行研究的文章每年几乎都是最多的，而生产调度及自动控制等实际应用领域的研究成果较少。遗传算法在数据挖掘和机器学习领域进行研究的文章不多，但在研究成果中所占的比重逐年增长。结合以上对比分析可知，遗传算法在函数优化及组合优化方面的研究在减少，尤其在函数优化方面减少更明显，但是在生产调度及自动控制等领域的研究比重明显增加，这充分说明遗传算法的研究已经从理论方面逐渐转向应用领域;机器人学及图像处理也在逐渐成为研究的热点。涉及数据挖掘研究方面的文章不是很多，但随着数据挖掘技术的广泛应用，遗传算法在数据挖掘领域的研究会成为新的热点。多智能体进化、免疫进化计算、粒子群遗传算法是这几年研究比较多的题目，对传统遗传算子(选择、交叉、变异)的改进也是讨论比较多的话题。随着应用的不断深入，遗传算法在优化多峰问题时的不足逐渐暴露出来。小生境作为优化多峰问题的一种有效手段，得到了广泛关注，并已经成为遗传算法领域的一个研究热点。协同进化算法是在进化算法的基础上，通过考虑种群与环境之间、种群与种群之间在进化过程中的协调关系提出的一类新的进化算法，目前遗传算法已经成为当前进化计算的一个热点问题。五、遗传算法在计算机科学领域的应用与代表性文章函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。车间调度问题是一个典型的NP-Hard问题，遗传算法作为一种经典的智能算法广泛用于车间调度中，很多学者都致力于用遗传算法解决车间调度问题，现今也取得了十分丰硕的成果。从最初的传统车间调度（JSP）问题到柔性作业车间调度问题（FJSP），遗传算法都有优异的表现，在很多算例中都得到了最优或近优解。随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。[5