遗传算法毕业论文.doc

遗遗传算法毕业论文【摘要】遗传算法(GeneticAlgorithm,GA)是近年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想基于Darwin的进化论和Mendel的遗传学。遗传算法的广泛应用和发展潜能使很多学者深入研究遗传算法，并出版了很多关于它的书籍。TSP问题是古老的经典的问题，有关的研究有几百年的时间。TSP旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。论文首先介绍了遗传算法的基本原理、遗传算法的特点,遗传算法的发展方向和它的主要应用领域；接着针对TSP问题论述了遗传算法在编码表示和遗传算子（包括选择算子，交叉算子，变异算子这三种算子）等方面的应用情况，简单讨论几种编码方法，并改进了交叉算子。接着对改进的遗传算法做了实验，得出结果并分析了数据。最后我做了一个TSP简单应用。【关键词】遗传算法；TSP；遗传算子；编码毕业论文题目2【Abstract】GeneticAlgorithm(GeneticAlgorithm,GA)isanewrandomsearchandoptimizationalgorithm，developrapidlyinrecentyears,thebasicideaofthetheoryisDarwinandMendelsgenetics.Extensiveuseofgeneticalgorithmsanddevelopmentpotentialmakemanyscholarsin-depthstudyofgeneticalgorithms,andpublishedmanybooksaboutit.TSPproblemistheoldclassicquestionandaboutitsresearchhavehundredsofyearsoftime."TSP"TravelingSalesmanProblemisakindofatypicalNP-completeproblem,geneticalgorithmstosolveNPproblemsisamoredesirablemethod.Paperfirstintroducesthecharacteristics,developmentdirectionandmajorapplicationsofbasicgeneticalgorithms,andthendiscussedfortheTSPproblemofgeneticalgorithmsandgeneticcodingthatoperator(includingtheselectionoperator,crossoveroperator,mutationoperatorofthesethreeoperator)andotheraspectsoftheapplication,makeabriefdiscussionaboutseveralcodingmethods,andimprovedcrossoveroperator.Thenuseimprovedgeneticalgorithmtodotheexperiment,gettheoutcomeandanalyzethedata.Finally,IdoasimplesuingaboutTSP.【Keywords】geneticalgorithm；TSP；geneticoperator；coding遗传算法毕业论文3目录第一章遗传算法理论.41.1遗传算法的起源.41.2遗传算法概念.61.3遗传算法的原理.71.3.1遗传算法在应用中关键的问题.91.3.2遗传算法基本操作.91.4遗传算法的特点.101.5遗传算法几个主要应用领域.111.6遗传算法发展方向.13第二章遗传算法的基本原理和实现技术.152.1模式定理.152.2编码技术.162.2.1群体设定.162.2.2适应度函数.172.2.3遗传操作.172.3混合遗传算法.19第三章TSP问题描述与实算.203.1旅行商问题描述.203.2编码选择.213.2.1群体设定.213.2.2适应函数度.213.2.3选择算子的设计.213.2.4交叉算子的设计.223.2.5变异算子的设计.243.3对TSP遗传算法的改进：.253.3.1TSP遗传算法参数实验.253.3.2改进的交叉算子：产生多个个体的部分映射与顺序交叉结合的算子.293.4TSP算法实例.383.5附录（求51个城市最短距离算法）.42总结.54参考文献.55致谢.56毕业论文题目4第一章遗传算法理论1.1遗传算法的起源当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。1967年，Holland的学生在博士论文中首次提出“遗传算法”（GeneticAlgorithms）一词。此后，Holland指导学生完成了多篇有关遗传算法研究的论文。1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化。1975年Holland出版了他的著名专著自然系统和人工系统的自适应（AdaptationinNaturalandArtificialSystems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schematheory）。该理论首次确认了结构重组遗传操作对于获得并行性的重要性。同年，K.A.DeJong完成了他的博士论文一类遗传自适应系统的行为分析（AnAnalysisoftheBehaviorofaClassofGeneticAdaptiveSystem）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管DeJong和Hollstien一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generationgap）等新的遗传操作技术。可以认为，DeJong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（InternationalConferenceonGeneticAlgorithms，ICGA），并且成立国际遗传算法学会（InternationalSocietyofGeneticAlgorithms，ISGA），以后每两年举行一次。1989年，Holland的学生D.E.Goldberg出版了专著搜索、优化和机器学习中的遗传算法（GeneticAlgorithmsinSearch,Optimization,andMachineLearning）。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。同年，美国斯坦福大学的Koza基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计(geneticprogramming,GP)方法，成遗传算法毕业论文5功地解决了许多问题。在欧洲，从1990年开始每隔一年举办一次ParallelProblemSolvingfromNature学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有FoundationsofGeneticAlgorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。1991年，L.Davis编辑出版了遗传算法手册（HandbookofGeneticAlgorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。1992年，Koza发表了他的专著遗传程序设计:基于自然选择法则的计算机程序设计”。1994年，他又出版了遗传程序设计，第二册:可重用程序的自动发现深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在ArtificialIntelligence、MachineLearning、Informationscience、ParallelComputing、GeneticProgrammingandEvoluableMachines、IEEETransactionsonNeuralNetworks、IEEETransactionsonSignalProcessing等杂志上发表。1993年，MIT出版社创刊了新杂志EvolutionaryComputation。1997年，IEEE又创刊了TransactionsonEvolutionaryComputation。AdvancedComputationalIntelligence杂志即将发刊，由模糊集合创始人L.A.Zadeh教授为名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。遗传算法(GeneticAlgorithm,GA)是近三十年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想是基于Darwin的进化论和Mendel的遗传学说。该算法由密执安大学教授Holland及其学生于1975年创建。此后，遗传算法的研究引起了国内外学者的关注。自1985年以来.国际上已召开了多次遗传算法的学术会议和研讨会.国际遗传算法学会组织召开的ICGA(InternationalConferenceonGeneticAlgorithms)会议和FOGA(WorkshoponFoundationofGeneticAlgorithms)会议。为研究和应用遗传算法提供了国际交流的机会。作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传程序设计是借鉴生物界的自然选择和遗传机制，在遗传算法的基础上发展起来的搜索算法，它已成为进化计算的一个新分支。在标准的遗传算法中，由定长字符串(问题的可行解)组成的群体借助于复制、交叉、变异等遗传操作不断进化找到问题的最优解或次优解。遗传程序设计运用遗传算法的思想，常采用树的结构来表示计算机程序，从而解决问题。对于许多问题，包括人工智能和机器学习上的问题都可看作是需要发现一个计算机程序，即对特定输入产生特定输出的程序，形式化为程序归纳，那么遗传程序设计提供了实现程序归纳的方法。毕业论文题目6把遗传算法和计算机程序结合起来的思想出现在遗传算法中，Holland把产生式语言和遗传算法结合起来实现分类系统，还有一些遗传算法应用领域的研究者将类似于遗传算法的遗传操作施加于树结构的程序上。近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回归和图像处理等，作为一种新技术，它已经与遗传算法并驾齐驱。1996年，举行了第1次遗传程序设计国际会议，该领域己引起越来越多的相关学者们的兴趣。现在的基因表达式算法应该算是遗传算法的继承者1.2遗传算法概念遗传算法和字面意思一样，原理是关于遗传的算法。遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。遗传算法的概念最早是由BagleyJ.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的不是对遗传算法系统研究而是说明自然和人工系统的自适应过程。遗传算法简称GA(GeneticAlgorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保留下来。Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。19遗传算法毕业论文7这些概念如下：(1)串(String)它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。(2)群体(Population)个体的集合称为群体，“串”是群体的元素（3）群体大小(PopulationSize)在群体中个体的数量称为群体的大小。（4）基因(Gene)基因是串中的元素，基因用于表示个体的特征。例如有一个串S1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因。（5）基因位置(GenePosition)一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串从左向右计算，例如在串S1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。（6）基因特征值(GeneFeature)在用“二进制串”表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。（7）串结构空间（SS）在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。（8）参数空间SP这是“串空间”在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。（9）适应度(Fitness)表示某一个体对于环境的适应程度。1.3遗传算法的原理遗传算法GA把“问题的解”表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，“一代一代”地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。