
遗传算法研究与应用论文.doc
38页毕业设计(论文)设计论文题目: 遗传算法研究与应用 学生姓名:学生学号:专业班级:学院名称:指导老师:学院院长:5月 22 日 毕业设计(论文) 第 I 页 遗传算法研究与应用摘要遗传算法(Genetic algorithms, GAs)是借鉴生物界自然选择和重组机制的随机的搜索算法。
由于它简单易行、鲁棒性强,应用范围极为广泛,并且已在众多领域得到了实际应用,引起了广大学者和工程人员的关注Traveling Salesman Problem(TSP)问题是一个典型NP难题,是衡量近似算法效率的主要标准,因此设计TSP问题的近似算法具有非常重要的意义本文讨论遗传算法及其对于TSP问题的解决方法论文首先介绍了遗传算法的基本概念、原理、意义及发展现状通过对遗传算法基本理论的学习和研究,提出了解决TSP问题的算法,并详细给出了算法中的编码方案、适应度函数、选择算子、交叉算子、变异算子最后用C++语言设计并实现了该算法,结果表明该算法可以在较短的时间内得到TSP问题的近似最优解关键词:遗传算法;TSP问题;适应度函数;交叉;变异Research and Application of Genetic AlgorithmsAbstractGenetic algorithms (GAs) are optimization search algorithms based on the mechanics of artificial selection and genetic recombination operators. They are simple, robust and easy to implement. They have been used in many fields. For these reasons now they are the hot research field which has got many scholars’ attention. Traveling Salesman Problem (TSP) is a classic NP problem, which is the main standard of measuring the efficiency of approximative algorithms. So the solution of the problem has has very important significance. The paper discusses the basic genetic algorithms and their application.The essay first introduces the basic concepts, principle, procedure, significance and characteristics of genetic algorithms. By learning the basic theory of genetic algorithms one solution of TSP is given. The detailed coding scheme, fitness function, selection operator, cross operator and mutation operator of the solution are also given. Finally using C++ implement the solution. The result of the program show that the algorithm can get optimal solution of the problem quickly. Keywords: Genetic Algorithms(G A); Traveling Salesman Problem( TSP); fitness function; cross operator; mutation operator; 毕业设计(论文) 第 IV 页 目 录1 绪论 11.1 课题背景 11.2 课题研究意义 21.3 国内外研究现状 31.4 论文内容 52 遗传算法简介 62.1 遗传算法基本概念 62.2 遗传算法基本原理 72.3 遗传算法的步骤 83 遗传算法基本理论 113.1 模式定理 113.2 积木块假设与欺骗问题 123.3 收敛性分析 134 旅行商问题概述 144.1 旅行商问题的定义和数学模型 144.1.1 定义 144.1.2 数学模型 144.2 旅行商问题的计算复杂性 154.3 研究旅行商问题的意义 165 遗传算法在巡回旅行商问题中的应用 185.1 旅行商问题的建模 185.1.1 编码 185.1.2 适应度函数 185.2 遗传算法中三个算子的设计 195.2.1 选择算子的设计 205.2.2 交叉算子的设计 215.2.3 变异算子的设计 255.3 遗传算法求解旅行商问题的步骤 275.4 测试结果 276 结束语 29致 谢 30参考文献: 31 毕业设计(论文) 第 1 页 1 绪论1.1 课题背景遗传算法(Genetic Algorithm,GA),是一类以达尔文的自然进化论与遗传变异理论为基础的求解复杂全局优化问题的仿生型算法。
它借鉴生物界自然选择和自然遗传机制,以概率论为基础在解空间中进行随机化搜索,最终找到问题的最优解 毕业设计(论文) 第 32 页 遗传算法的兴起是在80年代末90年代初期,但是它的历史可以追溯到60年代初期。
早期的研究大多以对自然遗传系统的计算机模拟为主早期遗传算法的研究特点是侧重于对一些复杂的操作的研究其中像自动博弈、生物系统模拟、模式识别和函数优化等给人以深刻的印象,但总的说来,这是一个无明确目标的发展时期,缺乏带有指导性的理论和计算工具的开拓这种现象直到70年代中期由于Holland和DeJong的创造性研究成果的发表才得到改观1967年,Bagley在他的论文中首次提出了遗传算法 [1]这一术语,并讨论了遗传算法在自动博弈中的应用1970年,Cavicchio把遗传算法应用于模式识别中第一个把遗传算法应用于函数优化的是Hollstien,1971年他在论文《计算机控制系统中的人工遗传自适应方法》中阐述了遗传算法用于数字反馈控制的方法1975年在遗传算法研究的历史上是十分重要的一年,Holland出版了他的著名专著《自然系统和人工系统的适配》,该书系统的阐述了遗传算法的基本理论和方法,并提出了对遗传算法理论研究和发展极为重要的模式理论(schemata theory),该理论首次确认了结构重组遗传操作对于获得隐并行性的重。












