使用新预测模型的动态多目标优化算法

李智翔,李赟,贺亮,沈超

(1.盲信号处理重点实验室,610041,成都; 2.西安交通大学智能网络与网络安全教育部重点实验室,710049,西安)

在许多实际的工程问题,如规划调度、数据挖掘、资源分配、电路设计、控制系统等等问题中,由于问题的复杂性,优化目标往往不止一个,多个优化目标之间相互冲突并且取值随时间变化,这样的优化问题被称作动态多目标优化问题(dynamic multiobjective optimization problems,DMOPs)[1]。与求解静态多目标优化问题不同,在处理动态多目标优化问题时,需要在每次环境发生变化之前找到近似最优解集,这就要求算法能够跟踪随时间变化的环境[2]。特别地,当环境变化的速度较快时,动态多目标优化问题的求解难度进一步提升。

近些年来,在动态多目标优化问题的相关研究领域,学者做了很多工作,其中一部分研究工作针对如何在动态多目标优化算法的迭代过程中检测环境变化。文献[3]提出了一种最常见的基于解再计算方式检测环境变化的方法,文献[4]提出了一种基于反转模型的两阶段检测的方法,文献[5]则通过解的分布性来判断环境的变化情况。动态多目标优化算法为了在变化发生时加快收敛速度,通常需要在变化时增加解集的多样性。文献[6]通过优化变异算子来增加解集的多样性,文献[7]通过对部分解进行重定位来增加解集的多样性,文献[8]通过引入多种群协同进化机制,使得不同种群采用不同的进化策略,从而增加了解集的多样性。为了跟随和预测环境的变化,一些学者对基于历史记录的方法进行了深入研究:文献[9]采用记忆串的方式对历史信息进行记录,保持解的多样性并快速响应新的环境变化;文献[10]提出了通过维护一个外部存储空间来保留历史信息,利用历史信息实现对变化后的最优解集进行快速逼近;文献[11]通过对动态变化的环境进行学习,自适应地调整算法参数,从而提升了算法效率。除了对历史信息的记录,学者们还提出采用预测的方法对变化后的环境进行主动判断和逼近,已有的研究成果包括对最优解的变化进行预测[12]、对区域的变动进行预测[13]、对变化发生的时间进行预测[14]等。与其他思路相比,采用预测思想的算法取得了较好的效果,但该类算法应用于实际问题求解时仍存在对快速变化的最优解集的跟踪能力不强,算法运行效率较差等问题,有待进一步解决。

本文采用预测解集变化的思路,提出了一种基于卡尔曼滤波的动态多目标优化算法(dynamic multiobjective optimization evolutionary algorithm based on decomposition with Kalman filter,DDKF)。卡尔曼滤波是一种利用包含噪声的观测数据对未来数据进行预测的方法,其思想在动态优化算法中得到了广泛的使用[15-16]。卡尔曼滤波能够快速、准确地跟踪线性系统的变化,具有计算复杂度低、抗噪声干扰能力强等特点,适合动态多目标优化算法用来在环境变化时快速逼近最优解。与已有算法为每个解维护一个卡尔曼滤波模型不同,DDKF算法提出了一种全新的预测模型,一方面通过记录每次环境变化前解集的中心并使用卡尔曼滤波对该中心进行预测,利用中心变化的方向和幅度对一部分新解进行放置和搜索,并且为每个新解增加垂直于变化方向的随机扰动以丰富新解的多样性;另一方面,保持一部分解不变,避免因变化方向无规律时导致预测偏差较大影响解的收敛速度。与其他3种算法在标准测试集上的对比实验表明,本文DDKF算法在大多数测试函数上得到的结果优于其他3种算法,并且算法运行时间较已有的基于卡尔曼滤波模型进行预测的MOEA/D-KF算法[15]更短,从而说明了DDKF算法的有效性。

1 背景知识

1.1 动态多目标优化问题

一个动态多目标优化问题的优化模型如下

(1)

1.2 基于分解的多目标优化算法

基于分解的多目标进化算法的核心思想是通过降维的方式将一个高维的多目标优化问题转换成若干子问题,子问题通常是单目标优化问题。每个子问题对应原多目标优化问题的一个解,由于不同子问题的参数不同,因此通过合理地选择参数,所有子问题的解组合起来就构成了原多目标优化问题的最优解集。在求解的过程中,子问题既可以独立求解,也可以通过对比采纳参数相近的邻居子问题得到的解加速自身的收敛速度。与其他多目标优化算法相比,基于分解的多目标优化算法通常具有较好的收敛速度并且能够得到分布多样性更优的解集[18]。

1.3 卡尔曼滤波预测模型

参考文献[19],考虑一个线性系统的状态差分方程如下

xt=Axt-1+But-1+wt-1

(2)

式中:xt∈Rn为t时刻的系统状态变量;A为n×n的转换矩阵;ut-1为t-1时刻的系统输入,长度为l;B为将输入转换为状态的矩阵,大小为n×l;wt-1为t-1时刻的系统噪声。t时刻的测量值zt∈Rm可表示为

zt=Hxt+vt

(3)

式中:H是状态变量到测量的转换矩阵,其大小为m×n;vt为t时刻的测量噪声。假设任意时刻的系统噪声w和测量噪声v是相互独立的白噪声,且具有如下多元高斯分布

(4)

式中Q、R分别为系统噪声和测量噪声的协方差矩阵。卡尔曼滤波的预测模型采用迭代的形式,模型估计某一时刻的状态,之后收到带有噪声的测量值反馈后对模型进行修正,如此往复。卡尔曼滤波预测模型的公式分为时间更新和测量更新两个部分,时间更新和测量更新的公式如下

(5)

(6)

2 动态多目标优化算法DDKF

2.1 卡尔曼滤波模型设计

(7)

(8)

式中:x为决策空间的变量;v表示x的一阶导数,即观测对象的速度;a为x的二阶导数,即观测对象的加速度。采用这样的定义,有利于将更多的历史数据用来进行预测。系统只能通过x进行观测,有

(9)

(10)

式中:矩阵A的值表示这里的卡尔曼滤波模型为二阶线性模型;矩阵H的值表示在该问题中只能测量到系统状态变量的第一维,即观测对象的位置。结合式(5)可以看出,对观测对象下一时刻的位置的预测,与上一时刻的位置、速度的预测值和上一时刻的位置测量值有关。

2.2 新解集的生成

当根据卡尔曼滤波预测模型得到t+1时刻的预测值xt+1时,可以计算出相应的位移为

(11)

V(dt)={v∈Rn:‖v‖=1,dtv=0}

(12)

对t+1时刻变化之前得到的解集中的任意一个解x,所对应的新解xnew的计算方式如下

(13)

式(13)表明:一部分新解按照概率pn保持不变,避免预测产生错误;其他新解则在原始解的基础上叠加预测的位移分量和垂直的超平面扰动分量。这样处理能够进一步增加新解的多样性,避免因变化方向预测的错误带来对收敛速度的影响。

图1 本文算法在环境变化时的预测模型

2.3 算法流程

步骤1初始化种群、权重向量、邻居大小等参数;

步骤4判断环境是否发生变化:若未变化,则跳转至步骤9;若环境发生变化,继续执行步骤5;

步骤5应用式(7)生成当前时刻的中心点,即测量值zt;

步骤6应用式(6)进行卡尔曼滤波测量更新;

步骤7利用式(5)进行卡尔曼滤波时间更新,得到对下一时刻的预测值xt+1;

步骤8根据式(11)～式(13)计算生成新一代解;

步骤9进行下一代进化。若算法达到终止条件,则返回结果,算法结束;否则返回步骤2。

3 实验分析

3.1 实验设置

为了验证本文DDKF算法的有效性,选择3种优秀的动态多目标优化算法进行对比测试。这3种算法分别是DNSGAII算法[20]、MOEA/D-KF算法[15]及PPS算法[21]。其中DNSGAII是在经典的多目标优化算法NSGAII的基础上针对动态多目标优化问题重新设计的算法;MOEA/D-KF是一种为每个解构造一个卡尔曼滤波预测模型的基于分解的动态多目标优化算法;PPS算法对分布进行了估计,并采用了一种时间序列回归分析的技术进行预测。

本文选择使用10个动态多目标测试函数对上述算法进行对比测试,这些测试函数选自文献[21-23]。测试函数的特征如表1所示。

表1 测试函数属性

DNSGAII算法、MOEA/D-KF算法以及PPS算法的参数参照相应文献进行设置,其他参数设置如下:种群大小为100;算法执行代数为4 000代,变化程度nt=10,式(13)中pn=0.3。此外,为了对4种算法在动态多目标优化问题发生变化前充分收敛和未充分收敛的情况进行分析,令环境变化频度τt的值分别取40和5,其他参数不变。4种算法在10个测试函数上分别运行20次。

(14)

3.2 实验结果和分析

4种算法在10个测试函数上的平均反向距离指标均值测试结果如表2所示。可以看出:针对环境变化频度τt取40的情形,本文提出的DDKF算法在10个测试函数中的8个测试函数上的平均反向距离指标测试结果优于其他3种算法,而MOEA/D-KF算法和PPS算法分别在dMOP2和F7测试函数上最优;针对环境变化频度τt取5的情形,本文提出的DDKF算法在10个测试函数中的7个测试函数上的平均反向距离指标结果优于其他3种算法,而MOEA/D-KF算法在FDA1测试函数上最优,PPS算法在dMOP1和F7两个测试函数上最优。测试结果说明,本文提出的DDKF算法在大多数测试函数上优于其他3种算法,当环境变化频度τt由40变成5时,MOEA/D-KF算法、PPS算法和本文提出的DDKF算法得到的平均反向距离指标结果平均有3～5倍的增大,而DNSGAII算法得到的结果平均有1个数量级左右的增大,其增幅大于其他3种算法。这是因为当环境变化频度τt由40变成5时,每次变化之间的迭代次数减少,由于算法均不能充分收敛,相应的平均反向距离指标结果均较原先的值变差,但此时本文提出的DDKF算法在大部分测试函数上仍优于其他3种算法。此外,与DNSGAII算法采用随机初始化策略对种群进行处理相比,其他3种算法均采用了各自不同的预测策略,其效果优于DNSGAII的随机初始化策略,尤其是当环境变化频度τt的值取5时,算法在两次变化之间的迭代次数较少,无法充分收敛,此时具有预测策略的3种算法的优势更加明显。

为了进一步说明本文提出的DDKF算法的有效性,选取F6测试函数对上述4种算法在环境变化频度τt的值取40时的测试结果进行深入分析。首先对4种算法在F6上不同时刻的反向距离指标的值进行对比,结果如图2和图3所示。可以看出:本文提出的DDKF算法在迭代次数为5之后基本趋于稳定,反向距离随环境变化的波动很小,且平均值小于其他3种算法;MOEA/D-KF算法及PPS算法的结果相当,但PPS波动性较小;从算法的稳定性来讲,本文算法优于MOEA/D-KF算法;DNSGAII算法的结果差于其他3种算法,且波动性较强。

表2 4种算法的平均反向距离比较

注:黑体数据表示最优值

图2 4种算法在F6测试函数上不同迭代次数的 反向距离对比

图3 4种算法在F6测试函数上的反向距离的箱线图对比

为了观察不同时刻4种算法得到的解的分布情况,这里选取了t为65、67、69、71、73 s这5个时刻4种算法得到的解在目标空间的值,其结果如图4至图7所示。图中实线为不同时刻的最优面,点为不同时刻求得的解集。可以看出,本文提出的DDKF算法在这5个时刻的解均优于其他3种算法的对应解,收敛性好且分布较为均匀,基本覆盖了整个最优面;PPS算法和MOEA/D-KF算法的结果次之,收敛性较好但分布不够均匀,最优面的一些片段附近并没有相应的解;而DNSGAII算法的收敛性差于上述3种算法,分布均匀程度与MOEA/D-KF算法和PPS算法相当。

为了对比分析不同算法的时间效率,将4种算法在上述10个测试函数上分别运行10次,记录并对比总的运行时间。令本文提出算法DDKF的总运行时间为1,其他3种算法的总运行时间与本文算法运行时间的比值如表3所示。

表3 4种算法的运行时间对比

由表3可以看出,DNSGAII算法的运行时间最短,本文DDKF算法次之,而MOEA/D-KF算法和PPS算法运行时间较长。这是因为:与其他3种算法相比,DNSGAII采用的随机初始化策略较为简单,时间复杂度较低;与PPS使用的回归模型相比,本文DDKF算法使用的单个状态向量的卡尔曼滤波模型时间复杂度更低,而MOEA/D-KF尽管也采用了卡尔曼滤波模型,但该算法对每一个解分别构造一个卡尔曼滤波模型,而本文仅构造了一个卡尔曼滤波模型,因此本文提出的DDKF算法运行时间优于MOEA/D-KF算法和PPS算法。

图4 在测试函数F6上DNSGAII算法的结果分布

图5 在测试函数F6上MOEA/D-KF算法的结果分布

图6 在测试函数F6上PPS算法的结果分布

图7 在测试函数F6上DDKF算法的结果分布

4 结 论

当环境发生变化时,如何快速均匀地收敛到新的最优面是动态多目标优化算法需要解决的一个核心问题。本文设计了一种新的预测方法,一方面使用卡尔曼滤波模型对不同时刻的解集中心点进行跟踪,预测其变化;另一方面为新解集在预测的变化方向的垂直超平面上增加一个扰动量,使得新解集保持充分的多样性。与其他优秀算法在公开测试集上的对比实验结果证明了本文提出算法的有效性。如何优化选取参考点以及如何在环境不变时加速算法收敛是今后研究的重点。