搜索
遗传算法及其应用I摘要遗传算法是一种模拟自然界生物进化的搜索算法，由于它的简单易行、鲁棒性强，尤其是其不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程，从而使它的应用范围极为广泛，并且己在众多领域得到了实际应用，取得了许多令人瞩目的成果，引起了广大学者和工程人员的关注。在简要的介绍了遗传算法的发展历史和研究现状及其生物学、数学基础后，文中引出了遗传算法的基本概念和原理、分析了遗传算法的基本实现技术。如：编码、适应度函数、遗传算法的三大遗传操作、参数规则等。最后在介绍了遗传算法程序设计原则的基础上，编程实现了遗传算法在图像识别中的应用，在实践中检验了遗传算法的实际效果。关键词：遗传算法，适应度函数，图像识别遗传算法及其应用IIABSTRACTThegeneticalgorithmisakindofsearchingmethodwhichsimulatesthenaturalevolution.Itissimpleandeasytoimplement,especiallyitdonotneedthespecialfieldknowledge,soithasbeenusinginverybroadfields.Nowthegeneticalgorithmhasgotalotoffruits,andmoreandmorescholarsbegintopayattentiononit.Afterbriefintroductedthegeneticalgorithmandstudyedthehistoryofthedevelopmentstatusandbiology,mathematicalbasis,webroughtoutthebasicgeneticalgorithmconceptsandprinciples,analysisedthegeneticalgorithmtoachievethebasictechnology.Suchas:coding,fitnessfunction,geneticalgorithmofthethreemajorgeneticmanipulation,andotherparametersoftherules.Finally,introducedageneticalgorithmproceduresbasedontheprinciplesofdesign,programmingageneticalgorithmintheapplicationofimagerecognition,inpractice,wetestthepracticaleffectsofgeneticalgorithm.Keyword：geneticalgorithm，Fitnessfunction，imagerecognition遗传算法及其应用III引言当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中的一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。制造机器智能一直是人类的梦想，人们为此付出了巨大的努力。近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题已变得越来越突出，这些困难甚至使某些学者对人工智能提出了强烈批判，对人工智能的可能性提出了质疑。在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。因此，研究能在搜索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而得到最优解或准优解的通用搜索算法一直是令人瞩目的课题。遗传算法就是在这种背景下产生并经实践证明特别有效的算法。遗传算法(GeneticAlgorithmGA)是近年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想是基于Darwin的进化论和Mendel的遗传学说。该算法由密执安大学教授Holland及其学生于1975年创建。自1985年以来。国际上已召开了多次遗传算法的学术会议和研讨会。国际遗传算法学会组织召开的ICGA(InternationalConferenceonGeneticAlgorithms)会议FOGA(Workshop-onFoundationofGeneticAlgorithms)会议。为研究和应用遗传算法提供了国际交流的机会。作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择，来指导学习和确定搜索的方向。近年来，遗传算法已被成功地应用于工业、经济管理、交通运输、工业设计等不同领域。解决了许多问题。例如：可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。遗传算法及其应用1第一章绪论1.1遗传算法的发展历史与研究现状20世纪60年代，美国Michigan大学的JohnHolland教授开始研究自然和人工系统的自适应行为，在这些研究中，他试图发展一种用于创造通用程序和机器的理论，使得通用程序和机器具有适应任意环境的能力。他意识到用群体方法搜索以及选择、交换等操作策略的重要性。在六十年代中期至七十年代末期，基于语言智能和逻辑数学智能的传统人工智能十分兴盛，而基于自然进化的思想则遭到怀疑和反对，Holland及其数位博士生仍坚持了这一方向的研究。Bagley发明“遗传算法”一词，并发表了第一篇有关遗传算法应用的论文，在他开创性的博士论文中采用双倍体编码，发展了与目前类似的复制、交换、突变、显性、倒位等基因操作，他还敏锐地察觉到防止早熟收敛的机理，并发展了自组织遗传算法的概念。与此同时，Rosen-berg在他的博士论文中进行了单细胞生物群体的计算机仿真研究，对以后函数优化的研究颇有启发，并发展了自适应交换策略。Cavicohio1970年研究了基于遗传算法的子程序选择和模式识别问题，在模式识别问题上，采用整数编码，检索空间很大，他提出了以预选择策略保证群体多样性，对遗传算法参数进行中心控制的方法。同年，Weinberg研究了生物体的计算机仿真，他的贡献在于提出运用多层遗传算法来进行遗传算法的参数自优化。1968至1971年，Holland提出了重要的模式理论，建议采用二进制编码。与前面几位博士不同，Holland首次采用二进制编码来研究函数优化问题，并指出了运用Gray码的一些优点，他研究了从生物系统引申出的各种不同的选择和配对策略。1972年，Frantz的博士论文中研究了许多新的问题，如基因非线性(异位显性)现象，基因迁移操作及多点交换操作等，由于没有设计出诸如GA－eception之类合适的非线性优化问题，实验结果并不具备说服力。这一年，Holland的模式理论也渐趋成熟，但在编码策略上出现了至今仍执争论的二派，一派根据模式定理建议用尽量少的符号编码，一派以数值优化计算的方便和精度为准采用一个基因一个参数的方法，并把相应的基因操作改造成适合实数操作的形式，Bosworth，Zoo和Zeigler是后者的开创者。1975年竖立了遗传算法发展史上的两块里遗传算法及其应用2程碑，一是Holland出版了经典著作《AdaptationinNatureandArtificialSystem》，该书是作者十几年间许多思想及其实现的结晶，详细阐述了遗传算法的理论，并为其奠定了数学基础，发展了一整套模拟生物自适应系统的理论；二是DeJong完成了具有指导意义的博士论文《AnAnalysisoftheBehaviorofaClassofGeneticAdaptiveSystem》，他深入领会了模式定理并做了大量严格的计算实验，给出了明确的结论，他还建立了著名的DeJong五函数测试平台，定义了性能评价标准，并以函数优化为例，对遗传算法的六种方案的性能及机理进行了详细实验和分析，他的工作成为后继者的范例并为以后的广泛应用奠定了坚实的基础。为克服DeJong的轮盘赌(随机)选择操作中的随机误差，Brindle于1981年在她的博士论文中研究了六种复制策略。进入八十年代，随着以符号系统模仿人类智能的传统人工智能暂时陷入困境，神经网络、机器学习和遗传算法等从生物系统底层模拟智能的研究重新复活并获得繁荣。Goldberg在遗传算法研究中起着继往开来的作用，他在1983年的博士论文中第一次把遗传算法用于实际的工程系统—煤气管道的优化，从此，遗传算法的理论研究更为深入和丰富，应用研究更为广泛和完善，自1985年起，遗传算法及其应用国际会议每二年召开一次，有关人工智能的会议和刊物上大多有遗传算法的专题，Goldberg的课本，及其他学者的专著的出版有力地推动了遗传算法的传播。进入九十年代，以不确定性、非线性、时间不可逆为内涵，以复杂问题为对象的科学新范式得到学术界普遍认同，如广义进化综合理论。由于遗传算法能有效地求解属于NPC类型的组合优化问题及非线性多模型、多目标的函数优化问题，从而得到了多学科的广泛重视，一些学者也认识到求解复杂问题最优解是不现实的，故而寻求满意解，而遗传算法是最佳工具之一，生物进化的历史比任何数学证明都强有力，问题是遗传算法在吸收遗传学、进化论及分子生物学最新成果和在实验得到证明和证伪的同时本身也在进化。目前，遗传算法引起包括数学、物理、化学、生物学、计算机科学等领域的科学家的极大兴趣。遗传算法的研究领域和内容十分的广泛，如遗传算法的设计与分析，遗传算法的理论基础及其在各个领域的应用。随着理论的深入研究和应用领域的不断拓展，遗传算法必将取得更大的发展。遗传算法及其应用31.2遗传算法的生物学基础1.2.1生物的进化过程19世纪50年代。英国生物学家达尔文根据他对世界各地生物的考察结果和人工选择实验。提出了“生物进化论”。1859年达尔文发表了《物种起源》巨著。提出了以自然选择为基础的生物进化论学说。根据达尔文的进化论，生物进化的发展来源于三种动力：遗传、变异和选择。遗传就是子代总是保持和亲代的相似性，遗传性是一切生物所共有的特征。正是这种遗传性，使得生物能够把它的特性、性状传给后代，并在后代中保持相似。现代遗传学研究表明，生物都具有遗传性。遗传学的建立和发展有力地推动和促进了进化论，变异是子代和亲代有某些不相似的现象。即子代永远不会和亲代完全一样，变异是一切事物所具有的共同特征，是生物个体之间相互区别的基础。引起变异的原因主要是生活条件的影响，器官使用的不同及杂交。变异性为生物的进化发展创造了条件，选择决定了生物进化的方向，所谓选择是指生物具有保留和淘汰的特性，选择分为人工选择和自然选择。人工选择是在人为环境下把对人有利的生物保留下，把对人不利的个体淘汰掉；自然选择就是指生物在自然界的生存环境中适者生存，世界上所有形形色色的生物都是在自然选择的影响下、在悠久的岁月中形成的。自然选择的过程是通过生存斗争的过程来实现生存斗争的结果，优胜劣汰。这样就保证了生物去适应环境，通过不断地自然选择，那些有利于生存的变异就遗传下去，日积月累越来越大，逐步产生了新的物种。生物的各项生命活动都有他的物质基础。生物的遗传和变异也不例外。遗传物质的主要载体为染色体。研究表明，染色体主要有脱氧核糖核酸和蛋白质，其中脱氧核糖核酸在染色体中含量稳定，结构相对稳定，能够自我复制，前后保持一定的连续性，能够产生可遗传的变异。因此它是主要的遗传物质。生物的性状遗传主要是通过染色体传递给后代。因此，基因是控制生物性状的遗传物质的功能和结构单位。生物变异与遗传一样，也是很复杂的，由遗传物质引起的变异称为遗传变异。它有三种来源：基因重组、基因变异和基因突变。基因重组是控制不同性状的基因的重新组合；基因变异是指基因内部的化学变化；基因突变的产生是在一定外界环境条件和生物内部因素的作用下，基因的分子结构发生改变的结果。每种生物染色体无论结构和数目都是相对恒定的。但在遗传算法及其应用4自然条件和人为条件的影响下染色体结构和数目