《遗传算法及其在TSP问题中的应用.doc》由会员分享，可在线阅读，更多相关《遗传算法及其在TSP问题中的应用.doc（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、遗传算法及其在TSP问题中的应用摘要：本文首先介绍了遗传算法的根本理论与方法，从应用的角度对遗传算法做了认真的分析与研究，总结了用遗传算法提出求解组合优化问题中的典型问题TSP问题的最优近似解的算法。 其次，本文在深入分析与研究了遗传算法根本理论与方法的根底上，针对旅行商问题的具体问题，设计了基于TSP的遗传算法的选择、穿插与变异算子等遗传算子，提出了求解旅行商问题的一种遗传算法，并用Matlab语言编程实现其算法，最后绘出算法的仿真结果，并对不同结果作出相应的分析。 然后，本文还针对遗传算法求解TSP时存在的一些问题对该算法进展了适当的改良。如针对初始群体、遗传算子作出适当改良，或者将遗传算
2、法与其他方法相结合，以及在编程过程中对算法流程的改良。 本人在用计算机模拟遗传算法求解TSP问题时，首先分析了用Matlab语言设计遗传算法程序的优越性，接着以遗传算法求解TSP问题为例，深入讨论了各个遗传算子的程序实现，并通过分析实验数据，得到各个遗传算子在搜索寻优过程中所起的作用，最后指出了用Matlab语言编程同用其它高级程序语言编程的差异所在，以及运用Matlab编写遗传算法程序的一些考前须知。 最后，本文提出将遗传算法与其它算法相结合来求解一般问题的想法；并将遗传算法的应用范围扩展，提出可以运用遗传算法求解由TSP衍生出的各类TSP扩展问题，如求解配送/收集旅行商问题的遗传算法TSP
3、D、遗传算法在货物配送问题中的应用STTSP、多旅行商问题MTSP等。引言：优化问题可以自然地分为两类：一类是连续变量的优化问题；另一类是离散变量的优化问题，即所谓组合优化问题。对于连续变量的优化问题，一般是求一组实数或一个函数；而在组合优化问题中，一般是从一个无限集或有限的几个无限集中寻找一个对象它可以是一个整数，一个集合，一个排列或者一个图，也即是从可行解中求出最优解的问题。TSP问题就是其中的典型例子，就本质上而言它可抽象为数学上的组合优化，它描述的是旅行商经N个城市的最短路径问题，因而对TSP问题的求解是数学上，同时也是优化问题中普遍关注的。 旅行商问题Traveling Salesm
4、an Problem，简称TSP也称为货担郎问题，是一个较古的问题，最早可以追溯到1759年Euler提出的骑士旅行问题9。旅行商问题可以解释为，一位推销员从自己所在城市出发，必须邀访所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小与旅行距离最短的路径。 TSP是一个典型的组合优化问题，并且是一个NP难题，所以一般很难准确地求出其最优解，因而寻找出其有效的近似求解算法就具有重要的理论意义。另一方面，很多实际应用问题，如公安执勤人员的最优巡回路线、流水作业生产线的顺序问题、车辆调度问题、网络问题、切割问题以至机组人员的轮班安排、教师任课班级负荷分配等问题，经过简化处理后，
5、都可建模为TSP问题，因而对旅行商问题求解方法的研究也具有重要的应用价值。再者，在各种遗传算法应用实例中，其个体编码方法大多都是采用二进制编码方法或浮点数编码方法，而TSP问题是一种典型的需要使用符号编码方法的实际问题，所以，研究求解TSP问题的遗传算法，对促进遗传算法本身的开展也具有重要意义。 在过去的20年里，在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究，很多问题还在期待满意的答复。 另外，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机搜索算法。早在1983年，就有学者用GA求解组合优化中著名的TSP问题5
6、。Wetzel、Brady、Grefenstette等人都曾用遗传算子来讨论TSP问题6,7,8。实践也证明，遗传算法对于组合优化中的NP完全问题非常有效。因此遗传算法在TSP问题求解方面的应用研究，对于构造适宜的遗传算法框架、建立有效的遗传操作以及有效地解决TSP问题等有着多方面地重要意义。3.TSP问题的数学模型与根本解法遗传算法的主要应用领域就包括组合优化问题，而组合优化中主要是TSP问题等。TSP问题是一个NP完全问题，近几年来，基于遗传算法求解TSP问题的研究相当活泼，在遗传算法研究中，TSP问题已被广泛地用于评价不同的遗传操作及选择机制的性能14,15。 TSP问题的提出最早可追溯
7、到18世纪的欧拉时代，但直到20司世纪中叶才由于优化技术的兴起逐渐为人所认识而著名。1948年，由美国兰德公司推动，TSP成为近代组合优化领域的一个典型难题。它是一个具有广泛应用背景与重要理论价值的组合优化问题。TSP的搜索空间随着城市规模数n的增加而增大，这类组合优化问题称之为NP完全问题16。TSP问题可以简单地描述成：一名旅行商从一个城市出发，欲遍访n个城市推销商品，每个城市到一次且仅到一次后返回原出发城市，求总距离最短的巡回路径。 旅行商问题可分为两类： （1） 对称旅行商问题； （2） 非对称旅行商问题。 TSP问题的数学模型如下：设有n个城市，寻找一条巡回路径，使得以下目标函数最小
8、：其中为城市号，取值为1到n之间的自然数，为城市i与城市j之间的距离，对于对称式TSP，有。 旅行商问题属于典型的组合优化问题，并且是一个NP完全问题，其可能的路径数目为(n-1)!/2 11 ,至今尚未找到有效的解决方法。在理论上一些方法是可以解这一问题，但 当n较大时，解题的时间消耗会使这些方法显得没有任何实际价值，所以设计一种有效算法以获得问题的最优解或近似解是具有重要意义的。目前已有很多求解TSP近似最优解的算法，主要包括：分枝定界法branch and bound、最近邻法nearest neighbor、贪婪法greedy algorithm 、最近插入法nearest inser
9、tion、最远插入法farthest insertion、双最小生成树法double mining spaning tree、剥脱法strip、空间填空曲线法space-filling curve、Karp法、Litke法、Christofides法、2-穿插法2-opt、k-穿插法及Lin-Kernighan法等11,17,18。 正是由于TSP问题在实际应用中所具有的典型意义,如可用来解决分配问题、路径问题、车辆调度问题等,以及算法理论研究上的价值,所以它一直吸引着各个领域的研究人员去研究各种新的算法。3.2 TSP的传统解决方法几十年来对于求解TSP问题出现了很多传统方法，其中有准确算法
10、如线性规划方法、动态规划方法、分枝定界法，近似优化算法如最近插入法、最近邻法、Clark&Wright算法、双最小生成树法、Christofides算法、r-opt算法、混合算法、概率算法等。 其中，线性规划方法是求解TSP的最早的一种算法，主要是采用整数规划中的割平面法。动态规划方法一般用于很小规模的问题。分枝定界算法是一种应用范围很广的搜索算法，它通过有效的约束界限来控制搜索进程使之能向着空间状态树上有最优解的分支推进，以便尽快找出一个最优解，该方法的关键在于约束界限的选取，不同的约束界限，可形成不同的分支定界法；但分枝定界算法对于解大规模问题不是很有效。 近似算法都是适用于对称TSP问题
11、的。其中r-opt方法是一种局部改良搜速算法。混合算法是用某个近似算法求得初始解，然后借助一个或者假设干个r-opt算法对解加以改良，这种混合型算法往往能获得较好的解，但也很耗时。 总而言之，传统的优化算法是一种局部搜索算法，一般得到局部最优解，很难到达全局最优解，并且很难适用于大规模的最优化问题。 3.3 TSP的智能优化算法 近年来，有很多解决TSP问题的较为有效的智能优化方法不断被推出，例如禁忌搜索方法、模拟退火算法、遗传算法等。 禁忌搜索方法TS是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储构造与相应的禁忌准那么来防止迂回
12、搜索，并通过藐视准那么来赦免一些被禁忌的优良状态，进而保证多样化的有效搜索以实现全局优化。 模拟退火算法的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法是在某一初温下，伴随温度参数的不断下降，结合概率突跳性在解空间中随机寻找目标函数的全局最优解，使得局部最优解能概率性的跳出并最终趋于全局最优解。 这两种方法是从一个解进展局域搜索，虽然都有其各自的长处，但却存在着全局搜索能力差的弱点，极有可能找到的是局部最优解；尽管可以采用一定机制有效防止陷入局部极小并最终趋于全局最优，但是时间效率比拟低。 而遗传算法具有良好的全局搜索能力，是目前解决各种优化问题的最有效方法，
13、已经形成研究热点。因此，遗传算法在TSP问题求解方面的应用研究，对于构造适宜的遗传算法框架、建立有效的遗传操作以及有效地解决TSP问题等有着多方面地重要意义。 传算法是按并行方式搜索一个种群数目的点，而不是单个点16。它的并行性表现在两个方面，一是遗传算法的内在并行性，即可以多台机器各自进展独立种群的演化计算，运行过程中可以进展信息交换也可以不进展信息交换。二是遗传算法的内含并行性，这是由于遗传算法采用种群的方式组织搜索。此外，遗传算法还可以很好地与其它算法如上面讲到的禁忌搜索方法与模拟退火方法相结合，从而使得遗传算法更加有效。 图3-1就是传统优化方法与遗传算法的比拟，从图中我们可以很直观的
14、看出传统方法与遗传算法在求解具体问题时的区别。 传统方法 遗传算法终止吗？改良依赖问题 单初始点 初始种群YesYesNo NNNo NN终止终止终止吗？改良不依赖问题图31传统优化方法与遗传算法的比拟4. 基于TSP问题的遗传算法4.1 根本算法4.1.1 编码如何将问题的解转换为编码表达的染色体是遗传算法的关键问题。对于任何应用问题，都必须将解的表达方法与适用于问题的遗传算子结合起来分析考虑。Holland的编码方法是二进制串表达，但对于许多遗传算法的应用，这种简单的编码方法很难直接描述出问题的性质，这种简单的表达方法尤其不能较好的适用于TSP与其它组合优化问题。因此，为TSP提出了以下几
15、种染色体编码方法。 TSP的编码策略主要包括近邻(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
16、） 次序表示 次序表示仍将路径表示成n个城市的一个排列，该排列的第i个元素在1至n-i+1间取数。其表示方法为：先取城市集合C的顺序排列作为次序排列的一个参照点，然后按路径中城市处在C的位置确定表示串中的点，且每确定一个那么从C中删除相应的城市。 次序表示的主要优点是可以使用传统的杂交算子。即以次序表示的任两条路径，从某点截断后交换相应的子串所得到的两个后代仍是合法路径。 （3） 路径表示 路径表示可能是TSP的最自然、最直接的表示方式，大多数求解旅行商问题的遗传算法都是以它为描述方法的。路径表示直接采用城市在路径中的相当位置来进展表示，即巡回旅行线路所经过的各个城市的顺序排列。 例如：1 2
17、 3 4 5 6 7 8 9表示路径1-2-3-4-5-6-7-8-9。 总之，选择适当的候选解的表达方法是遗传算法解决实际问题的根底。对于任何应用问题，都必须将解的表达方法与适于问题的遗传算子结合起来分析考虑。 4.1.2适应度函数 用遗传算法求解TSP时，可用费用函数或距离作为问题的适应值度量。通常我们取适应度函数为路径长度的倒数，即。假设结合TSP的约束条件每个城市且经过一次，那么适应度函数可表示成：，其中是对TSP路径不合法的度量如取为未遍历的城市的个数，为惩罚系数5。可见，假设取每条旅行路线的总行程的倒数为适应值，那么适应值越大，方案越优。 4.1.3选择算子 用遗传算法求解TSP问
18、题时，最常用的选择算子是比例选择算子，即赌轮策略；其次，还有最优保存选择策略与期望值策略。 4.1.4 穿插算子 旅行商问题对穿插算子的设计要求是：对任意两条巡回路线进展穿插操作之后，都能够得到另外两条新的并且具有实际意义的巡回路线。经过实验说明，传统的杂交算子并不适合求解TSP问题11。下面介绍常用的几种用于旅行商问题求解的穿插算子。 （1） 局部映射穿插 PMX操作的主要思想是：整个穿插操作过程由两步来完成，首先对个体编码串进展常规的双点穿插操作，然后根据穿插区域内各个基因值之间的映射关系来修改穿插区域之外的各个基因座的基因值。 PMX步骤： Step1：在字串上均匀随机地选择两点，由这两
19、点定义的子串称为映射段； Step2：交换双亲的两个子串，产生原始后代；Step3：确定两映射之间的映射关系； Step4：根据映射关系将后代合法化。 PMX操作保存了局部城市的绝对访问顺序，但是它更多的产生出了父代巡回路线中所没有的新路线，所以这种操作方法的性状遗传特性不太好。 （2） 顺序穿插 OX的主要思想是：先进展常规的双点穿插，然后进展个体巡回路线的有效顺序修改，修改时，要尽量的维持各城市原有的相对访问顺序。 OX步骤： Step1：从第一双亲中随机选一个子串； Step2：将子串复制到一个空字串的相应位置，产生一个原始后代； Step3：删去第二双亲中子串已有的城市，得到原始后代需
20、要的其它城市的顺序； Step4：按照这个城市顺序，从左到右将这些城市定位到后代的空缺位置上。OX操作保存了局部城市的相对访问顺序，但是它也更多的城市出了父代巡回路线中所没有的局部新路线，所以这种操作方法的性状遗传特性不太好。 （3） 循环穿插 CX的根本思想是：任意两条巡回路线都可能组成一些互补相交的巡回回路，相互交换其中一个循环回路的基因就有可能产生出新的巡回路线。 CX步骤： Step1：根据双亲相应的城市位置找出一个循环； Step2：把一个双亲的循环上的城市复制到一个后代上； Step3：删去另一个双亲的已在循环上的城市，剩下的城市即可用来确定剩余城市的位置； Step4：用这些剩余
21、城市填满后代剩余的位置。 （4） 基于位置的穿插 步骤： Step1：从一个双亲上随机地选一组位置； Step2：将这些位置复制到一个空字串的相应位置，产生一个原始后代； Step3：删去第二双亲上该组中已有的城市，剩下的城市构成了原始后代需要的顺序； Step4：按照这个城市顺序，从左到右将这些城市定位到后代的空缺位置上。 除此之外，还有一些穿插算子：基于顺序的穿插，该方法实际上是基于位置的穿插的变型，其中一个双亲选定位置上的城市的顺序强制被另一双亲的相应城市所替代；边重组穿插Edge Recombination Crossover,简称EX，其主要思想是重点强调了对父代巡回路线上的边之间的
22、邻接关系的遗传，它考虑了旅行商问题性状的遗传特点；启发式杂交，选择由现行城市出发的不构成循环的最短边。 旅行商问题对变异算子的设计要求是：对任意一个个体编码串进展变异操作后，所产生的新个体应该能够对应于一条具有实际意义的巡回路线。针对TSP问题，变异算子主要包括位点变异、逆转变异inversion mutation、插入变异insertion mutation、移位变异displacement mutation、互换变异s等。 1位点变异：变异仅以一定的概率通常较小对串的某些位作值的变异。 2逆转变异：逆转变异是先在父体中随机地选择两截断点，然后将该两点所夹的子串中的城市进展反序。 3插入变异
23、：插入变异是随机选择一个城市，并将它插入到一个随机的位置中。 4移位变异：移位变异是随机选择一子路径，并将其插入到一个随机的位置中。5互换变异：也称基于次序的变异order-based mutation，它是随机地选择两个位置，并将这两个位置上的城市相互交换。 其它还有一些变异算子：基于位置的变异position-based mutation是随机选择两城市，将第二个城市放在第一个之前；打乱变异scramble mutation是随机选择一子路径，打乱其次序，重新插入；启发式变异采用了邻域技术，以获得后代的改良，即对于一个染色体按它的邻域交换不多于个基因，可获得一族染色体，选择其中最好的一个作
24、为变异产生的后代。 对于变异操作还有一些变体形式，如Sushil J.Louis提出的贪心对换变异(greedy-s)9，其根本思想是从一个染色体中随机的选择两个城市(即两个码值)，然后交换它们，得到新的染色体，以旅程长度为依据比拟交换后的染色体与原来的染色体的大小，保存旅程长度值小的染色体。这种算子实际上是互换变异算子的改良算子。 求解TSP问题时，变异算子的设计要比杂交算子的设计灵活的多，任何具有局部搜索功能的算子都可以作为它的变异算子。4.2算法设计 基于以上理论，本人先采用经典的遗传算法理论及个体整数编码方法设计了算法。但从算法的实现结果分析发现，算法的运行结果虽然得到了相对最优解，但
25、是当群体规模较大时，算法在运行过程中出现了局部早熟的现象。所以本人对算子的选取进展了改良重组，重新设计了各个算子，试图进一步探索TSP组合优化问题的有效解决方案。 在求解TSP问题的各种遗传算法中，多采用以遍历城市的次序排列进展编码的方法，本文也采用这种最自然的编码方式，即以n个城市的遍历次序作为遗传算法的编码。每一个解的码串形如：，其中，表示遍历城市的序号。程序中的解定义为一维数组A(N)，N表示TSP问题中的城市数目，数组中的各个元素A(i)(i1,2,N)的取值为1至N间的整数，分别表示城市的序号，根据问题的约束条件，每一整数内的各元素值互不一样。 4.2.2初始群体 在遗传算法中，初始
26、群体一般是随机产生的，通过种群的进化最终到达最优值。但在实际操作时，这样进化的速度太慢，且进化效果往往不太好。因此，本人对初始种群的选取方式做了改良。在这里，初始群体也是随机产生的，但所不同的是这里的随机是有一定前提条件的。具体操作是：设群体规模是popsize，首先用贪婪法Greedy Method产生nnpopsize个个体，这n个个体的起点城市分别是1,2,n，再随机产生剩余的城市个体。贪婪法是将每一步都取局部最优的求解方法，这种用贪婪法产生的个体在一定程度上具有有效的基因模式，有利于提高寻优能力。 在次算法中，随机生成规模为popsize的初始群体，n取为城市个数lchrom。 4.2
27、.3适应度函数 由于本算法在可行解群体的初始化、穿插操作及变异操作中均隐含TSP问题的合法性约束条件即对所有城市要做到不重不漏，故适应度函数取为哈密顿圈Hamilton的长度的倒数无惩罚函数5,21。用路径倒数作为适应值是Glodberg.D.E.首先提出的4。 适应度函数取路径长度即哈密顿圈长的倒数，即 其中表示第i个解所表示的遍历城市的路径长度，即： =-+=1 1 11),(),()(jnnjjdvvdvvdiT 4.2.4选择算子 遗传算法采用的选择算子一般有赌轮法、最优保存方法与期望值选择方法等。赌轮选择个体的方法是，先把群体中的每个个体的适应值按比例转化为选中概率ip，将轮盘分成p
28、opsize个扇区；产生一个0,1之间的随机数r，如果从第一个个体的选中概率开场累加，直到累加概率之与iq大于或等于r，那么将最后一个被累加选中概率的个体挑选出来，并复制到子代中。随着遗传算法的执行，我们始终保存popsize个较优的个体作为样本群体，以供选择。但是对于赌轮选择算子，由于是随机操作的原因，这种选择方法的选择误差比拟大，有时甚至连适应度较高的个体也选择不上。遗传算法的理论已经证明了赌轮法选择算子不能收敛到全局最优解，而最优保存方法相比之下那么能收敛到全局最优解。 遗传算法中一个要求解决的问题是如何防止“早熟收敛现象。为了保证遗传算法的全局收敛性，就要维持群体中个体的多样性，防止有
29、效基因的丧失。因此，作为改良，本文将引入最优选择策略即保持群体中最好的个体不丧失，以保证算法的收敛性。 采用最优保存选择方法的优点是，进化过程中某一代的最优解可不被穿插与变异操作所破坏。但是，这也隐含了一种危机，即如果只选用最优选择策略，那么局部最优个体的遗传基因会急速增加而使进化有可能限于局部解。所以此方法一般都与其它选择方法结合使用5。因此，我改良了遗传算法的选择算子，采用赌轮选择策略与最优保存策略相结合的方法。 本文所采用的赌轮与最优保存相结合的方法，具体描述如下： Stepl：求出popt中适应度最大的1个个体，记为best，将best作为下一代的个体，即最优个体必遗传到下一代中。 S
30、tep2：令p(k)为个体k的轮转法选择概率，那么 20 -=1 1 )(/)()(Niifkfkp k1,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)irq(k)，那么选个体k为下一代的个体。 4.2.5穿插算子 算法思想：通过赌轮策略，从父代中选择两个个体，利用如下操作，通过从一个亲体中挑选一个城市子序列并保存另一个亲体的城市相对次序来构造两个新的个体，然后将这两个新个体添加到子代中去。 基于基因片段保序在求解TSP问题中的
31、应用21，本文采用了一种改良的穿插操作，这种穿插方法与OX法有点类似19，具体操作如下： 1 随机在串中选择一个交配区域，如两父体及交配区域选定为： oldp1=1 2 | 3 4 5 6 | 7 8 9， oldp2=9 8 | 7 6 5 4 | 3 2 1 2将oldp2的交配区域加到oldp1的前面，oldp1的交配区域加到oldp2的前面，得： oldp12=7 6 5 4 | 1 2 3 4 5 6 7 8 9， oldp21=3 4 5 6 | 9 8 7 6 5 4 3 2 1 3对oldp12，oldp21自交配区域后依次删除与交配区一样的城市码，得到最终的两子串为： new
32、p1=7 6 5 4 1 2 3 8 9， newp23 4 5 6 9 8 7 2 1 与其它方法相比，这种方法在两父串一样的情况先仍能产生一定程度的变异效果，这对维持群体内一定的多样化特性有一定的作用。 4.2.6变异算子 算法思想：依赌轮策略，从父代中选择两个个体，然后随机选取个体中的两个元，再交换他们。由于在选择机制中采用保存最正确样本方式，以及引入了“进化逆转操作技术，为保持群体内个体的多样化，我们采取连续屡次对换的变异技术，使可行解有较大的顺序排列上的变化。变异操作发生的概率取得比拟小，一旦变异操作发生，那么用随机方式选取两个交换的点，并将其对换位置。 4.2.7进化逆转操作 引入
33、“进化逆转操作的主要目的是改善遗传算法的局部搜索能力。所谓局部搜索通常指的是基于邻域的试探搜索方法。在根本遗传算法操作中，穿插操作在可行解空间中的动作方位较宽，步伐较大；变异操作由于受“选择压力的作用，通常也难以发挥局部搜索的成效特别在遗传算法趋向收敛的后期阶段。因此，在遗传算法框架中参加适当的、基于邻域的局部搜索机制，构成一种全局搜索与局部搜索相结合的优化搜索算法，对改良优化质量以及提高搜索效率都是很有意义的。 在自然遗传与进化过程中，“逆转也是一种常见的现象。自然生物遗传上“逆转现象有消极的作用如导致致死因素、不育因素等，也可能产生积极作用如导致生物的适应能力增强等。从优化意义上讲，如果说穿插、变异等遗传操作使子代趋向于拥有较优品质的基因型的话，那么逆转、对换等遗传操作的功能就是使这些基因型及其组合以较优的次序遗传给后代。在针对TSP问题的遗传算法中，“逆转是一种常见的“变异技术。我们使用的“进化逆转是一种单方向的朝着改良方向与连续屡次的“逆转第 19 页