基于迁移学习的拐点预测策略求解动态多目标优化问题

江储文,葛方振,刘怀愚,高向军,沈龙凤

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

动态多目标优化问题(dynamic multi-objective optimization problems,DMOPs)广泛地存在现实生活中,如动态调度[1-3]、路径规划[4-5]、货位优化[6-7]。动态多目标优化问题具有时变的目标函数和约束条件的特征,因此求解动态多目标优化问题不仅要得到最优解或最优前沿,而且要在下一次变化之前持续快速地得到最优解或最优前沿。处理动态多目标优化问题的技术有很多,如遗传算法[8-9]、人工免疫系统[10]、粒子群优化[11-12]等,其中进化算法是最受研究者关注的方法之一[13]。求解DMOPs的传统方法通常是当环境变化时在传统的静态多目标优化算法中增加种群多样性[9-14],如DNSGA-Ⅱ[14],在每次环境变化时通过移民策略增加种群多样性,DNSGA-Ⅱ-A 通过替换ζ%新种群增加多样性,DNSGA-Ⅱ-B通过替换ζ%具有突变解的新种群确保多样性。这些方法仅增加种群多样性,寻找最优解的能力仍然依靠种群的自主进化,其主要缺点是种群的收敛性差和收敛速度慢。为此,研究人员提出基于记忆的策略和基于预测的策略来引导种群进化方向。记忆策略根据以前获得的最优解或其他最优信息来快速应对环境变化,这对周期性的环境变化能够取得较好的效果,但是对于非周期性的环境变化难以获得较好的收敛性。GOH 和TAN 将存档中的过时个体添加到临时内存中[8],并根据外部种群更新存档,这样任何关于当前种群的有用信息都可以被使用。预测策略利用历史环境信息预测新环境最优解的位置,引导种群进化加快算法的收敛速度,但是历史环境信息众多,如何选取有的信息十分重要,利用PF 面上的信息进行预测是一种有效的方法。HATZAKIS 和WALLACE 提出了一种向前预测策略(FPS)[15],FPS通过PF 面上的边界点和自回归模型预测新的最优解位置,从而加速种群收敛。LI等[16]提出一种基于特殊点的预测策略(SPPS),SPPS通过中心点和特殊点跟踪PF 来快速响应环境变化。然而,PF上有很多信息(中心点,边界点等),所以想要跟踪PF就需要选择一些有代表性的点。DEB[17]证明了在HV[18]度量标准下拐点优于PF上的其他点。ZOU 等[18]提出一种基于中心点和拐点的预测策略(CKPS),将拐点集加入预测种群中,引导种群收敛,同时指出PF上的拐点是边际收益率最大的点。此外,研究人员开始将机器学习知识加入到进化计算中。2017 年,JIANG等[19]提出了基于迁移学习的动态多目标优化算法(Tr-DMOEA)。现有的大多数动态多目标优化算法通常假设不同环境下的决策空间分布是独立同分布(IID),JIANG 等认为这样的假设可能会导致算法失败。因此,他们提出了一种新的假设:DMOPs在不同的环境下解空间相互独立,并且解空间分布不同,但是它们具有相关性。JIANG 等将Tr-DMOEA 加入3种著名的多目标优化算法:NSGA-Ⅱ[20]、MOPSO[21]和RM-MEDA[22],并且做了一系列的对比实验,实验结果表明将迁移学习技术引入动态优化算法中,可以大大提高解的质量和算法的鲁棒性。

通过对迁移学习和拐点的分析,本研究提出一种基于迁移学习的拐点预测策略(TKPS)求解动态多目标优化问题。实验选取DMOP1,DMOP2,DMOP3[23],FDA1,FDA2,FDA3、FDA4 和FDA5[23]8个经典动态测试函数,将TKPS 算法与DNSGA-Ⅱ[11],PPS[24],Tr-RM-MEDA[19]算法进行对比研究,实验结果表明TKPS算法能更好地响应环境变化。

1 动态多目标优化问题

在不失一般性的前提下,DMOP可以定义为[13]

其中:x 为决策变量,f 是与时间变量t有关的M 维目标函数,g 和h 的函数分别表示不等式和等式约束集,t表示问题的时间或动态性质,M 表示目标函数的个数。

定义1(Pareto支配)设p 和q 是种群中任意两个个体,p 支配q 表示为f(p)≺f(q),当且仅当fi(p)≤fi(q),∀i＝{1,2,…,m}且∃j＝{1,2,…,m}满足fj(p)＜fj(q)。

定义2(Pareto最优解集,PS)设x 为决策变量,Ω 为决策空间,F 为目标函数,则PS 定义为

定义3(Pareto最优前沿,PF)设x 为决策变量,F 为目标函数,则PF 定义为

PF＝{y＝F(x)|x∈PS}。

2 基于迁移学习的拐点预测策略

2.1 PF拐点

拐点是距离PF 边界点连线最远的点[18],图1给出拐点的寻找过程。

图1 寻找拐点的示意图Fig.1 Sketch map of finding knee points

设有2个目标函数,A～N 是14个非支配点,其中M 和N 是非支配集的边界点,M、N 构成直线L。将PF 分成三个区域,在每个区域内找出距离直线L 最远的非支配点作为拐点,因此B、G 和K是该PF 的拐点。当目标函数的个数是3时,用非支配集的边界点构成一个平面,然后在每个区域内找到距离平面最远的非支配点作为拐点。

具体步骤如算法1所示。

算法1寻找拐点的伪代码:Seek Knee

输入:PF,拐点数目Knum。

输出:拐点集Knee。

1)寻找边界点,用边界点构成直线或平面;

2)将PF 平均分成Knum 个区域;

3)分别计算Knum 个区域上的点到直线或平面的距离,找出每个区域上距离直线或平面最远的点作为拐点,并将它们存入拐点集Knee中。

2.2 迁移成分分析

迁移成分分析[25](transfer component analysis,TCA)是本工作使用的迁移学习方法,TCA 算法用来处理领域适应问题,当源域和目标域处于不同的数据分布时,将两个域的数据一起映射到一个高维希尔伯特空间中,并且在此空间中最小化源域数据与目标域数据的距离。在处理DMOPs时,将得到的t时刻的帕累托最优前沿(PF)作为源域,以t＋1时刻的可行解为目标域,使用TCA 算法得到映射矩阵W。

2.3 记忆策略

基于记忆的方法在解决循环变化的DMOPs时是有效的。使用非支配排序的方法从种群中选取优秀个体保存在内存池中,如果内存池满了,就把当前时刻的优秀个体取代最先进入内存池的个体。记忆策略的具体步骤如算法3所示。

算法3记忆策略:Ememory

输入:内存池Memory,内存池容量Msize,当前时刻的种群Popt,Esize。

输出:Memory。

1)使用非支配排序从当前种群Popt中找到Esize个优秀个体;

2)判断Memory是否已满,如果内存池满了就转到步骤2;否则将Esize个优秀个体存入Memory;

3)Ememory使用“先进先出”原则更新Memory。

2.4 TKPS算法

本工作使用RM-MEDA 算法[22]对种群进行优化,并从种群中选取优秀个体存入Memory中。如果环境发生变化,从Memory中选取个体组成2个种群,分别作为t 时刻和t＋1 时刻的种群(如果Memory中的个体不足以组成2个种群,那么不足的个体随机生成),然后计算得到它们的目标值Yt和Yt＋1,将Yt作为源域,Yt＋1作为目标域,通过TCA 算法得到映射关系矩阵W。通过映射关系矩阵W 将t时刻PF的拐点集Kneet映射到高维希尔伯特空间得到一组映射解PLSk,然后在高维希尔伯特空间内找到下一时刻PFt＋1的拐点集对应的个体集KneePt＋1。

为了增加种群的多样性,在t＋1 时刻Knum个拐点对应的个体Pj周围,半径为r 的区域内随机产生4×Knum 个伴随个体(如果伴随个体超出决策空间范围,就将其删除),伴随个体表示如下:

将KneePt＋1和4×Knum 个伴随个体放在一起进行非支配排序,选出2×Knum 个相对最优的个体添加到下一时刻的初始种群Popt＋1中。TKPS算法的具体步骤如算法4所示。

算法4TKPS算法伪代码

输入:动态多目标优化问题F(x,t)。

输出:F(x,t)的最优解集PS。

1)初始化:t＝0,随机初始化种群Pop0,Esize,,Msize,Knum;

2)检测环境是否发生变化,如果环境发生变化,转步骤5;否则转步骤3;

3)使用RM-MEDA 算法求出当前时刻的PS、PF 和种群Popt;

4)Memory ＝Ememory (Memory,Esize,Msize,Popt);

5)环境发生变化:使用TCA 算法得到映射关系矩阵W;

6)Kneet＝Seek Knee(PF,Knum);

7)通过W 将拐点集Kneet映射到高维希尔伯特空间中,得到PLSk;

8)设置t＝t＋1;

9)for k∈PLSkdo;

10)在当前解空间中找到个体q,使得它的目标值在高维希尔伯特空间中的映射离k 最近,那么q就作为下一时刻PFt＋1的拐点对应的个体;

11)将个体q 存入KneePt＋1;

12)end;

13)通过(1)式获得伴随个体;

14)使用快速非支配排序得到一个种群大小为Pop Size 的新种群Popt＋1,并将其作为下一时刻的初始种群;

15)判断是否满足停止条件,若满足就停止;否则,跳转步骤2。

3 实验分析

3.1 测试函数

选取3个DMOP[23]和5 个FDA 系列[23]系列问题作为测试函数,其中FDA1、FDA4和DMOP3属于第一类问题[26]:PS随时间变化,PF 不随时间变化;FDA2、DMOP1 属于第二类问题:PS 不随时间变化,PF 随时间变化;FDA3、FDA5 和DMOP2属于第三类问题:PS和PF都随时间变化。函数的具体定义与特征如表1所示。

表1 测试函数Table 1 Test functions

续表1

3.2 评价指标

本研究采用反向世代距离(inverted generational distance,IGD)[23]和Schott 的间隔度量(Schott′s spacing metric,SP)[23]2个评价指标来评价算法的性能,具体信息如下:

1)反向世代距离(IGD)的值可以反应算法的收敛性和种群的多样性的优劣,IGD 的值越小,说明算法的收敛性和种群的多样性越好。计算IGD 的公式如下:其中,di表示真实PF 中的个体到算法求出的种群个体的最小欧几里得距离,|P|是算法求出的种群数量。

2)Schott的间隔度量(SP)反映算法获得的PS 在目标空间中分布的均匀性,SP 的值越小,PS的分布越好。计算SP 的公式如下:

其中:Di表示真实PF中的个体到算法求出的种群个体的最小欧几里得距离,为所有Di的均值,|P*|是算法求出的种群数量。

3.3 参数设置

1)本研究算法以基于规则模型的多目标分布估计算法(RM-MEDA)[22]为框架进行设计,RM-MEDA 算法和TCA 算法的相关参数按文献[19]进行设置。种群大小Pop Size 设置为100[26],Memory的容量大小Msize 设置为200,拐点的个数Knum设置为10[18],优秀个体Esize 设置为20,邻域半径r 设置为0.05。

参照文献[19]对时间t 的相关参数进行设置,其中nt表示变化的严重程度,设为10,τT表示最大迭代次数,设为200,τt表示变化的频率,设为10,即每个测试函数有20个环境变化,每个环境变化迭代10次。

3.4 实验结果与分析

4种算法所获解集性能指标见表2。绘制了4个算法部分时刻的解集分布图,如图2～9所示。

表2 4种算法所获得解集的性能指标Table 2 Performance indexes of the solution sets obtained by the four algorithms

图2 4种算法在FDA1上的解集分布图Fig.2 Solution sets distribution of the four algorithms on FDA1

实验环境为:Intel Core i5-8300H CPU ＠2.30 GHz,内存8 GB 2 667 MHz,硬盘为512 GB的固态硬盘,操作系统为Windows 10家庭版;所有实验都在Matlab2014b上完成。

每个测试函数将在TKPS、DNSGA-Ⅱ、PPS和Tr-RM-MEDA 算法上运行。每个算法独立运行20次,记录每次得到的IGD 和SP的值,计算它们的均值,如表2所示,表中加粗数据为较好数据。

1)针对第一类问题(FDA1,FDA4 和DMOP3),这3个测试函数部分时刻的解集分布图分别如图2、图3和图4所示。

图3 4种算法在FDA4上的解集分布图Fig.3 Solution sets distribution of the four algorithms on FDA4

图4 4种算法在DMOP3上的解集分布图Fig.4 Solution sets distribution of the four algorithms on DMOP3

从图2 中可以看出,对于FDA1 测试函数,DNSGA-Ⅱ算法在第1次和第15次环境变化时,并不能收敛到真实的PF上,表2的数据也显示DNSGA-Ⅱ的收敛性最差,这是因为DNSGA-Ⅱ算法在环境变化时仅仅增加种群多样性,无法加速种群收敛。PPS在第10次环境变化时没有收敛到真实PF上,而Tr-RM-MEDA 在第15次环境变化时没能完全收敛到真实PF 上,但从表2的数据中看出这两个算法的收敛性比DNSGA-Ⅱ算法好,这说明预测的方法可以加快种群收敛。对于FDA4测试函数,只有DNSGA-Ⅱ算法的收敛性和分布性较差,其它3个算法的收敛性和分布性较好。对于DMOP3测试函数,DNSGA-Ⅱ算法和PPS 算法的收敛性较差,DNSGA-Ⅱ算法的分布性最差,Tr-RM-MEDA算法和TKPS算法的收敛性和分布性都比较好。

2)针对第二类问题(FDA2 和DMOP1),这两个测试函数部分时刻的解集分布图分别如图5和图6所示。

图5 4种算法在FDA2上的解集分布图Fig.5 Solution sets distribution of the four algorithms on FDA2

图6 4种算法在DMOP1上的解集分布图Fig.6 Solution sets distribution of the four algorithms on DMOP1

由图5～6可以看出,对于FDA2测试函数,4种算法的收敛性都较差,都没能完全收敛到真实的PF上,但是它们的分布性都很好。对于DMOP1测试函数,4种算法中DNSGA-Ⅱ算法的收敛性和分布性最差,其余3种算法的收敛性和分布性都较好,能够快速收敛到真实PF上。

总之,TKPS算法在处理第二类问题时具有较好的效果,能够快速响应环境变化,及时收敛且保持较好的分布性。

3)针对第三类问题(FDA3、FDA5 和DMOP2),这三个测试函数部分时刻的解集分布图分别如图7、图8和图9所示。

图7 4种算法在FDA3上的解集分布图Fig.7 Solution sets distribution of the four algorithms on FDA3

图8 4种算法在FDA5上的解集分布图Fig.8 Solution sets distribution of the four algorithms on FDA5

图9 4种算法在DMOP2上的解集分布图Fig.9 Solution sets distribution of the four algorithms on DMOP2

由图7～9可知,对于FDA3测试函数,DNSGA-Ⅱ的收敛性和分布性最差,PPS也无法完全收敛到真实PF 上,Tr-RM-MEDA 表现较好,能收敛到真实的PF上,而TKPS表现最好,完全收敛到最优前沿,种群的分布性也非常好。对于FDA5和DMOP2 测试函数,这4 种算法的效果与FDA3测试函数效果表现一样,Tr-RM-MEDA的收敛性和分布性较好,TKPS的收敛性和分布性最好。

综上所述,TKPS算法的收敛性和分布性是最好的,说明TKPS算法得到的最优解更接近Pareto真实解,在目标空间中分布更均匀。这是因为TKPS算法通过记忆策略提高迁移学习的准确性,加强了算法的预测效果,在环境变化的初始时刻就能获得具有较好收敛性的解集,通过伴随个体增加种群多样性,避免种群陷入局部最优,提高了种群的分布性。

4 结 语

针对动态多目标优化问题,本研究提出了一种基于拐点和迁移学习的预测策略(TKPS),该策略将拐点和迁移学习相结合,使用记忆策略保存种群中优秀个体,通过迁移学习算法预测下一时刻的拐点,并将这些拐点对应的个体加入下一时刻的初始种群,引导种群进化方向,加快算法响应环境变化的速度。TKPS与基于规则模型的多目标分布估计算法(RM-MEDA)相结合,并在FDA 和DMOP 8个测试函数上与其它3种算法进行比较,实验结果表明TKPS算法有较好的收敛性和分布性。同时该算法结构较为简单,能够融入其它的多目标优化算法中求解动态多目标优化问题。