摘要论文的研究对象是旅行商问题（TSP），旅行商问题是一个易于描述却难以处理的组 合优化问题。其可能路径数随着城市数目的增长呈指数型增长。现实生活中，交通道路 的建设，网路节点的布置，甚至电路板的焊接都可以看作旅行商问题。因为其精确求解 起来相当困难，至今没有一个完美的计算方法。有效解决旅行商问题能够很大限度的节 约资源和最大程度上的工作提高效率。本论文首先介绍了旅行商问题的由来，以及旅行 商问题的历史发展和各种解决方法。其中遗传算法在解决此类组合优化问题中能够迅速 收敛，并且遗传算法的交叉变异操作又能够取得物种多样性的特点，能够有效的跳出局 部极值。因此本文采用遗传算法来解决旅行商问题。并通过不同规模的旅行商实验来确 定程序的可行性，最后通过多组实验数据比较，找出最优解决旅行商问题的遗传算子。84864

本论文最终比较了多组旅行商案例，并且比较了多组遗传算子的程序适应度，最终 确定了一组适应本程序的遗传算子。

毕业论文关键词：旅行商问题；遗传算法；组合优化；遗传算子；染色体

ABSTRACT Traveling salesman problem is the subject of the paper (TSP)。The traveling salesman problem is easy to describe but difficult to deal with a combination of optimization problems。 With the number of paths which may increase the number of cities increases exponentially。 Exact Solution is pretty difficult, so far there is no perfect method of calculation。 Effectively solve the traveling salesman problem can save a lot of resources and work limits  the maximum extent to improve efficiency。 This paper introduces the origin of the traveling salesman problem, as well as the historical development and various solutions Traveling Salesman Problem。 Wherein the genetic algorithm to solve this combinatorial optimization problems can quickly converge, and genetic algorithm crossover and mutation of species persity can be obtained, and can effectively jump out of local optima。 Therefore, this article uses genetic algorithms to solve the traveling salesman problem。 And to determine the feasibility of the program through a different scale traveling salesman experiments, and finally through multiple sets of experimental data, finds the optimal solution of the traveling salesman problem genetic operators。

This paper compares the final group traveling salesman more cases, and compare multiple sets of genetic operator of fitness program, we finalized a set of procedures to adapt this genetic operators。

Keywords: TSP; genetic algorithm; combinatorial optimization; genetic operators; chromosome

目录

第一章 绪论 1

1。1  研究背景 1

1。2  遗传算法发展历史 1

1。3  旅行商问题研究现状 2

1。4  本文的主要研究工作及内容 2

1。5  本文概述 2

第二章 预备知识 4

2。1  旅行商问题 4

2。1。1  旅行商问题的发展历史 4

2。1。2 TSP 问题的定义和分类 4

2。1。3 TSP 问题的应用和价值 5

2。1。4  前人研究方法 6

2。1。5 TSP 问题未来研究方向