1、 摘 要 I 摘要摘要 旅行商问题（Travelling Salesman Problem，简称 TSP）是一个典型的组合优 化问题，并且是一个 NP 难题，其可能的路径总数与城市数目 n 是成指数型增长 的，所以一般很难精确地求出其最优解，因而寻找出有效的近似求解算法就具有 重要的意义。 遗传算法（GA）是求解旅行商问题（TSP）的常用方法之一。针对中国旅 行商问题（CTSP） ，本文利用遗传算法的全局搜索能力进行组合优化问题求解， 设计一种大比例的优秀个体保护的大变异遗传算法，并使用 MATLAB 语言进行 了实际的编程求解， 编程中的各个模块分别实现了选择、 交叉、 变异等关键环节。 用
2、编制的程序快速求解出了满足的结果， 用本文设计的遗传算法的思路和编程程 序是正确的。用该策略迅速找到了 CTSP 最优解，该路径长度为 15378km，比目 前已知 CTSP 解更优。对遗传算法迅速求解 TSP 最优解提供了可行解决方案。 关键词：遗传算法；CTSP；最短路径；MATLAB 摘 要 II Abstract The traveling salesman problem (TSP) is a well-known NP complete problem, Its increased by exponential n. So, it is hard to find a precisi
3、on result, and it is very important to search for the near result. The genetic algorithm (GA) is one of the ideal methods in solving it. For CTSP， According to genetic algorithms global searching proterty, a kind of big probability variations genetic algorithm is put forward, which copies big propor
4、tion of fittest. In MATLAB, the typical Chinese traveling salesman problem is computed and the result shows the thought and program is correct. The best path for CTSP is found quickly through the algorithm. The best path 15378km is get, the result is the best so far. Key words: The Genetic Algorithm (GA); Chinese Traveling Salesman Problem (CTSP); The Shortest Path; MATLAB 目 录 III 目目 录录 摘要I Abstract . II 绪论. 1 1 CTSP 数学模型及常用算法 2 11 TSP 的数学模型. 2 1
