遗传算法研究与应用(含开题+任务书)

遗传算法研究与应用

摘要

遗传算法（Genetic algorithms, GAs）是借鉴生物界自然选择和重组机制的随机的搜索算法。由于它简单易行、鲁棒性强，应用范围极为广泛，并且已在众多领域得到了实际应用，引起了广大学者和工程人员的关注。Traveling Salesman Problem（TSP）问题是一个典型NP难题，是衡量近似算法效率的主要标准，因此设计TSP问题的近似算法具有非常重要的意义。本文讨论遗传算法及其对于TSP问题的解决方法。

论文首先介绍了遗传算法的基本概念、原理、意义及发展现状。通过对遗传算法基本理论的学习和研究，提出了解决TSP问题的算法，并详细给出了算法中的编码方案、适应度函数、选择算子、交叉算子、变异算子。最后用C++语言设计并实现了该算法，结果表明该算法可以在较短的时间内得到TSP问题的近似最优解。

关键词：遗传算法；TSP问题；适应度函数；交叉；变异

目     录

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