组合预测策略的动态多目标优化算法

唐晓乐，王宏伟+，夏 浩，罗洪平

(1.新疆大学 电气工程学院，新疆 乌鲁木齐 830047； 2.大连理工大学 控制科学与工程学院，辽宁 大连 116024)

0 引 言

现实生活中许多问题可抽象为动态多目标优化问题。近年来，动态多目标优化在工程应用[1,2]与科学研究[3,4]中得到了广泛应用。在交通运输领域，海上运输中多个港口对不同产品的供需要求，不同港口开放的时间窗口都是动态变化的，考虑上述因素的情况下，如何合理规划船舶路线与调度的同时减小碳排放与运输成本就是一个动态多目标优化问题(dynamic multi-objective optimization problems，DMOPs)；在节能环保方面，污水处理过程中的进水流量与污染物浓度总是随时间动态变化的，如何在这一变化过程中优化污水处理厂的处理成本，提高污水质量指标也是一类DMOPs。动态问题的时变性为解决动态多目标优化问题带来了很大的挑战[5]。在过去5年里，许多新的策略被陆续提出，其中多以预测机制为主[6-9]。但这些方法大多只适用于线性的环境变化，并且算法在历史信息较少的前期，若历史信息不够准确，则会影响后续预测的准确性。考虑到上述问题，本文提出一种基于新型组合预测策略的多目标优化算法(ADNSGA)。与现有算法相比，该算法主要有以下优势：

(1)利用ARIMA(autoregressive integrated moving average)与SVR(support vector regression)组合预测模型对Pareto解集(pareto set，PS)质心进行预测，可以增强算法对复杂问题与非线性问题预测的准确性；

(2)历史信息不足时，通过惯性预测方法在新环境下真实Pareto前沿(pareto front，PF)附近生成初始种群，保持多样性的同时加快算法收敛，确保历史最优解集的准确性；

(3)ARIMA-SVR与惯性预测方法的组合预测策略既增强了预测的准确性，又在多个方向上增加了预测的多个可能性，避免种群陷入局部最优。

本文选取FDA1、FDA4、FDA5[10]、dMOP1、dMOP2[11]、SW2[12]这6个动态测试函数，将本文提出的ADNSGA算法与DNSGA-II-A、DNSGA-II-B[13]、PMGA算法[14]和SGEA算法[15]进行对比研究，实验结果表明，所提算法在多个测试问题中均表现出更好的收敛性、多样性与分布性，在适应环境变化，处理线性及非线性问题方面具有一定的优势。

1 问题描述

考虑如下动态多目标优化问题

(1)

2 基于新型预测策略的动态多目标优化算法(ADNSGA)

在本节中提出了一种以NSGA-II为进化框架，用以解决DMOPs的新型进化算法，目的是利用历史最优信息，通过组合预测策略在新环境下的真实PS附近生成初始种群。为了实现这一目的，首先对每个时刻的历史信息进行有效筛选，利用聚类算法选出一定数量的代表个体。当检测到环境发生变化时，通过这些代表个体在前两个时刻的值预测产生初始种群。最后，当积累的质心时间序列足够长时使用组合预测模型预测新的质心，并与惯性预测方法结合产生初始种群，这一初始种群的产生过程可以描述为下文中的算法2。

2.1 代表个体的选取

对环境变化后的目标函数进行预测的基础是使用大量的历史数据。在多目标优化问题中，目标函数所形成的点集较大，记录PS的全部历史信息需要大量的存储空间，这将影响算法的性能。为了避免占用大量的存储空间，可从PS中选择几个有代表性的点，但是所选择的点需要能够近似描述PS及PS的分布，而不是随意选择几个点。综上考虑本文采取聚类的方法，在每一次检测到环境变化时，选取K-1个代表个体，与当前PS的质心点Ci(t) 组成代表个体集，以此来代替当前的PS流形。

首先选择当前PS的质心点Ci(t) 以及在M个目标函数上的极值点组成初始代表个体集，然后通过计算PS中所有个体到每一个代表个体的距离，将PS划分成若干簇。若选取代表性的个体不充分，则以半径最大的聚类中，距离代表个体最远的个体最为新的代表个体，重新计算该类下每个个体与代表个体的欧氏距离，相应的PS中的个体将被重新划分到对应的类中。如此往复直到选出K个代表个体。

2.2 预测模型

2.2.1 ARIMA-SVR预测模型

ARIMA-SVR组合预测模型在处理线性问题与非线性问题方面均有着良好的表现。历史最优信息先由ARIMA进行线性拟合，然后通过SVR模型预测残差，弥补ARIMA在非线性性能方面的缺失，具体流程如图1所示。该模型在一些工程应用领域中已验证了其有效性。ARIMA与SVR的模型及定义请参见文献[16,17]。

图1 组合预测模型流程

2.2.2 惯性预测模型

在算法运行前期，因可用的历史信息较少，无法建立复杂的时间序列预测模型，为了在环境变化后更快的跟踪最优解集，采用惯性预测方法提高算法的适应性，使得历史信息更加准确，为ARIMA-SVR模型的建立提供有效的历史最优信息。惯性预测可表示如下

xi(t+1)=xi(t)+(xi(t)-xi(t-1))

(2)

其中，xi(t+1) 是新环境下的预测点，因为惯性预测并不准确，因此需要加入高斯变异的方式在减小预误差的同时增加种群在新环境下的多样性。邻域中的点采用高斯变异的方式产生，产生方式如下

u(t+1)=gaussrand(xi(t+1),d)i=1,2,…,K

(3)

其中，gaussrand产生以预测点为均值，方差为d的高斯随机数，d用来控制随机数邻域大小。

2.3 预测集的产生

通过历史最优时间序列，利用ARIMA-SVR预测模型可以对新环境下的Pareto最优解集的质心进行预测，从而提高算法的适应性。然而在前期并没有足够多的变化来提供历史数据，可用历史数据较少。因此首先采用一种简单的预测方法，称为惯性预测，当累积到一定的历史最优数据后，再加入质心预测策略，进一步提高算法的适应性。预测集的产生可以描述为算法1。

算法1：预测集的产生

步骤1 选取K个代表个体组成代表个体集CS(t)；

步骤2 当t=1时，转到步骤7；当1T时，t取正整数，转到步骤4；

步骤3 根据式(2)生成新环境下的K个预测个体Cset， 然后根据式(3)得到新环境下预测集u(t+1)。 转到步骤6；

步骤5 其它K-1个预测个体根据式(2)生成，然后根据式(3)通过Cset得到新环境下预测集u(t+1)。 转到步骤6；

步骤6 对预测集中个体ui(t+1) 进行如下调整

(4)

其中，ai，bi分别为搜索空间的上界与下界，i=1,2,…,n， 算法结束。

2.4 新型预测模型的动态多目标优化算法(ADNSGA)

本文将所提出的组合预测策略作为环境变化响应与DNSGA-II框架相结合，提出了基于新型预测策略的动态多目标优化算法ADNSGA，其算法框架可以描述如算法2所示。

算法2：ADNSGA

步骤2 环境变化检测，若环境发生变化则Dynamic←Truth， 否则Dynamic←False；

步骤3 若Dynamic=Truth；

由算法1生成新环境下的预测集u(t+1) 并计算其F(x,t)， 接着pop←u(t+1)，t←t+1；

步骤4 若Dynamic←False；

(1)根据交叉概率Pc从种群pop(t) 中选出父代 (xi(t),xj(t)) 进行算数杂交，生成后代种群O1(t)；

(2)按照变异概率Pm对种群pop(t) 进行变异操作，生成后代种群O2(t)；

步骤5 对pop(t)∪O1(t)∪O2(t) 中的个体进行快速非支配排序，根据前沿等级与拥挤度距离选择出N个个体，得到新的种群Q(t)， 并令pop(t)←Q(t)；

步骤6 若t>tmax， 则停止；否则转步骤2。

ADNSGA从初始种群initialpop(N)开始，每次迭代前都会先进行环境变化检测，一般可以通过对当前种群的部分个体进行重新评估[5]，本文中采用当前种群5%的个体pl， 根据如下环境变化检测算子进行检测

(5)

其中，ω为当前代数。当μ(ω) 大于阈值μ*时，则判定此时环境发生了变化，采取相应的变化响应机制。

3 实验分析

3.1 动态优化问题

本文将在6个测试问题上进行算法比较，其中包括Farina等所提出的经典测试问题FDA1，4，5[10]，两个dMOP问题[11]，以及武燕等所提出的SW2测试问题[12]。其定义及其PS与PF见表1。

图2(a)～图2(f)分别为nT=10，n=20时F1～F6的真实帕累托前沿(pareto front，PF)，其中F1与F4的PF不随时间变化。图3(a)～图3(f)分别为参数设置nT=10，n=20时F1～F6的PS在低维空间中的投影，其中F2的PS不随时间变化。这些问题中时间步t=τ/τT， 其中τ为当前种群迭代次数，τT为环境变化频率，nT代表环境变化程度。

表1 动态多目标优化问题定义

图2 F1～F6的真实PF

图3 F1～F6的PS在低维空间中的投影

3.2 性能指标

本文采用改进的反向世代距离MIGD(modified inver-ted generational distance)[6,15]、改进的分布测度MHVD(modified hypervolume difference)、改进的超体积MSP(modified spacing)3个评价指标来评价算法的性能。MIGD、MHVD主要通过对真实PF的接近程度来衡量算法的收敛性与多样性，MSP用于衡量算法的均匀分布性，3个评价指标的结合可以帮助更加全面了解每种算法。与MIGD一样，MHVD、MSP分别为一段时间内HVD[6,15]与SP[6,15]的平均值。实验中两目标问题FDA1、dMOP1、dMOP2和SW2设置参考点数为1000个，三目标问题FDA4、FDA5参考点数为2500个。

3.3 对比算法及参数设置

为了验证所提出算法的优越性，本文选择了有代表性的4种动态多目标算法来进行对比研究。分别为：加入重新初始化种群方法的DNSGA-II-A、DNSGA-II-B[13]，当检测到环境变化时，前者随机重新初始化部分个体，后者则是随机对部分个体进行变异操作；PMGA[14]通过聚类选取PS质心，结合惯性预测的方法生成新环境下的初始种群。SGEA[15]通过线性时间序列模型，利用相邻时刻的两个PS中心点预测种群进化的步长；通过少量相邻时刻的非支配解集中心点预测进化方向，指导生成预测种群。

5种算法中的参数设置如下：

(1)迭代进化：两目标问题F1、F2、F3、F6中种群规模N=100，三目标问题F4、F5中N=200；交叉概率Pc=0.9，变异概率Pm=0.1，n=20为决策空间的维数，进化代数设定为gen=1600；

(2)预测部分：PMGA中质心选取个数与ADNSGA中代表个体数均为K=10，ARIMA模型阶数为p=3，q=3，SVR模型选取径向基函数(RBF)为核函数，历史最优序列长度L=23，高斯随机数的方差d=0.35；

(3)环境变化：设定环境变化程度nT=10，变化频率τT=10，环境变化检测阈值μ*=0.01，最大环境变化次数tmax=160； 从当前种群中随机选择5%的个体用以检测环境变化，当t>tmax时算法终止。

3.4 实验结果与分析

表2～表4分别为5种算法在环境变化设置为nT=10，τT=10时，求解F1～F6动态多目标测试问题所获得的3种度量的平均值与标准差。从表2中可以看出。

表2 独立运行20次的MSP度量统计结果

(1)就SP度量而言，在0≤t<20时，ADNSGA仅在F6上表现最佳，这说明单一的惯性预测策略无法保证算法在真实PF上分布的均匀性，应在运行前期结合一些策略来改善其分布性能；

(2)当20≤t≤160时，ADNSGA在F1、F3、F5、F6上表现优异，在F4上也优于除DNSGA-II-A外的其它3种算法，说明组合预测策略比起单一的预测策略能有效提升算法沿真实PF均匀分布的性能；

(3)整个运行过程中，ADNSGA在F6上始终优于其它对比算法，表明了其在处理非线性问题方面有更好的分布性。

从表3中可以得到以下信息：

(1)当0≤t<20时，ADNSGA在F2、F3、F6上有着更好的收敛性与多样性，但在F4、F5两个三目标问题上，DNSGA-II-A优于其它对比算法，说明重新初始化部分个体的动态响应策略在三目标问题上比单一的预测方法拥有更好的适应性;

(2)当20≤t≤160时，ADNSGA在所有6个动态测试问题上均优于其它对比算法，表明了组合预测策略的有效性。

表3 独立运行20次的MHVD度量统计结果

从表4中可以看出：

(1)从数值上看，ADNSGA在大部分测试问题上都取得了不错的结果。当0≤t<20时，ADNSGA算法在F1～F5的问题上，虽然不是表现最佳，但也始终处于第二的水平，优于其它3种算法，这表明惯性预测方法在算法运行初期是有效的，并且有着更好的普适性；

(2)当20≤t≤160时，ADNSGA算法在F1、F3～F6问题上均表现更好的性能，在F2问题上，DNSGA-II-B算法表现出了更好的收敛性与多样性，原因在于F2问题中PS是固定不变的，采用预测的方式并不能很好指引新环境下的初始种群，因此PMGA、SGEA、ADNSGA均表现欠佳，而采取重新初始化或变异部分个体的方法，一旦找到F2的真实PS，就可以快速逼近新环境下的PS和PF。DNSGA-II-B在均值上略微优于DNSGA-II-A，说明采用变异的策略可以具有更好的多样性；

(3)在F6测试问题上，ADNSGA始终优于其它对比算法，表现出更好的收敛性与多样性。

表4 独立运行20次的MIGD度量统计结果

为了进一步讨论所提算法的性能，图4(a)～图4(f)绘制了ADNSGA及4种对比算法在F1～F6上，独立运行20次的平均IGD度量与时间的关系图。首先在0≤t<20时，ADNSGA在大部分问题上优于其它对比算法，当t≥23时，开始通过ARIMA-SVR模型对PS质心点进行预测，ADNSGA的IGD值在除F2之外的5个问题上均优于其它对比算法，且数值波动较小，而未采取预测策略的DNSGA-II-A、DNSGA-II-B则波动很大，这表明采用中心点预测的方法能够有效的跟踪环境变化。将PMGA、SGEA、ADNSGA这3种采取预测策略的算法进行对比，采取组合预测策略的ADNSGA始终优于PMGA与SGEA，在F6问题上优势尤为显著。

图4 5种算法平均IGD值与时间的关系

图5、图6中(a)～(e)分别为5种算法在F6问题上，20次独立运行中，当t=140，t=143，t=147时IGD最小的初始种群与最终种群。从图5和图6中同样能清晰看到，ADNSGA相比于对比算法能更准确追踪Pareto最优前沿。

图5 5种算法IGD最小的初始种群

图6 5种算法IGD最小的最终种群

通过对5种算法的MIGD、MSP和MHVD性能指标的统计分析可知，本文提出的ADNSGA算法所采取的组合预测策略更适用于PS变化及PS、PF同时变化的问题，在算法运行前期加入的惯性预测方法可以使算法在大部分测试问题中保持较好的收敛性与多样性，具有很好的推广性与普适性，但在分布性方面有所欠缺，积累到足够的历史信息后，组合预测模型使得算法在非线性问题上表现出良好的竞争优势，同时提升算法对真实PF的均匀覆盖性。

4 结束语

针对动态多目标优化问题，本文提出一种基于组合预测策略的动态多目标优化算法(ADNSGA)，该算法在单一的惯性预测方法上增加了组合预测模型的质心预测，为预测最新的PS提供了更准确的指导依据。实验结果表明，ADNSGA算法在多种动态问题上都有很好的环境适应能力。此外如何在算法前期提高在PF上的分布性是未来工作的一个可研究方向。另外如何根据环境变化程度[18]合理分配预测策略也是一个值得研究的课题。当前，动态多目标优化在控制问题、调度问题、机械设计问题、图像分割问题，资源管理问题等现实生活和工业生产方面[5,16,17]应用广泛。本文所提算法在为求解此类问题提供新思路的同时，丰富了动态多目标优化的应用前景。