遗传算法研究与应用

论文编号:TX259  论文字数:15114,页数:37 有开题报告，任务书

摘要
 遗传算法（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;

  目     录
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