基于子空间对齐和反向学习的进化多任务优化算法

徐 奇,葛方振

(淮北师范大学 计算机科学与技术学院,安徽 淮北 235000)

进化算法是一种通过模拟生物基因遗传和种群进化而产生的群体导向随机搜索的方法,由于其具有高度并行、自适应等特征,可以有效解决现实生活中存在的许多优化问题,如路径规划[1]、车间调度[2]等。随着优化问题的日益复杂,研究人员发现很多问题并不是独立存在的[3-4],它们之间可能存在着或多或少的联系。受人类同时处理多个不同任务的能力的启发,研究人员提出了进化多任务优化(Evolutionary Multitasking Optimization,EMT)[5-6]的概念。

与传统的单任务进化算法相比,进化多任务算法在对不同任务进行进化搜索时,能够利用任务间的相似性,在任务间共享可重复使用的知识,使其在解决优化问题时具有更好的性能[7]。然而,随着任务变得越来越复杂,不同任务有可能来自不同领域,或拥有完全不同的特征,负向任务间交互就会导致信息的负迁移[8],使算法的性能受到负面影响。因此,在EMT 算法中,迁移什么信息、如何迁移信息一直以来都受到了研究者们的广泛关注。

在进化算法中,种群个体是任务的信息载体,迁移什么信息就是要选择哪些个体进行迁移。Gupta等[9]提出了多因素进化算法(MFEA),该算法以遗传算法为框架,将多个任务的决策空间映射到统一空间中,在个体选择交配阶段,将另一任务种群中随机选取的个体与当前任务的个体作为父代,以一定概率进行交叉变异产生新的子代,实现不同任务知识的迁移。然而,这种方法在解决不相似问题时会产生大量无效的解,造成信息的负迁移。Fend等[10]在EMEA 中利用单个目标对个体进行排序,将排名靠前的个体作为迁移个体。这种方法在任务最优解相邻时可以取得好的效果,但任务之间相似度低时,不能取得较好效果。Lin等[11]提出了一种基于历史支配关系的策略选择迁移个体。该方法根据迁移到目标任务的表现来选择下一个进化过程中要迁移的个体。实验结果表明,该方法优于前两种迁移个体选择方法。

然而,直接对源任务选择出的优秀个体进行迁移不能保证迁移信息适配于目标任务。因此,需要选择一种合适的信息迁移方式,避免将源任务中无关信息迁移至目标任务中造成负迁移。随着多任务优化的深入研究,研究人员意识到迁移学习[12]方法在探索任务之间存在的关系的重要性。为深入理解任务之间的潜在关系,减少知识负迁移的产生,Bali等[13]提出了一种线性化域自适应(LDA)策略,该策略将简单任务的搜索空间转化为具有高度相关性的复杂搜索空间,以实现任务之间的信息交换。Liang等[14]提出了一种基于子空间对齐和自适应差分进化(DE)的MOMFEA-SADE 算法。其通过学习映射矩阵将种群的搜索空间映射到一个子空间,实现任务之间的高效知识转移。Chen等[15]提出了EMT-LTR 算法,在该方法中,每个任务的决策空间被看作一个流形,任务关系被表示为多个映射函数组成的联合映射矩阵M,通过M将任务间转移的个体映射到潜在空间,在不同决策空间之间进行信息传递。Hu等[16]提出了一种TCADE算法,将TCA 方法用于构建降维子空间,利用任务之间的相关性来寻找迁移个体,同时使用DE算子提高种群多样性,通过实验表明,TCADE 能够有效利用任务之间的潜在关系,减少知识迁移时负迁移的产生。

为了在多任务优化过程中迁移更多样、更有用的特征信息,避免源任务无关信息迁移至目标任务中造成的负迁移,本文提出了一种基于子空间对齐和反向学习的EMT 算法(EMT-SOL)。该算法基于历史支配关系选取迁移个体,通过利用迁移学习中子空间对齐策略,建立任务之间的映射关系,减小源任务与目标任务之间的个体差异;同时迁移个体利用目标任务种群进行反向学习,提高目标任务种群的多样性,加快种群收敛。本文选取技术报告[17]中的9个标准测试集作为测试对象,将EMT-SOL 算法与MFEA[9]、EMEA[10]、EMT-ET[11]、MOMFEA-SADE[14]、SPEA2[18]和NSGA-Ⅱ[19]进行对比研究,研究结果表明,EMT-SOL算法迁移个体存活率更高,目标任务可以从迁移个体获取更多的有益信息,并且算法收敛性能更好。

1 相关知识

1.1 问题描述

EMT 包括单目标多任务优化(STO)和多目标多任务优化(MTO)[20]。本文研究的是求解MTO 问题的算法性能。MTO 由多个多目标优化问题组成,不失一般性,MTO 问题定义为:

其中,Fk表示第k个多目标优化问题表示第k个任务的决策空间;nk表示第k个任务的决策空间维数由mk个实数连续目标函数f1k,…,fmkk组成;Rmk表示第k个任务的目标空间。

1.2 子空间对齐

多维数据通常具有一个或多个有效的低维结构模型,这些低维结构代表了数据的本质维度和特征。子空间对齐[21]是一种域自适应算法,可以有效挖掘数据低维结构。对于两个样本数据,通过特征向量表示源域和目标域的子空间,学习映射函数来寻找域不变特征空间,该映射函数将源子空间与目标子空间对齐,实现最小化源数据和目标数据之间的差异。

对给定的源域数据样本S和目标域数据样本T(其中S,T∊Rm×d,m为数据集大小,d为数据维度),首先,使用主成分分析(PCA)获得源数据和目标数据的特征向量,保留其对应的特征值95%信息,通过特征向量生成源域和目标域的子空间ZS∊Rd×h和ZT∊Rd×h(h为子空间维度);然后通过最小化Bregman散度L(M)=‖ZS·M-ZT‖2F≈0(其中F表示Frobenius范数,M表示最小化ZS和ZT之间的差异的转换矩阵)实现ZS与ZT坐标对齐,Z′S=ZT·M(Z′P表示对齐后的源域子空间)。由于ZS与ZT均为正交矩阵,且F具有正交不变性,因此Bregman散度为:

式中,ZTS为ZS的转置矩阵。

通过式(2)实现ZS与ZT的最优对齐,从而消除源域与目标域之间的数据分布差异:

1.3 反向学习

反向学习策略[22]是由Tizhoosh提出的一种能够提高算法搜索的智能计算方法,目前已广泛应用于进化算法、粒子群算法等智能优化算法中。点x,x∊[a,b]在一维空间中反向学习搜索空间跃变示意图如图1所示。

图1 搜索空间反向学习示意图

假设x∊[a,b],则x的对立点定义为=a+b-x。将定义拓展到n维空间,设在n维空间中存在点p=(x1,x2,…,xn),其中xi∊[ai,bi],i=1,2,…,n,则其对立点=(1,2,…,n),其中i=ai+bix i。

汪慎文等[23]在反向学习的基础上提出了精英反向学习策略,该策略首先找到当前种群中的若干精英个体,计算出当前种群个体的精英反向解,从而生成一个精英反向种群;然后将产生的精英反向种群与当前种群一起竞争,选出优秀个体作为下一代种群。实验结果表明[23],精英反向学习策略可以促进群体进化过程的跃变,从而使算法具有较快的收敛速度。

2 本文算法

2.1 统一搜索空间

为了构建任务之间的信息交流环境,在M TO 问题的研究中通常将所有任务的搜索空间归一化到统一的搜索空间Y∊[0,1]DY中。假设在一个MTO问题中有K个优化任务{T1,T2,…,TK},任务Ti对应的决策空间和维数分别为Xi和Di。为了在信息迁移时能够给目标任务提供完整的信息,将所有任务中维度最大值作为统一搜索空间维数,即DY=Max{D1,D2,…,DK},假设任务Ti的第j个决策变量Xji∊归一化公式为

2.2 迁移个体选择

在多任务进化算法中,基于历史支配关系选取策略是一种具有代表性的迁移个体选择方法。当被迁移的个体在目标任务中是非支配的,那么该个体实现了正迁移;同时,在正迁移个体的源任务的搜索空间中,与该个体最接近的解(基于欧式距离)最有可能实现正迁移。从t-1(t>1)代种群中选取迁移个体的示意图如图2所示。

图2 迁移个体选取示意图

给定任务T1的种群P={p1,p2,…,pn}和任务T2的种群Q={q1,q2,…,qn}(其中P,Q∊Rm×d,m表示种群中的个体数,d表示决策变量维数)。假设T1为源任务,T2为目标任务,在源任务种群P进化至t代时,对将要迁移的个体X={x1,x2,…,xk}的选择方式具体如下:

①当t=1时,从P中随机挑选k个个体进行迁移;

②当t>1时,根据第t-1代正迁移个体选择新的迁移个体;如果t-1代源任务的迁移个体在目标任务上均未实现正迁移,则从种群P的第t代选取k个非支配解作为迁移个体。

2.3 个体迁移策略

对于选择后的迁移个体,需要合适的迁移策略来减少将源任务中无关信息迁移至目标任务中去。为此,基于1.2中子空间对齐方法对给定的源任务种群P和目标任务种群Q使用PCA方法获取对应的子空间ZP和ZQ,利用最小化Bregman散度获取子空间之间的映射关系M*,通过M*实现P与Q之间的数据分布差异最小化,达到有效地利用任务之间的潜在关系;同时借鉴精英反向学习思想,将迁移个体集X*作为一个种群,利用目标任务种群计算出反向迁移解,从而生成一个反向迁移种群*与目标种群个体竞争。第t代个体迁移策略流程图如图3所示。

图3 个体迁移策略流程图

(1)子空间对齐。对于从源任务种群P中选取的迁移个体集X={x1,x2,…,xk}中的个体xi,i=1,…,k,首先通过xi·ZP映射到子空间ZP中;根据子空间映射关系M*将xi转换到子空间ZQ;最后,通过xi·Z*P·ZTQ将xi转换到Q空间作为选择的迁移个体,即

式中,x*i为源任务中个体xi转换到目标任务后的个体;ZTQ为ZQ的转置矩阵。

(2)反向学习。为了提高目标任务种群的勘探能力,EM T-SOL算法借鉴精英反向学习思想,对转换后的迁移个体集X*执行反向学习策略,使*充分吸收目标种群中个体的有益搜索信息,加快目标任务种群的收敛速度;同时将*与目标种群Q合并,选出优秀个体进入下一代群体中以增强种群的多样性,帮助算法跳出局部最优陷阱。

对于迁移个体集X*={x1*,x2*,…,xk*,}和目标任务种群Q={q1,q2,…,qn};设第t代qi,j和xi*,j(t)分别为qi(t)和x*i(t)在第j维上的值,迁移个体反向解*i,j(t)通过式(5)进行计算:

式中,λ∊(0,1)为随机数;aj=min(q1,j(t),…,qm,j(t));bj=max(q1,j(k),…,qm,j(k));若*i,j(t)>bj(t),则取

2.4 EMT-SOL算法

EMT-SOL以EMT-ET 算法为框架,对其个体迁移策略进行了改进。EMT-SOL 算法的伪代码如表1所示。

表1 EMT-SOL伪代码

3 实验与结果分析

为验证本文所提出算法的性能,选取技术报告[17]中的9个标准测试集作为测试对象。在标准测试集上,每一个多任务优化问题都包含两个多目标优化问题,每个问题的性质如表2所示。

表2 多目标多任务优化问题性质

3.1 实验设置

对于每个测试问题,本文所提出算法EMT-SOL 都将与算法EMT-ET、MOMFEA-SADE、EMEA、MFEA、SPEA2和NSGA-Ⅱ进行对比。

(1)种群大小:在测试问题中,两目标优化问题种群大小设置为100,三目标优化问题设置为120。

(2)最大迭代次数:Gmax=500。

(3)独立运行次数:nr=30。

(5)MFEA 算法中的随机交叉概率(rmp)根据文献[9]设置为Pr=0.3。

3.2 算法评价指标

在本文中,采用IGD(In verted Generational Distance)[24]评估算法的收敛性和种群的多样性,算法性能越好,IGD 值越小。公式如下:

式中,|P|为真实PF中的种群个体个数;di为真实Pareto前沿上的每个个体到算法选出的种群个体的最短距离。

3.3 实验结果与分析

各个算法在测试集上分别运行30次的IGD 平均值如表3所示。根据表3中数据可以看出,本文所提出算法EMT-SOL 与其他算法相比,在大多数的测试问题中都显示出较好的性能。结合测试函数性质,我们对EMT-SOL算法能够表现出良好的性能进行了以下分析:从表中CIHS-CILS的测试结果可以看出,EMT-SOL算法在大多数问题上都优于其他比较算法。这是因为在CIHS-CILS测试集上,每个问题都是由两个具有相同Pareto前沿的任务组成,当源任务种群收敛到Pareto前沿上时,目标任务就能够得到解决,但源任务种群的非支配个体并不能直接帮助目标种群。EMT-SOL 算法根据历史支配关系能够选取更合适的迁移个体,并通过构建任务之间的映射关系,最小化任务之间的差异,从而对源任务选取的迁移个体进行转换,使源任务个体能够更好地帮助目标任务种群加快收敛速度。

表3 7种算法在测试函数上的IGD 平均值

在PIHS-PILS测试集上,本文所提出算法的性能明显优于其他算法,这是因为在此测试集上每个问题包含的两个任务在Pareto前沿上有部分交集,但两个任务的Pareto前沿并不相同。EMT-SOL算法在选取合适的迁移个体后,迁移个体利用目标任务种群进行反向学习,能够增强目标任务种群的多样性,帮助目标任务跳出局部最优陷阱。

在NIHS-NILS测试集上,本文所提出算法在部分问题中仍然优于其他比较算法。对于此测试集中的每个问题,其两个优化任务在Pareto集合中并没有任何交集,因此,直接迁移源任务个体可能无法有效的提高目标任务的求解效果。EMT-SOL算法基于子空间对齐的方法,减小迁移个体与目标种群个体的数据差异,避免源任务中无关信息迁入目标任务中;同时通过反向学习使迁移个体吸收了目标任务种群中的个体有益搜索信息,从而提高目标种群的多样性和算法搜索能力,加快算法的收敛速度。

同时,为验证迁移个体在目标任务种群中的存活率,将本文所提出算法与EMT-ET、MOMFEASADE、MFEA 在进化过程中分别获得的正迁移比例(正迁移的比例为正迁移解决方案的数量除以迁移解决方案的总数)进行比较,以比较它们选择有价值的知识迁移个体的能力。在本实验中,每50代计算一次正迁移的比例,独立运行30次。

4种算法在9个测试问题的进化过程中得到的正迁移的平均比例如图4所示。从图4中可以看出,本文所提出算法在正迁移比例方面比其他4种算法更适合大多数测试问题。特别是针对CIHS、CIMS、CILS、PILS-Task1等问题,EMT-SOL 算法平均正迁移率接近0.46,而EMT-ET、MOMFEA-SADE 和MFEA 的平均正迁移率分别为0.38、0.31和0.24。在其他测试问题上,虽然EMT-SOL算法获得的正迁移比例存在一定的波动,但仍然比EMT-ET、MOMFEA-SADE 与MFEA 具有更好的性能和更好的稳定性。因此,本文所提出算法从源任务中选择的迁移个体能够实现更多的正迁移,目标任务可以从迁移个体获取更多的有益信息,帮助目标任务种群加速收敛。

图4 各算法在进化过程中的正迁移的平均比例

4 结论

本文基于子空间对齐和反向学习提出了一种新的EMT 算法(EMT-SOL)。为了在多任务优化过程中迁移更有用的特征信息,通过基于历史支配关系选择出更为有效的迁移个体,然后利用子空间对齐的方法,构建源任务种群和目标任务种群的映射关系,通过映射关系减小迁移个体与目标种群个体的数据差异,提高迁移个体在目标任务中的存活率,避免产生信息的负迁移;同时,为了提高目标任务种群的多样性,利用目标任务中的个体对迁移个体进行反向学习,使迁移个体吸收目标任务种群中的个体有益搜索信息,以探索目标种群的搜索空间。实验结果验证了所提算法的有效性,与其他多目标多任务算法相比较,本文所提出算法在测试集上运行的效果更好,并且迁移个体在目标任务种群中实现正迁移的比例更高。