巢湖学院计算机系2009届毕业设计（论文）
满足上述约束的解构成了一条Hamilton回路。通常一个组合优化问题的解可能不是唯一的，即可以同时存在着多个满足条件的赋值使得目标函数达到最大(或最小)值，但目标函数所达到的最大(或最小)值总是唯一的[6]。 4.3、TSP问题的数学分类:
4.3.1、从问题对应到图的类型，TSP可以分为两类:
(1) 任意两个城市间的距离都是对称的，它对应的是图论中的无向图； (2) 两个城市间的距离是非对称的，它对应的是图论中的有向图； 4.3.2、从问题本身的限制条件的强弱，主要有三类:
(1) 不做任何限制(但是一般都要求城市间的费用不为负数)，只是给出距离矩阵，求最小回路；
(2) 要求距离间要满足三角不等式;任意两个城市距离满足dij < dik + djk； (3) 定义在欧式平面上的TSP即Euclid TSP，它给出每个点在欧式平面上的坐标，而城市间的距离就是以它们的欧式距离来定义。
4.3.3、从问题的多项式可解性上分，TSP可以分为两类:
(1) 目前己经知道有多项式时间算法可解的，比如其距离矩阵满足特定的条件(Demidenko条件、Kalmanson条件、Supnick条件)等；
(2) 目前尚没有发现多项式时间算法可解的，而研究热点是如何寻找更多的多项式时间可解的情形。 4.3.4、其他
TSP的研究经过几十年的发展，还引申出其它扩展形式:多旅行商问题(Multi-Salesman Problem),多目标旅行商问题(Multi-Objective TSP) [7]。 4.3、TSP问题的应用和价值:
组合优化 (combinational optimization)是遗传算法最基本的也是最重要的研究和应用领域之一。所谓组合优化是指在离散的、有限的数学结构上，寻找一个满足给定约束条件并使其目标函数值达到最大或最小的解。一般来说，组合优化问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全问题，因此，精确地求解组合优化问题的全局最优解一般是不可能的。遗传算法作为一种新型的、模拟生物进化过程的随机化搜索、优化方法，近十几年来在组合优化领域得到了相当广泛的研究和应用，并已在解决诸多典型组合优化问题中显示了良好的性能和效果。
TSP问题是一个具有广泛的实用背景与重要的理论价值的组合优化难题。许多关于TSP的工作并不是由应用直接推动的，而是因为TSP为其它一般的各类算法提供了思想方法平台，而这些算法广泛地应用于各种离散优化问题。其次，TSP大量的直接应用给研
18
巢湖学院计算机系2009届毕业设计（论文）
究领域带来了生机，并引导了未来的工作。
虽然运输问题是TSP最自然的应用，但由于其模型的简单性，使得TSP在其他领域都有着有趣的应用。一个经典的例子是如何安排机器在一块电路板或其他物体上钻孔，其中需要钻的孔可以看成是各个城市，而旅行的费用就是钻头从一个孔移到下一个孔所花的时间。虽然钻孔的技术不断发展，但无论何时，只要钻机设备的移动时间在所有制造业的过程中占据显著的地位，TSP在减少费用上就扮演了一个非常重要的角色。 4.4、TSP问题的计算复杂性:
在考虑算法的复杂性时，我们往往指的是它的渐进时间复杂性。也就是R，我们关心的是算法随着输入规模的增长，其所需计算步数的增长速度。关于这个问题，计算机科学家们有一个共识:即当输入规模n表示的算法复杂性函数f(n)是以多项式为界的，算法才被认为是有效的。对于组合优化问题，我们关心的一般不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解。有的最优化问题可以有许多方法加以解决，大们需要根据求得最优解的效率对它们进行分类;也有的最优化问题可能根本难以解决，因而不存在有效地寻求最优解的方法。计算复杂性理论就是用于研究算法有效性和问题难度的手段。 4.4.1、复杂性分类:
从本质上讲，所有的计算问题又可以归结为判定问题，如果说:一个算法解决了某一判定问题，则算法输出“是”，否则输出“非”。而从输入到输出，算法所需要运行的步骤即为算法的时间复杂性。
很多优化问题，诸如旅行商问题、最小覆盖问题、多处理器任务调度问题背包问题等都被发现可以多项式约化为NP中最难的问题，即NP完全问题,普遍认为多项式时间的算法是“好的算法” 、“有效的算法”，而所有的NP问题目前都没有找到多项式时间的算法，未得到最优解，它们需要耗费时间复杂性函数的数量级往往是指数级甚至更高，所以单单依靠提高计算机的速度对问题的解决是非常有限的。 4.4.2、TSP问题的时间复杂度
著名的Cook定理告诉我们:可满足性问题是NP完全的。这一定理奠定了NP完全问题的体系基础。随后，许多被证明是NP完全的问题归根到底都是通过证明可满足问题可以在多项式时间内变换到该问题的方法来实现的。到目前为止，所有的NP完全问题还没有多项式时间算法[8]。
首先，TSP问题属于NP是显然的。又因为TSP问题可以间接的规约为可满足问题SAT，所以很显然TSP问题是一个NP完全问题。TSP搜索空间随着城市数n的增大而增大，所有的旅程路线组合数为(n-1)!/2。5个城市的情形对应120/10=12条路线，10个城市的情景对应3628800/20=181440条路线，100个城市的情景对应有4.666E155
19
巢湖学院计算机系2009届毕业设计（论文）
条路线。所以对于输入规模为n个城市的TSP找到最优解的时间复杂性函数的数量级是O (n!)，当n比较大时，耗费的时间已经是个天文数字。表4.1是在假定所用计算机每秒可以执行10亿次运算的前提下，对不同的时间复杂性函数所耗费时间的比较。
表4.1 不同的时间复杂性函数所耗费时间的比较
4.5、TSP问题的研究现状
目前针对TSP的算法主要分为两类:完全算法(精确计算)和不完全算法(近似算法)。
4.5.1、TSP问题的精确计算:
完全算法能保证完全搜索问题的整个解空间，从而找到最有巡回，但需要消耗O(n!)级的运算时间;有些完全算法虽然运用一些精巧的技术来减少搜索空间，但其本质上还是进行全局搜索，并没有降低运算时间复杂度。如线性规划，动态规划，分支限界。 4.5.2、TSP问题的近似计算:
不完全算法不能保证搜索问题的全部解空间，所以也不能保证能够找到最优解，甚至在某些实例上连解都得不到，但它们与完全算法相比却具有运算时间上的优势，即它们的运算时间复杂度都只是多项式，并不会随着输入规模的扩大产生“组合爆炸”;这类算法采用的是启发式策略来指导搜索，普遍比完全算法要快。对TSP不完全算法(近似算法)的研究是本文的重点。由于 精 确 式算法所能求解的问题规模非常有限，实际中使用的往往都是多项式阶的近似算法或启发式算法(heuristics)。几十年来，出现了很多近似优化算法，如近邻法、贪心算法(greedy algorithm)、最近插入法(nearest insertion)、最远插入法(farthest insertion)、双极小生成树法(double minimum spanning tree)等等。近年来，有很多解决该问题的较为有效的算法不断被推出，例如Hopfield神经网络方法、模拟退火方法以及遗传算法方法。
20
巢湖学院计算机系2009届毕业设计（论文）
第五章 利用遗传算法求解TSP问题
TSP问题的搜索空间非常庞大，在这庞大的搜索空间寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多的计算困难。借助遗传算法的搜索能力解决TSP问题，是很自然地想法。由于其全局搜索的特性，遗传算法在解决TSP问题中存在着其他算法没有的优势。接下来，就根据TSP问题，来讨论遗传算法的应用方法。 5.1、针对TSP问题的遗传算法设计： 5.1.1、一个假设
我们用正整数1~n来表示城市，n表示城市的个数。 5.1.2、输入文件的格式：
输入文件存储TSP问题的城市距离矩阵，本例中的TSP问题是的城市之间距离是对称的，文件中存储的是上三角阵，不包括对角线元素。 5.1.3、个体的编码方法：
用遗传算法解决TSP，一个周游方案很自然地表示为n个城市的排列，但基于二进制编码的交叉和变异操作不能适用，所以需要重新设计遗传操作，以适应这类遗传基因表示问题。目前为止针对TSP提出的编码方法主要有:顺序表示(ordinal representation );路径表示(path representation)。路径表示是表示旅程对应的基因编码的最自然、简单和符合逻辑的表示方法。然而，除非初始基因是固定的，否则这种编码方式不具备唯一性。例如:旅程(5-1-7-8-9-4-6-2-3)与(1-7-8-9-4-6-2-3-5)表示的是同一条路径[9]。 5.1.3、初始种群的产生
考虑到初始群体的多样性，在解空间中随机产生初始群体，并使其均匀分布于解空间。考虑到城市的数目大小，一般s取300-500。初始化方法：首先初始化染色体，每个个体的初始化，就是随机产生一个城市序列，将该个体加入种群当中，不应有重复，直到种群规模达到s。 5.1.4、种群进化
种群进化采用代进化的方案，将最优的个体直接传入下一代种群中。然后依照交叉，变异的概率对种群进行交叉，变异操作。在种群进化到新的一代时，要保证种群数目不变，
通常有两种类型的种群进化。一种是代进化(Generational evolution):即每一代中产生新的种群替代目前的种群。因为遗传算法固有的随机性而产生的弱收敛性，一种好的解决方法是将最优秀的个体直接传入下一代种群中。代进化存在的问题是在开始计算被产生的新的染色体的适应度时，整个的新种群必须已经产生。另一种进化是稳定状态的进化(Steady state evolution):将产生的某一染色体直接加入到目前的种
21
巢湖学院计算机系2009届毕业设计（论文）
群中。在稳定状态的进化中被替换掉的染色体是随机选出来的。 5.1.5、适应度函数的设计
在TSP问题中，用所产生的路径长度总和作为适应度函数，来衡量得到的解是否最优。
5.1.6、选择操作
从种群中选择适应度最高的个体，直接放入下一代种群之中即精英策略，对于选择用于交叉和变异的个体，则采用赌轮选择。 5.1.3、交叉操作
1987年Suh和Gucht发现遗传算法的收敛性在利用交叉操作的情况下要远远快于不利用交叉操作的情况。
路径表示(path representation)是表示旅程对应的基因编码的最自然、最简单的表示方法。例如，旅程5-1-7-8-9-4-6-2-3可以直接表示为(517894623)，基于路径表示的编码方法，要求一个个体(即一条旅程)的染色体编码中不允许有重复的基因码，也就是说要满足任一个城市必须而且只能访问一次的约束。这样，基本遗传算法的交叉操作生成的个体一般不能满足这一约束条件，如：9个城市的例子，
个体1：1-2-4-5-6-8-7-9-3 个体2：2-1-4-3-9-6-7-5-8
从第5个位置进行交叉得到的结果如下： 个体1：1-2-4-5-9-6-7-5-8 个体2：2-1-4-3-6-8-7-9-3
个体1，2显然对于TSP问题而言，没有意义。
基于以上原因1985年 ，Grefenstette等针对TSP提出了一种遗传基因编码方法。这种编码的思想是，对于一个给定的个体，即一个周游方案，对于一个城市，计算出它在该城市之后的所有城市中的顺序，把该顺序作为城市的编码，也可以理解为在该城市之后的城市中，小于该城市的城市数目,然后需要加一（城市本身）。为了更好的理解，给出下面的例子：
(1) 我们有9个城市，城市的原来编码为1~9，假设有一个个体（周游方案）为1-2-4-5-6-8-7-9-3则相应的编码过程如表5.1，按照Grefenstette编码则编码后的为1-1-2-2-2-3-2-2-1，得到的城市周游方案为：1-2-4-5-6-8-7-9-3
表5.1 Grefenstette编码过程 当前城市 1 2 4 5 6 当前城市之后的城市 2-4-5-6-8-7-9-3 4-5-6-8-7-9-3 5-6-8-7-9-3 6-8-7-9-3 8-7-9-3 22
排序（Grefenstette编码） 1 1 2 2 2