遗传算法毕业论文遗遗传算法毕业论文【摘要】遗传算法(Genetic Algorithm, GA)是近年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想基于Darwin的进化论和Mendel的遗传学。遗传算法的广泛应用和发展潜能使很多学者深入研究遗传算法，并出版了很多关于它的书籍。TSP问题是古老的经典的问题，有关的研究有几百年的时间。TSP旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。 论文首先介绍了遗传算法的基本原理、遗传算法的特点,遗传算法的发展方向和它的主要应用领域；接着针对TSP 问题论述了遗传算法在编码表示和遗传算子（包括选择算子，交叉算子，变异算子这三种算子）等方面的应用情况，简单讨论几种编码方法，并改进了交叉算子。接着对改进的遗传算法做了实验，得出结果并分析了数据。最后我做了一个TSP简单应用。【关键词】遗传算法；TSP；遗传算子 ；编码【Abstract】Genetic Algorithm (Genetic Algorithm, GA) is a new random search and optimization algorithm ，develop rapidly in recent years, the basic idea of the theory is Darwin and Mendels genetics. Extensive use of genetic algorithms and development potential make many scholars in-depth study of genetic algorithms, and published many books about it.TSP problem is the old classic question and about its research have hundreds of years of time. TSP Traveling Salesman Problem is a kind of a typical NP-complete problem, genetic algorithms to solve NP problems is a more desirable method.Paper first introduces the characteristics, development direction and major applications of basic genetic algorithms, and then discussed for the TSP problem of genetic algorithms and genetic coding that operator (including the selection operator, crossover operator, mutation operator of these three operator) and other aspects of the application, make a brief discussion about several coding methods, and improved crossover operator. Then use improved genetic algorithm to do the experiment, get the outcome and analyze the data. Finally, I do a simple suing about TSP.【Keywords】genetic algorithm; TSP; genetic operator; coding目录第一章 遗传算法理论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.1 TSP遗传算法参数实验253.3.2 改进的交叉算子：产生多个个体的部分映射与顺序交叉结合的算子.293.4 TSP算法实例383.5 附录（求51个城市最短距离算法）42总结54参考文献55致谢56第一章 遗传算法理论1.1遗传算法的起源当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。1967年，Holland的学生在博士论文中首次提出“遗传算法”（Genetic Algorithms）一词。此后，Holland指导学生完成了多篇有关遗传算法研究的论文。1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化。1975年Holland出版了他的著名专著自然系统和人工系统的自适应（Adaptation in Natural and Artificial Systems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schema theory）。该理论首次确认了结构重组遗传操作对于获得并行性的重要性。同年，K.A.De Jong完成了他的博士论文一类遗传自适应系统的行为分析（An Analysis of the Behavior of a Class of Genetic Adaptive System）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管De Jong和Hollstien 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术。可以认为，De Jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（International Conference on Genetic Algorithms ，ICGA），并且成立国际遗传算法学会（International Society of Genetic Algorithms ，ISGA），以后每两年举行一次。1989年，Holland的学生D.E.Goldberg出版了专著搜索、优化和机器学习中的遗传算法（Genetic Algorithms in Search , Optimization, and Machine Learning）。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。同年，美国斯坦福大学的Koza基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计( genetic programming, GP)方法，成功地解决了许多问题。 在欧洲，从1990年开始每隔一年举办一次Parallel Problem Solving from Nature 学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有Foundations of Genetic Algorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。1991年，L.Davis编辑出版了遗传算法手册（Handbook of Genetic Algorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。 1992年，Koza发表了他的专著遗传程序设计:基于自然选择法则的计算机程序设计”。1994年，他又出版了遗传程序设计，第二册:可重用程序的自动发现深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在Artificial Intelligence、Machine Learning、Information science、Parallel Computing、Genetic Programming and Evoluable Machines、IEEE Transactions on Neural Networks、IEEE Transactions on Signal Processing等杂志上发表。1993年，MIT出版社创刊了新杂志Evolutionary Computation。1997年，IEEE又创刊了Transactions on Evolutionary Computation。Advanced Computational Intelligence杂志即将发刊，由模糊集合创始人L.A.Zadeh教授为名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。遗传算法(Genetic Algorithm, GA)是近三十年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想是基于Darwin的进化论和Mendel的遗传学说。该算法由密执安大学教授Holland及其学生于1975年创建。此后，遗传算法的研究引起了国内外学者的关注。自1985年以来.国际上已召开了多次遗传算法的学术会议和研讨会.国际遗传算法学会组织召开的ICGA( International Conference on Genetic Algorithms)会议和FOGA( Workshop on Foundation of Genetic Algorithms)会议。为研究和应用遗传算法提供了国际交流的机会。作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传程序设计是借鉴生物界的自然选择和遗传机制，在遗传算法的基础上发展起来的搜索算法，它已成为进化计算的一个新分支。在标准的遗传算法中，由定长字符串(问题的可行解)组成的群体借助于复制、交叉、变异等遗传操作不断进化找到问题的最优解或次优解。遗传程序设计运用遗传算法的思想，常采用树的结构来表示计算机程序，从而解决问题。对于许多问题，包括人工智能和机器学习上的问题都可看作是需要发现一个计算机程序，即对特定输入产生特定输出的程序，形式化为程序归纳，那么遗传程序设计提供了实现程序归纳的方法。把遗传算法和计算