遗传算法的发展现状

遗传算法的发展现状丑强 (清华大学数学科学系 北京 100084) 摘要:当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进。制造机器智能一直是人类的梦想，人们为此付出了巨大的努力。人工智能技术的出现，就是人们得到的成果。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。关键词:遗传算法;编码;控制参数;发展现状ACTUALITYANDDEVELOPMENTALTRENDFORGENETICALGORITHMSCHOUQiang(DepartmentofMathematicalSciencesTsinghuaUniversity,Beijing100084)Abstract:Scienceandtechnologyisenteringthecurrentmulti-disciplinarycross-cutting,mutualpenetration,influenceeachotherofthetimes.Lifesciencesandengineeringsciencesarecross-cutting,infiltrationandpromoteeachother.Intelligentmanufacturingmachinehasbeenadreamofmankind.Peoplepaidagreatdealofeffortforit.Artificialintelligencetechnology,iswhatpeopleget.GA(GeneticAlgorithms)isthevigorousdevelopmentofthescientificdevelopmentofthecharacteristicsandtrends.Keywords:geneticalgorithms;encoding;parameters;actuality1.遗传算法简介遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。它最早由美国密西根大学的H.Holland教授提出，起源于60年代对自然和人工自适应系统的研究；1967年，Bagley发表了关于遗传算法应用的论文，在其论文中首次使用“遗传算法（GeneticAlgorithm）”一词。70年代DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。近年来,遗传算法(GA)的卓越性能引起人们的关注.对于以往难以解决的函数优化问题,复杂的多目标规划问题,工农业生产中的配管,配线问题,以及机器学习,图像识别,人工神经网络的权系数调整和网络构造等问题,GA是最有效的方法之一.虽然GA在许多优化问题中都有成功的应用,但其本身也存在一些不足.例如局部搜索能力差,存在未成熟收敛和随机漫游等现象,从而导致算法的收敛能力差,需要很长时间才能找到最优解,这些不足阻碍了遗传算法的推广应用.如何改善遗传算法的搜索能力和提高算法的收敛速度,使其更好地应用于实际问题的解决中,是各国学者一直探索的一个主要课题.2.遗传算法的发展历史进化算法与其他科学技术一样，都经历一段成长过程，逐渐发展壮大。此过程可大致分为三个时期：萌芽期、成长期和发展期。(1)萌芽期(50年代后期至70年代初期)50年代后期，一些生物学家着手采用电子计算机模拟生物的遗传系统，尽管这些工作纯粹是研究生物现象，但其中已使用现代遗传算法的一些标识方式。1965年，德国的L.Rechenberg等人正式提出进化策略的方法，当时的进化策略只有一个个体，而且进化操作也只有变异一种。1965年，美国的L.j.Fogel正式提出进化规划，在计算中采用多个个体组成的群体，而且只运用变异操作。60年代期间，美国J.H.Holland在研究自适应系统时，提出系统本身与外部环境相互协调的遗传算法。1968年，J.H.Holland教授又提出模式理论，它成为遗传算法的主要理论基础。1967年，Bagley发表了关于遗传算法应用的论文，在其论文中首次使用“遗传算法（GeneticAlgorithm）”一词。(2)成长期(70年代中期至80年代末期)1975年，J.H.Holland教授的专著《自然界和人工系统的适应性(AdaptationinNaturalandArtificialSystem)》正式出版，全面地介绍了遗传算法，人们常常把这一事件视作遗传算法问世的标志，Holland也被视作遗传算法的创始人。1975年，De.Jong在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。1987年，美国D.Lawrence总结人们长期从事遗传算法的经验，公开出版《遗传算法和模拟退火(GeneticAlgorithmandSimulatedAnnealing)》一书，以论文集形式用大量实例介绍遗传算法。1985年，作为Holland的学生，D.E.Goldberg博士出版专著《遗传算法——搜索、优化及机器学习(GeneticAlgorithms——inSearch，OptimizationandMachineLearning)》，全面、系统地介绍遗传算法，使这一技术得到普及与推广。该书被人们视为遗传算法的教科书。1985年，在美国举行第一届遗传算法国际学术会议(InternationalConferenceonGeneticAlgorithms，简称ICGA），与会者交流运用遗传算法的经验。随后，1987，1989，1991，1993，l995及l997年，每2年左右都举行一次这种会议。(3)发展期(90年代以后)90年代，遗传算法不断地向广度和深度发展。1991年，D.Lawrence出版《遗传算法手册(HandbookofGeneticAlgorithms)一书，详尽地介绍遗传算法的工作细节。1996年Z.Michalewicz的专著《遗传算法+数据结构=进化程序》深入讨论了遗传算法的各种专门问题。同年，T.Back的专著《进化算法的理论与实践：进化策略、进化规划、遗传算法》深入阐明进化算法的许多理论问题。1992年，Koza出版专著《遗传规划——应用自然选择法则的计算机程序设计(GeneticProgramming:ontheProgrammingofComputerbyMeansofNaturalSelection)》，该书全面介绍了遗传规划的原理及应用实例，标明遗传规划己成为进化算法的一个重要分支。Koza本人也被视作遗传规划的奠基人。1994年，Koza又出版第二部专著《遗传规划Ⅱ：可再用程序的自动发现(GeneticProgrammingⅡ:AutomaticDiscoveryofReusablePrograms)》，提出自动定义函数的新概念，在遗传规划中引入子程序的新技术。同年，K.E.Kinnear主编《遗传规划进展(AdvancesinGeneticProgramming)》，汇集许多研究工作者有关应用遗传规划的经验和技术。3.遗传算法的发展现状近年来有关遗传算法的期刊论文和会议论文每年都有数百乃至上千篇,这些文献主要都是从某个方面对遗传算法进行了不同形式的改进,然后对所作改进的机理进行了分析并且都有针对性的用于解决某类实际问题.下面的各个表格是文献统计情况,来源于EI数据库(1884-2008).CountryArticlesofGeneticAlgorithmsChina9378UnitedStates6824Japan3095UnitedKingdom2436Taiwan1980India1309Korea1259Canada1123Italy1104Spain947从上表可以看出,中国在1884-2008年期间发表的关于遗传算法方面的文章数多于其他各国.LanguageLanguageofthearticlesaboutGAEnglish37578Chinese5438Japanese241Russian55Chinese,English36Japanese,English27Turkish25Spanish22French22English,Japanese19从上表可以看出,英语文章占的比例最大,其次,汉语文章也占较大比例.下表统计了1999-2008年之间每年发表的GA文章数(数据来源于EI数据库):YearArticlesofGeneticAlgorithms20081251200755882006600220055969200452482003304920022669200123832000222019991757从上表可以看出,除了2008年GA文章有大幅度减少外,其余每年的文章数大体上呈上升的趋势.4.结论我国开展遗传算法研究，主要在90年代。从上表可以看出,国人在遗传算法中发表的文章占的比例巨大,在遗传算法的研究中处于领先地位,为遗传算法的发展作出了巨大的贡献.参考文献[1] 徐成贤，陈志平，李乃成.近代优化方法[M].北京：科学出版社,2002.24～27. [2] Isidori A. Nonlinear control systems[M].2nd,New York:Springer Press,1989.32～33. [3] 王俊伟，汪定伟.微粒群算法中惯性权重的实验与分析[J].系统工程学报,2005,20(2):194～198. [4] Reynolds C W, Locks F. Adistributed behavioral model [J],Computer Graphic,1987,21(4):25～30. [5] 肖龙光.部分智能优化算法的改进及其数学理论分析[D].上海：东华大学，2005. [6] Sun M.A study of helicopter rotor aerodynamics in ground effect[D].Princeton:品册，1983. [7] 辛希孟. 信息技术与信息服务国际研讨会论文集：A集[C]. 北京：中国社会科学出版社，1994. [8] 北京空气动力研究所. 第九届高超声速气动力会议论文集[C]. 北京：北京空气动力研究所，1997. [9] 陈永康，李素循，李玉林. 高超声速流绕双椭球的实验研究[A]. 见：北京空气动力研究所编. 第九届高超声速气动力会议论文集[C]. 北京：北京空气动力研究所，1997：9～14. [10] Peng J, Luo X Z, Jin C J. The study about the dynamics of the approach glide‐down path control of the carrier aircraft[A]. In: GONG Yao‐nan ed. Proceedings of the Second Asian‐Pacific Conference on Aerospace Technology and Science[C]. Beijing: Chinese Society of Aeronautics and Astronautics, 1997: 236～241. [11] 孔祥福. FD‐09风洞带地面板条件下的流场校测报告[R]. 北京空气动力研究所技术报告 BG7‐270，北京：北京空气动力研究所，1989. [12] MIL‐E‐5007 D, 航空涡轮喷气和涡轮风扇发动机通用规范[S]. 美国空军，1973. [13] 黎志华，黎志军. 反馈声抵消器[P]. 中国专利：ZL85100748，1986－09－24.