摘要
通过利用跨任务的知识转移, 多任务优化可以实现比传统单任务优化更好的收敛性能. 然而, 在多任务优化中, 搜索空间和优化场景的偏差以及干扰知识转移的噪声, 都可能导致有效知识转移效率的降低, 甚至出现负向迁移. 为解决此问题, 本文提出一种基于最小二乘法 (PLS) 子空间对齐和种群重用机制的多任务优化算法 (PRMTEA). 首先, 通过引入PLS子空间投影策略, 将高维任务搜索空间向低维空间转化, 并建立各任务所拥有种群的特定低维子空间; 其次, 实时调整子空间Bregman散度获取对齐矩阵, 实现跨任务知识转移; 最后, 设计基于Residual残差结构的种群重用机制, 避免出现负向迁移和陷入局部最优情况, 并提高算法的收敛性能. 实验结果表明: 与其他4种先进多任务优化算法进行相比, PR-MTEA具有更好的收敛性能和快速搜索能力. 另外, 通过传感器覆盖问题进行测试分析, 进一步验证算法的可行性和适用性.
Abstract
By using cross-task knowledge transfer, multi-task optimization can achieve better convergence performance than traditional single-task optimization. However, in multi-task optimization, the deviation of the search space and optimization scenarios, as well as noise that may interfere with knowledge transfer, can lead to a decrease in the efficiency of effective knowledge transfer and even negative transfer. An multi-task optimization algorithm based on partial least squares (PLS) subspace alignment and reuse population mechanism (PR-MTEA) is proposed to solve the problem. Firstly, by introducing the PLS subspace projection strategy, the high-dimensional task search space is transformed into a low-dimensional space and specific low-dimensional subspaces are established for each task’s population. Secondly, real-time adjustment of the Bregman divergence of the subspace is used to obtain an alignment matrix and achieve cross-task knowledge transfer. Finally, a population reuse mechanism based on the Residual structure is designed to avoid negative transfer and getting stuck in local optima, as well as to improve the convergence of the algorithm. Comparative experimental results with four other advanced multi-task algorithms show that PR-MTEA has better convergence performance and faster search ability. In addition, sensor coverage problem is conducted to test and analyze the feasibility and applicability of the improved algorithm.
1 引言
种群进化算法是一类基于达尔文进化学说思想而提出的启发式搜索算法. 种群进化算法通过对群体中个体进行交叉,变异和选择等操作来不断改进解的质量,以求得给定问题的最优解 [1] . 在过去的几十年中,种群进化算法因其具有优异的全局搜索能力和无导数特性,在解决大量复杂现实优化问题的最优解或近似最优解方面表现卓越,包括连续优化 [2-3]、组合优化 [4-5]、约束优化 [6-8] 和作业车间调度 [9] 等. 然而,在优化过程中,存在着多个相同或相似的场景. 传统的种群进化算法只针对当前应用场景进行参数优化,未能充分利用相似场景中的优化数据,从而限制了其算法性能的提升空间.
进化多任务(evolutionary multi-tasking,EMT)是当前进化计算领域备受关注的新兴分支 [10-11] . 其目的是通过利用多个任务间的潜在协同作用同时解决多个优化任务. 多因素优化(multi-factorial optimization,MFO)是EMT的先驱范式 [12] . 在这个范式下,Gupta等提出多因子进化算法(multi factorial evolutionary algorithm,MFEA)来解决多任务优化问题. MFEA利用了单个种群的隐式并行性,从而使得不同任务的知识转移成为了现实,并有效地解决了多个优化任务.
迄今为止,学者们已提出了许多的多任务优化算法,主要分为两类: 基于统一搜索空间的多任务优化算法和基于显式自编码知识转移的多任务优化算法. 基于统一搜索空间的多任务优化算法通过将不同任务的搜索空间共同映射至同一搜索空间,并利用种群的隐式并行性完成知识转移 [13-15] . 基于显式自编码知识转移的多任务优化算法则是设计额外的知识转移策略,通过自动编码器将一个搜索空间中的高质量解显式地转移至另一个搜索空间中以实现跨任务的知识转移 [16-17] . 值得注意的是,有研究表明任务间的相似程度很大程度上影响多任务优化的性能 [18] . 然而,每个任务之间的相似度并不总是很高,存在搜索空间的上下限,维度不同以及凹凸性相反的情况. 在上述文献中,第1类多任务优化算法为了方便进行知识转移,将各任务限定于统一的搜索空间,忽略了任务间相似度差异引起的搜索空间和优化场景的不同,从而导致算法性能的下降. 而第2类多任务优化算法中,额外设计的知识转移策略转移的是原始高维空间中的解,并且自动编码器的设定仅依赖于种群中有限的个体,因此知识转移容易受到噪声的干扰.
为解决上述问题,本文提出一种基于最小二乘法(partial least squares,PLS)子空间对齐和种群重用机制的多任务优化算法(partial repeats population multitasking evolutionary algorithm,PR-MTEA). 首先,采用基于PLS的降维方法,将优化任务的搜索空间降维至子空间中,以提高知识转移对噪声的鲁棒性; 其次,实时调整子空间Bregman散度获取对齐矩阵,以实现更好的知识转移效果; 最后,设计种群重用机制以进一步改善负向迁移的现象,从而避免搜索进程陷入局部最优. 为了验证PR-MTEA的有效性,对两种多任务优化基准测试问题进行了全面实证研究. 实验结果表明,PR-MTEA优于其他多任务优化算法.
2 算法设计与分析
2.1 基于PLS子空间对齐的知识转移策略
近年来,基于子空间对齐的迁移学习方法被广泛研究并应用于实践中 [19-20] . 因为它可以将源域和目标域的数据分布映射到一个公共的低维子空间,从而提高知识转移的效果和对噪声的鲁棒性. 而PLS作为监督式的降维方法,则能够保证提取得到的特征变量不仅能够很好地概括源域数据的信息,而且能对目标域数据有很强的解释能力. 因此,本文提出一种基于PLS子空间对齐的知识转移策略,旨在进一步提升算法在知识转移过程中的效率和抵抗干扰噪声的能力.
该知识转移策略的具体过程如下: 首先,采用基于PLS的降维方法分别获得源域数据和目标域数据的特征向量; 其次,以挖掘到两组数据相关性最大的特征向量为基底,生成源域数据和目标域数据的子空间; 最后,采用优化线性变化函数L,即Bregman散度矩阵,来寻找对齐矩阵以实现子空间的对齐. 假设两个任务对应的子空间分别为X1和X2,其中: X1,X2∈,r代表源域数据和目标域数据的维数,h代表子空间维数,则线性变化函数L如式(1)所示:
(1)
其中:表示Frobenius范数,M表示使子空间X1 和X2之间差异最小的对齐矩阵. L(M)的最优解M∗ 表示为
(2)
对式(2)运用正交运算进行求解,使得
(3)
其中,由X1标准正交后得到, · X1 = I,I是单位矩阵,I ∈ . 由式(3)可以推导得到
(4)
根据式(4)可得式(1)的最优解M∗
(5)
由式(5)可以得到子空间X1的新坐标系,即=X1× M∗,子空间X1可以通过对齐矩阵M∗映射到X2.
给定两个初始种群S = {s1,· · ·,sn}和P = {p1,· · ·,pn},每个种群与一个任务相互关联(其中S,P ∈ ,n 表示种群数量, d表示单个决策变量维度),假设S作为源域数据,P作为目标域数据. 根据子空间对齐方法,利用PLS方法对S和P进行降维并构造子空间,如式(6)所示:
(6)
其次,根据式(5)可以得到子空间XS映射到XP的对齐矩阵M∗,因此XS与XP的对齐如式(7)所示:
其中表示将XS转化为XP的新坐标系.
子空间中两个种群的知识转移过程如图1所示. 由于M∗表示从S的子空间XS到P的子空间XP的对齐矩阵,因此种群S和P的映射关系可以由式(7)建立. 特别地,种群S中的单个个体x 可以通过如式(8)所示,将其映射并转换为种群P中的x∗,即
(8)
图1子空间中的知识转移过程
Fig.1The knowledge transfer process in the subspace
个体x首先通过x · XS投射至子空间XS中,再以 x · XS · M的方式转化至子空间XP中,最后通过与 相乘还原至种群P的原始空间中. 在本文中,任务之间知识转移的间隔设定为m = 2.
2.2 种群重用机制设计
在多任务优化的过程中,任务之间的知识转移可以帮助种群获得其他任务的高质量解,从而促进收敛. 然而,随着知识转移的进行,个体携带的有效信息逐渐减少,可能会影响种群的收敛性能,甚至导致收敛陷入局部最优. 为解决这个问题,受到Residual残差结构在深层网络中解决退化问题的启示 [21],本文提出一种种群重用机制,它通过维持种群的收敛能力来避免陷入局部最优.
不同于Residual应对网络退化问题,Respop的目标是保持种群的收敛能力,以防止种群在迭代和知识转移中陷入局部最优. 因此,Respop在每隔y次迭代后将抽取当前迭代中的优秀个体进行存储,并在相隔 y代后,将之前存储的优秀个体取出并替换当前种群个体. 通过这种方式让原有种群的优秀个体参与当前迭代的变异和更新,以解决种群收敛能力退化以及陷入局部最优的问题. 在本文中,设定y = 20,每次存储个体数量为h = 10. Respop的结构如图2所示.
2.3 多任务优化算法PR-MTEA
本文将两种不同的优化器: 遗传算法(genetic algorithm,GA)[22] 和粒子群算法(particle swarm optimization,PSO)[23] 作为多任务优化算法的基本进化单位,每个优化器都有独立的种群用于进化. 其次,引入基于PLS子空间对齐的知识转移策略和Respop机制,以实现多个任务之间高效和高质量的知识转移. 在求解多个由两个任务以上组成的优化问题时,可以将原问题拆分为若干个双任务优化问题,每个双任务问题采用同样方法求解. PR-MTEA 的整体流程如算法1(见表1)所示.
图2Respop结构示意图
Fig.2Schematic diagram of the Respop structure
2.4 PR-MTEA时间复杂度分析
本文以同时优化2个任务为例,讨论PR-MTEA的时间复杂度. 假设种群Pi(i = 1,2)处理任务Ti,任务 Ti 的决策变量维度为Di,知识转移策略的空间维度为Dmax ,种群的规模均为N,迭代次数为maxgen. 假设PR-MTEA优化任务Ti的时间复杂度为Qi,则总体复杂度为2个任务时间复杂度和两个关键组件时间复杂度之和. 该算法的整体时间复杂度为
表1算法1: PR-MTEA
Table1Algorithm 1: PR-MTEA
1)优化任务 T1 的时间复杂度分析. 种群P1的时间复杂度 Q1包括: 初始化种群位置的复杂度为 O(N · D1); 初始化进化算子参数时间复杂度为 O(1); 计算每个个体适应度值的时间复杂度为 O(N · D1); 交叉变异时间复杂度为O(N · D1); 计算当前个体适应度值的时间复杂度为O(N · D1); 得出当前全局最优个体时间复杂度为O(N); 循环maxgen代后, Q1 = O(maxgen ·N · D1).
2)优化任务T2的时间复杂度分析. 种群P2的时间复杂度Q2包括: 初始化种群粒子速度和位置的复杂度为O(N · D2); 计算每个个体适应度值的时间复杂度为O(N · D2); 初始化进化算子参数时间复杂度为 O(1); 更新粒子速度和位置的时间复杂度为 O(N · D2); 更新个体自我最优解时间复杂度为 O(N); 更新全局最优个体位置的时间复杂度为 O(D2); 得出当前全局最优个体时间复杂度为 O(N); 循环maxgen代后,Q2 =O(maxgen ·N · D2).
3)知识转移策略时间复杂度分析. 抽取两个任务种群决策变量的时间复杂度为O(N · Dmax); 子空间对齐的时间复杂度为O(T(T − 1)min(,N3)),其中 PLS降维的时间复杂度为O(min(,N3 )),同时需要T(T − 1)次PLS来获得T个任务的子空间.在知识转移 次后,知识转移策略的时间复杂度为
4)Respop机制时间复杂度分析. 存储次个体的时间复杂度为
3 实验与结果分析
3.1 测试问题与参数设置
本文选取 IEEE CEC2017-MTSO 测试问题 [24] 来验证多任务优化算法PR-MTEA的有效性. 此外为了体现先进性. CEC17测试集共包含了9个测试问题,每一个问题都涵盖了2个具体的最小化任务. 在深入探究这些测试问题时,可以根据全局最优解的相交程度,将其细分为 3大类别: 第1类是完全相交(complete intersection,CI),在这一类别中,全局最优解之间存在完全的交集; 第2类是部分相交(partial intersection,PI),在这一类别中,全局最优解之间存在一定的交集,但并非完全重合; 第3类则是无相交(no intersection,NI),在这一类别中,全局最优解之间完全不存在交集. 此外,还可以从函数适应度外观之间的相似性,来对这些测试问题进行分类. 根据这一标准,同样可将其划分为3组: 第1组是高相似性(high similarity,HS),在这一组中,函数适应度外观极为相似,难以区分; 第2组是中等相似性(medium similarity,MS),在这一组中,函数适应度外观存在一定的相似性,但仍有差异; 第3组则是低相似性(low similarity,LS),在这一组,函数适应度外观差异显著,易于区分. 综上所述,CEC17测试集的组成结构相当复杂且多样化,测试集中各类问题的分布情况及其特征如表2所示.
采用其余6 种流行的多任务优化算法( MFEA [12],MFEA-II [18],MFEA-AKT [25],MFPSO [26],MTEA-SaO [27],MTPSO-DTS [28])作为对比算法. 实验中保持各算法在论文中的原始设置. PR-MTEA算法中使用了两个基本的单任务优化器,即GA和PSO. 其余实验设置总结如下:
1)种群规模: 多任务优化算法的每个任务种群大小设置配置为100. 同时,将rmp算子设置为0.3,多项式变异中的η = 2, β = 5.
2)最大更新次数: 所有算法的maxgen = 400.
3)独立运行次数: 为了避免随机性带来的干扰,每个算法都将独立运行20次.
3.2 实验结果分析
本文提出的PR-MTEA算法和其他6种算法在CEC2017-MTSO 基准测试问题上独立运行20次所得的平均目标值和标准差如表3所示.
表2CEC17测试集组成结构
Table2Composition structure of the CEC17 test set
表3PR-MTEA与其他算法在CEC2017-MTSO上的测试结果
Table3The test results of PR-MTEA and other algorithms on CEC2017-MTSO
( 转下表)
( 接上表)
( 转下表)
( 接上表)
( 转下表)
( 接上表)
3.2.1 解的质量分析
从表3可以得知,在 CEC2017-MTSO基准测试问题中,本文提出的PR-MTEA算法在大部分任务中的平均目标值显著优于其余 4种算法. 值得注意的是,GA 是MFEA,MFEA-II,MFEA-AKT 的基本优化器,而PSO是MFPSO的基本优化器,因此证明了本文所提出的知识转移策略能够在不同优化器中有效传递高质量解,此外,从表2可以知道,本文的PR-MTEA算法在18个任务中有12个平均目标值最优. 在部分测试函数上没有取得最佳效果,这可能是由于在迭代过程中没有产生足够多的优秀个体. 特别地,PR-MTEA 在面对CI,PI,NI 3种不同相交程度和HS,MS,LS 3种不同任务相似度的多任务优化问题中均能取得很好的收敛效果,这也进一步地说明了本文所提出的知识转移策略的有效性.
3.2.2 算法收敛轨迹分析
为了清晰地比较不同算法在优化效果上的差异,本文绘制了PR-MTEA和其他算法在部分基准测试问题上的平均收敛轨迹,如图3所示. 需要注意的是,每个子图中的X轴代表迭代次数,Y 轴代表当前迭代次数对应的平均目标函数值的对数. 限于篇幅,仅给出PR-MTEA个部分算法在部分基准测试函数上的平均收敛轨迹.
图3显示了算法在部分问题上20次运行的平均收敛轨迹. 从图中可以明显看出,在前期的迭代过程中,PR-MTEA在大多数问题中都能保持一个较快的收敛速度,并且在后期的迭代中能够取得较好的收敛结果.
PR-MTEA通过基于PLS子空间对齐的知识转移策略和Respop机制,在面对不同类型和相似度的任务时能够帮助算法迅速转移有效的高质量解,并避免种群出现局部最优的情况. 因此,PR-MTEA具有快速收敛的能力和出色的性能.
3.2.3 参数敏感性分析
PR-MTEA中引入了两个关键参数: 任务知识转移代数m和Respop间隔代数y. 本节通过改变各参数值来检验算法的收敛效果. 对任务知识转移代数m选取5个代表性的点2,4,6,8,10; Respop间隔代数选取5个代表性的点20,30,40,50,60; 在每一种参数组合的具体配置下对测试函数进行50次独立重复实验以确保结果的稳定性和可靠性,同时将该平均值作为衡量综合收敛精度的标准. 限于篇幅,仅列出CIHS-T1函数的实验数据,具体结果如表4所示.
由实验结果可知,当固定任务知识转移代数m时,随着Respop间隔代数y的增大,函数的求解性能逐渐下降,在取20时可获得最优收敛精度. 与此同时,随着任务知识转移代数的增加,函数的平均值整体呈现出增大趋势,收敛精度也随之呈现出下降趋势.
3.2.4 改进策略有效性分析
为了分析提出的改进策略有效性以及对算法性能的影响,将仅引入PLS子空间对齐知识转移策略的多任务优化算法(partial multi-tasking evolutionary algorithm,P-MTEA),仅引入种群重用机制的多任务优化算法(respop multi-tasking evolutionary algorithm,RMTEA)与使用完整策略的PR-MTEA进行对比分析. 限于篇幅,选取6个基准函数对算法进行测试,实验结果详见表5.
图3PR-MTEA和其他算法在WCCI2020 MTSO3,MTSO6-T1,MTSO7-T1,MTSO9和MTSO10上20次独立运行的平均收敛图
Fig.3The average convergence plots of PR-MTEA and other algorithms running independently for 20 times on WCCI2020 MTSO3, MTSO6-T1, MTSO7-T1, MTSO9 and MTSO10
表4不同参数组合下测试函数的平均值
Table4The average value of the test function under different parameter combinations
表5不同改进策略的对比结果
Table5The comparison results of different improvement strategies
从表5中可以看出,PR-MTEA整体上取得了最好的最优值,平均值及标准差,未使用任何改进策略的原始多任务优化算法效果最差,仅融合单一改进策略的算法无法完全提升算法的性能,同时融合子空间对齐知识转移策略与种群重用机制算法可有效提升原算法的全局寻优能力.
4 传感器覆盖问题
传感器覆盖问题(sensor coverage problem,SCP)是一个复杂且关键的问题,它主要由传感器的线圈数量与所能覆盖的面积这两个核心因素共同关联而形成 [29] . 理想的传感器模型能够在特定的给定区域内提供完全无遗漏的100%覆盖,核心目标在于探索如何以一种既经济又高效的方式,来最小化给定区域内未被覆盖的部分,从而确保监测或感知任务的有效执行. 该问题的数学模型为
(9)
其中: x =(x1,y1,r1,· · ·,xK,yK,rK)决定了传感器在特定区域中的精确位置,xi ,yi ,ri分别表示传感器的横坐标,纵坐标及半径大小, A表示传感器所要覆盖的广泛区域范围(A ∈ [−1,1] × [−1,1]),K为需要优化的传感器的总数目. 式(9)的核心在于构建了一个在预设区域条件下的优化问题,通过科学的方法寻找出最佳的传感器数量配置,以尽可能全面且高效地覆盖目标区域,即该式目标在于最小化一个目标函数,该函数直接关联于覆盖效率与传感器数量的平衡状态.
考虑 7个待优化的任务,每个任务均由式(9)衍生得到,它们的K值分别设置为26,27,28,29,30,31和 32. 所有算法均独立运行25次,同时选取第3.1节中的算法与本文算法进行一系列对比实验. 表6详细列出了各算法在实验中所取得的最优值以及达到这些最优值时所使用的传感器数目.
限于篇幅,选取MFPSO,MFEA,PR-MTEA这3种算法的结果进行图形化展示. 图4(a),(b)以及(c)分别详尽地展示了这3种算法在覆盖指定区域时所需要的传感器数量的具体情况. 通过观察这些图表,可以更加直观地理解不同算法在达成同一目标时的资源消耗差异. 表6与图4相结合,进一步清晰地揭示了相比其他算法而言,PR-MTEA算法在覆盖指定区域时所需的传感器数量明显更少,这凸显了其在资源效率方面的优势. 另外,从图4(d)收敛曲线可以看出,在前期迭代过程中,MFPSO算法的收敛速度无疑是最快的,这一优势主要得益于它采用了PSO作为优化器,从而能够探索出更多样化的搜索路径,并在这一阶段内更快地找到质量较高的解. 然而,随着迭代的深入,PR-MTEA算法开始逐渐超越了MFPSO,并且在整个迭代过程中持续保持优势,最终获得了问题的最优解. 这一转变不仅证明了PR-MTEA算法在后期阶段具有更强的收敛能力,还进一步说明了其在处理复杂优化问题时所具备的卓越性能和稳定性.
表6仿真实验结果
Table6Simulation experiment results
5 结语
本文提出了一种基于PLS子空间对齐和种群重用的多任务优化算法PR-MTEA,以解决多任务优化搜索空间与优化场景的偏差问题和知识转移效果不佳的问题. 相对于其他多任务优化算法,本文设计的子空间知识转移策略可以有效提高不同任务之间的知识转移的效率和鲁棒性. 同时,本文还引入了种群重用机制,有效避免算法陷入局部最优,提升了算法的收敛能力. 实验结果证明了本文所提算法的有效性. 在下一步的研究工作中,计划研究迁移学习在多任务优化算法中的不同融合方式,以增强优化较低相似度多任务问题的能力. 此外,将进一步拓宽PR-MTEA算法的应用领域,例如将其应用于解决铝电解多槽优化工艺参数的多任务问题.
图4传感器最佳覆盖数及收敛曲线
Fig.4The optimal coverage number of the sensor and the convergence curve