一类多旅行商问题求解算法及分析
摘要旅行商问题（Traveling Salesman Problem, TSP）是一个组合优化的典型难题。多旅行商问题是旅行商问题拓展而来，具有非常高的理论研究价值和实际应用背景。本文 通过查阅资料，学习遗传算法，提出使用遗传算法对一类多旅行商问题，特别是旅行商 访问路径里程最大值进行最小化的过程进行了深入的研究。并提出了一种矩阵解码方法， 解决遗传算法中的解码步骤。本文通过对多旅行商问题加入特别的约束条件，使其能够 具有现实意义的问题，并通过 MATLAB 编程，进行多次数据分析、求解和仿真，并对结果 进行阐述和展示。除此之外，本文更进一步地对此类问题进行归纳。 77064
毕业论文关键词 多旅行商问题；遗传算法
毕 业 设 计 说 明 书 外 文 摘 要
Title A Kind of Traveling Salesman Problem Solving and Analysis of Algorithms
Abstract Traveling Salesman Problem (Traveling Salesman Problem, TSP) is a typical problem of combinatorial optimization。 Multiple traveling salesman problem, an extension of traveling salesman problem, has a very high theoretical research value and an actual application background。 Through referring to materials and learning genetic algorithm, this paper, by means of genetic algorithm, carried out a deep research on a series of multiple traveling salesman problems, especially on how to minimize the maximum access path mileage of traveling salesmen。 Besides, a matrix decoding method was proposed to solve the decoding procedures in the genetic algorithm。 By adding special constraint conditions into multiple traveling salesman problems, this paper was of more practical significance。 Moreover, it analyzed, solved and simulated data for many times by means of MATLAB before expounding and presenting the results。 In addition, this paper also further summarized problems of this type。
Keywords MTSP genetic algorithm
目 次
1 引言 。。。 1
1。1 多旅行商问题简介 。 2
1。2 遗传算法简介 。 4
1。3 本文主要内容及安排 。。。 6
2 多旅行商问题描述 。。。 7
3 多旅行商问题求解 。。。 8
3。1 求解策略 。 8
3。2 优化算法 。 8
3。3 基于遗传算法的多旅行商问题算法设计 。。。 8
3。3。1 个体编码 。。。 8
3。3。2 群体规模选择 。。。 9
3。3。3 适值函数 。。 10
3。3。4 选择 。。 10
3。3。5 交叉与变异 10
3。3。6 解码 。。 11
4。1 程序参数 14
4。2 仿真结果 14
4。3 结果分析 17
结 论 。。。 18
致 谢 。。。 19
参 考 文 献 。。 20
1 引言
旅行商问题（TSP）是组合优化领域中具有代表意义的问题。由于其描述简单但求解困 难，旅行商收到了大量的关注，并且已提出很多方法。TSP 问题在几十年的发展中，取得了 可观的成果。分支定界算法[1]、局域搜索算法[2]、模拟退火[3]、禁忌搜索[4]以及进化计算[5]等 一些高效算法被引 入用来解决 TSP 问题。通常可以将 TSP 问题分为对称模型