基于蚁群算法的中国旅行商问题研究(4)

菜单

本论文是基于理论与实际相结合的研究，并且利用MATLAB仿真加以实现。本论文分为五章，下列是对每章的基本内容做出的归纳：

第一章是绪论主要讲述旅行商问题的研究背景、发展以及研究的目的，对国内外研究进行了概述，以及确定了本论文所选择的研究方法。最后是介绍了论文的构成以及每章的研究内容。

第二章主要讲述旅行商问题的建模以及针对其的一些基本的优化方法，主要包括传统优化算法和人工智能优化算法。传统优化算法介绍了枚举法、蒙特卡洛算法，人工智能优化算法介绍了遗传算法和模拟退火算法。

第三章简要地描述蚁群的生物原理，主要讲述蚁群优化算法的基本原理及应用，以及改进后的蚁群优化算法。

第四章利用MATLAB仿真来解决旅行商问题。比较了枚举法跟最大最小蚁群算法解决旅行商问题，以及最大最小蚁群算法解决不同规模的旅行商之间的比较。

第五章讲述本次论文研究所学到的内容，以及对未来的展望。

2 解决旅行商问题的基本方法

2.1 中国旅行商问题的分析

中国旅行商问题归根到底就是求解,源)自(751+文=论]文]网[www.751com.cn一系列排列组合中最短距离的子序列问题。利用一个带权完全图来描述中国旅行商问题，其中是城市节点的集合，是所有边的集合。用表示城市到城市的距离，每个边都属于，和都属于。旅行商问题分为非对称式旅行商问题和对称式旅行商问题。在非对称旅行商问题中，最少存在一条边使得。本论文主要研究的是对称式旅行商问题，集合中所有的边必须要满足。用表示路径的距离，一个最优解对应一个排列，为节点的一个集合。定义为：

旅行商问题的描述虽然简单，但是运算却是相当复杂的[9]。一个城市规模为的旅行商问题的可行性路径全都列举，将会有条路径，如此以来，城市数目越多，计算复杂的指数将会越高。具体来说，例如现有20个城市，通过计算将会有条路径，而现如今计算机的工作速度为每秒条路径，也就是说解决一个旅行商问题至少得需要350年。下表2-1所示为不同规模的旅行商问题的计算量以及运行时间。