第13卷第5期 智能系统学报 Vol.13 No.5 2018年10月 CAAI Transactions on Intelligent Systems Oct.2018 D0:10.11992/tis.201706061 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180423.0946.002.html 遗传算法求解多旅行商问题的相对解空间分析 赵新超，郭赛 (北京邮电大学理学院，北京100876) 摘要：首先介绍了多旅行商问题的模型，并指出遗传算法解决多旅行商问题的关键是染色体编码方案的设 计，为了诚少冗余解带来的代价，本文给出了传统的两种染色体编码方案（单染色体和双染色体），以及最新的 两段式染色体编码方案；接着引入相对解空间概念，以此定量地给出不同染色体方案对应解空间的相对大小关 系：基于相对解空间概念，本文分析了3种染色体编码方案对应的解空间在极限意义下的相对大小关系，并分 析了旅行商数与城市数在不同情形下解空间的近似相对大小关系。本文对搜索空间定量分析的理论结果对工 程问题的求解提供了科学的指导意义。 关键词：多旅行商问题：遗传算法：染色体编码：相对解空间：Stirling公式 中图分类号：0224：TP18文献标志码：A文章编号：1673-4785(2018)05-0760-09 中文引用格式：赵新超，郭赛.遗传算法求解多旅行商问题的相对解空间分析.智能系统学报，2018,13（⑤）：760-768. 英文引用格式：ZHAO Xinchao,.GUO Sai.Analysis on the relative solution space for MTSP with genetic algorithm[J.CAAI trans- actions on intelligent systems,2018,13(5):760-768. Analysis on the relative solution space for MTSP with genetic algorithm ZHAO Xinchao,GUO Sai (School of Science,Beijing University of Posts and Telecommunications,Beijing 100876,China) Abstract:This paper introduces the concept of multiple traveling salespersons problem(MTSP)and a chromosome en- coding design method for solving the MTSP using genetic algorithm.In order to reduce the cost of redundant solution, two traditional chromosome design methods(single and double chromosome designs)are proposed,as well as the cur- rent two-part chromosome encoding design.Then the concept of relative solution space is introduced to quantitatively compare the relative size order of spaces for different solutions.Then on based on the relative solution space,the relat- ive size order of the solution spaces of three chromosome-encoding designs are analyzed under an infinite limit.Sub- sequently,the relative size order of the solution spaces is analyzed individually when the relationship presents different situations between the number of travelers and the number of cities.The theoretical results of the quantitative analysis on the search space given in this paper are of great significance in guiding engineering applications and solving practic- al problems. Keywords:multiple traveling salespersons problem;genetic algorithm;chromosome encoding;relative solution space; Stirling formula 多旅行商问题(multiple traveling salesman 商访问一次且只访问一次，如何安排m(大于1)位 problem,MTSP)可直观描述为一个旅行商团队要 旅行商遍历（大于m)个城市，使得总的访问行程 分头遍历若干个城市，每个城市至少被一个旅行 最小"。该问题最常见的应用领域是车间调度领 收稿日期：2017-06-17.网络出版日期：2018-04-23 域，在生产线上的作业调度通常被建模为一个旅 基金项目：国家自然科学基金项目(61375066,11671052， 行商问题(traveling salesman problem,TSP)。如果 71772060). 通信作者：郭赛.E-mail:saisaismily(@l63.com. 生产经营扩展到有多条平行线，工作可以分配
DOI: 10.11992/tis.201706061 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180423.0946.002.html 遗传算法求解多旅行商问题的相对解空间分析 赵新超，郭赛 （北京邮电大学 理学院，北京 100876） 摘 要：首先介绍了多旅行商问题的模型，并指出遗传算法解决多旅行商问题的关键是染色体编码方案的设 计，为了减少冗余解带来的代价，本文给出了传统的两种染色体编码方案 (单染色体和双染色体)，以及最新的 两段式染色体编码方案；接着引入相对解空间概念，以此定量地给出不同染色体方案对应解空间的相对大小关 系；基于相对解空间概念，本文分析了 3 种染色体编码方案对应的解空间在极限意义下的相对大小关系，并分 析了旅行商数与城市数在不同情形下解空间的近似相对大小关系。本文对搜索空间定量分析的理论结果对工 程问题的求解提供了科学的指导意义。 关键词：多旅行商问题；遗传算法；染色体编码；相对解空间；Stirling 公式 中图分类号：O224；TP18 文献标志码：A 文章编号：1673−4785(2018)05−0760−09 中文引用格式：赵新超, 郭赛. 遗传算法求解多旅行商问题的相对解空间分析[J]. 智能系统学报, 2018, 13(5): 760–768. 英文引用格式：ZHAO Xinchao, GUO Sai. Analysis on the relative solution space for MTSP with genetic algorithm[J]. CAAI transactions on intelligent systems, 2018, 13(5): 760–768. Analysis on the relative solution space for MTSP with genetic algorithm ZHAO Xinchao，GUO Sai (School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China) Abstract: This paper introduces the concept of multiple traveling salespersons problem (MTSP) and a chromosome encoding design method for solving the MTSP using genetic algorithm. In order to reduce the cost of redundant solution, two traditional chromosome design methods (single and double chromosome designs) are proposed, as well as the current two-part chromosome encoding design. Then the concept of relative solution space is introduced to quantitatively compare the relative size order of spaces for different solutions. Then on based on the relative solution space, the relative size order of the solution spaces of three chromosome-encoding designs are analyzed under an infinite limit. Subsequently, the relative size order of the solution spaces is analyzed individually when the relationship presents different situations between the number of travelers and the number of cities. The theoretical results of the quantitative analysis on the search space given in this paper are of great significance in guiding engineering applications and solving practical problems. Keywords: multiple traveling salespersons problem; genetic algorithm; chromosome encoding; relative solution space; Stirling formula 多旅行商问题 (multiple traveling salesman problem，MTSP) 可直观描述为一个旅行商团队要 分头遍历若干个城市，每个城市至少被一个旅行 商访问一次且只访问一次，如何安排 m(大于 1) 位 旅行商遍历 n(大于 m) 个城市，使得总的访问行程 最小[1]。该问题最常见的应用领域是车间调度领 域，在生产线上的作业调度通常被建模为一个旅 行商问题 (traveling salesman problem，TSP)。如果 生产经营扩展到有多条平行线，工作可以分配， 收稿日期：2017−06−17. 网络出版日期：2018−04−23. 基金项目：国家自然科学基金项 目 (61375066， 11671052， 71772060). 通信作者：郭赛.E-mail：saisaismily@163.com. 第 13 卷第 5 期 智 能 系 统 学 报 Vol.13 No.5 2018 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2018
第5期 赵新超，等：遗传算法求解多旅行商问题的相对解空间分析 ·761· 这个问题可以建模为一个多旅行商MTSP四：另一 数m=4时染色体编码的一种设计方法的一个实 个经常被建模为多旅行商问题的就是车辆调度问 例。这种设计使用了一个染色体编码长度为 题(VSP)。车辆调度问题是指对一些车辆进行 n+m-l的染色体，因此被称为“单染色体(one 调度，所有的车辆离开并回到原地点，使得每个 chromosome)设计。该设计方案中，n个城市用 地方只能而且必须被访问一次。 从1~n正整数编码表示，并进行无规则的排列，代 由于多旅行商问题的复杂性，必须根据实际 表着n个城市的整数编码列被-1~-(m-1)这 问题的大小采用启发式解决方案。遗传算法 -1个负整数分为m段，分别依次对应着有序的 (genetic algorithms,,GA)是一种基于生物自然选 m个旅行商所访问的城市，因此这个长度为 择和基因遗传学原理的高效并行、随机全局优化 +m-1的整数列的任何一种排列组合都可能是这 搜索算法。Keshavarz等l学者发现遗传算法对调 个MTSP问题的解。以图1为例，第一个旅行商 度问题有很强的适应性，MTSP有效的遗传算子 将访问编号为2、5、14、6的这几座城市，第二个 也激发了研究者的极大兴趣；张永库等研究了 旅行商将访问编号为1、11、8、13的这几座城市， 改进的遗传算法在模糊聚类中的表现；Kataya- 依次类推。在这种染色体设计中，MTSP所有问 ma等⑧提出的混合变异遗传算法在旅行商问题中 题的解将可能是由(n+m-1)!个解构成的一个空 间。这些解中有很多是冗余的，例如，旅行商1与 的应用提高了遗传算法解决旅行商问题的性能。 旅行商2的访问城市全部按顺序相互调换位置后 多旅行商问题在实际问题中有很广泛的应用。 的解和现有解。 Huang等研究了多旅行推销员问题在热轧规划 城市 中的应用：江贺等研究了近年来出现的新NP 251461111813-24103-3121597 难解问题，即黑白旅行商问题(BWTSP),给出了 遗传算法解决问题的一种新思想；Trigui等提 旅行商1 旅行商2 旅行商3 旅行商4 出一种解决多机器人系统多目标多旅行椎销员问 图1单染色体方案 题的模糊逻辑方法。最近出现了多种解决TSP Fig.1 One chromosome 问题的方法，王宇平等提出的求解TSP的量子 1.2 双染色体设计 遗传算法使用了有关量子方面的知识。研究者们 图2描述了同样一个MTSP问题由遗传算法 也在其他经典优化算法中找到了许多新思想。 中染色体编码方案的另一种设计方法。一般称它 遗传算法求解MTSP的关键是要根据问题设 为“双染色体(two chromosomes)”设计。这种设 计一种好的染色体编码方法，而好的遗传算法染 计使用两个长度为n的染色体表示一个解。图2中， 色体编码方案应该能够从候选解中减少或消除冗 第一个染色体表示n个城市的一组排列，第二个 余的解。冗余解是指以一种以上的方式表示同一 染色体的每一位数对应上面相应的城市，由对应 染色体，并多次出现在种群中的染色体编码方 编码的旅行商来访问。例如，旅行商1访问的城市 式。相同解的多次再现不仅增加了查找空间，而 为5、14、10、15，旅行商2访问的城市为2、8、12、9。 且降低了查找效率。 使用这种编码设计，对应的空间是由lm”个可能 本文首先列出了传统的两个染色体方案（单 的解构成的一个集合。同样，这种编码方案也有 染色体设计方案和双染色体方案)，以及最近提出 许多冗余的解。例如，上述事例解中头两个基 的较新的两段式染色体设计方案；本文引入相对 因位交换位置后得到的解与现有解就是相同的。 城市 解空间概念，以此定量地衡量不同染色体方案给 25146111813410321597 出的相对解空间大小关系，先给出对旅行商数目 和城市数目在趋于无穷时的极限相对大小关系， 旅行商 接下来近似分析了旅行商数目与城市数目在不同 211343244132123 情形下解空间的相对大小关系。 图2双染色体方案 Fig.2 Two chromosomes 13种染色体方案 131 两段式染色体设计 MTSP染色体的设计主要有以下3种山。 图3描述了一个新的染色体设计方案，它 1.1单染色体设计 由前后两个部分组成，因此称为“两段式染色体 图1描述了MTSP问题城市数n=15、旅行商 (two-part chromosome)”设计。前段是整数l~n
这个问题可以建模为一个多旅行商 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.2 双染色体设计 图 2 描述了同样一个 MTSP 问题由遗传算法 中染色体编码方案的另一种设计方法。一般称它 为“双染色体 (two chromosomes)”设计。这种设 计使用两个长度为 n 的染色体表示一个解。图 2 中， 第一个染色体表示 n 个城市的一组排列，第二个 染色体的每一位数对应上面相应的城市，由对应 编码的旅行商来访问。例如，旅行商 l 访问的城市 为 5、14、10、15，旅行商 2 访问的城市为 2、8、12、9。 使用这种编码设计，对应的空间是由 n!m n 个可能 的解构成的一个集合。同样，这种编码方案也有 许多冗余的解。例如，上述事例解中头两个基 因位交换位置后得到的解与现有解就是相同的。 1.3 两段式染色体设计 图 3 描述了一个新的染色体设计方案，它 由前后两个部分组成，因此称为“两段式染色体 (two-part chromosome)”设计。前段是整数 l~n 2 5 6 14 −1 1 8 11 13 −2 4 3 10 −3 12 9 7 15 城市 旅行商1 旅行商2 旅行商3 旅行商4 图 1 单染色体方案 Fig. 1 One chromosome 2 5 6 14 1 11 8 4 10 12 13 3 15 9 7 2 1 3 1 4 3 4 2 4 1 2 3 1 2 3 城市 旅行商 图 2 双染色体方案 Fig. 2 Two chromosomes 第 5 期 赵新超，等：遗传算法求解多旅行商问题的相对解空间分析 ·761·
·762· 智能系统学报 第13卷 的一个排列，代表了n个城市的一个顺序排列；后 m的取值范围是正整数，且一般m<(旅行商人数 段长度为m,按顺序分别表示m个旅行商在前段 小于城市数)。 编码中对应访问的城市数，并且这m个数之和等 式(1)~(3)按大小排序有：C2m<Ce<C四 于n。图3所示旅行商1访问前段中的头4个城 (>m),这几个代数式给出的解空间大小从数量上 市顺序分别为2、5、14、6；旅行商3访问从第 来讲是对解空间的绝对衡量，假若将其两两作比 4+4+1个开始的连续3个城市，分别为4、10、3。 值运算（较大的作分母），得到的结果是个相对值， 使用新的两段式染色体设计，不仅减少了查找空 当m和n取较大的正整数时，比值结果是一个小 间，而且由于固定了旅行商的顺序而消除了部分 于1的真分数，我们称之为“相对解空间”，分别 (但不是全部的)冗余的解。使用这种染色体编码 用C1、C2和C2表示，即 设计，对于前段可能会有种排列，后段由于是 n!C (4) 一个和为n的正整数向量，因此需要C种可能 C1=C= (m+n-1)H 的m维正整数表示，才能满足要求。从而，可以 -Ca-pnnC C2= (5) 得到解空间大小为C。 n!' 每个旅行商 Come (m+n-1)! 城市 经过的城市数 C2= (6) Ctwo n!m" 25146183410325974434 2.2相对解空间的极限分析 旅行商1 旅行商2 旅行商3 旅行商4 在现实的工程应用中，比如车辆调度问题，m、 n一般取值较大，因此随着自变量的增大或问题 规模的扩大，我们需要了解相对解空间对应的比 图3两段式染色体方案 值结果的变化趋势，从而从数学表达式中讨论 Fig.3 Two-part chromosome m和n取较大正整数时，相对解空间的极限行为， 23种染色体编码方案下的相对解空 也可以认为是讨论m、n趋于无穷时的极限。 间分析 2.2.1C31的极限分析 上一节介绍了遗传算法求解多旅行商问题 1)m适当大时 的3种染色体编码方案。文献[]给出了3种染色 在多旅行商问题中，城市数目与旅行商数目 体编码方案对应的搜索空间的大小，仅是定性分 之间的差距一般都比较大，因此当讨论C31的极 析了3种方案的优劣，即两段式染色体方案对应 限性质时，不妨假设n多m,当n充分大、m应适当 的解空间优于前两种编码方案对应的解空间，而 大时，对C31取对数，分析可得： 第一种单染色体设计方案优于双染色体编码方 案。如果只是定性地了解3种编码方案对应解空 间大小关系，对染色体编码方案和算法设计以及 实际工程应用并没有太大的指导意义。因此本文 首先引入相对解空间概念，然后详细地定量分析 了3种染色体方案对应的解空间相对大小，这对 hk- 多旅行商问题的研究和求解具有现实的指导意义。 2.1相对解空间 3种染色体编码方案对应的解空间大小山分 别为 C31 e-ln(m-1)! 0m-1月 Come=(m+n-l)！ (1) 所以C31<1。 Ctwo=n!m" (2) C,<1意味着第三种编码方案对应的解空间 C2-pn =nCm (3) 严格小于第一种方案对应的解空间，这严格证明 式中：Co表示单染色体编码对应的解空间规模， 了Carter!给出的解空间的定性比较结果。当 Cw。表示双染色体编码对应的解空间规模，C2 n足够大时，所需的旅行商数也有相应增大，因此 表示两段式染色体解空间的规模。从3种编码方 当n充分大、m适当大时，C1《1。例如：m=10, 案解空间的代数表达式可以看出，它们都是城市 C1<ea≈2.76x10-。 数n和旅行商数目m的二元函数，自变量n和 2)m是不大的常数时
C m−1 n−1 C m−1 n−1 的一个排列，代表了 n 个城市的一个顺序排列；后 段长度为 m，按顺序分别表示 m 个旅行商在前段 编码中对应访问的城市数，并且这 m 个数之和等 于 n。图 3 所示旅行商 l 访问前段中的头 4 个城 市顺序分别为 2、5、l4、6；旅行商 3 访问从第 4+4+1 个开始的连续 3 个城市，分别为 4、10、3。 使用新的两段式染色体设计，不仅减少了查找空 间，而且由于固定了旅行商的顺序而消除了部分 (但不是全部的) 冗余的解。使用这种染色体编码 设计，对于前段可能会有 n!种排列，后段由于是 一个和为 n 的正整数向量，因此需要 种可能 的 m 维正整数表示，才能满足要求。从而，可以 得到解空间大小为 。 2 3 种染色体编码方案下的相对解空 间分析 上一节介绍了遗传算法求解多旅行商问题 的 3 种染色体编码方案。文献[1]给出了 3 种染色 体编码方案对应的搜索空间的大小，仅是定性分 析了 3 种方案的优劣，即两段式染色体方案对应 的解空间优于前两种编码方案对应的解空间，而 第一种单染色体设计方案优于双染色体编码方 案。如果只是定性地了解 3 种编码方案对应解空 间大小关系，对染色体编码方案和算法设计以及 实际工程应用并没有太大的指导意义。因此本文 首先引入相对解空间概念，然后详细地定量分析 了 3 种染色体方案对应的解空间相对大小，这对 多旅行商问题的研究和求解具有现实的指导意义。 2.1 相对解空间 3 种染色体编码方案对应的解空间大小[1]分 别为 Cone = (m+n−1)! (1) Ctwo = n!m n (2) C2-part = n!C m−1 n−1 (3) C2-part 式中：Cone 表示单染色体编码对应的解空间规模， Ctwo 表示双染色体编码对应的解空间规模， 表示两段式染色体解空间的规模。从 3 种编码方 案解空间的代数表达式可以看出，它们都是城市 数 n 和旅行商数目 m 的二元函数，自变量 n 和 m 的取值范围是正整数，且一般 m<n(旅行商人数 小于城市数)。 式 (1)～(3) 按大小排序有： C2-part < Cone <Ctwo [1] (n>m)，这几个代数式给出的解空间大小从数量上 来讲是对解空间的绝对衡量，假若将其两两作比 值运算 (较大的作分母)，得到的结果是个相对值， 当 m 和 n 取较大的正整数时，比值结果是一个小 于 1 的真分数，我们称之为“相对解空间”，分别 用 C31、C32 和 C12 表示，即 C31 = C2-part Cone = n!C m−1 n−1 (m+n−1)! (4) C32 = C2−part Ctwo = n!C m−1 n−1 n!mn (5) C12 = Cone Ctwo = (m+n−1)! n!mn (6) 2.2 相对解空间的极限分析 在现实的工程应用中，比如车辆调度问题，m、 n 一般取值较大，因此随着自变量的增大或问题 规模的扩大，我们需要了解相对解空间对应的比 值结果的变化趋势，从而从数学表达式中讨论 m 和 n 取较大正整数时，相对解空间的极限行为， 也可以认为是讨论 m、n 趋于无穷时的极限。 2.2.1 C31 的极限分析 1) m 适当大时 n ≫ m 在多旅行商问题中，城市数目与旅行商数目 之间的差距一般都比较大，因此当讨论 C31 的极 限性质时，不妨假设 ，当 n 充分大、m 应适当 大时，对 C31 取对数，分析可得： ln C31 = ∑n k=1 ln k+ ∑n−1 k=1 ln k− m∑+n−1 k=1 ln k− ∑n−m k=1 ln k− ∑m−1 k=1 ln k = ∑n k=1 ln k+ ∑n−1 k=1 ln k− ∑n−1 k=1 ln k+ n∑+m−1 k=n ln k − ∑n k=1 ln k− ∑n k=n−m+1 ln k − ∑m−1 k=1 ln k = − n∑+m−1 k=n ln k+ ∑n k=n−m+1 ln k− ∑m−1 k=1 ln k− < ∑m−1 k=1 ln k < 0 C31 = e −ln(m−1)! = 1 (m−1)! 所以 C31<1。 C31 ≪ 1 C31 < e − ∑9 k=1 lnk ≈ 2.76×10−6 C31<1 意味着第三种编码方案对应的解空间 严格小于第一种方案对应的解空间，这严格证明 了 Carter[ 1 ]给出的解空间的定性比较结果。当 n 足够大时，所需的旅行商数也有相应增大，因此 当 n 充分大、m 适当大时， 。例如：m=10， 。 2) m 是不大的常数时 2 5 6 14 1 11 8 4 10 12 13 3 15 9 47 4 3 4 城市 每个旅行商 经过的城市数 旅行商1 旅行商2 旅行商3 旅行商4 图 3 两段式染色体方案 Fig. 3 Two-part chromosome ·762· 智 能 系 统 学 报 第 13 卷
第5期 赵新超，等：遗传算法求解多旅行商问题的相对解空间分析 ·763· (n-1)1可与(+m-1)1相抵消，n可与(n-m)相 C2<1。C2的大小说明第一种编码方案对应的解 抵消，所以当n趋于无穷时得出： 空间小于第二种编码方案对应的解空间。 n!n-1! 1 至此，在合理适当的条件下：n适当大，对 =n+m-1)!n-m!(0m-1)！→0m-11 3种解空间的相对大小给出详细严密的论证，很 即当旅行商人数m取不大的常数时，随着城市数 好地补充了文献[1]中定性的结论，即C。> 目的增加，单染色体编码方案对应的空间约是两 Cme>C2a,而且由分析可知，当n充分大、m适当 段式染色体方案解空间的(m-1)！倍，此结果与两 大时，Co多Coae多C2paio 种解空间的极限分析是一致的。 以上分析中，对一般的m和n给出的是相对 2.2.2C2的极限分析 1)m适当大时 解空间理论上的对比，但是如果只知道相对大 小，对实际问题应用几乎没有实质性的帮助，例 依然假设n多m,当n充分大、m适当大时，取 对数分析可得： 如求C31的极限，实质上m为常数，n逐渐增大， 也就是说，在某一个多旅行商问题中，我们保持 商人的数目不变，增大工程的规模，让城市数目 hk-m- 逐渐增大，这也就意味着单个商人访问的城市数 ∑nk 目随着城市数目的增多而无限增加下去，这显然 =1 艺nk中有m1项，通项是城市数n的对 不符合实际情况，因为每个旅行商访问的城市数 目是有上限的，即最大负荷能力。因此单一用这 数，而nlnm中有n项，lnm是旅行商数目的对 个极限结果去估计解空间的大小，虽然能得出严 数，并且当n充分大时，lim =+o141,所以 密的定量分析结果，但是其代表的实际意义是不 乏片面性的。 当n→o时， lnk-nlnm<0。因为 我们不仅需要知道染色体编码方案C2-对应 Ink-nlnm<(m-1)-In (n-1)-nlnm< 的解空间小，更重要的是需要知道到底小多少， mln n-nln m<O 这也是本文最初的研究目的。通过研究发现，对 m-1 一般性的m和n,很难给出解空间的具体差距，因 所以，nC2<-∑hk<0,即C2<l。 此本文在旅行商数m与城市数n之间成几种典型 C32<1同样意味着第三种编码方案对应的解 函数关系的条件下给出相对解空间的差距，包括 空间小于第二种方案对应的解空间。同C1的分 城市数n与旅行商数m的线性关系、幂函数关系 析类似，当n足够大、m适当大时，C2《1。 和指数关系。 2)m是不大的常数时 2.3相对搜索空间的粗略估计 Cn=Cum=C (n-1)月 Ciwo 图4描述了15个城市，是旅行商数量从1增 n!m(m-1)！(n-m)m (n-1)(n-2)…(n-m+1) 加到14时，3种染色体编码设计的搜索空间的变 (m-1)!m" (m-1)m 化示意图。图4的纵轴表示搜索空间的数量级。 由此可知，C<m-1° 1 由图4可以看出，在旅行商逐步增加的情况下，单 由对C2的分析可知，当m取大于2的常数 染色体编码对应的搜索空间数量的增加由快到 时，C2<1。此结果显示，第三种编码方案对应的 慢；双染色体编码对应的搜索空间数量的增加比 解空间小于第二种编码方案对应的解空间，此结 较平稳；而两段式染色体编码对应的搜索空间数 果与两种解空间的极限分析是一致的。 量呈现两端相当、中间略微增加的大体对称的情 2.2.3C2的极限分析 况。因此图4与2.2节的解空间分析结果显示出 假设nm,当n充分大、m,适当大时，对 了两段式染色体编码设计的初步优越性。 C2取对数，即 众所周知，当城市数目逐步增加时，旅行商人 In C2= ∑nk-nk-血m=nk-血m 数也应该相应增加，而m一般会随n的变化而变 k=1 k=+1 化。以下详细讨论m与n有特定关系时的相对搜 (m-1)In (n+m-1)-nln m 索空间。例如：n=10m,=m2,n=e"三种情形下，相 当n充分大时，limIn n -=+oo,因此nC2<0, 对搜索空间的变化趋势
(n–1)!可与 (n+m–1)!相抵消，n!可与 (n–m)!相 抵消，所以当 n 趋于无穷时得出： C31 = Ct-part Cone = n!n−1! (n+m−1)!(n−m)!(m−1)! → 1 (m−1)! 即当旅行商人数 m 取不大的常数时，随着城市数 目的增加，单染色体编码方案对应的空间约是两 段式染色体方案解空间的 (m–1)！倍，此结果与两 种解空间的极限分析是一致的。 2.2.2 C32 的极限分析 1)m 适当大时 依然假设n ≫ m，当 n 充分大、m 适当大时，取 对数分析可得： ln C32 = ∑n−1 k=1 ln k− ∑n−m k=1 ln k−nln m− ∑m−1 k=1 ln k = ∑n−1 k=n−m+1 ln k−nln m− ∑m−1 k=1 ln k ∑n−1 k=n−m+1 ln k limn→∞ n ln n = +∞ n → ∞ ∑n−1 k=n−m+1 ln k−nln m < 0 中有 m-1 项，通项是城市数 n 的对 数 ，而 nln m 中有 n 项 ，ln m 是旅行商数目的对 数，并且当 n 充分大时， [14] ，所以 当 时， 。因为 n∑−1 k=n−m+1 ln k−nln m < (m−1)·ln (n−1)−nln m < mln n−nln m < 0 C32 < − ∑m−1 k=1 所以，ln ln k < 0，即 C32<1。 C32 ≪ 1 C32<1 同样意味着第三种编码方案对应的解 空间小于第二种方案对应的解空间。同 C31 的分 析类似，当 n 足够大、m 适当大时， 。 2)m 是不大的常数时 C32 = Ct-part Ctwo = n!C m−1 n−1 n!mn = (n−1)! (m−1)!(n−m)!mn = (n−1) (n−2)···(n−m+1) (m−1)!mn < n m (m−1)!mn C32 < 1 (m−1)! 由此可知， 。 由对 C32 的分析可知，当 m 取大于 2 的常数 时，C32< 1。此结果显示，第三种编码方案对应的 解空间小于第二种编码方案对应的解空间，此结 果与两种解空间的极限分析是一致的。 2.2.3 C12 的极限分析 假设n ≫ m ，当 n 充分大、 m，适当大时，对 C12 取对数，即 ln C12 = n∑+m−1 k=1 ln k− ∑n k=1 ln k−nln m = n∑+m−1 k=n+1 ln k−nln m < (m−1)ln (n+m−1)−nln m limn→∞ n ln n 当 n 充分大时， = +∞，因此 ln C12 < 0 ， C12 < 1。C12 的大小说明第一种编码方案对应的解 空间小于第二种编码方案对应的解空间。 Ctwo > Cone > C2-part Ctwo ≫ Cone ≫ C2-part 至此，在合理适当的条件下： n 适当大，对 3 种解空间的相对大小给出详细严密的论证，很 好地补充了文献 [ 1 ] 中定性的结论，即 ，而且由分析可知，当 n 充分大、m 适当 大时， 。 以上分析中，对一般的 m 和 n 给出的是相对 解空间理论上的对比，但是如果只知道相对大 小，对实际问题应用几乎没有实质性的帮助，例 如求 C31 的极限，实质上 m 为常数，n 逐渐增大， 也就是说，在某一个多旅行商问题中，我们保持 商人的数目不变，增大工程的规模，让城市数目 逐渐增大，这也就意味着单个商人访问的城市数 目随着城市数目的增多而无限增加下去，这显然 不符合实际情况，因为每个旅行商访问的城市数 目是有上限的，即最大负荷能力。因此单一用这 个极限结果去估计解空间的大小，虽然能得出严 密的定量分析结果，但是其代表的实际意义是不 乏片面性的。 我们不仅需要知道染色体编码方案 C2−part 对应 的解空间小，更重要的是需要知道到底小多少， 这也是本文最初的研究目的。通过研究发现，对 一般性的 m 和 n，很难给出解空间的具体差距，因 此本文在旅行商数 m 与城市数 n 之间成几种典型 函数关系的条件下给出相对解空间的差距，包括 城市数 n 与旅行商数 m 的线性关系、幂函数关系 和指数关系。 2.3 相对搜索空间的粗略估计 图 4 描述了 l5 个城市，是旅行商数量从 l 增 加到 14 时，3 种染色体编码设计的搜索空间的变 化示意图。图 4 的纵轴表示搜索空间的数量级。 由图 4 可以看出，在旅行商逐步增加的情况下，单 染色体编码对应的搜索空间数量的增加由快到 慢；双染色体编码对应的搜索空间数量的增加比 较平稳；而两段式染色体编码对应的搜索空间数 量呈现两端相当、中间略微增加的大体对称的情 况。因此图 4 与 2.2 节的解空间分析结果显示出 了两段式染色体编码设计的初步优越性。 众所周知，当城市数目逐步增加时，旅行商人 数也应该相应增加，而 m 一般会随 n 的变化而变 化。以下详细讨论 m 与 n 有特定关系时的相对搜 索空间。例如：n=10m，n=m 2 ，n=e m 三种情形下，相 对搜索空间的变化趋势。 第 5 期 赵新超，等：遗传算法求解多旅行商问题的相对解空间分析 ·763·
·764· 智能系统学报 第13卷 30 C31和C2在前期的差别不大，纵轴随着m的增大 6 -+-C 很快收敛，且C2在n=m2情形下比在n=10m情形 24 下收敛得更快些；在n=e"情形下C2相对搜索空 22 间和C12相对搜索空间比其他两种情形收敛更 快，但C1在前期收敛得有些缓慢，而在n=e"情形 16 下明显比其他两种情形收敛更快。从同一情形下 看3种相对搜索空间的变化时，可以看出C1、 12 10 C2和C2都是纵轴随着m的增大很快收敛，C32 旅行商m的数量/个 和C2收敛较快些，在m≤6时就能定性地看出收 图4解空间变化示例 敛；C!收敛最慢，在m取较大值时能判断出也是 Fig.4 Example of solution space change 收敛的。从两种判断方法中我们能够看出收敛， 从图57所示的3组函数图像可以看出，3种 但是很难直观地从函数图像上直接看出m取较 情形下的相对搜索空间变化，总体来说，从相对 大值时的收敛状况，也即只能定性得出收敛的结 搜索空间上比较，在n=10m和n=m2情形下， 论，这与前面的结论亦是吻合的。 1.0 1.0 1.0 0.8 0.8 0.8 0.6 0.6 0.6 0.4 0.4 0.4 0.2 0.2 0.2 234 5 60 2 34 5 60 1 2 3 4 5 旅行商数m个 旅行商数m/个 旅行商数m个 (a)C1随m变化的曲线 (b)C2随m变化的曲线 (c)C2随m变化的曲线 图5=10m情形下的相对搜索空间变化曲线图 Fig.5 Solution space change in the case of n=10 m 1.0 1.0 1.0 0.8 0.8 0.8 0.6 0.6 0.6 C 0.4 0.4 0.4 0.2 0.2 0.2 2 3 5 6 0 2 3 4 5 60 2 3 4 5 6 旅行商数m个 旅行商数m/个 旅行商数m个 (a)C,随m变化的曲线 (b)C2随m变化的曲线 (c)C2随m变化的曲线 图61=m情形下的相对搜索空间变化曲线图 Fig.Solution space change in the case of 2.4分情形下的相对解空间大小分析 为阶乘项和等价的多项式项的变化示意图。 2.4.1 Stirling公式 Stirling公式为 相对解空间表达式中出现阶乘项，增加了相 n! 应的分析和对比运算，而我们在此要讨论的是 imn→w (7) m、n取较大正整数时相对解空间的变化属性，因 此本文用Stirling公式来近似化简分式（当n取 2.4.21=10m时相对解空间分析 充分大的正整数时，用多项式代替阶乘运算)，图8 当n=10m时：
从图 5~7 所示的 3 组函数图像可以看出，3 种 情形下的相对搜索空间变化，总体来说，从相对 搜索空间上比较， 在 n=10m 和 n=m 2 情形下， C31 和 C32 在前期的差别不大，纵轴随着 m 的增大 很快收敛，且 C12 在 n=m 2 情形下比在 n=10m 情形 下收敛得更快些；在 n=e m 情形下 C32 相对搜索空 间和 C1 2 相对搜索空间比其他两种情形收敛更 快，但 C31 在前期收敛得有些缓慢，而在 n=e m 情形 下明显比其他两种情形收敛更快。从同一情形下 看 3 种相对搜索空间的变化时，可以看出 C3 1、 C32 和 C12 都是纵轴随着 m 的增大很快收敛，C32 和 C12 收敛较快些，在 m≤6 时就能定性地看出收 敛；C31 收敛最慢，在 m 取较大值时能判断出也是 收敛的。从两种判断方法中我们能够看出收敛， 但是很难直观地从函数图像上直接看出 m 取较 大值时的收敛状况，也即只能定性得出收敛的结 论，这与前面的结论亦是吻合的。 2.4 分情形下的相对解空间大小分析 2.4.1 Stirling 公式 相对解空间表达式中出现阶乘项，增加了相 应的分析和对比运算，而我们在此要讨论的是 m、n 取较大正整数时相对解空间的变化属性，因 此本文用 Stirling 公式来近似化简分式[14] (当 n 取 充分大的正整数时，用多项式代替阶乘运算)，图 8 Stirling公式为 为阶乘项和等价的多项式项的变化示意图。 limn→∞ n! √ 2πn ( n e )n = 1 (7) 2.4.2 n=10m 时相对解空间分析 当 n=10m 时： 0 5 10 15 12 14 16 18 20 22 24 26 28 30 Cone Ctwo Ct-part 旅行商m的数量/个 数量级 图 4 解空间变化示例 Fig. 4 Example of solution space change (b) C32 随 m 变化的曲线 0 1 2 3 4 5 6 C32 0.2 0.4 0.6 0.8 1.0 旅行商数 m/个 (c) C12 随 m 变化的曲线 0 1 2 3 4 5 6 C12 0.2 0.4 0.6 0.8 1.0 旅行商数 m/个 (a) C31 随 m 变化的曲线 0 1 2 3 4 5 6 C31 0.2 0.4 0.6 0.8 1.0 旅行商数 m/个 图 5 n=10m 情形下的相对搜索空间变化曲线图 Fig. 5 Solution space change in the case of n= 10 m (b) C32 随 m 变化的曲线 0 1 2 3 4 5 6 C32 0.2 0.4 0.6 0.8 1.0 旅行商数 m/个 (a) C31 随 m 变化的曲线 0 1 2 3 4 5 6 C31 0.2 0.4 0.6 0.8 1.0 旅行商数 m/个 (c) C12 随 m 变化的曲线 0 1 2 3 4 5 6 C12 0.2 0.4 0.6 0.8 1.0 旅行商数 m/个 图 6 n=m 2 情形下的相对搜索空间变化曲线图 Fig. 6 Solution space change in the case of n=m 2 ·764· 智 能 系 统 学 报 第 13 卷