英文：Operators of the Two-Part Encoding Genetic Algorithm in Solving the Multiple Traveling Salesmen Problem

其他关于多旅行商问题(MTSP)的相关文章见个人主页：多旅行商问题（MTSP）的相关论文总结_脑电永不过时的博客-CSDN博客

---

摘要

       多旅行推销员问题（mTSP）考虑m个推销员访问n个城市。这个问题涉及到将销售人员分配到某些位置，我们必须优化路线内的顺序，因此它在本质上比旅行商问题（TSP）更难。因此，当问题规模较大时，有一些算法可用于求解mTSP。特别是遗传算法（GA）在解决这一问题时非常有名，而问题规模很大。当我们比较现有的主要mTSP编码方法时，最好的方法可能是两部分染色体编码，因为它的解空间最小。这两部分负责每个销售人员应访问的城市的顺序和数量。然而，由于两部分染色体技术是最近提出的编码方法，因此还没有研究这种编码方法中交叉算子和变异算子的更好组合。因此，本文研究了遗传算子在实验设计中的应用。本文提出了合适的遗传算子，并将其应用于采用两部分染色体编码技术的遗传算法中。

---

一、引言

       多旅行推销员问题（mTSP）对于模拟日常生活状况非常重要。例如，经理喜欢让他们的销售人员每天访问n位置，每个位置都必须有销售人员访问，其中n>m。销售人员还需要优化路线中的旅行顺序。它直接影响到旅行的成本和时间。此外，MTSP可以建模为不同的问题[2]。MTSP可以在生产调度[5]、[21]、[26]、劳动力规划[29]、[28]、运输规划[1]、[10]、[27]、全球导航卫星系统测量网络的设计[22]等领域制定。因此，MTSP很重要，需要在这方面作出更多努力，因为这一问题没有得到足够的重视。

       从以上对mTSP的描述来看，这个问题比旅行商问题（TSP）更复杂。尽管mTSP可以通过精确算法（exact algorith）来解决[7]、[12]、[15]，但精确算法可能无法有效地处理大型问题。为了求解大型mTSP问题，遗传算法是常用的算法之一。遗传算法有四种主要变体，包括一条染色体[25]、两条染色体[13]、[19]、两部分染色体[4]和分组遗传算法[3]、[6]、[11]、[20]、[23]。在四种主要技术中，最好的方法可能是两部分染色体技术，因为它需要较少的解决方案空间来进行探索。因此，本研究选择这种编码技术来解决mTSP。

       两部分染色体编码是最近提出的一种方法。据我们所知，没有研究两部分染色体最佳遗传算子的论文。在文献[4]中，他们只建议在两部分染色体的第一部分和第二部分进行有序和单点交叉。他们的论文中没有提到变异算子。此外，没有后续的论文研究两部分染色体的遗传算子。因此，本文通过实验设计（DOE）研究了可用于此目的的遗传算子。在检查了合适的遗传算子后，研究人员在求解mTSP时采用两部分染色体编码技术是有益的。

       论文的其余部分组织如下。第二节介绍了两部分染色体编码，我们在第三节介绍了这种编码方法的遗传算子。随后，我们进行了大量实验，以测试TSPLIB的一些基准实例和GA中的参数配置。我们可以在第四节中获得哪些遗传算子可以进化为最优（或良好）解决方案。最后，第五部分给出了结论和未来的研究方向。

---

二、两部分染色体编码技术

       根据Carter和Ragsdale[4]，他们评估了mTSP三种主要编码的解空间大小。当我们有n个城市和m个推销员时，三种空间大小为：

        因此，两部分染色体的解空间比其他两种方法小。换句话说，当使用这种编码技术时，GA将更加有效。这就是本研究采用图1所示方法的原因。

        图1说明了n=15和m=3的编码，有两个不同的部分。染色体的第一部分代表n个城市的排列。染色体的第二部分显示了分配给每个m推销员的城市数量，因此其染色体长度为m。m基因的总和等于要访问的城市数量。以图1为例，第一个销售员访问了第一部分染色体中的前6个城市，即城市7、8、10、15、12和13。然后，第二个推销员在第一个推销员之后前往4个城市，分别是5、2、14和3。最后，第三个销售人员的指定城市数为5，他/她需要访问城市11、1、6、9和4。所以当我们总结第二部分染色体中三个基因的值时，总数是15。

       一般来说，由两部分组成的染色体考虑每个推销员的序列和每个人指定的城市数量。当我们想要开发遗传算子时，我们可以首先将它们分为这两部分，因为它们代表着不同的目的。然后，针对这两个不同的部分分别设计了遗传算子。当我们设计新的遗传算子时，它可以保持简单性。下一节讨论两部分染色体的遗传算子。

---

三、两部分染色体的遗传算子

       因为我们喜欢研究两部分染色体中可以使用的交叉和变异算子，所以本节介绍了两部分染色体中的一些算子。因此，遗传算子（交叉算子和变异算子）与两部分染色体之间有4种组合。第III-A节至第III-D节分别讨论了每种组合

A、 染色体第一部分的交叉算子

       两部分染色体的第一部分是城市的排列。我们可以利用两种著名的交叉算子，包括两点中央交叉算子（two-point central crossov）[17]和循环交叉算子（cycling crossover）[8]、[24]、[18]。

两点中央交叉

       如图2所示。我们随机选择两个切割点，命名为C1和C2，其中C1<C2。位于C1和C2之间范围之外的基因从父代复制到子代。C1和C2中的基因根据另一个父代中的序列进行复制。

循环交叉

       当谈到循环交叉时，我们在图3中说明了这种方法。循环交叉的程序如下所示。

（1） 在父级A中选择一个随机位置。

（2） 考虑父B中的对应元素。

（3） 考虑父A中的相同元素。

（4） 继续此过程2-3，直到我们得到父级B的一个元素，这是我们在父级A中考虑的第一个元素。然后，在排列父级A和B的这些考虑元素后，我们可以得到两个分支。然后将父A和B的中对应元素互换位置。

       通过使用两点中心交叉和循环交叉，我们可以在两部分染色体的第一部分通过这些交叉算子形成一个新的序列。

B、染色体第二部分的交叉算子

       我们设计了两个交叉算子，可以交换遗传信息，并在两部分染色体的第二部分保持m个销售人员访问的n个城市的可行性。当我们为两部分染色体的第二部分设计交叉算子时，我们应该记住m个基因的总和应该等于n个城市。我们考虑了两种算术交叉算子，在产生新的染色体后，我们将确保其可行性。

算术交叉1（arithmetic crossover 1 ）（ARC1）

       第一种方法被命名为算术交叉1（arithmetic crossover 1 ）（ARC1），它是从[14]修改而来的。在将连续问题转化为整数解空间时，使用原方法求解连续问题。假设在群体中选择了两条染色体 Xi 和 Xj，它们是染色体的第二部分，一个随机值α∈生成（0,1）以确定从两个父级继承的加权和值。因此，当我们计算染色体 Xi 和 Xj 位置 [k] 的加权和时，新的基因值分别计算为公式1和公式2:

        式中，k=n+1，。。。，n+m和n>m。值得注意的是，我们取计算结果的下限值。我们可以获得代表销售人员指定城市的整数值。虽然Xi和Xj可能不可行，但我们在为第二部分染色体引入另一个交叉算子后对它们进行了检查。

算术交叉2（ARC2）

       第二种方法被称为算术交叉2（ARC2），这在文献[14]中也有提及。随机值α仍然用于确定从双亲继承的加权值。当我们想在[k]位置配对两条染色体Xi和Xj时，计算结果列在等式3和等式4中

        在ARC1或ARC2生成Xi和Xj后，我们需要通过以下等式5和等式6检查染色体的可行性。

       如果Δ（Xi）（或Δ（Xj））不等于零，则表示解决方案Xi（或Xj）不可行。使用修复方法。我们随机将所需的城市Δ（Xi）（或Δ（Xj））分配给Xi（或Xj）上的基因。因此，它确保了新解决方案保持可行性。

C、染色体第一部分的变异算子

       变异算子旨在增加搜索中的种群多样性。为了简单起见，我们在第一部分染色体中采用了著名的交换和反向突变算子（swap and inverse mutation operators ）。

交换突变

       在交换突变中（见图4），两个随机点C1和C2决定了两个基因应该交换到新的位置。在我们的示例中，两个随机点C1和C2位于位置4和位置7。15移动到位置7，5更改到位置4。

（图4：给定序列中的交换突变）

反向变异算子

       在反向变异算子中（见图5），两个随机点C1和C2被生成为C2>C1的位置。然后，我们对C1和C2之间的序列求逆。

（.图5：给定序列中的反向突变）

D、 染色体第二部分的突变算子

       当我们突变第二部分染色体的解Xi时，我们随机选择两个位置P1和P2，其中两个位置都大于n+1且小于n+m+1。P1和P2绝对不相等，P2不必大于P1。我们将把一些城市从位置P2的销售人员转移到位置P1的其他销售人员。从均匀分布中提取随机值α，以确定应移动多少个城市的百分比。式7和式8表示用于第二部分染色体的突变算子的计算。等式8自动满足每个销售人员至少访问一个城市的约束条件。

        以上各节说明，当我们进行交叉和突变程序时，遗传算子可以用于两部分染色体。下一节将展示这些遗传算子的最佳组合的实验结果。

---

四、实验结果

A、设置

       为了验证两部分染色体中使用的遗传算子，本文在TSPLIB1的基准实例上进行了大量实验。在所有实验中，每个实例在每个方法和问题组合上重复30次。问题组合是销售人员数量和城市数量，分别为m=3、15和20，n=51和150。在这些情况下，我们将最后一点设定为家乡城市。此外，目标函数是最小化所有销售人员的总旅行距离。所以所有的销售人员都开始和结束在家乡的旅行。

       终止标准为500×m×n函数评估。在实验中，种群规模设定为100。我们在Windows 2003服务器（Intel Xeon 3.2 GHZ）上用Java编写算法。

       除了要检查的方法外，GA还有一些参数需要调整，包括交叉率和变异率。当我们需要找到一个稳定和更好的参数配置时，ANOVA可以对这些结果进行有力的分析。GA的参数设置如表I所示

B、 比较

       方差分析结果见表二。在ANVOA表格中，source表示因素和因素组合。DF表示自由度，SS表示平方和。mean square 等于SS除以DF。如果Pr−value的值小于0.05，这意味着该因子存在显著差异【16】。由于表II中某些因素的Pr-values小于0.0001，两种方法之间存在显著差异。我们进一步进行duncan grouping test 测试，以区分这些算法的性能（见表III至表VI）。

       在Duncan grouping 测试中，mean是平均值，N是观察值的数目。如果等级共享相同的字母表（the levels share thesame alphabet (）（即，它们在同一组中），则它们之间没有显著差异。否则，它们会有显著的不同【16】。从表III至表VI的邓肯分组测试中可以明显看出，这些水平在表现上存在显著差异。

 

       为了理解两个因素之间的相互作用，两个因素的相互作用图如图6所示。在图6中，我们已经将Pcis设置为0.5。

        为了总结操作员选择和参数配置的实验结果，我们在表VII中列出了它们。我们可以建议研究人员在使用两部分染色体技术来解决mTSP时应用这些设置。

 

---

五、 结论与未来展望

       MTSP无论在学术研究还是在实践中都是一个重要的问题，因为MTSP可以转化为各种各样的问题。由于这个问题比TSP复杂得多，我们必须选择一种更好、更有效的方法来解决这个问题。本研究旨在研究两部分染色体编码技术，以有效解决mTSP问题。最重要的是，本研究填补了两部分染色体遗传算子的空白。我们可以建议使用两点中心交叉来处理第一部分染色体的排列。然后，当我们对第二部分染色体进行交叉时，可以应用ARC2。此外，在对第二部分染色体进行交叉后，进行了可行性检验。对于第一部分和第二部分染色体的突变，建议使用反向突变和算术突变。我们还测试了遗传算法中的交叉率（Pc）和交叉率（Pm），它们的最佳参数配置可以是0.5和0.1。通过使用上述建议的遗传算子和参数设置，这项工作为研究人员或实践者设计新的两部分染色体遗传算法提供了重要参考。

       最后，由于mTSP是一个复杂的问题，可以通过使用一些算法来提高路径内的解质量，从而提高解的质量。例如，求解TSP的最佳启发式算法是Lin Kernighan的增强版[9]，用于求解10000多个城市。将Lin-Kernighan启发式算法引入到遗传算法中，可以大大提高算法的性能。由于之前的研究没有使用Lin-Kernighan启发式，这可能是未来研究的一个好方向