遗传算法及其在TSP问题中的应用

1、遗传算法及其在 TSP 问题中的应用摘要： 本文首先介绍了遗传算法的基本理论与方法，从应用的角度对遗传算法做了认真的分析和研究，总结了用遗传算法提出求解组合优化问题中的典型问题一一TSP问题的最优近似解的算法。 其次，本文在深入分析和研究了遗传算法基本理论与方法的基础 上，针对旅行商问题的具体问题，设计了基于TSP的遗传算法的选择、交叉和变异算子等遗传算子，提出了求解旅行商问题的一种遗传算法，并用 Matlab 语言编程实现其算 法，最后绘出算法的仿真结果，并对不同结果作出相应的分析。然后，本文还针对遗传算法求解TSP时存在的一些问题对该算法进行了适当的改进。如针对初始群体、遗传算子作出适当改

2、进， 或者将遗传算法与其他方法相结合， 以及在编程过程中对算法流程 的改进。本人在用计算机模拟遗传算法求解TSP问题时，首先分析了用 Matlab语言设计遗传算法程序的优越性，接着以遗传算法求解 TSP问题为例，深入讨论了各个遗传算子的程序实现， 并通过分析实验数据，得到各个遗传算子在搜索寻优过程中所起的作 用，最后指出了用 Matlab 语言编程同用其它高级程序语言编程的差异所在，以及运用 Matlab 编写遗传算法程序的一些注意事项。 最后，本文提出将遗传算法与其它算法相 结合来求解一般问题的想法； 并将遗传算法的应用范围扩展，提出可以运用遗传算法求 解由TSP衍生出的各类TSP扩展问题，

3、如求解配送/收集旅行商问题的遗传算法 （TSPD、 遗传算法在货物配送问题中的应用（ST TSP、多旅行商问题（MTSP等。引言：优化问题可以自然地分为两类：一类是连续变量的优化问题；另一类是离散变量 的优化问题，即所谓组合优化问题。对于连续变量的优化问题，一般是求一组实数或一 个函数； 而在组合优化问题中， 一般是从一个无限集或有限的几个无限集中寻找一个对 象它可以是一个整数，一个集合，一个排列或者一个图，也即是从可行解中求出最 优解的问题。TSP问题就是其中的典型例子，就本质上而言它可抽象为数学上的组合优 化，它描述的是旅行商经 N个城市的最短路径问题，因而对 TSP问题的求解是数学上，

4、同时也是优化问题中普遍关注的。旅行商问题（Traveling Salesman Problem，简称TSP也称为货担郎问题，是一个较古的问题，最早可以追溯到 1759年Euler提出的骑 士旅行问题 9 。旅行商问题可以解释为，一位推销员从自己所在城市出发，必须邀访 所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小（和旅行距离最短）的路径。TSP是一个典型的组合优化问题，并且是一个NP难题，所以一般很难精确地求出其最优解， 因而寻找出其有效的近似求解算法就具有重要的理论意 义。另一方面，很多实际应用问题，如公安执勤人员的最优巡回路线、流水作业生产线 的顺序问题、车辆调度

5、问题、网络问题、切割问题以至机组人员的轮班安排、教师任课 班级负荷分配等问题，经过简化处理后，都可建模为TSP问题，因而对旅行商问题求解方法的研究也具有重要的应用价值。再者，在各种遗传算法应用实例中，其个体编码方 法大多都是采用二进制编码方法或浮点数编码方法，而TSP问题是一种典型的需要使用符号编码方法的实际问题，所以，研究求解TSP问题的遗传算法，对促进遗传算法本身的发展也具有重要意义。 在过去的 20 年里，在求解旅行商问题的最优解方面取得了 极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究， 很多问题还在期待满意的回答。另外， 遗传算法就其本质来说， 主要是解决

6、复杂问题的一种鲁棒性强的启发式随机搜索算法。早在1983年，就有学者用GA求解组合优化中著名的 TSP问题。Wetzel、 Brady、Grefenstette等人都曾用遗传算子来讨论 TSP问题6,7,8。实践也证明，遗传算法对于组合优化中的 NP完全问题非常有效。因此遗传算法在TSP问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决TSP问题等有着多方面地重要意义。3.TSP 问题的数学模型和基本解法遗传算法的主要应用领域就包括组合优化问题，而组合优化中主要是TSP问题等。TSP问题是一个NP完全问题，近几年来，基于遗传算法求解TSP问题的研究相当活跃，在

7、遗传算法研究中，TSP问题已被广泛地用于评价不同的遗传操作及选择机制的性能14,15 。TSP问题的提出最早可追溯到 18世纪的欧拉时代，但直到 20司世纪中叶才由于优化技 术的兴起逐渐为人所认识而著名。 1948年，由美国兰德公司推动，TSP成为近代组合优 化领域的一个典型难题。它是一个具有广泛应用背景和重要理论价值的组合优化问题。TSP的搜索空间随着城市规模数 n的增加而增大，这类组合优化问题称之为 NP完全问题 16 。3.1TSP 问题的数学模型TSP问题可以简单地描述成：一名旅行商从一个城市出发，欲遍访 n个城市推销商品， 每个城市到一次且仅到一次后返回原出发城市，求总距离最短的巡回

8、路径。旅行商问题可分为两类：(1) 对称旅行商问题( dij dji, i, j 1,2, ,n)；(2) 非对称旅行商问题( dij dji, i, j 1,2, ,n)。TSP问题的数学模型如下：设有 n个城市，寻找一条巡回路径 T (t,t2, ,tn)，使得下列目标函数最小：n1f(T)d(ti,ti 1) d(tn,t1)i1其中 ti 为城市号，取值为 1 到 n 之间的自然数， d(i, j) 为城市 i 和城市 j 之间的距离，对于对称式TSF，有d(i, j) d(j,i)。旅行商问题属于典型的组合优化问题，并且是一个NP完全问题，其可能的路径数目为(n-1)!/211 ,至

9、今尚未找到有效的解决方法。在理论上一些方法是可以解这一问题，但 当 n 较大时，解题的时间消耗会使这些方法显得没有任何实际价值，所以设计一种 有效算法以获得问题的最优解或近似解是具有重要意义的。目前已有很多求解 TSP近似最优解的算法，主要包括：分枝定界法( branch and bound )、最近邻法( nearest neighbor )、贪婪法( greedy algorithm )、最近插入法( nearest insertion )、最 远插入法( farthest insertion )、双最小生成树法( double mining spaning tree )、剥脱法（ str

10、ip ）、空间填空曲线法（ space-filling curve）、 Karp 法、 Litke 法、Christofides 法、2-交叉法（2-opt ）、k-交叉法及 Lin-Kernighan 法等11,17,18。 正是由于TSP问题在实际应用中所具有的典型意义，如可用来解决分配问题、路径问题、 车辆调度问题等 , 以及算法理论研究上的价值 , 所以它一直吸引着各个领域的研究人员 去研究各种新的算法。3.2 TSP 的传统解决方法几十年来对于求解TSP问题出现了很多传统方法，其中有精确算法如线性规划方法、动 态规划方法、 分枝定界法， 近似优化算法如最近插入法、 最近邻法、 Cla

11、rk&Wright 算法、 双最小生成树法、 Christofides 算法、 r-opt 算法、混合算法、概率算法等。其中，线性规划方法是求解TSP的最早的一种算法，主要是采用整数规划中的割平面 法。 动态规划方法一般用于很小规模的问题。 分枝定界算法是一种应用范围很广的搜索 算法，它通过有效的约束界限来控制搜索进程使之能向着空间状态树上有最优解的分支 推进，以便尽快找出一个最优解， 该方法的关键在于约束界限的选取， 不同的约束界限， 可形成不同的分支定界法；但分枝定界算法对于解大规模问题不是很有效。近似算法都是适用于对称 TSP问题的。其中r-opt方法是一种局部改进搜速算法。混 合算法是

12、用某个近似算法求得初始解， 然后借助一个或者若干个 r-opt 算法对解加以改 进，这种混合型算法往往能获得较好的解，但也很耗时。总而言之，传统的优化算法是一种局部搜索算法，一般得到局部最优解，很难达到全 局最优解，并且很难适用于大规模的最优化问题。3.3 TSP 的智能优化算法近年来，有很多解决TSP问题的较为有效的智能优化方法不断被推出，例如禁忌搜索方法、模拟退火算法、遗传算法等。禁忌搜索方法（TS）是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对 人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避 免迂回搜索， 并通过藐视准则来赦免一些被禁忌的优良状态

13、，进而保证多样化的有效搜 索以实现全局优化。模拟退火算法的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间 的相似性。模拟退火算法是在某一初温下，伴随温度参数的不断下降，结合概率突跳性 在解空间中随机寻找目标函数的全局最优解， 使得局部最优解能概率性的跳出并最终趋 于全局最优解。这两种方法是从一个解进行局域搜索，虽然都有其各自的长处，但却存在着全局搜 索能力差的弱点， 极有可能找到的是局部最优解； 尽管可以采用一定机制有效避免陷入 局部极小并最终趋于全局最优，但是时间效率比较低。而遗传算法具有良好的全局搜索能力，是目前解决各种优化问题的最有效方法，已 经形成研究热点。因此，遗传算法在

14、 TSP问题求解方面的应用研究，对于构造合适的遗 传算法框架、建立有效的遗传操作以及有效地解决TSP问题等有着多方面地重要意义。传算法是按并行方式搜索一个种群数目的点， 而不是单个点 16 。它的并行性表现在两 个方面，一是遗传算法的内在并行性，即可以多台机器各自进行独立种群的演化计算， 运行过程中可以进行信息交换也可以不进行信息交换。二是遗传算法的内含并行性，这 是由于遗传算法采用种群的方式组织搜索。此外， 遗传算法还可以很好地与其它算法如 上面讲到的禁忌搜索方法和模拟退火方法相结合，从而使得遗传算法更加有效。图 3-1 就是传统优化方法与遗传算法的比较， 从图中我们可以很直观的看出传统方

15、法与遗传算法在求解具体问题时的区别。传统方法单初始点遗传算法改进(依赖问题)No终止吗？NNYes终止改进(不依赖问题)No终止吗？NNYes匕 终止图3 1传统优化方法与遗传算法的比较4.基于TSP问题的遗传算法4.1基本算法编码如何将问题的解转换为编码表达的染色体是遗传算法的关键问题。对于任何应用问题， 都必须将解的表达方法和适用于问题的遗传算子结合起来分析考虑。Holla nd的编码方法是二进制串表达，但对于许多遗传算法的应用，这种简单的编码方法很难直接描述出 问题的性质，这种简单的表达方法尤其不能较好的适用于TSP和其它组合优化问题。因此，为TSP提出了以下几种染色体编码方法。TSP的

16、编码策略主要包括近邻(adjacency)表示、次序(ordinal) 表示、路径(path)表 示、矩阵表示、边表示和随机键表达等11,13。(1) 近邻表示近邻表示是指巡回旅行路线所经过的连接两个城市的路线的顺序排列。即：将路径表示成n个城市的一个排列，且在第i位城市为j当且仅当路径中从i所到达的下一个城 市为j，其中每一条路径都唯一对应一个近邻表示。例如：(2 4 8 3 9 7 1 5 6)表示路径 1-2-4-3-8-5-9-6-7。采用近邻表示的优点之一是它比较适合模式分析；缺点是操作比较复杂，且遗传算子打断好路径的概率较大，因此，算法的性能较差。（2）次序表示次序表示仍将路径表示

17、成 n个城市的一个排列，该排列的第i个元素在1至n-i+1间取 数。其表示方法为：先取城市集合 C的顺序排列作为次序排列的一个参照点，然后按路 径中城市处在C的位置确定表示串中的点，且每确定一个则从C中删除相应的城市。次序表示的主要优点是可以使用传统的杂交算子。即以次序表示的任两条路径，从某 点截断后交换相应的子串所得到的两个后代仍是合法路径。（3）路径表示 路径表示可能是TSP的最自然、最直接的表示方式，大多数求解旅行 商问题的遗传算法都是以它为描述方法的。 路径表示直接采用城市在路径中的相当位置 来进行表示，即巡回旅行线路所经过的各个城市的顺序排列。例如：（ 1 2 3 4 5 6 7 8

18、 9 ）表示路径 1-2-3-4-5-6-7-8-9。总之，选择适当的候选解的表达方法是遗传算法解决实际问题的基础。对于任何应用 问题，都必须将解的表达方法和适于问题的遗传算子结合起来分析考虑。4.1.2 适应度函数用遗传算法求解TSP时，可用费用函数或距离作为问题的适应值度量。通常我们取适应度函数为路径长度Td的倒数，即f 1/Td。若结合TSP的约束条件（每个城市且经过一次），则适应度函数可表示成：f 1/（TdNt），其中Nt是对TSP路径不合法的度量（如取Nt为未遍历的城市的个数），为惩罚系数5。可见，若取每条旅行路线的总行程的倒数为适应值，则适应值越大，方案越优。4.1.3 选择算子

19、用遗传算法求解TSP问题时，最常用的选择算子是比例选择算子，即赌轮策略；其次,还有最优保存选择策略和期望值策略。4.1.4 交叉算子旅行商问题对交叉算子的设计要求是：对任意两条巡回路线进行交叉操作之后，都能够得到另外两条新的并且具有实际意义的巡回路线。经过实验表明，传统的杂交算子并不适合求解TSP问题11。下面介绍常用的几种用于旅行商问题求解的交叉算子。（ 1 ） 部分映射交叉PMX 操作的主要思想是：整个交叉操作过程由两步来完成，首先对个体编码串进行常 规的双点交叉操作， 然后根据交叉区域内各个基因值之间的映射关系来修改交叉区域之 外的各个基因座的基因值。PMX 步骤：Step1 ：在字串上

20、均匀随机地选择两点，由这两点定义的子串称为映射段；Step2 :交换双亲的两个子串，产生原始后代；Step3 :确定两映射之间的映射关系；Step4 ：根据映射关系将后代合法化。pmX操作保留了部分城市的绝对访问顺序，但是它更多的产生出了父代巡回路线中 所没有的新路线，所以这种操作方法的性状遗传特性不太好。（2）顺序交叉OX 的主要思想是：先进行常规的双点交叉，然后进行个体巡回路线的有效顺序修改， 修改时，要尽量的维持各城市原有的相对访问顺序。0X步骤：Step1 ：从第一双亲中随机选一个子串；Step2 ：将子串复制到一个空字串的相应位置，产生一个原始后代；Step3 :删去第二双亲中子串已

21、有的城市，得到原始后代需要的其它城市的顺序；Step4 :按照这个城市顺序，从左到右将这些城市定位到后代的空缺位置上。0X操作保留了部分城市的相对访问顺序，但是它也更多的城市出了父代巡回路线中所没有的部分新路线，所以这种操作方法的性状遗传特性不太好。（3）循环交叉CX的基本思想是：任意两条巡回路线都可能组成一些互补相交的巡回回路，相互交换其中一个循环回路的基因就有可能产生出新的巡回路线。CX 步骤：Stepl :根据双亲相应的城市位置找出一个循环；Step2 ：把一个双亲的循环上的城市复制到一个后代上；Step3 :删去另一个双亲的已在循环上的城市，剩下的城市即可用来确定剩余城市 的位置；St

22、ep4 :用这些剩余城市填满后代剩余的位置。（4）基于位置的交叉步骤:Step1 :从一个双亲上随机地选一组位置；Step2 :将这些位置复制到一个空字串的相应位置，产生一个原始后代；Step3 :删去第二双亲上该组中已有的城市，剩下的城市构成了原始后代需要的顺 序；Step4 :按照这个城市顺序，从左到右将这些城市定位到后代的空缺位置上。除此之外，还有一些交叉算子:基于顺序的交叉，该方法实际上是基于位置的交叉 的变型， 其中一个双亲选定位置上的城市的顺序强制被另一双亲的相应城市所替代；边 重组交叉（Edge Recomb in ation Crossover, 简称EX）,其主要思想是重点强

23、调了对父 代巡回路线上的边之间的邻接关系的遗传，它考虑了旅行商问题性状的遗传特点；启发式杂交,选择由现行城市出发的不构成循环的最短边。4.1.5 变异算子旅行商问题对变异算子的设计要求是:对任意一个个体编码串进行变异操作后,所产生的新个体应该能够对应于一条具有实际意义的巡回路线。针对TSP问题，变异算子主要包括位点变异、 逆转变异（ inversion mutation ）、插入变异（ insertion mutation ）、 移位变异（displacement mutation ）、互换变异（s） 等。（1）位点变异: 变异仅以一定的概率（通常较小）对串的某些位作值的变异。（2）逆转变异:

24、 逆转变异是先在父体中随机地选择两截断点,然后将该两点所夹 的子串中的城市进行反序。（ 3）插入变异: 插入变异是随机选择一个城市,并将它插入到一个随机的位置中。(4) 移位变异： 移位变异是随机选择一子路径，并将其插入到一个随机的位置中。( 5)互换变异： 也称基于次序的变异( order-based mutation )，它是随机地选 择两个位置，并将这两个位置上的城市相互交换。其它还有一些变异算子：基于位置的变异( position-based mutation )是随机选 择两城市，将第二个城市放在第一个之前；打乱变异(scramble mutation )是随机选择一子路径， 打乱其

25、次序， 重新插入； 启发式变异采用了邻域技术， 以获得后代的改进， 即对于一个染色体按它的邻域交换不多于 个基因， 可获得一族染色体， 选择其中最好 的一个作为变异产生的后代。对于变异操作还有一些变体形式，如 Sushil J.Louis 提出的贪心对换变异 (greedy-s)9 ，其基本思想是从一个染色体中随机的选择两个城市(即两个码值 ) ，然后交换它们， 得到新的染色体， 以旅程长度为依据比较交换后的染色体与原来的染色体 的大小，保留旅程长度值小的染色体。这种算子实际上是互换变异算子的改进算子。求解TSP问题时，变异算子的设计要比杂交算子的设计灵活的多，任何具有局部搜 索功能的算子都可

26、以作为它的变异算子。4.2 算法设计基于以上理论，本人先采用经典的遗传算法理论及个体整数编码方法设计了算法。但从算法的实现结果分析发现， 算法的运行结果虽然得到了相对最优解，但是当群体规 模较大时， 算法在运行过程中出现了局部早熟的现象。所以本人对算子的选取进行了改 进重组，重新设计了各个算子，试图进一步探索TSP组合优化问题的有效解决方案。4.2.1 编码在求解TSP问题的各种遗传算法中，多采用以遍历城市的次序排列进行编码的方法， 本文也采用这种最自然的编码方式，即以 n 个城市的遍历次序作为遗传算法的编码。每 一个解的码串形如：Vi，V2，, Vn，其中，Vi表示遍历城市的序号。程序中的解

27、定义为一维数组A(N) , N表示TSP问题中的城市数目，数组中的各个元素A(i)(i 1,2, , ,N)的取值为1至N间的整数，分别表示城市的序号，根据问题的约束条件，每一整数内的 各元素值互不相同。4.2.2 初始群体 在遗传算法中，初始群体一般是随机产生的，通过种群的进化最终达到最优值。但在实 际操作时，这样进化的速度太慢，且进化效果往往不太好。因此，本人对初始种群的选 取方式做了改进。在这里，初始群体也是随机产生的，但所不同的是这里的随机是有一 定前提条件的。具体操作是：设群体规模是 popsize ，首先用贪婪法( Greedy Method ) 产生n (nvpopsize )个

28、个体，这n个个体的起点城市分别是 1,2,n，再随机产生剩 余的城市个体。 贪婪法是将每一步都取局部最优的求解方法，这种用贪婪法产生的个体 在一定程度上具有有效的基因模式，有利于提高寻优能力。在次算法中，随机生成规模为 popsize 的初始群体， n 取为城市个数 lchrom 。4.2.3 适应度函数由于本算法在可行解群体的初始化、 交叉操作及变异操作中均隐含 TSP问题的合法性 约束条件(即对所有城市要做到不重不漏)，故适应度函数取为哈密顿圈(Hamilton )的长度的倒数(无惩罚函数) 5,21 。用路径倒数作为适应值是 Glodberg.D.E. 首先提出的 4 。适应度函数取路径

29、长度(即哈密顿圈长)Td 的倒数，即Fitness(i ) 1/Td (i)其中 Td(i) 表示第 i 个解所表示的遍历城市的路径长度，即： 1 111),(),()(jnnjjdvvdvvdiT 4.2.4 选择算子 遗传算法采用的选择算子一般有赌轮 法、最优保存方法和期望值选择方法等。赌轮选择个体的方法是，先把群体中的每个个 体的适应值按比例转化为选中概率 ip ，将轮盘分成 popsize 个扇区；产生一个 0,1 之 间的随机数 r ，如果从第一个个体的选中概率开始累加， 直到累加概率之和 iq 大于或等 于 r ，则将最后一个被累加选中概率的个体挑选出来，并复制到子代中。随着遗传算

30、法 的执行，我们始终保留 popsize 个较优的个体作为样本群体，以供选择。但是对于赌轮 选择算子，由于是随机操作的原因，这种选择方法的选择误差比较大，有时甚至连适应 度较高的个体也选择不上。 遗传算法的理论已经证明了赌轮法选择算子不能收敛到全局 最优解， 而最优保存方法相比之下则能收敛到全局最优解。 遗传算法中一个要求解决 的问题是如何防止“早熟”收敛现象。 为了保证遗传算法的全局收敛性，就要维持群体 中个体的多样性，避免有效基因的丢失。因此，作为改进，本文将引入最优选择策略即 保持群体中最好的个体不丢失， 以保证算法的收敛性。 采用最优保存选择方法的优点 是，进化过程中某一代的最优解可不

31、被交叉和变异操作所破坏。但是，这也隐含了一种 危机，即如果只选用最优选择策略，则局部最优个体的遗传基因会急速增加而使进化有 可能限于局部解。所以此方法一般都与其它选择方法结合使用 5 。因此，我改进了遗 传算法的选择算子， 采用赌轮选择策略和最优保存策略相结合的方法。 本文所采用的 赌轮和最优保存相结合的方法，具体描述如下： Stepl ：求出 pop(t )中适应度最大 的 1 个个体，记为 best ，将 best 作为下一代的个体，即最优个体必遗传到下一代中。 Step2 :令p(k)为个体k的轮转法选择概率，则201 1 )(/)()(Niifkfkp k= 1,2, , ,N Step3 :令 q(0)=0 ,q(k)=q(1) + q(2)+ +q(k), k=1,2, ,N Step 4:产生 N-1 个0,1 )中的均匀分布的随机数ir，i=1,2, ,N-1，依次判断这N-1个随机数，若q(k-1) vir vq(k)，则选 个体 k 为下一代的个体。 4.2.5 交叉算子 算法思想:通过赌轮策略，从父代中选择 两个个体， 利用如下操作， 通过从一个亲体中挑选一个城市子序列并保存另一个亲体的 城市相对次序来构造两个新的个体，然后将这两个新个体添加到子代中去。基于基因片段保序在求解TSP问题中的应用21,本文采用了一种改进的交叉