【智能系统】遗传算法求解多旅行商问题的相对解空间分析

团购合买资源类别：文库，文档格式：PDF，文档页数：9，文件大小：1.1MB

第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的取值范围是正整数，且一般mm),这几个代数式给出的解空间大小从数量上市顺序分别为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 的取值范围是正整数，且一般 mm)，这几个代数式给出的解空间大小从数量上来讲是对解空间的绝对衡量，假若将其两两作比值运算 (较大的作分母)，得到的结果是个相对值，当 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 目的增加，单染色体编码方案对应的空间约是两 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 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 卷

第5期赵新超，等：遗传算法求解多旅行商问题的相对解空间分析 ·765· C31= C2-pan n!C Cone (m+n-1)！ m+n-】 V2x(m+n-1) e V2πm-1 (8) 5(10m-1) mm-io 1020m-1.em-l W9π(11m-1)m-1) ("-i) (0m-1)m- 11m-l.99m 1.0 1.0 10 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 4 5 0 5 60 2 3 4 5 旅行商数m个旅行商数m个旅行商数m/个 (a)C,随m变化的曲线 (b)C2随m变化的曲线 (c)C2随m变化的曲线图7n=e"情形下的相对搜索空间变化曲线图 Fig.7 Solution space change in the case of n=em 40*10 通常会用到时间复杂度和空间复杂度。性按照某 3.5 一速度增长。它只表示增长的速度(Order),这个 3.0 时间或空间复杂度并不是与程序复杂性严格相等的数学表达式，它只抽象表示增长速度的类型， 2.0 通常用大O表示法。本文中的解空间的大小也 1.5 称为空间复杂度，也同样用算法设计中的空间复 1.0 杂度表示法（大O表示法）来衡量本文中讨论的 0.5 .---Inx! 3种染色体设计方案的相对解空间。 -xlnr-x 0 20 40 60 80 100 因增长速度主要体现在第二项和第三项幂指 x的值数项，也就是说，我们评价整个代数表达式随着图8与v2)变化示意图 m的增大其增长速度可以用第二项和第三项代替。于是，式(8)化简结果为 Diagram of changesiad C31= C2-pan 10 (9) 式(8)是一个关于m的分式，可分为3个部 5(10m-1) 式()的结果可以用) 来代表其收敛速分。当m取较大值时，第一部分 9元(11m-1)(m-1) 度，则该等式可表示为 1110m-1 cw=caog） (10) 可以用近似代替第二部酚 mm-1 同样 2元m m-li) (m-1)m- C32=1 omm=nC (11) n!" 是幂指数次项，在m较大时可以用 m代替，第当m取较大正整数时，指数项可以用二项展三部分10e 开式的前两项近似替代，具体过程不在此赘述， 11m-1.9m 可以化简为em-。在这三项中，以下相似替代过程将不特殊说明，式(11)化简为增长速度主要体现在第二项和第三项幂指数项， C2~ 111010m-1 也就是说，我们评价整个代数表达式随着m的增 V2m'mom9咖 (12) 大其增长速度可以用第二项和第三项代替。则该等式可表示为在计算机程序设计中，衡量一个算法的好坏， Cwo=C2pen·O(mom） (13)

C31 = C2-part Cone = n!C m−1 n−1 (m+n−1)! ∼ √ 2πn ( n e )n √ 2π(n−1) ( n−1 e )n−1 √ 2π(m+n−1) ( m+n−1 e )m+n−1 √ 2π(m−1) ( m−1 e )m−1 √ 2π(n−m) ( n−m e )n−m ∼ √ 5(10m−1) 9π(11m−1) (m−1) · m m ( m− 1 10)10m−1 ( m− 1 11)11m−1 (m−1) m−1 · 1020m−1 · e m−1 1111m−1 · 9 9m (8) √ 5(10m−1) 9π(11m−1) (m−1) √ 1 2πm m m ( m− 1 10)10m−1 ( m− 1 11)11m−1 (m−1) m−1 1 mm−1 1020m−1 · e m−1 1111m−1 · 9 9m e m−1 式（8）是一个关于 m 的分式，可分为 3 个部分。当 m 取较大值时，第一部分可以用近似代替，第二部分是幂指数次项，在 m 较大时可以用代替，第三部分可以化简为。在这三项中，增长速度主要体现在第二项和第三项幂指数项，也就是说，我们评价整个代数表达式随着 m 的增大其增长速度可以用第二项和第三项代替。在计算机程序设计中，衡量一个算法的好坏，通常会用到时间复杂度和空间复杂度。性按照某一速度增长。它只表示增长的速度 (Order)，这个时间或空间复杂度并不是与程序复杂性严格相等的数学表达式，它只抽象表示增长速度的类型，通常用大 O 表示法。本文中的解空间的大小也称为空间复杂度，也同样用算法设计中的空间复杂度表示法 (大 O 表示法) 来衡量本文中讨论的 3 种染色体设计方案的相对解空间。因增长速度主要体现在第二项和第三项幂指数项，也就是说，我们评价整个代数表达式随着 m 的增大其增长速度可以用第二项和第三项代替。于是，式 (8) 化简结果为 C31 = C2-part Cone ∼ √ 1 2πm ( e m )m (9) ( e m )m 式（ 9）的结果可以用来代表其收敛速度，则该等式可表示为 Cone = C2-part ·O ((m e )m) (10) 同样 C32 = C2-part Ctwo = n!C m−1 n−1 n!mn (11) 当 m 取较大正整数时，指数项可以用二项展开式的前两项近似替代，具体过程不在此赘述，以下相似替代过程将不特殊说明，式 (11) 化简为 C32 ∼ √ 1 2πm · 1 m10m · 1010m−1 9 9m (12) 则该等式可表示为 Ctwo = C2-part ·O ( m 10m ) (13) 0 20 40 60 80 100 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 lnx! xlnx−x x 的值所得值 ×102 √ 2πn ( n e )n 图 8 n!与变化示意图 √ 2πn ( n e )n Fig. 8 Diagram of changes in n! and (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/个 n=e 图 m 7 情形下的相对搜索空间变化曲线图 n=e m Fig. 7 Solution space change in the case of 第 5 期赵新超，等：遗传算法求解多旅行商问题的相对解空间分析 ·765·

·766· 智能系统学报第13卷对于C2同样可得到： 2.4.3平方关系下的相对解空间分析 C12= Cme=m+n-1'-(1lm-10川上一小节讨论了3种染色体方案在城市数目 n (10m)m10m 11 与旅行商人数为线性关系时，解空间的相对大小 11m-1 V2π(11m- 1) /1111 关系，实际上，在线性关系n=km下，系数k代表 e 10m V10'mnm'em-可的是平均每个商人访问的城市数目。因此讨论相 V2π(10m 10m 对解空间时，让m逐渐递增时，k是作为常数处理 e (14) 的，也就是说，平均每个商人访问的城市数目是则该等式可表示为大体不变的。在现实的工程问题中，随着工程规 Co=Coe·O(mm.e"） (15) 模的增加，即待访问城市数目的急剧增多，旅行由前两个关系式：商的人数也应该随之增加。考虑这个实际问题 Come=C2pa o() (16) 时，不应该单纯依靠旅行商人数的增加来完成所有城市的访问，也应该随着城市的增加，相应地 Co=C2pm0mo） (17) 增大每个商人的工作负载，即访问城市的数目。用等式(17)除以等式(16)可得于是，我们应该找到一个函数来表示城市数目和 Ce-C2-pam·Oma） Omm.e） (18) 旅行商人数的关系，满足随着城市数目的增多， C-p og 旅行商人数也随之增加，同时平均每个商人访问式(18)等价于Co=Cme·O(mm,e),这与上述的城市数目也随之相应增加。考虑到城市数与旅推导中的等式(15)是吻合的，由此该方法计算三者行商人数的关系和商人访问城市效率的不同，本解空间大小在逻辑上是严密的，从式(15)~(17) 文选择两种常见的不同增速关系，即二次幂函数可知，Co=CoeO(mm.e）=C2ptO(mom),可以看与指数增长关系。出，随着问题规模的逐渐增大，3种编码方案对应本节讨论n与m在二次函数关系下相对解空解空间的差距呈幂指函数的关系。由此可以看间的收敛速度。出，两段式染色体编码方案的优越性。将1=m2代入式(19)： C2-pant nC m21(m2-1)月 C31= Cone (m+n-1)！ (m2+m-1)!(m-1)m2-m √2元m -1 e V2π(m2-万 e (19) 2+m-1 2+m-1 V2π(m2+m-1 V2r (m-1) m-1 V2π(m2-m) m2-m wi-m e e e 同样用二项展开式的前两项去近似代替指数式(22)的增长速度仍取决于第二项的幂指数项部分，式(19)可简化为项，所以式(22)关系可表示为 1 C31~ ·em-l (20) V2元mmm Cwo=C2 panO(m-m） (23) 式(20)的收敛速度主要取决于第二项幂指数继而将n=m代入C12化简得到因式心和第三项，所以式(20)关系可表示为 /r-21m (24) Cm=caog】) 21) (m"-2m 由式21、(23)、24可得C。=Co0e = 同样将=m2代入式(22)： Cu=Comm=ntC (n-1)H C2-pt·O(mm-m,看出在旅行商人数和城市数为二 Ciwo n'm" (m-1)1(n-m)m" 次关系时，双染色体编码对应的解空间是两段式 (m2-1)1 染色体编码对应的解空间的增长速度的m-m倍， (m-11m2-m)m` 2πm-m-la 因此不同染色体编码方案的选择对问题的求解经 e 常起主要的作用，可以指导实际问题的求解。 2.44指数关系下的相对解空间分析 V2π(m-1) m- V2π(0m2-m m2-m w-m e 本节讨论n与m在指数函数关系下相对解空 1 V2π(m-万mm2-m'm 间的收敛速度。 22) 将n=e"代入式(4)：

对于 C12 同样可得到： C12 = Cone Ctwo = m+n−1! nmn = (11m−1)! (10m)!m10m ∼ √ 2π(11m−1) ( 11m−1 e )11m−1 √ 2π(10m) ( 10m e )10m m10m ∼ √ 11 10 · 1 m9m · 1 e m−1 (14) 则该等式可表示为 Ctwo = Cone ·O ( m 9m · e m ) (15) 由前两个关系式： Cone = C2-part ·O ((m e )m) (16) Ctwo = C2-part ·O ( m 10m ) (17) 用等式 (17) 除以等式 (16) 可得 Ctwo Cone = C2−part ·O ( m 10m ) C2−part ·O ((m e )m) = O ( m 9m · e m ) (18) Ctwo = Cone ·O ( m 9m · e m ) Ctwo = Cone ·O ( m 9m · e m ) = C2-part·O ( m 10m ) 式（18）等价于，这与上述推导中的等式 (15) 是吻合的，由此该方法计算三者解空间大小在逻辑上是严密的，从式 (15)～(17) 可知，，可以看出，随着问题规模的逐渐增大，3 种编码方案对应解空间的差距呈幂指函数的关系。由此可以看出，两段式染色体编码方案的优越性。 2.4.3 平方关系下的相对解空间分析上一小节讨论了 3 种染色体方案在城市数目与旅行商人数为线性关系时，解空间的相对大小关系，实际上，在线性关系 n=km 下，系数 k 代表的是平均每个商人访问的城市数目。因此讨论相对解空间时，让 m 逐渐递增时，k 是作为常数处理的，也就是说，平均每个商人访问的城市数目是大体不变的。在现实的工程问题中，随着工程规模的增加，即待访问城市数目的急剧增多，旅行商的人数也应该随之增加。考虑这个实际问题时，不应该单纯依靠旅行商人数的增加来完成所有城市的访问，也应该随着城市的增加，相应地增大每个商人的工作负载，即访问城市的数目。于是，我们应该找到一个函数来表示城市数目和旅行商人数的关系，满足随着城市数目的增多，旅行商人数也随之增加，同时平均每个商人访问的城市数目也随之相应增加。考虑到城市数与旅行商人数的关系和商人访问城市效率的不同，本文选择两种常见的不同增速关系，即二次幂函数与指数增长关系。本节讨论 n 与 m 在二次函数关系下相对解空间的收敛速度。将 n=m 2 代入式（19）： C31 = C2-part Cone = n!C m−1 n−1 (m+n−1)! = m 2 ! ( m 2 −1 ) ! (m2 +m−1)!(m−1)!(m2 −m)! ∼ √ 2πm2 ( m 2 e )m 2 √ 2π(m2 −1)( m 2 −1 e )m 2−1 √ 2π(m2 +m−1) ( m 2 +m−1 e )m2+m−1 √ 2π(m−1) ( m−1 e )m−1 √ 2π(m2 −m) ( m 2 −m e )m2−m (19) 同样用二项展开式的前两项去近似代替指数项部分，式（19）可简化为 C31 ∼ 1 √ 2πm · 1 mm · e m−1 (20) 1 mm e m 式（20）的收敛速度主要取决于第二项幂指数因式和第三项，所以式（20）关系可表示为 Cone = C2-part ·O ((m e )m) (21) 同样将 n=m 2 代入式（22）： C32 = C2-part Ctwo = n!C m−1 n−1 n!mn = (n−1)! (m−1)!(n−m)!mn = ( m 2 −1 ) ! (m−1)!(m2 −m)!mm2 ∼ √ 2π(m2 −1) ( m 2 −1 e )m 2−1 √ 2π(m−1) ( m−1 e )m−1 √ 2π(m2 −m) ( m 2 −m e )m2−m mm2 ∼ 1 √ 2π(m−1) · 1 mm2−m · 1 m (22) 式（22）的增长速度仍取决于第二项的幂指数项，所以式（22）关系可表示为 Ctwo = C2-part ·O ( m m 2−m ) (23) 继而将 n=m 2 代入 C12 化简得到 Ctwo = Cone ·O ( m m 2 −2m e m ) (24) Ctwo = Cone·O ( m m 2 −2m e m ) = C2−part ·O ( m m 2−m ) m m 2−m 由式 (21)、(23)、(24) 可得，看出在旅行商人数和城市数为二次关系时，双染色体编码对应的解空间是两段式染色体编码对应的解空间的增长速度的倍，因此不同染色体编码方案的选择对问题的求解经常起主要的作用，可以指导实际问题的求解。 2.4.4 指数关系下的相对解空间分析本节讨论 n 与 m 在指数函数关系下相对解空间的收敛速度。将 n=e m 代入式（4）： ·766· 智能系统学报第 13 卷

第5期赵新超，等：遗传算法求解多旅行商问题的相对解空间分析 ·767· V2π(e"-I nC Cone (m+n-1)1 m+em-】 m-1 V2π(m+em- e e Vatc-mn V2nm mm (25) 同样用二项展开式的前两项取近似代替指数基于3种染色体方案求解多旅行商问题的相项部分，式(25)可化简为对解空间大小关系分析，就目前方案给出的解空 1 1 间仍然有冗余解存在。两段式染色体方案在单染 C31~ (26) V2um mm 色体方案和双染色体方案基础之上消除了相当大式(26)的收敛速度主要取决于第二项幂指数的一部分冗余，虽然没有完全消除，但是给了我因式，所以式(26)关系可表示为们很大启发，去寻找更加合理的新的染色体编码 cc) 方案以进一步减小解空间的冗余。 27) 同样将=e"代入式(5)得参考文献：一C=nm=0m-1Dn-mm (n-1)月 C32= (28) [1]CARTER A E,RAGSDALE C T.A new approach to solv- ing the multiple traveling salesperson problem using genet- 式(28)的增长速度仍是取决于第二项的幂指 ic algorithms[J].European journal of operational research, 数项，所以式(28)关系可表示为 2006.175(1):246-257. Cwo=C2paaO(m） (29) [2]YUAN Shuai,SKINNER B,HUANG Shoudong,et al.A 继而将n=e"代人C2化简得到： new crossover approach for solving the multiple travelling c=cog） salesmen problem using genetic algorithms[J].European (30) journal of operational research,2013,228(1):72-82 [3]WANG Xuping,XU Chuanlei,HU Xiangpei.Genetic al- 由式(27)1、(29)、(30)可得Co=Cme0em gorithm for vehicle routing problem with time windows C-tO(m),可以看出在旅行商人数和城市数为 and a limited number of vehicles[Cl/Proceedings of 2008 指数关系时，双染色体编码对应的解空间是两段 International Conference on Management Science and En- 式染色体编码对应的解空间的增长速度的m倍， gineering 15th Annual Conference.Long Beach,CA,USA, 不同染色体编码方案的选择对问题的求解效率有 2010:128-133 非常重要的影响，因此本文得到的对3种编码方 [4]BRANKE J,NGUYEN S,PICKARDT C,et al.Auto- mated design of production scheduling heuristics:a re- 案对应解空间的大小分析对实际问题的求解提供了定量的指导意义。 view[J].IEEE transactions on evolutionary computation, 2016,20(1):110-124 3结束语 [5]GOLDBERG D E.Genetic algorithms in search,optimiza- tion,and machine learning[M].Reading,Mass:Addison- 本文首先介绍了多旅行商问题的概念和3种 Wesley Publishing Company,1989. 染色体编码方案，已有文献只是定性地给出3种 [6]KESHAVARZ T,SALMASI N,VARMAZYAR M.Min- 编码方案对应解空间的大小关系，并没有给出严 imizing total completion time in the flexible flowshop se- 格证明。本文首先给出相对解空间的概念，然后 quence-dependent group scheduling problem[J].Annals of 在城市数充分大和城市数大于旅行商人数的条件 operations research,2015,226(1):351-377. [7]张永库，尹灵雪，孙劲光.基于改进的遗传算法的模糊聚下，在极限意义下严格证明了3种解空间的相对类算法).智能系统学报，2015,10(4)：627-635. 大小关系，最后利用Stirling公式严密分析了几种 ZHANG Yongku,YIN Lingxue,SUN Jinguang.Fuzzy 染色体编码方案中旅行商人数和城市数目在不同 clustering algorithm based on the improved genetic al- 关系下相对解空间的大小，得出了相对解空间的 gorithm[J].CAAI transactions on intelligent systems, 理论增长速度，给实际工程问题求解中染色体编 2015.10(4):627-635. 码方案的选择提供了科学的参考依据和指导意 [8]KATAYAMA K,SAKAMOTO H,NARIHISA H.The ef- 义。 ficiency of hybrid mutation genetic algorithm for the trav-

C31 = Ct−part Cone = n!C m−1 n−1 (m+n−1)! ∼ √ 2πe m ( e m e )e m √ 2π(e m −1) ( e m −1 e )e m−1 √ 2π(m+e m −1) ( m+e m −1 e )m+e m−1 √ 2π(m−1) ( m−1 e )m−1 √ 2π(e m −m) ( e m −m e )e m−m ∼ 1 √ 2πm · 1 mm · e m−1 (25) 同样用二项展开式的前两项取近似代替指数项部分，式（25）可化简为 C31 ∼ 1 √ 2πm · 1 mm · e m−1 (26) 1 mm 式（26）的收敛速度主要取决于第二项幂指数因式，所以式（26）关系可表示为 Cone = C2-part ·O ((m e )m) (27) 同样将 n=e m 代入式（5）得 C32 = C2-part Ctwo = n!C m−1 n−1 n!mn = (n−1)! (m−1)!(n−m)!mn (28) 式 (28) 的增长速度仍是取决于第二项的幂指数项，所以式（28）关系可表示为 Ctwo = C2-part ·O ( m e m ) (29) 继而将 n=e m 代入 C12 化简得到： Ctwo = Cone ·O ( m e m−m e m ) (30) Ctwo = Cone ·O ( m e m−m e m ) = C2-part ·O ( m e m ) m e m 由式（27）、（29）、（30）可得，可以看出在旅行商人数和城市数为指数关系时，双染色体编码对应的解空间是两段式染色体编码对应的解空间的增长速度的倍，不同染色体编码方案的选择对问题的求解效率有非常重要的影响，因此本文得到的对 3 种编码方案对应解空间的大小分析对实际问题的求解提供了定量的指导意义。 3 结束语本文首先介绍了多旅行商问题的概念和 3 种染色体编码方案，已有文献只是定性地给出 3 种编码方案对应解空间的大小关系，并没有给出严格证明。本文首先给出相对解空间的概念，然后在城市数充分大和城市数大于旅行商人数的条件下，在极限意义下严格证明了 3 种解空间的相对大小关系，最后利用 Stirling 公式严密分析了几种染色体编码方案中旅行商人数和城市数目在不同关系下相对解空间的大小，得出了相对解空间的理论增长速度，给实际工程问题求解中染色体编码方案的选择提供了科学的参考依据和指导意义。基于 3 种染色体方案求解多旅行商问题的相对解空间大小关系分析，就目前方案给出的解空间仍然有冗余解存在。两段式染色体方案在单染色体方案和双染色体方案基础之上消除了相当大的一部分冗余，虽然没有完全消除，但是给了我们很大启发，去寻找更加合理的新的染色体编码方案以进一步减小解空间的冗余。参考文献： CARTER A E, RAGSDALE C T. A new approach to solving the multiple traveling salesperson problem using genetic algorithms[J]. European journal of operational research, 2006, 175(1): 246–257. [1] YUAN Shuai, SKINNER B, HUANG Shoudong, et al. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms[J]. European journal of operational research, 2013, 228(1): 72–82. [2] WANG Xuping, XU Chuanlei, HU Xiangpei. Genetic algorithm for vehicle routing problem with time windows and a limited number of vehicles[C]//Proceedings of 2008 International Conference on Management Science and Engineering 15th Annual Conference. Long Beach, CA, USA, 2010: 128–133. [3] BRANKE J, NGUYEN S, PICKARDT C, et al. Automated design of production scheduling heuristics: a review[J]. IEEE transactions on evolutionary computation, 2016, 20(1): 110–124. [4] GOLDBERG D E. Genetic algorithms in search, optimization, and machine learning[M]. Reading, Mass: AddisonWesley Publishing Company, 1989. [5] KESHAVARZ T, SALMASI N, VARMAZYAR M. Minimizing total completion time in the flexible flowshop sequence-dependent group scheduling problem[J]. Annals of operations research, 2015, 226(1): 351–377. [6] 张永库, 尹灵雪, 孙劲光. 基于改进的遗传算法的模糊聚类算法[J]. 智能系统学报, 2015, 10(4): 627–635. ZHANG Yongku, YIN Lingxue, SUN Jinguang. Fuzzy clustering algorithm based on the improved genetic algorithm[J]. CAAI transactions on intelligent systems, 2015, 10(4): 627–635. [7] KATAYAMA K, SAKAMOTO H, NARIHISA H. The efficiency of hybrid mutation genetic algorithm for the trav- [8] 第 5 期赵新超，等：遗传算法求解多旅行商问题的相对解空间分析 ·767·

点击进入文档下载页（PDF格式）

已到末页，全文结束

点击下载（PDF格式）

浏览记录