guimow 多任务优化是计算智能领域中一个新兴的研究方向，旨在利用任务间的联系进行任务间知识迁移，以加快算法的收敛速度和计算精度。多任务进化优化的出现对于进化算法的发展具有重要意义。针对旅行商问题(Traveling Salesman Problem,TSP)，本文研究一种多任务进化求解算法。现有优化算法往往对不同TSP问题进行独立求解而忽略它们的关联，不仅浪费计算资源，而且存在搜索速度慢、易陷入局部最优等缺陷。本文所提多任务粒子群优化算法，分别针对任务间所迁移知识的构成、知识迁移时机和利用策略等关键问题提出了有效的解决方法，并根据TSP问题的特点设计一种自适应交叉粒子更新策略。最后，将其用于典型测试集生成的多任务TSP问题上，并与经典算法进行对比，实验证明，本文所提多任务粒子群优化算法提升了算法的收敛速度和计算精度，为求解多任务TSP问题提供了一种有竞争力的新算法。
1.1研究背景及意义（Research background and significance）
多任务优化是计算智能领域一个新兴的在研究方向，其出现对于进化算法的发展具有重要意义。在大数据时代，很多实际问题往往需要同时解决多个类似的优化任务。有效挖掘任务间的潜在联系，是进一步提升优化算法效率的关键。
进化算法是一种受生物进化行为启示提出的启发式搜索算法。该算法以初始种群为基础，模仿生物进化的方式，逐渐筛选并进化出优秀的个体，进而得到（或者接近）问题的全局最优解[1-3]。自诞生以来，诸多应用已证明了进化算法解决复杂优化问题的强大能力。这些年，许多学者对于进化算法进行了不断改进和创新，提出了多种典型的进化算法，包括遗传算法、差分进化、进化策略和进化编程等等[4-9]。
进化算法最大的优势在于，其能够几乎不受问题性质的限制，在不同类型的优化问题上均能成功应用，且抗干扰能力较强，具有广泛的适用性和较好的鲁棒性。对于一些精确算法无法解决，或者解决的时间长到无法接受的问题，进化算法一般会有较好的效果。本文所研究的旅行商问题就是一个典型的例子。当城市数增多时，传统算法所需要的时间呈指数级增长，而进化算法能在有限的时间中得到一个相对接近最优解的结果，这往往更加符合现实需要。
然而，进化算法仍然存在一些限制其实用性的缺点。由于传统进化算法每次从随机种群开始只能专注于一个优化任务，因此，对于具有多个相似任务的优化问题只能独立解决每个任务。然而，我们现实生活中的很多问题经常是相互关联的而非独立的。将这些相似优化任务或问题当作独立的问题来分析计算，会导致计算效率较低，程序并行度不高等问题。如果能够合理利用问题间的联系对问题进行共同求解，势必可以大大提高算法的收敛速度和计算精度。同时，如果盲目地进行任务间知识迁移，反而会干扰问题的解决。如何提取任务间所迁移知识，如何确定合适的知识迁移时机，以及如何利用知识是需要提前新且有效的方法。鉴于此，本文以具有多个优化任务的TSP问题为例，研究其多任务粒子群求解算法。
1.2国内外研究现状（Analysis of research status at China and abroad）
多任务优化(Multitask Optimization)着眼于同时解决多个相似又彼此独立的任务，发现他们彼此相关的地方，以加快算法计算速度。换句话说，如果多个任务优化的问题彼此相似，则可以将一个问题的求解过程中的一些优秀个体转移到另一个问题，加快其搜素进度。通过这种任务间知识转移可以大大提高算法的搜索速度[10]。。
近年来，多任务优化吸引了许多研究者的关注。Gupta等[11]提出了一种多任务多因子进化算法(M-FEA)。该算法通过统一的随机密匙来编码不同优化任务的解决方案，每个种群被加入了代表不同任务的技能因子，通过多种不同技能因子交叉遗传，实现跨任务的知识转移。Yin等[10]提出了一种基于搜索方向的任务间知识转移策略，增强了搜索的多样性，提高了任务间知识转移策略的有效性和效率，加强了算法的全局搜索性能，有效解决了多任务进化容易陷入局部最优的不足。Huynh等[12]提出了一种基于目标点的多目标多任务算法(MO-MFEA)，采用一组参考点来确定当前种群的多样性，缓解了当目标函数增加时其他算法的计算困难问题。Liang等[13]为解决进化搜索过程中知识转移效率不断下降的问题，将超矩形搜索策略和遗传转化策略进行融合，进一步提高了知识的转移效率。Rauniyar等[14]将多任务优化策略运用于运输路线规划问题，解决了如何同时生成多条路线的问题，证明了多任务优化应用于路线规划领域的可行性。Zheng等[15]提出了一种简单有效的知识转移策略，基于随机替换帮助解决优化过程的其他问题。该算法在不引入额外计算成本的前提下，相对比单独解决每个问题更有效。李豪等[16]将多任务优化用于机器学习算法的改进邱立明等[17]提出一种MT-DMOEA算法，将迁移算法与多任务算法相融合。赵映红[18]等将多任务优化应用于工程设计中，用以解决三维设计中并行任务间冲突的问题。袁源[19]提出一种平衡种群收敛性和多样性的方法，用以解决高维多目标算法。Chen等[1]提出了一种改进的多任务进化算法(MaTEA)，通过考虑任务之间的相似性，为每个任务选择合适的辅助任务，提高了搜索效率；对于动态多任务优化也有很好的效果，进一步提升了多任务算法的实用性。
已有成果表明，多任务进化优化的使用显著提高了算法解决实际问题的能力。然而，现有算法研究将多任务优化用于TSP问题的很少，如今流行的TSP算法大多数每次只能解决一个问题，无法利用一个任务的搜索进度提升其它任务的解决速度。除此之外，现有的多任务优化算法依然存在如下问题：1）当任务数目较多时，如何从众多的历史问题或任务中选出最为合适的迁移对象，是提升算法性能的关键。由于知识迁移方式不合理，现有一些多任务进化优化算法，在任务目标数增加时性能会急剧下降。2）选择合理的迁移时机，可以在不影响算法性能的前提下减少算法的计算时间，提高算法的效率。3）对于迁移的数据，一些文献[20][21]直接使用源问题的优秀个体替换目标问题的优秀个体，忽略了源问题和目标问题之间的差异。当源问题和目标问题差异过大时，源问题较优秀的种群个体未必在目标问题上取得较好的结果。如不解决这一问题而强行进行迁移，势必会导致其算法性能的下降。4）早期一些简单的多任务优化算法在选择需要进行迁移的种群个体时，往往只考虑种群个体的适应度，将每个任务中适应度最好的个体进行迁移。这些算法所进行的知识迁移难以保证迁移种群的多样性，降低了算法跳出局部最优的能力。
1.3论文主要工作（Main work of this paper）
基于上述分析，本文研究一种面向TSP问题的多任务粒子群优化算法，用于同时解决多个有一定关联的TSP问题。根据多个TSP任务间城市的相应联系，从每个任务中找出对其它任务搜索有帮助的搜索信息；通过合适的方法从中提取到有价值的部分，将其迁移到其它任务；通过合理组合、利用并替换其它任务的部分较差个体，用以加速算法的搜索速度、增强算法的计算精度。具体而言，本文主要工作如下：
（1）给出一种任务间知识迁移时机判断方法。判断每个问题中种群个体在当前迭代中是否有所更新，并以此作为是否进行任务间知识迁移的重要依据。在不影响迁移算法效果的情况下，该方法可以大幅度增强迁移算法的有效性，避免无效迁移对算法性能的影响。
（2）给出一种迁移知识选择策略。首先，选择合适的聚类算法，将待迁移种群进行聚类；然后，将类中的最佳个体作为待迁移对象。该策略可以保证迁移知识的适应性和多样性，进而提高算法的全局搜索能力。
（3）给出一种迁移后数据的利用方法。综合考虑迁移前后种群的个体数目、种群相似度等因素，确定迁移后知识的利用程度，以避免出现负迁移现象。
（4）此外，依据TSP问题自身的特点，设计一种基于自适应交叉和变异的整数型粒子更新策略。使算法更好的适应TSP问题的特点，取得更好的优化效果。
1.4论文结构安排（Paper structure arrangement）
本文结构作如下安排：第2节主要介绍算法有关基础知识，包括旅行商问题数学模型、粒子群算法的基本理论、K-中心点聚类算法、余弦相似度以及多任务优化算法的基础知识；第3部分给出所提多任务TSP进化求解算法；第4部分与其它典型算法进行对比实验，验证算法的有效性；第5部分总结本文工作。
2论文基础知识
2 Basic work
2.1旅行商问题（Traveling Salesman Problem）
旅行商问题(Traveling Salesman Problem)TSP可以看出这是一个非常具有代表性的组合优化问题。首先，我们指定n个城市，并且确定它们的坐标位置，寻找一条合适的路线，这条路线既可以经过每个城市且只能经过一次，其目标是在满足条件的路线中选择距离最短的路线。或者，也可以表示为：在有n个结点的完全图中找出最短的Hamilton回路。具体而言，其数学模型描述如下：存在一组城市,其中每个城市与城市之间的距离为，在C中找到一条穿过每个城市的路线，使得，
(1)
其中，为的一个位置置换向量。
下面是一个简单TSP问题的例子。有一个商人想要访问中国的某些城市，如徐州、深圳、上海、北京4个城市。要求：1）每个城市都必须访问且只能访问一次，2）从某一个城市出发，最后必须返回这个城市。3）在满足前两条要求的情况下，所走的路程的最短。用数学语言可以表示为，目标域{徐州、北京、上海、深圳}，不失一般性的，假设该商人从徐州出发，则目标函数可以归纳为。
不难发现，当城市数目较少时，TSP问题并不难解决，但是当城市数目增加后，其计算难度呈指数级增加。TSP是一种典型的NP（Non-deterministic Polynomial）难问题。如果给出一种路径安排，便可以轻松算出其距离，但是如果想要确定这条路径是否是最短的，在最坏的情况下就要检查所有的路径，其计算时间将会是很大。传统局部启发式算法着眼于问题本身局部特征，包括贪心算法，动态规划算法，穷举算法等等。对于城市规模比较小的TSP问题，这些算法表现突出，但是随着城市数目的增多，他们的计算时间呈现指数级增加[22-25]。进化算法，包括蚁群算法，遗传算法，粒子群算法[26-31]，在处理这类问题时，虽然无法保证给出一个精确解，但是其能在有限的时间内给出一个相对较短的路径，具有传统算法无法比拟的优势。
旅行商问题在物流规划、芯片制造、交通路线导航、计算机路由优化[32]等众多领域都有着十分重要的作用。如今随着快递、外卖等领域的快速发展，旅行商问题的规模不断扩大，如何快速、高效的解决这一类问题，对算法领域提出了新的挑战。
2.2粒子群优化算法（Particle Swarm Optimization Algorithm）
粒子群优化算法（Particle swarm optimization,PSO）[32][33]这是一种以群体为基础的进化算法，它是通过在鸟类寻找食物等这种自然现象的中得到了启示而产生的。在对优化问题寻求解法的时候，PSO将整个搜寻的空间中一个粒子的位置看作为其问题的潜在的答案，并把其称为“粒子(particle)”或“微粒”。这种没有质量、没有体积的粒子在搜索的空间中随机游走，就如天空中的鸟在飞翔，不断将位置进行更新。设粒子i在N维空间的位置表示为矢量，飞行速度表示为矢量，每个粒子都有一个由目标函数决定的适应值，用来确定其位置的优劣。PSO是一种迭代搜索策略，每个粒子通过记忆和追随两个最优位置来不断更新自身的位置。一个是该粒子到目前为止自己发现的最好位置，即通常说的粒子个体最优点或局部引导者。另一个是目前为止邻域微粒发现的最好位置，即通常说的粒子的全局最优点或全局引导者。考虑常用的全局版粒子群优化算法，即每个粒子的邻域为整个粒子群，粒子i的更新公式如下：
(2)
其中，为算法迭代次数，迭代次数越大则算法效果越好，但是计算时间也相应增加，和为学习因子，通常，和为服从均匀分布的随机数。为惯性权重，值为非负数，当我们需要较好的全局搜索能力时取较大值，反之，当我们需要较好的局部搜索能力时，取较小值。实际使用PSO算法的过程中，为了取得较好的效果，一般进行动态变化，通常采用线性递减权值(LDW)策略，公式如下
(3)
其中为最大迭代次数，为初始惯性权重值，为算法迭代到最大迭代次数时的惯性权重值，为当前迭代代数。通过这种惯性权重递减的方法能够平衡算法的加强算法在迭代前期的全局搜索能力，而又不影响算法的后期的局部搜索能力。典型的权值取值为，。
PSO算法易于实现，无需进行复杂的参数调节就能实现较好的效果，已经被广泛应用于模糊控制、训练神经网络、优化函数等等方面
2.3 K-中心点算法（K-medoids Algorithm）
K-中心点算法[34]的核心思想是，对于输入的数据，试图通过迭代找出簇中位置最中心的对象，将所给的N个对象划分为K类。相对于K-均值算法（K-means）将每一次选择簇的均值作为新的中心点，K-中心点算法对于离群点不是特别敏感，不会因为一个或者少数几个很大的极端数值影响整体分布。
在算法开始的时候，我们将初始簇定为随机选取的k个对象，并且将中心点设置在这k个对象上，之后对其欧式距离进行计算，并划分初始簇，然后，通过计算出的结果将其他的对象划分到每个中心点所表示的簇之中，我们可以把其中的中心点称为代表对象，除此之外的对象称为非代表对象。在该算法中，不断利用其中的数据把当前代表对象替换为非代表对象，目的是能够找到更加合适的中心点来改进聚类质量。算法进程中，将会对每次迭代中的所有可能对象进行分析，在每次替换过程中，一对替换对象中总有一个是中心点，而其另外的一个则为非代表对象。假如其中一个非代表对象替换了其中心点，则在代价函数中将会记录这次替换的代价，我们可以用所有非中心对象替换所产生的代价的和来表示这次替换的总代价。假如总代价为负，那么实际误差会减小，这意味着这次的替换是一次有益的替换，可以用非代表对象替换代表对象。这种全局计算代价函数的方法保证了这种算法产生的聚类结果受少数几个离群点影响较小。
此节所述K-中心点算法伪代码如下：
算法1：K-中心点算法
输入:集合中包含的元素数目，簇的个数
输出：簇使得对象与其距离最近的中心点的距离总和达到最小的集合
步骤1：随机选择个对象作为中心点，称为初始中心点；
步骤2：将其他所有对象按照离其最近的中心点分簇；
步骤3：随机跳出一个从没有被选择过的非中心点和中心点；
步骤4：使用非中心点替换中心点，成为新的中心点，在S中记录替换所产生的总代价；
步骤5：直到不存在未被选择的中心点和非中心点；
步骤6：如果所有替换所产生的总代价为负值，那么使用该非中心点替换对应的中心点，组成一个新的具有个中心点的集合；
步骤7：直到所有的S都不为负值，即不再发生中心点的重新选择；
步骤8：输出簇使得对象与其距离最近的中心点的距离总和达到最小的集合。
2.4余弦相似度（Cosine Similarity）
对于多任务优化中任务间迁移算法来说，源种群和目标种群的相似程度对于算法的决策具有重要意义。选择一种合适的相似度判断方法有助于帮助算法做出正确决策。
余弦相似度，又称余弦距离，是用向量空间中两个向量夹角的余弦值来度量它们之间的相似度的一种方法。由数学中余弦的定义，我们容易很得出，如果两个矢量指向同一方向，余弦相似性的值为1；如果两个向量之间的角度为90°；则余弦相似性值为0；如果两个向量指向相反的方向，则余弦相似性的值为-1。余弦相似性通常应用于正空间，所以余弦相似度的值通常在0和1之间的。其中，余弦值越接近1，角度越接近0，则两个向量越相似；相反的，余弦值越接近0，则表明个体与个体之间的差异越大，这就称之为余弦相似性。具体而言，对于a，b两个向量，它们的余弦相似度由如下公式计算：
(4)
余弦相似度在检测相似文本，相似用户，相似物品，处理自然语言等领域都有重要应用。本节通过计算余弦相似度来判断两组城市间坐标差异程度，帮助算法定义后续的迁移策略。
2.5多任务优化算法（Multi-task Optimization Algorithm）
多任务优化(Multi-task Optimization)旨在同时处理或优化多个问题或任务，利用其每个问题或任务间的联系，加速算法的搜索速度，提高算法的计算精度。
对于一个包含m个任务（）的问题，设每个任务的最优解为，算法输出的解为，则每个任务误差的计算公式为，m个任务的平均误差为：
(5)
对于TSP问题，在进化算法每次轮回过程中，通过依次对m个问题中的2个问题进行，完成所有m个任务之间的知识共享。不失一般性，考虑任务，其中。这里假设算法将的一些优秀种群个体经过处理应用于的搜索进程中，以加速的搜索进度。通过多次操作，直至两两判断所有m个问题或任务；通过不同任务之间不断共享优化信息，加快算法的搜索速度与计算精度，最终实现最小。
3面向TSP问题的多任务粒子群优化算法
3 Multi-task PSO algorithm suitable for TSP problem
3.1算法框架（The Algorithm Framework）
本文提出一种多任务粒子群优化算法，用以同时解决多个TSP问题。利用不同任务间相似性进行知识迁移，将对一个问题的搜索进度转移到另一个问题，以达到提升算法收敛速度，改善算法计算精度的目的。
图1给出了所提算法的流程图。首先，根据多个预设条件进行判断（详见3.2节），决定任务间是否需要迁移。当符合迁移条件时，从进化算法迭代过程所产生的种群信息中提取有用知识，执行迁移算法。即将一个问题（即源问题）的优秀个体集合迁移给另一个合适的问题（即目标问题）；接受到迁移信息后，当前种群会基于这些信息重新初始化部分粒子的位置，并返回到进化迭代中，继续执行求解TSP问题的离散PSO算法，直到满足下次迁移时机或达到终止条件。分析上述算法容易得知，迁移时机的判断、迁移个体的选择、迁移知识的利用等关键策略会影响算法的性能。针对上述关键策略，下文将作详细论述。
3.2迁移时机的判断（Judgement of Transfer Opportunity）
对于多任务粒子群优化算法，如果不采用合适的迁移时机判断算法，而是在每次迭代时都进行迁移，那么，程序会执行次任务间迁移，这无疑会带来很大的计算开销，其中，M为任务数目，T为算法迭代次数。因此，设置合适的迁移时机来减少不必要的迁移次数，是提升算法性能的关键因素之一。
在进化算法的每次迭代中，种群个体不一定会发生改变。如何能够依据种群需要自主确定迁移时机，则可以在不影响算法的性能的情况下大幅度减少迁移次数。鉴于此，本节所提算法通过两个指标判断迁移时机：1）如果在此次迭代中，种群中最优秀个体发生变化，则视为需要迁移；否则，依据第2条准则判断是否需要迁移；2）计算本次迭代后种群个体与上次迭代后种群个体之间的余弦相似度，如果其值小于某个常数a，则进行迁移。通过对a的大小进行控制，可以控制算法执行任务间迁移的频率。当常数a较大时，任务间迁移频率较快，种群个体以较大的概率被迁移；反之，当常数a较小时，迁移策略较为保守，较多的种群个体不会被迁移。
在pcb442测试集上的实验表明，相对每代都迁移的传统方法，通过增加迁移时机判断算法，可以减少40%以上的迁移次数，而且对算法的计算精度基本没有影响。进一步，算法2给出了所提迁移时机判断算法的伪代码。当算法输出结果为flag=1时，则启动任务间的迁移。
算法2：迁移时机判断算法
输入:第t次迭代后种群，上次迭代后种群
输出:程序间知识迁移判断标识
步骤1：输入种群和；
步骤2：分别将种群和中个体按照适应度值从小到大排序；
步骤3：=0；
步骤4：对比中最优个体和中最优个体，
如果，则=1；否则，转入步骤5；
步骤5：计算和的余弦相似度，如果
，则设置=1；
步骤6：输出程序间知识迁移判断标识。
3.3迁移数据的选择（Selection of Transfer Data）
对于迁移数据的选择，传统的多任务优化算法往往只考虑种群个体的适应性，将种群中最优的个体进行迁移。这样做可以增加算法的收敛速度，但是会导致算法过早陷入局部最优。为了增强算法跳出局部最优的能力，需要迁移的数据应该具有很好的多样性。为了同时保证任务间知识迁移算法的多样性和有效性，本节提出一种基于聚类的迁移个体选择策略，利用K-中心点（K-medoids）算法对种群中个体进行聚类处理后，再从每个聚类簇中选择优秀的个体进行迁移。
对于每一个需要迁移的种群，首先使用K-中心点算法将其聚类成K簇；然后，对每簇中的种群个体进行排序，获得每一类中最佳的个体，组成待迁移最优个体集合进行迁移。可以看出，从每个类中选择适应值最大的个体，可以保证被迁移个体具有较高的适应值；同时，对种群个体进行聚类，从每一类中选出代表个体，可以保证迁移个体具有较好多样性。进一步，算法3给出了所提迁移数据选择算法的伪代码。
算法3：迁移数据的选择算法
输入:需要迁移的种群，聚类数目K；
输出：待迁移最优个体集合；
步骤1：输入需要迁移的种群；
步骤2：对种群进行K-中心点聚类，得到K簇；
步骤3：从第1个簇到第K个簇,依次执行下述操作：
对第i个簇中的个体按照适应性进行排序，选出最优秀的个体，
并将其保存到中；
步骤5：输出最优集合=。
3.4迁移知识的利用（Utilization of Transfer Knowledge）
如前文所提，现有多任务进化优化算法大都将迁移后数据直接用于目标任务，忽略了源域任务（或问题）和目标任务（或问题）的差异性。事实上，由于多任务优化中任务间存在的差异性，对于一个任务较好的种群个体未必适合另一个任务。在源问题与目标问题差异较大时，直接迁移策略很容易导致源问题污染目标问题。此外，如果通过简单判断源问题和目标问题的相似性，对迁移与否做二元判断的话，又会导致一些优秀知识信息的丢失。鉴于上述原因，本节提出一种多任务优化的种群个体迁移算法，用以解决任务间知识利用效率问题。该算法通过学习源问题的最优行走路径，来为目标问题产生高质量的个体。
当确定好需要迁移的源个体后，首先比较源个体与目标个体之间的差异性：1）对于两者中位置相同的城市，充分利用任务间的相关性，直接继承源域中这些最优行走顺序；2）对于剩余城市，利用余弦相似性判断源域个体与目标个体关于这些城市的相似程度。如果相关性较大，则认为源问题种群个体有较大概率可以促进目标问题的搜索速度，可以将源问题的种群个体转移到目标问题。反之，删除这部分城市的迁移信息，防止迁移不相关数据的污染目标问题；进一步，为增强种群多样性，随机初始化这些城市的行走顺序。算法4给出了迁移知识的利用算法。
算法4：迁移知识的利用算法
输入:来自源问题的迁移个体，目标问题中待初始化个体，相似度阈值a。
输出：初始化后的个体，
步骤1:对比源问题和目标问题,找出它们相同的城市，记为=，
它们剩余不同的城市分别记为和；
步骤2：对于中城市，直接继承中对应城市在上的行走顺序，不妨记为；
步骤3：对于中城市，首先计算和之间的余弦相似度（：
步骤3.1：若，则中城市继承中对应城市在上的行走顺序，不妨记为
步骤3.2：若，则随机初始化中城市的行走顺序，不妨记为；
步骤4：拼接和，生成完整路径；
步骤5：由确定个分量的取值，输出。
3.5改进的离散粒子群更新策略（Improved discrete update strategy of particle swarm）
TSP问题是典型的离散组合优化问题。当使用传统的连续PSO算法解决此问题时，粒子更新过程需要被离散化。遗传算法中的交叉变异算子有两个优势，一是具有出色的搜索性能，二是更适合解决离散优化问题。另外，虽然传统的粒子群更新策略具有收敛性好的特点，但是这也常常导致粒子群过早地陷入局部收敛。因此，本节提出了一种融合交叉变异的改进粒子群更新策略。改进粒子群的特征：在进化的过程中，使当前粒子与个体最优点及整体最优点等优异的位置交叉融合，以确保粒子群快速收敛。
用个体最优点和全局最优点将粒子位置进行更新。而就当前的粒子而言，首先要选择任意长度的交叉区域，交叉区域要在和中分别进行随机挑选，然后在当前粒子中找到一个城市，使其与交叉区域终点城市的距离是最近的，并且把选择的交叉区域加入到该城市的前面；之后，为了使粒子进行更新，把那些在交叉区域中显现过的城市进行删除。下面是具体的更新公式：
(6)
其中，表示置换序列，表示提取序列，表示随机数，。
下面进行更深入的分析，将图2中的6个城市作为例子来看，当前粒子为，表示为个体的最优点为，表示为粒子全局的最优点为，随机数。我们先在中随机选择个连续城市，在当前粒子中，城市与城市距离最近，则我们把其放在城市之前，并删除中有的城市，从而可以确定新的粒子的位置即=；同样，也可以由交叉与，可以得到的位置变为。
图2改进的交叉算子
Figure 2 Improved crossover operator
3.6所提的多任务粒子群优化算法（The Proposed multitask Particle Swarm Optimization Algorithm）
基于上述工作，本节给出用于求解多任务TSP问题的改进粒子群算法（M-TSP）。其伪代码如下：
算法5：所提多任务粒子群优化算法
输入:带求解的多个TSP问题，种群规模N，最大进化代数T。
输出：每个TSP问题的最优解。
步骤1：随机生成M组规模为的粒子群；
%对每一个粒子群执行下述操作——————–
步骤2：运行3.6节所提改进粒子群更新策略，更新粒子位置；
步骤3：运行3.3节所提迁移时机判断算法。若不满足迁移时机，则跳转至步骤4；
步骤3.1：提取当前问题的种群；
步骤3.2：由3.4节所提迁移数据选择算法，从其它种群中选出待迁移最优个体；
步骤3.3：使用3.5节所提知识利用算法产生新解；
步骤3.4：使用产生的新解替代当前种群中部分个体。
步骤4：判断是否达到最大迭代次数T。如果达到，输出当前最优解集；否则返回步骤2.
4实验分析
4 Experiment analysis
本节通过两组实验来验证所提算法的性能。第1组实验分析检测任务数目M和随机选择城市比例系数对本文所提算法性能影响；第2组实验将本文所提多任务TSP求解算法（M-TSP）与多个经典算法进行比较，验证其性能，证明多任务优化算法对于解决TSP问题的优越性。
4.1实验环境及测试集（Experimental Environment and Test Problems）
选择5种典型的TSP进化优化算法，与本章所提M-PSO算法进行性能对比。所用对比算法包括：标准PSO算法(PSO)[35]、标准蚁群算法(ACO)[36]、PSO-ACO算法(PSO-ACO)[37]，以及免疫克隆算法(ICPSO_TSP)[38]。选择TSPLIB数据库中常用的8个典型TSP问题作为源对象，表1展示了这些TSP测试集的基本情况。由4.2节所提算法对每个测试集生成4组城市差异比例不同的测试集合，每组任务包含8个子任务，用以检验算法的多任务能力。具体测试集详见表2。所有实验采用相同的运行环境，即Intel Core(TM)i7、3.60GHz的CPU、32.00GB RAM存储。采用Matlab2018a实现所提算法，并构建模型库。
4.2测试集的生成（Test-set Generation）
为验证本文所提算法的性能，本文选择8组典型TSP测试集合，用以生成实验所需测试集合。典型测试集选择如下：eil76，rat99，kora100，eil101，ch150，pcb442，pr1002，pr2392，具体见表1。其中eil76的城市数目最少，为76个，pr2392的城市中数目最多，为2392个。
现实生活中，每个地点的坐标基本不变，而每次路径规划所需的地点不尽相同。为了模拟真实情况，对于每个测试集合，采用下述方式产生多个相似的优化任务，即多个相似的TSP问题；对于每个典型测试集，我们需要生成含有8个问题的测试集，每个问题包含个城市，的取值大约为经典测试集数目的2/3，对于每个测试集其生成方法如下。1）首先从经典测试集中选出数目为(1-)%的城市，将这一部分直接作为8个问题的固定部分。2）对于8个问题，分别再从经典测试集中选出第一步未选出的部分城市，数目为%。3）将第一步和第二步的城市组合，并随机打乱作为实验测试集；4）保证每组测试集中的城市数目略微差异以更符合真实情况，此节所述生成TSP数据集程序伪代码如下。
算法6：生成所需要的TSP问题集
输入:TSP原始数据集；随机选择的比例系数；生成测试集城市大约数目；测试集生成相关任务组数M。
输出：组相互有一定关联的TSP问题集
步骤1：输入经典TSP问题测试集TSP0；
%—–循环执行步骤2-4，直到产生规定数目的相似TSP问题
步骤2：从TSP0中选出(1-)%的城市，直接作为相似TSP问题的固定城市部分；
步骤3：从TSP0测试集中在步骤2未选择的部分中，随机选出大约%的城市，作为相似TSP问题的随机城市部分。
步骤4：合并步骤2和3产生的城市位置，组成相似TSP问题，并随机打乱；
步骤5：输出M个TSP问题集合。
表1经典TSPLIB数据集
Table 1 Classic TSPLIB Data-set
序号数据集城市数目已知最优解
1 eil76 76 538
2 rat99 99 1211
3 kora100 100 21282
4 eil101 101 629
5 ch150 150 6528
6 pcb442 442 50778
7 pr1002 1002 259045
8 pr2392 2392 378032
表2 eil76生成数据集
Table 2 Eil76 Generated Data Set
随机城市比例：20%随机城市比例：30%随机城市比例：40%随机城市比例：50%
序号已知最优解序号已知最优解序号已知最优解序号已知最优解
1 427 1 428 1 432 1 431
2 439 2 417 2 417 2 409
3 441 3 424 3 453 3 409
4 419 4 426 4 417 4 432
5 437 5 448 5 406 5 417
6 400 6 413 6 432 6 401
7 406 7 434 7 431 7 409
8 429 8 452 8 402 8 430
表3 rat99生成数据集
Table 3 Rat99 Generated Data Set
随机城市比例：20%随机城市比例：30%随机城市比例：40%随机城市比例：50%
序号已知最优解序号已知最优解序号已知最优解序号已知最优解
1 934 1 999 1 967 1 981
2 939 2 958 2 953 2 975
3 938 3 964 3 996 3 1000
4 917 4 888 4 976 4 987
5 983 5 950 5 964 5 982
6 921 6 990 6 988 6 962
7 924 7 946 7 966 7 964
8 964 8 968 8 991 8 964
表4 kora100生成数据集
Table 4 kora100 Generated Data Set
随机城市比例：20%随机城市比例：30%随机城市比例：40%随机城市比例：50%
序号已知最优解序号已知最优解序号已知最优解序号已知最优解
1 17218 1 17537 1 18856 1 18296
2 17691 2 17669 2 19120 2 18014
3 17820 3 18999 3 18650 3 18382
4 16835 4 18502 4 18651 4 18294
5 16726 5 17921 5 17771 5 17947
6 17587 6 17787 6 18039 6 18206
7 17250 7 17789 7 18475 7 17146
8 17934 8 17885 8 18429 8 19185
表5 eil101生成数据集
Table 5 Eil101 Generated Data Set
随机城市比例：20%随机城市比例：30%随机城市比例：40%随机城市比例：50%
序号已知最优解序号已知最优解序号已知最优解序号已知最优解
1 446 1 488 1 436 1 465
2 468 2 468 2 465 2 475
3 447 3 484 3 460 3 473
4 464 4 464 4 481 4 488
5 478 5 479 5 455 5 486
6 445 6 495 6 485 6 468
7 455 7 454 7 455 7 479
8 477 8 484 8 478 8 478
表6 ch150生成数据集
Table 6 Ch150 Generated Data Set
随机城市比例：20%随机城市比例：30%随机城市比例：40%随机城市比例：50%
序号已知最优解序号已知最优解序号已知最优解序号已知最优解
1 5119 1 5367 1 5490 1 5327
2 5248 2 4885 2 5500 2 5394
3 5160 3 5165 3 5367 3 5434
4 5339 4 5339 4 5213 4 5297
5 5190 5 5360 5 5329 5 5321
6 5194 6 5228 6 5317 6 5499
7 5353 7 5174 7 5291 7 5574
8 5244 8 5309 8 5459 8 5188
表7 pcb442生成数据集
Table 7 Pcb442 Generated Data Set
随机城市比例：20%随机城市比例：30%随机城市比例：40%随机城市比例：50%
序号已知最优解序号已知最优解序号已知最优解序号已知最优解
1 39312 1 39658 1 39327 1 40176
2 38780 2 39172 2 39949 2 40862
3 39276 3 41011 3 40128 3 40642
4 38799 4 40944 4 40005 4 40699
5 37691 5 38777 5 39757 5 40463
6 38332 6 39138 6 39930 6 40569
7 39142 7 40463 7 39896 7 39716
8 39453 8 39336 8 40164 8 40631
表8 pr1002生成数据集
Table 8 Pr1002 Generated Data Set
随机城市比例：20%随机城市比例：30%随机城市比例：40%随机城市比例：50%
序号已知最优解序号已知最优解序号已知最优解序号已知最优解
1 201723 1 207597 1 206492 1 207458
2 203261 2 205800 2 206956 2 207780
3 204636 3 204642 3 205297 3 206904
4 202311 4 206898 4 208866 4 211216
5 205030 5 207473 5 205574 5 209764
6 199902 6 204888 6 205522 6 209882
7 201937 7 202394 7 205648 7 209217
8 203704 8 208395 8 206236 8 206209
表9 pr2392生成数据集
Table 9 Pr2392 Gnerated Data Set
随机城市比例：20%随机城市比例：30%随机城市比例：40%随机城市比例：50%
序号已知最优解序号已知最优解序号已知最优解序号已知最优解
1 306024 1 306552 1 310591 1 311698
2 303118 2 305212 2 309248 2 313087
3 304075 3 306932 3 308686 3 314842
4 304873 4 304743 4 310039 4 311436
5 300785 5 308481 5 305577 5 310449
6 302496 6 306996 6 310259 6 309029
7 301699 7 308700 7 310009 7 308150
8 302256 8 308353 8 307787 8 311429
4.3关键参数或算子分析（Analysis of Key Parameters or Operator）
本节主要分析任务数目和知识迁移策略对所提算法性能的影响。首先，第4.3.1节验证城市差异程度对算法性能的影响，通过改变测试集城市差异比例为20%、30%、40%和50%等4种情况，检验知识迁移策略的有效性；第4.3.2节通过改变任务数M分别为2组、4组、6组和8组，验证任务数目对算法性能的影响。第4.3.2节保持测试集城市差异比例为30%不变。
4.3.1城市差异程度对算法性能影响
表10城市差异程度对算法性能影响
Table 10 The impact of city differences on the algorithm performance
城市差异程度对算法性能影响
城市名称城市差异比例平均值（%）CPU时间（s）城市名称城市差异比例平均值（%）CPU时间（s）
eil76测试集20%2.10 42.10 ch150测试集20%7.74 68.09
数据见表2 30%2.69 40.72数据见表6 30%7.75 67.90
40%2.83 43.41 40%7.85 67.98
50%2.93 42.65 50%8.12 68.70
城市名称城市差异比例平均值（%）CPU时间（s）城市名称城市差异比例平均值（%）CPU时间（s）
rat99测试集20%3.99 48.43 pcb442测试集20%9.92 280.76
数据见表3 30%4.19 47.76数据见表7 30%9.99 280.65
40%4.12 48.67 40%10.34 280.95
50%4.97 50.99 50%10.50 281.75
城市名称城市差异比例平均值（%）CPU时间（s）城市名称城市差异比例平均值（%）CPU时间（s）
kora100测试集20%6.05 48.90 pr1002测试集20%10.72 1223.23
数据见表4 30%6.03 48.92数据见表8 30%11.06 1224.51
40%6.84 47.27 40%11.02 1230.08
50%7.65 48.81 50%11.98 1249.14
城市名称城市差异比例平均值（%）CPU时间（s）城市名称城市差异比例平均值（%）CPU时间（s）
eil101测试集20%7.66 91.16 pr2392测试集20%12.66 7467.13
数据见表5 30%7.58 83.88数据见表9 30%13.13 7377.36
40%7.83 84.11 40%13.15 7409.46
50%8.03 83.49 50%13.25 7399.56
针对8个测试问题，分别运行M-TSP算法，设置最大迭代次数T=1000次种群规模N=100，聚类数目K=5，每次计算根据2.5节所提公式（5）得出平均结果。针对每组测试问题分别运行M-TSP算法20次，结果取平均值。表10展示了对于城市差异比例分别为20%、30%、40%和50%的测试集合，所提M-TSP算法的计算结果。
从表10可以看出，在城市差异比例为20%的时候，因为算法可以进行较多的任务间知识迁移，算法的性能最好；在城市差异比例达到50%的时候，因为可以进行的知识迁移较少，算法的性能相对较差。随着城市差异比例的提升，由于算法很难找到合适知识进行迁移，多任务优化算法性能逐渐下降。可见，得益于多任务优化算法的帮助，当任务间相似度较大的时候，算法可以取得较好的效果。
4.3.2任务数目对算法性能影响
针对8个测试问题，分别运行M-TSP算法，设置最大迭代次数T=1000次种群规模N=100，聚类数目K=5，每次计算根据2.5节所提公式（5）得出平均结果。针对每组测试问题分别运行M-TSP算法20次，结果取平均值。表11展示了当测试集合的任务数目分别为2组、4组、6组、8组时，所提M-TSP算法的计算结果。
表11任务数目算法性能影响
Table 4a Number of tasks algorithm performance impact
任务数目算法性能影响
城市名称任务数目平均值（%）CPU时间（s）城市名称任务数目平均值（%）CPU时间（s）
eil76测试集2 3.13 10.76 ch150测试集2 6.95 17.41
数据见表2 4 2.99 21.15数据见表6 4 7.07 34.38
6 3.22 31.45 6 7.17 51.94
8 2.69 40.72 8 7.75 67.90
城市名称任务数目平均值（%）CPU时间（s）城市名称任务数目平均值（%）CPU时间（s）
rat99测试集2 3.41 12.59 pcb442测试集2 9.57 68.43
数据见表3 4 4.36 24.16数据见表7 4 0.00 136.26
6 4.43 36.14 6 10.03 206.15
8 4.19 47.76 8 9.99 280.65
城市名称任务数目平均值（%）CPU时间（s）城市名称任务数目平均值（%）CPU时间（s）
kora100测试集2 5.86 12.17 pr1002测试集2 10.83 304.69
数据见表4 4 5.95 24.42数据见表8 4 11.02 609.23
6 6.88 36.78 6 11.05 917.06
8 6.03 48.92 8 11.06 1224.51
城市名称任务数目平均值（%）CPU时间（s）城市名称任务数目平均值（%）CPU时间（s）
eil101测试集2 6.74 22.72 pr2392测试集2 12.79 1897.73
数据见表5 4 7.61 41.59数据见表9 4 12.91 3736.35
6 7.61 65.29 6 12.93 5682.87
8 7.68 83.88 8 13.13 7377.36
从表11可以看出，随着任务数目的增加，算法所需时间基本呈现线性增加。这说明多任务算法在知识迁移方面没有引入过多额外计算开销。换句话说，本文迁移时机选择的较为正确，没有引入过多的无效迁移，任务间知识迁移的效率较高。
当任务数增多时，所提算法的平均误差率也仅有小幅度增加。这说明，本文所提知识迁移选择策略是有效的；在任务数目较多时，能够从中选择出合适的知识进行迁移，而没有产生较大的副作用。因此，本文所提M-TSP算法可以胜任任务数目较多的情况，其可扩展性较好。
4.4算法对比结果分析（Algorithm comparison result analysis）
4.4.1对比算法
为了证明所提算法性能，本文选择4种常见算法与所提算法进行比较。这些对比算法分别是：（1）粒子群优化算法（PSO）[35]；（2）蚁群算法(ACO)[36]；（3）PSO-ACO[37]算法；（4）免疫克隆算法(ICPSO)[38]。
4.4.2实验结果
在8个多任务测试集上，对比本节所提算法M-TSP和4种典型TSP求解算法。设置M-TSP算法粒子群规模为100，最大评价次数为1000次。为保证对比的公平性，其他对比算法的最大评价次数同样设置为1000，种群或者粒子群规模为100，其他参数参考相应文献进行设置。其中，PSO算法采用线性递减权值(LDW)策略，其惯性权重从0.9线性递减0.4；在ACO算法中，和的启发式因子分别设置为1和3；在ICPSO_TSP算法中，设置免疫样本数目为100，最多免疫迭代次数为1000。
针对8个多任务优化测试问题，均采用30%的城市差异度比例，任务数设置为8个，表12给出了M-TSP、PSO、ACO、PSO-ACO和ICPSO_TSP所得最短路径的平均误差。
表12多种算法对比测试结果
Table 12 Comparison test results of multiple algorithms
算法PSO ACO PSO-ACO ICPSO M-TSP
eil76测试集平均值16.24 5.05 2.32 22.64 2.69
数据见表2 CPU时间(s)157.60 49.63 2699.34 13.44 40.72
rat99测试集平均值25.14 6.61 4.48 29.72 4.19
数据见表3 CPU时间(s)205.15 83.41 3080.38 15.68 47.76
kora100测试集平均值26.72 8.32 7.82 40.11 6.03
数据见表4 CPU时间(s)207.40 84.64 3097.21 15.84 48.92
eil101测试集平均值23.43 8.48 8.12 27.2 7.68
数据见表5 CPU时间(s)213.50 89.04 3286.35 15.79 83.88
ch150测试集平均值28.83 8.93 8.45 39.52 7.75
数据见表6 CPU时间(s)322.81 203.21 5341.23 21.136 67.90
pcb442测试集平均值39.87 16.48 9.96 50.92 9.99
数据见表7 CPU时间(s)1121.68 2081.84 10334.64 55.32 280.65
pr1002测试集平均值47.23 14.21 13.85 80.82 11.06
数据见表8 CPU时间(s)3263.98 14027.68 30821.45 129.44 1224.51
pr2392测试集平均值58.72 23.20 14.93 108.93 13.13
数据见表9 CPU时间(s)11957.42 52824.12 60821.34 376 7377.36
通过表12中实验结果可以看出，在rat99、kora100、、eil101、ch150、pr1002和pr2392等6个测试集上，得益于本文所提多任务优化算法的帮助，M-TSP算法都取得了最好的收敛精度，所得平均误差最小；在eil76和pcb442测试集上，M-TSP算法结果略差于PSO-ACO算法，但是所需要的时间仅仅需要前者的几十分之一。在计算时间方面，ICPSO算法表现最好，但是其计算结果较差。特别是，对于大规模TSP问题，如pr2392测试集，其误差率超过了100%；本文所提M-TSP算法计算时间稍长于ICPSO算法，但是优于PSO、ACO和PSO-ACO算法。
综上所述，本文所提的多任务粒子群优化算法，显著改善了传统PSO算法的性能，提升了计算速度与计算结果质量，在解决多任务TSP问题上表现出了高的竞争力。
