发布时间：2015-01-24 来源：人大经济论坛

通信工程专业论文 1绪论1 1.1课题背景1 1.2课题研究意义2 1.3国内外研究现状3 1.4论文内容5 2遗传算法简介6 2.1遗传算法基本概念6 2.2遗传算法基本原理7 2.3遗传算法的步骤8 3遗传算法基本理论11 3.1模式定理11 3.2积木块假设与欺骗问题12 3.3收敛性分析13 4旅行商问题概述14 4.1旅行商问题的定义和数学模型14 4.1.1定义14 4.1.2数学模型14 4.2旅行商问题的计算复杂性15 4.3研究旅行商问题的意义16 5遗传算法在巡回旅行商问题中的应用18 5.1旅行商问题的建模18 5.1.1编码18 5.1.2适应度函数18 5.2遗传算法中三个算子的设计19 5.2.1选择算子的设计20 5.2.2交叉算子的设计21 5.2.3变异算子的设计25 5.3遗传算法求解旅行商问题的步骤27 5.4测试结果27 6结束语29 致 谢30 参考文献:31 摘要 遗传算法（Genetic algorithms, GAs）是借鉴生物界自然选择和重组机制的随机的搜索算法。由于它简单易行、鲁棒性强，应用范围极为广泛，并且已在众多领域得到了实际应用，引起了广大学者和工程人员的关注。Traveling Salesman Problem（TSP）问题是一个典型NP难题，是衡量近似算法效率的主要标准，因此设计TSP问题的近似算法具有非常重要的意义。本文讨论遗传算法及其对于TSP问题的解决方法。 论文首先介绍了遗传算法的基本概念、原理、意义及发展现状。通过对遗传算法基本理论的学习和研究，提出了解决TSP问题的算法，并详细给出了算法中的编码方案、适应度函数、选择算子、交叉算子、变异算子。最后用C++语言设计并实现了该算法，结果表明该算法可以在较短的时间内得到TSP问题的近似最优解。 关键词：遗传算法；TSP问题；适应度函数；交叉；变异 Research and Application of Genetic Algorithms Abstract Genetic 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;