毕业设计-TSP简单应用.docVIP

【摘要】 遗传算法(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  目录 第一章 遗传算法理论 4 1.1遗传算法的起源 4 1.2遗传算法概念 6 1.3 遗传算法的原理 7 1.3.1遗传算法在应用中关键的问题 9 1.3.2遗传算法基本操作 9 1.4遗传算法的特点 10 1.5遗传算法几个主要应用领域 11 1.6遗传算法发展方向 13 第二章．遗传算法的基本原理和实现技术 15 2.1 模式定理 15 2.2 编码技术 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 选择算子的设计 21 3.2.4 交叉算子的设计 22 3.2.5变异算子的设计 24 3.3 对TSP遗传算法