遗传算法研究与应用.rar

遗传算法研究与应用
1.5万字 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


参考文献
[4] Hollstien R B. Aritifical Genetic Adaptation in Computer Control Systems[D]. AnnArbor. University of Michigan
[5] 王小平.遗传算法--理论.应用与软件实现[M],西安:西安交通大学出版社
[6] Holland J H. Adaptation in Natural and Artificial Systems[M]. 2nd edition. Ann Arbor. The University of Michigan
[7] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社
[8] 陈国良,王煦法,庄镇泉等.遗传算法及其应用[M].北京:人民邮电出版社
[9]殷人昆,陶永雷等.数据结构(用面向对象方法与c＋＋描述) .北京:清华大学出版社
[10] 孙艳丰,王众托.自然数编码遗传算法的最优群体规模.信息与控制[J]