遗传算法完整毕业设计.doc

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：1.11M 资料格式：doc 举报版权申诉

第1页 / 共63页

第2页 / 共63页

第3页 / 共63页

第4页 / 共63页

第5页 / 共63页

第6页 / 共63页

第7页 / 共63页

第8页 / 共63页

文本预览

【摘要】遗传算法(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 Mendel's 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 目录第一章遗传算法理论 4 1.1 遗传算法的起源 4 1.2 遗传算法概念 6 1.3 遗传算法的原理 7 1.3.1 遗传算法在应用中关键的问题 9 1.3.2 遗传算法基本操作 9 2

大理学院本科毕业论文 1.4 遗传算法的特点 10 1.5 遗传算法几个主要应用领域 11 1.6 遗传算法发展方向 13 第二章．遗传算法的基本原理和实现技术 15 2.1 模式定理 2.2 编码技术 15 16 2.2.1 群体设定 16 2.2.2 适应度函数 17 2.2.3 遗传操作 17 2.3 混合遗传算法 19 第三章 TSP 问题描述与实算 20 3.1 旅行商问题描述 20 3.2 编码选择 21 3.2.1 群体设定 21 3.2.2 适应函数度 21 3.2.3 选择算子的设计 3.2.4 交叉算子的设计 21 22 3.2.5 变异算子的设计 24 3.3 对 TSP 遗传算法的改进： 25 3.3.1 TSP 遗传算法参数实验 25 3.3.2 改进的交叉算子：产生多个个体的部分映射与顺序交叉结合的算子. 29 3.4 TSP 算法实例 35 3.5 附录（求 51 个城市最短距离算法） 39 总结 51 参考文献 52 致谢 53 3

毕业论文题目第一章遗传算法理论 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 4

大理学院本科毕业论文 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)会议。为研究和应用遗传算法提供了国际交流的机会。作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传程序设计是借鉴生物界的自然选择和遗传机制，在遗传算法的基础上发展起来的搜索算法，它已成为进化计算的一个新分支。在标准的遗传算法中，由定长字符串(问题的可行解)组成的群体借助于复制、交叉、变异等遗传操作不断进化找到问题的最优解或次优解。遗传程序设计运用遗传算法的思想，常采用树的结构来表示计算机程序，从而解决问题。对于许多问题，包括人工智能和机器学习上的问题都可看作是需要发现一个计算机程序，即对特定输入产生特定输出的程序，形式化为程序归纳，那么遗传程序设计提供了实现程序归纳的方法。把遗传算法和计算机程序结合起来的思想出现在遗传算法中，Holland 把产生式语言和遗传算法结合起来实现分类系统，还有一些遗传算法应用领域的研究者将类似于遗传算法的遗传操作施加于树结构的程序上。 5

毕业论文题目近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回归和图像处理等，作为一种新技术，它已经与遗传算法并驾齐驱。 1996 年，举行了第 1 次遗传程序设计国际会议，该领域己引起越来越多的相关学者们的兴趣。现在的基因表达式算法应该算是遗传算法的继承者 1.2 遗传算法概念遗传算法和字面意思一样，原理是关于遗传的算法。遗传算法的基本思想是基于 Darwin 进化论和 Mendel 的遗传学说的。生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。遗传算法的概念最早是由 Bagley J.D 在 1967 年提出的；而开始遗传算法的理论和方法的系统性研究的是 1975 年，这一开创性工作是由 Michigan 大学的 J.H.Holland 所实行。当时，其主要目的不是对遗传算法系统研究而是说明自然和人工系统的自适应过程。遗传算法简称 GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。遗传算法的基本思想是基于 Darwin 进化论和 Mendel 的遗传学说的。 Darwin 进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保留下来。 Mendel 遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。[19] 这些概念如下： (1)串(String) 它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。 (2)群体(Population) 6

大理学院本科毕业论文个体的集合称为群体，“串”是群体的元素（3）群体大小(Population Size) 在群体中个体的数量称为群体的大小。（4）基因(Gene) 基因是串中的元素，基因用于表示个体的特征。例如有一个串 S＝1011，则其中的 1，0，1，1 这 4 个元素分别称为基因。它们的值称为等位基因。（5）基因位置(Gene Position) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串从左向右计算，例如在串 S＝ 1101 中，0 的基因位置是 3。基因位置对应于遗传学中的地点(Locus)。（6）基因特征值(Gene Feature) 在用“二进制串”表示整数时，基因的特征值与二进制数的权一致；例如在串 S=1011 中，基因位置 3 中的 1，它的基因特征值为 2；基因位置 1 中的 1，它的基因特征值为 8。（7）串结构空间（SS）在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。（8）参数空间 SP 这是“串空间”在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。（9）适应度(Fitness) 表示某一个体对于环境的适应程度。 1.3 遗传算法的原理遗传算法 GA 把“问题的解”表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，“一代一代”地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。在遗传算法里，优化问题的解被称为个体，它表示为一个参数列表，叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串，不过也有其他的表示方法适用，这一过程称为编码。一开始，算法随机生成一定数量的个体，有时候操作者也可以对这个随机产生过程进行干预，播下已经部分优化的种子。在每一代中，每一个个体都被评价，并通过计算适应度函数得到一个适应度数值。种群中的“个体”被按照适应度排序，适应度高的在前面。这里的“高”是相对于初始的种群的“低适应 7

毕业论文题目度”来说的。下一步是产生下一代个体并组成种群。这个过程是通过选择和交叉完成的，其中繁殖包括(crossover) 和突变(mutation)。选择则是根据新个体的适应度进行的，适应度越高，被选择的机会越高，而适应度低的，被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。之后，被选择的个体进入交配过程。一般的遗传算法都有一个交配概率，范围一般是 0.01-1，这个交配概率反映两个被选中的个体进行交配的概率。例如，交配概率为 0.8，则 80%的“夫妻”会生育后代。每两个个体通过交配产生两个新个体，代替原来的“老”个体，而没交配的个体则保持不变。交配父母的染色体相互交换，从而产生两个新的染色体，第一个个体前半段是父亲的染色体，后半段是母亲的，第二个个体则正好相反。不过这里的半段并不是真正的一半，这个位置叫做交配点，也是随机产生的，可以是染色体的任意位置。再下一步是突变，通过突变产生新的“子”个体。一般遗传算法都有一个固定的突变常数，通常是 0.1 或者更小，这代表变异发生的概率。根据这个概率，新个体的染色体随机的突变，通常就是改变染色体的一个字节（0 变到 1，或者 1 变到 0）。经过这一系列的过程（选择、交配和突变），产生的新一代个体不同于初始的一代，并“一代一代”向增加整体适应度的方向发展，因为最好的个体总是更多的被选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：每个“个体”被评价，计算出适应度，两个个体交配，然后突变，产生第三代。周而复始，直到终止条件满足为止。遗传算法的基础理论是摸式定理。它的有关内容如下： (1)摸式(Schema)概念[1] 一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是 0 或 1。例如：H=1 x x 0 x x 是一个模式。 (2)摸式的“阶”和“长度” 摸式中 0 和 1 的个数称为模式的阶，并用 0(H)表示。模式中第 1 个数字串和最后一个数字串间的距离称为模式的长度，并用δ(H)表示。对于模式 H＝1xx0xx，有 0(H)＝2，δ(H)＝4。 (3)Holland 摸式定理低阶，短长度的模式在群体遗传过程中将会按指数规律增加。当群体的大小为 n 时，每代处理的模式数目为 0(n3)。 1.3.1 遗传算法在应用中关键的问题（1）串的编码方式这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体” 串。串长度及编码形式对算法收敛影响极大 8

分享到：

赞收藏

资料库

遗传算法完整毕业设计.doc

相关推荐

开发技术

热门标签

最新资料