遗传算法求解多旅行商问题的相对解空间分析

赵新超，郭赛

多旅行商问题(multiple traveling salesman problem，MTSP)可直观描述为一个旅行商团队要分头遍历若干个城市，每个城市至少被一个旅行商访问一次且只访问一次，如何安排m(大于1)位旅行商遍历n(大于m)个城市，使得总的访问行程最小[1]。该问题最常见的应用领域是车间调度领域，在生产线上的作业调度通常被建模为一个旅行商问题(traveling salesman problem，TSP)。如果生产经营扩展到有多条平行线，工作可以分配，这个问题可以建模为一个多旅行商MTSP[2]；另一个经常被建模为多旅行商问题的就是车辆调度问题(VSP)[3]。车辆调度问题是指对一些车辆进行调度，所有的车辆离开并回到原地点，使得每个地方只能而且必须被访问一次。

由于多旅行商问题的复杂性，必须根据实际问题的大小采用启发式解决方案[4]。遗传算法(genetic algorithms，GA)[5]是一种基于生物自然选择和基因遗传学原理的高效并行、随机全局优化搜索算法。Keshavarz等[6]学者发现遗传算法对调度问题有很强的适应性，MTSP有效的遗传算子也激发了研究者的极大兴趣；张永库等[7]研究了改进的遗传算法在模糊聚类中的表现；Katayama等[8]提出的混合变异遗传算法在旅行商问题中的应用提高了遗传算法解决旅行商问题的性能。多旅行商问题在实际问题中有很广泛的应用。Huang等[9]研究了多旅行推销员问题在热轧规划中的应用；江贺等[10]研究了近年来出现的新NP-难解问题，即黑白旅行商问题(BWTSP)，给出了遗传算法解决问题的一种新思想；Trigui等[11]提出一种解决多机器人系统多目标多旅行推销员问题的模糊逻辑方法。最近出现了多种解决TSP问题的方法，王宇平等[12]提出的求解TSP的量子遗传算法使用了有关量子方面的知识。研究者们也在其他经典优化算法[13]中找到了许多新思想。

遗传算法求解MTSP的关键是要根据问题设计一种好的染色体编码方法，而好的遗传算法染色体编码方案应该能够从候选解中减少或消除冗余的解。冗余解是指以一种以上的方式表示同一染色体，并多次出现在种群中的染色体编码方式。相同解的多次再现不仅增加了查找空间，而且降低了查找效率。

本文首先列出了传统的两个染色体方案(单染色体设计方案和双染色体方案)，以及最近提出的较新的两段式染色体设计方案；本文引入相对解空间概念，以此定量地衡量不同染色体方案给出的相对解空间大小关系，先给出对旅行商数目和城市数目在趋于无穷时的极限相对大小关系，接下来近似分析了旅行商数目与城市数目在不同情形下解空间的相对大小关系。

1 3种染色体方案

MTSP染色体的设计主要有以下3种[1]。

1.1 单染色体设计

图1描述了MTSP问题城市数n=15、旅行商数m=4时染色体编码的一种设计方法的一个实例。这种设计使用了一个染色体编码长度为n+m–1的染色体，因此被称为“单染色体”(one chromosome)设计。该设计方案中，n个城市用从1～n正整数编码表示，并进行无规则的排列，代表着n个城市的整数编码列被–1～–(m–1)这m–1个负整数分为m段，分别依次对应着有序的m个旅行商所访问的城市，因此这个长度为n+m–1的整数列的任何一种排列组合都可能是这个MTSP问题的解。以图1为例，第一个旅行商将访问编号为2、5、14、6的这几座城市，第二个旅行商将访问编号为1、11、8、13的这几座城市，依次类推。在这种染色体设计中，MTSP所有问题的解将可能是由(n+m–1)!个解构成的一个空间。这些解中有很多是冗余的，例如，旅行商1与旅行商2的访问城市全部按顺序相互调换位置后的解和现有解。

图1 单染色体方案Fig. 1 One chromosome

1.2 双染色体设计

图2 描述了同样一个MTSP问题由遗传算法中染色体编码方案的另一种设计方法。一般称它为“双染色体(two chromosomes)”设计。这种设计使用两个长度为n的染色体表示一个解。图2中，第一个染色体表示n个城市的一组排列，第二个染色体的每一位数对应上面相应的城市，由对应编码的旅行商来访问。例如，旅行商l访问的城市为5、14、10、15，旅行商2 访问的城市为 2、8、12、9。使用这种编码设计，对应的空间是由n!mn个可能的解构成的一个集合。同样，这种编码方案也有许多冗余的解。例如，上述事例解中头两个基因位交换位置后得到的解与现有解就是相同的。

图2 双染色体方案Fig. 2 Two chromosomes

1.3 两段式染色体设计

图3 描述了一个新的染色体设计方案，它由前后两个部分组成，因此称为“两段式染色体(two-part chromosome)”设计。前段是整数 l～n的一个排列，代表了n个城市的一个顺序排列；后段长度为m，按顺序分别表示m个旅行商在前段编码中对应访问的城市数，并且这m个数之和等于n。图3所示旅行商l访问前段中的头4个城市顺序分别为2、5、l4、6；旅行商3访问从第4+4+1个开始的连续3个城市，分别为4、10、3。使用新的两段式染色体设计，不仅减少了查找空间，而且由于固定了旅行商的顺序而消除了部分(但不是全部的)冗余的解。使用这种染色体编码设计，对于前段可能会有n!种排列，后段由于是一个和为n的正整数向量，因此需要种可能的m维正整数表示，才能满足要求。从而，可以得到解空间大小为。

图3 两段式染色体方案Fig. 3 Two-part chromosome

2 3种染色体编码方案下的相对解空间分析

上一节介绍了遗传算法求解多旅行商问题的3种染色体编码方案。文献[1]给出了3种染色体编码方案对应的搜索空间的大小，仅是定性分析了3种方案的优劣，即两段式染色体方案对应的解空间优于前两种编码方案对应的解空间，而第一种单染色体设计方案优于双染色体编码方案。如果只是定性地了解3种编码方案对应解空间大小关系，对染色体编码方案和算法设计以及实际工程应用并没有太大的指导意义。因此本文首先引入相对解空间概念，然后详细地定量分析了3种染色体方案对应的解空间相对大小，这对多旅行商问题的研究和求解具有现实的指导意义。

2.1 相对解空间

3种染色体编码方案对应的解空间大小[1]分别为

式中：Cone表示单染色体编码对应的解空间规模，Ctwo表示双染色体编码对应的解空间规模，表示两段式染色体解空间的规模。从3种编码方案解空间的代数表达式可以看出，它们都是城市数n和旅行商数目m的二元函数，自变量n和m的取值范围是正整数，且一般m＜n(旅行商人数小于城市数)。

2.2 相对解空间的极限分析

在现实的工程应用中，比如车辆调度问题，m、n一般取值较大，因此随着自变量的增大或问题规模的扩大，我们需要了解相对解空间对应的比值结果的变化趋势，从而从数学表达式中讨论m和n取较大正整数时，相对解空间的极限行为，也可以认为是讨论m、n趋于无穷时的极限。

2.2.1 C31的极限分析

1) m适当大时

在多旅行商问题中，城市数目与旅行商数目之间的差距一般都比较大，因此当讨论C31的极限性质时，不妨假设，当n充分大、m应适当大时，对C31取对数，分析可得：

所以 C31＜1。

C31＜1意味着第三种编码方案对应的解空间严格小于第一种方案对应的解空间，这严格证明了Carter[1]给出的解空间的定性比较结果。当n足够大时，所需的旅行商数也有相应增大，因此当n充分大、m适当大时，。例如：m=10，。

2) m是不大的常数时

(n–1)!可与 (n+m–1)!相抵消，n!可与 (n–m)!相抵消，所以当n趋于无穷时得出：

即当旅行商人数m取不大的常数时，随着城市数目的增加，单染色体编码方案对应的空间约是两段式染色体方案解空间的(m–1)！倍，此结果与两种解空间的极限分析是一致的。

2.2.2 C32的极限分析

1)m适当大时

C32＜1同样意味着第三种编码方案对应的解空间小于第二种方案对应的解空间。同C31的分析类似，当n足够大、m适当大时，。

2)m是不大的常数时

由对C32的分析可知，当m取大于2的常数时，C32＜ 1。此结果显示，第三种编码方案对应的解空间小于第二种编码方案对应的解空间，此结果与两种解空间的极限分析是一致的。

2.2.3 C12的极限分析

至此，在合理适当的条件下：n适当大，对3种解空间的相对大小给出详细严密的论证，很好地补充了文献[1]中定性的结论，即，而且由分析可知，当n充分大、m适当大时，。

以上分析中，对一般的m和n给出的是相对解空间理论上的对比，但是如果只知道相对大小，对实际问题应用几乎没有实质性的帮助，例如求C31的极限，实质上m为常数，n逐渐增大，也就是说，在某一个多旅行商问题中，我们保持商人的数目不变，增大工程的规模，让城市数目逐渐增大，这也就意味着单个商人访问的城市数目随着城市数目的增多而无限增加下去，这显然不符合实际情况，因为每个旅行商访问的城市数目是有上限的，即最大负荷能力。因此单一用这个极限结果去估计解空间的大小，虽然能得出严密的定量分析结果，但是其代表的实际意义是不乏片面性的。

2.3 相对搜索空间的粗略估计

图4描述了l5个城市，是旅行商数量从l增加到14时，3种染色体编码设计的搜索空间的变化示意图。图4的纵轴表示搜索空间的数量级。由图4可以看出，在旅行商逐步增加的情况下，单染色体编码对应的搜索空间数量的增加由快到慢；双染色体编码对应的搜索空间数量的增加比较平稳；而两段式染色体编码对应的搜索空间数量呈现两端相当、中间略微增加的大体对称的情况。因此图4与2.2节的解空间分析结果显示出了两段式染色体编码设计的初步优越性。

众所周知，当城市数目逐步增加时，旅行商人数也应该相应增加，而m一般会随n的变化而变化。以下详细讨论m与n有特定关系时的相对搜索空间。例如：n=10m，n=m2，n=em三种情形下，相对搜索空间的变化趋势。

图4 解空间变化示例Fig. 4 Example of solution space change

从图5～7所示的3组函数图像可以看出，3种情形下的相对搜索空间变化，总体来说，从相对搜索空间上比较，在n=10m和n=m2情形下，C31和C32在前期的差别不大，纵轴随着m的增大很快收敛，且C12在n=m2情形下比在n=10m情形下收敛得更快些；在n=em情形下C32相对搜索空间和C12相对搜索空间比其他两种情形收敛更快，但C31在前期收敛得有些缓慢，而在n=em情形下明显比其他两种情形收敛更快。从同一情形下看3种相对搜索空间的变化时，可以看出C31、C32和C12都是纵轴随着m的增大很快收敛，C32和C12收敛较快些，在m≤6时就能定性地看出收敛；C31收敛最慢，在m取较大值时能判断出也是收敛的。从两种判断方法中我们能够看出收敛，但是很难直观地从函数图像上直接看出m取较大值时的收敛状况，也即只能定性得出收敛的结论，这与前面的结论亦是吻合的。

图5 n=10m情形下的相对搜索空间变化曲线图Fig. 5 Solution space change in the case of n= 10 m

图6 n=m2情形下的相对搜索空间变化曲线图Fig. 6 Solution space change in the case of n=m2

2.4 分情形下的相对解空间大小分析

2.4.1 Stirling公式

相对解空间表达式中出现阶乘项，增加了相应的分析和对比运算，而我们在此要讨论的是m、n取较大正整数时相对解空间的变化属性，因此本文用Stirling公式来近似化简分式[14](当n取充分大的正整数时，用多项式代替阶乘运算)，图8为阶乘项和等价的多项式项的变化示意图。Stirling公式为

2.4.2 n=10m时相对解空间分析

当n=10m时：

图7 情形下的相对搜索空间变化曲线图Fig. 7 Solution space change in the case of

图8 n!与变化示意图

式（8）是一个关于m的分式，可分为3个部分。当m取较大值时，第一部分可以用近似代替，第二部分是幂指数次项，在m较大时可以用代替，第三部分可以化简为。在这三项中，增长速度主要体现在第二项和第三项幂指数项，也就是说，我们评价整个代数表达式随着m的增大其增长速度可以用第二项和第三项代替。

在计算机程序设计中，衡量一个算法的好坏，通常会用到时间复杂度和空间复杂度。性按照某一速度增长。它只表示增长的速度(Order)，这个时间或空间复杂度并不是与程序复杂性严格相等的数学表达式，它只抽象表示增长速度的类型，通常用大O表示法。本文中的解空间的大小也称为空间复杂度，也同样用算法设计中的空间复杂度表示法(大O表示法)来衡量本文中讨论的3种染色体设计方案的相对解空间。

因增长速度主要体现在第二项和第三项幂指数项，也就是说，我们评价整个代数表达式随着m的增大其增长速度可以用第二项和第三项代替。于是，式(8)化简结果为

同样

当m取较大正整数时，指数项可以用二项展开式的前两项近似替代，具体过程不在此赘述，以下相似替代过程将不特殊说明，式(11)化简为

则该等式可表示为

对于C12同样可得到：

则该等式可表示为

由前两个关系式：

用等式(17)除以等式(16)可得

2.4.3 平方关系下的相对解空间分析

上一小节讨论了3种染色体方案在城市数目与旅行商人数为线性关系时，解空间的相对大小关系，实际上，在线性关系n=km下，系数k代表的是平均每个商人访问的城市数目。因此讨论相对解空间时，让m逐渐递增时，k是作为常数处理的，也就是说，平均每个商人访问的城市数目是大体不变的。在现实的工程问题中，随着工程规模的增加，即待访问城市数目的急剧增多，旅行商的人数也应该随之增加。考虑这个实际问题时，不应该单纯依靠旅行商人数的增加来完成所有城市的访问，也应该随着城市的增加，相应地增大每个商人的工作负载，即访问城市的数目。于是，我们应该找到一个函数来表示城市数目和旅行商人数的关系，满足随着城市数目的增多，旅行商人数也随之增加，同时平均每个商人访问的城市数目也随之相应增加。考虑到城市数与旅行商人数的关系和商人访问城市效率的不同，本文选择两种常见的不同增速关系，即二次幂函数与指数增长关系。

本节讨论n与m在二次函数关系下相对解空间的收敛速度。

将 n=m2代入式（19）：

同样用二项展开式的前两项去近似代替指数项部分，式（19）可简化为

同样将n=m2代入式（22）：

式（22）的增长速度仍取决于第二项的幂指数项，所以式（22）关系可表示为

童话大王郑渊洁说：“写童话，我不如孩子！”童话大王为什么这么说呢？大概是因为随着年龄的增长，人的认识越来越理性。人越来越成熟，而童真童趣却离我们越来越远。也许，在你三岁的时候，你会说出“风把嗓子哭哑了”这样的句子，而现在却只能说出“狂风怒吼”这样的成语……想要找回自己的童真童趣，一定有很多办法。今天老师要介绍的方法就是：在比你更小的小小孩身上去寻找自己的童年。你有三四岁的小弟弟小妹妹吗？请观察他们，记录他们的行为、他们的语言……持续观察一些日子，你一定会有所收获的。

继而将n=m2代入C12化简得到

2.4.4 指数关系下的相对解空间分析

本节讨论n与m在指数函数关系下相对解空间的收敛速度。

将 n=em代入式（4）：

同样将n=em代入式（5）得

式(28)的增长速度仍是取决于第二项的幂指数项，所以式（28）关系可表示为

继而将n=em代入C12化简得到：

3 结束语

本文首先介绍了多旅行商问题的概念和3种染色体编码方案，已有文献只是定性地给出3种编码方案对应解空间的大小关系，并没有给出严格证明。本文首先给出相对解空间的概念，然后在城市数充分大和城市数大于旅行商人数的条件下，在极限意义下严格证明了3种解空间的相对大小关系，最后利用Stirling公式严密分析了几种染色体编码方案中旅行商人数和城市数目在不同关系下相对解空间的大小，得出了相对解空间的理论增长速度，给实际工程问题求解中染色体编码方案的选择提供了科学的参考依据和指导意义。

基于3种染色体方案求解多旅行商问题的相对解空间大小关系分析，就目前方案给出的解空间仍然有冗余解存在。两段式染色体方案在单染色体方案和双染色体方案基础之上消除了相当大的一部分冗余，虽然没有完全消除，但是给了我们很大启发，去寻找更加合理的新的染色体编码方案以进一步减小解空间的冗余。