张涛，周晨，杜锋，陈芳，刘瑞林

1.长江大学信息与数学学院，湖北 荆州 434023 2.荆楚理工学院数理学院，湖北 荆门 448000

动态多目标规划问题(dynamic multi-objective optimization problem，DMOP)是一个涉及两个或多个目标函数、约束条件和问题参数随时间变化的问题[1]。动态多目标规划有着广泛的应用，如调度问题[2-6]、控制问题[7-10]、资源管理问题[11-13]、水热发电问题[14]等。由于动态多目标规划问题具有广泛的应用性与复杂性，其求解算法设计逐渐成为优化领域的热点与难点。马永杰等[15]利用种群的历史信息提出了一种基于卡尔曼滤波预测并修正种群中心点位置的动态多目标优化算法；呼子宇等[16]为了在检测到环境变化时能够及时有效地做出响应，提出了一种基于决策变量关系的动态多目标优化算法(DVR)；张杰等[17]为了能有效应对剧烈的环境变化提出了一种基于混合预测策略与改进社会学习优化算法的动态多目标优化方法；唐晓乐等[18]为适应较为复杂的动态环境，结合动态优化问题的可预测特性，提出一种基于组合预测策略的多目标优化算法。

由于动态多目标规划问题具有时变性，随时间动态变化，当环境变化较快时，该问题求解会变得更加的困难与复杂。怎样快速检测环境是否发生变化，以及怎样在时间窗的约束下准确追踪到当前时刻的Pareto最优前沿是算法设计的重点与难点。当前大多数变化检测的方法基于统计法，如SAHMOUD和TOPCUOGLU提出的一些检测环境变化的机制(sensor-based change detection，SBCD)[19]，实际上是选取一部分的个体进行重评估；还有杨圣祥等[20]提出的稳定状态的检测方法，该种环境检测方法对环境变化很敏感，不易于设置其阈值，具有不精确性。探索出新的环境变化检测方法，感知环境变化的类型和强度，提高对环境变化检测精度，已成为该领域亟需解决的问题。为此，笔者就环境检测与环境应答机制做了一定的研究，提出了一种基于数据流的K-S变化检测的动态多目标规划算法(DSK-SDMOP)，该算法使用非参数检测方法——Kolmogorov-Smirnov(K-S)检验来检测基于数据流的Pareto最优前沿是否发生变化，再根据变化的剧烈程度实行相应的环境变化应答机制，以提高对环境的适应程度。

1 模型与概念

动态多目标规划问题一般可以定义为如下形式[1]：

(1)

式中：x={x1，x2，…，xn}为n维决策变量；t为时间变量；f(x，t)为目标函数；m为目标函数的个数；g(x，t)，h(x，t)分别为相应的不等式约束和等式约束。

在最小化动态多目标规划问题中，对任意2个决策变量xa和xb，如果满足下列2个条件：

1)对于∀i∈1，2，…，m，都有fi(xa，t)≤fi(xb，t)成立；

2)∃j∈1，2，…，m，使得fj(xa，t)

则称xa支配xb，表示为xaxb。t时刻，如果不存在可行域内的x，使得xx*，则x*为t时刻的Pareto最优解，其组成的集合称为Pareto最优解集，记为PSt。而t时刻，PSt在目标空间的映射称为Pareto最优前沿，记为PFt。

根据PS和PF随时间变化的情况，DMOPs有以下4种类型[21]：

1)PS随时间变化而PF不随时间变化；

2)PS、PF都随时间变化；

3)PS不随时间变化而PF随时间变化；

4)PS、PF都不随时间变化。

2 环境变化检测和环境变化应答机制

动态多目标规划问题的算法设计主要考虑环境变化检测和环境变化应答机制两个方面。首先要检测出环境是否发生改变，然后针对改变做出相应的应答，使算法快速地适应改变的环境。

2.1 环境变化检测

2.1.1 数据流上移动窗口的数据提取

实际上，在动态多目标规划的求解中，每一时刻都能求得一个PF，可以看成一个数据流，而且t时刻与t+1时刻求得的|PF|大小可能不一样，导致取得的窗口所包含的数据点不一样。因此，为了更好检测环境是否发生了变化，笔者采用基于数据流的双移动窗口的检测方法，也就是说“参考窗口”与当前窗口都是移动的，并且每个窗口的数据的数量是不固定的。将上一个时刻所求得的目标函数值的所有数据作为“参考窗口”与当前时刻对应目标函数的函数值作为当前窗口，来进行环境检测。

2.1.2 Kolmogorov-Smirnov(K-S)检验

K-S检验用于比较基于分布函数的2个样本[18]，检验某个经验分布是否与某种理论分布相符或者比较两个经验分布之间是否有显著性的差异。笔者运用的是K-S双样本检验，通过检验2个样本的累计频数分布是否相当接近来判断是否接受原假设H0(H0表示2个样本分布一致)；反之，则认为不服从同一分布，拒绝原假设。其优点在于不用对数据做任何假设，也不要求样本容量一致，将“参考窗口”和当前窗口的数据当成2个独立的样本运用K-S检验来检测2个样本是否服从同一分布以此判断环境是否发生变化。

环境检测方法如下所示(以目标数为2的测试问题为例)：

(2)

(3)

2.2 环境应答机制

当检测到环境发生变化时，立即启动环境应答机制来适应环境的变化，调整搜索的方向，开始搜寻新的环境下的PS。

2.2.1 评估环境变化强度

一个进化算法通常很难准确的求得Pareto最优前沿，所以不能直接得到变化的程度。可以通过当前种群和历史种群之间目标值的偏差评估环境的变化。测量偏差Fmean和环境变化强度Ieva(t)的公式如下[24]：

(4)

(5)

2.2.2 系统预设的环境变化强度

环境变化的幅度τt会对算法对环境的适应程度产生比较大的影响，所以将系统预设的环境变化强度Isys设置为：

(6)

2.2.3 种群初始化比例自适应调整

如果环境发生了变化，则根据环境变化强度自适应调整种群初始化比例：

(7)

如果Irate(t)>Isys，证明环境变化是剧烈的，所以要大比例初始化种群，以更快地适应环境变化，调整其搜索方向，更快地追踪到新的Pareto最优前沿；如果Ieva(t)≤Isys，证明环境是温和可控的，只需要小幅度调整搜索方向即可。

3 DSK-SDMOP算法

DSK-SDMOP算法以求解静态多目标规划问题的NSGA-Ⅱ算法为基础，DSK-SDMOP算法的具体步骤如下：

Step1 参数及种群的初始化：对参数进行设置，种群大小pop、最大迭代次数Iteration、环境变化幅度τt，环境变化的频率为nt，并在决策空间中随机生成规模为pop的初始种群p0；

Step 2 按照NSGA-Ⅱ的进化操作选择、交叉、变异、快速非支配排序操作得到PFt；

Step 3 初始化种群，利用静态多目标规划算法NSGA-Ⅱ的进化操作与快速非支配排序得到PFt+1；

Step 4 当Iteration≥2时进行环境变化检测：利用K-S检验基于数据流的PFt与PFt+1中对应的目标函数值是否服从同一分布，若服从则认为环境没有变化，反之则认为发生变化；

Step 5 环境应答机制：若环境发生变化，将PFt对应PSt按照公式(4)～(7)初始化后，将其作为下一时刻的初始种群，即将当前时刻得到的PSt按确定的比例随机生成后得到的种群作为下一时刻的初始种群；若环境未发生变化，将t时刻进行进化操作得到PSt直接作为下一时刻的初始种群。

Step 6 判断是否满足算法停止的条件(达到最大迭代次数)，若满足则停止；若不满足，t=t+1，转Step 3。

4 仿真实验与结果分析

选取了FDA系列的5个动态多目标规划标准测试函数FDA1～FDA5来进行仿真实验，并与文献[14]提出的DNSGA-Ⅱ-A和DNSGA-Ⅱ-B算法来进行对比研究。

4.1 测试函数

在动态多目标规划的4种类型中[21]，这里主要研究的前两种类型的问题。对于类型Ⅲ，当环境发生改变时，PS也会一直保持不变，此时只需要把算法当前时刻追踪到的最优PS直接作为下一时刻的初始种群，研究意义不大；而对于类型Ⅳ中PS与PF都不发生变化的情形，不能将问题的变化特性用较为简单的数学模型来进行描述，所以不作讨论与研究。在测试函数FDA1～FDA5中，FDA1和FDA4属于类型Ⅰ，当环境发生变化时，PF不变；而FDA2、FDA3、FDA5属于类型Ⅱ，当环境发生变化时，PS和PF均改变。

4.2 性能指标

本文主要用到准确率(the true positive rate，TPrate)、反世代距离(inverted generational distance，IGD)以及其在环境变化下的平均值mIGD、间距(scotts spacing，SS)以及其在环境变化下的平均值mSS来评价算法的性能，具体计算方法分别见文献[25-27]。其中，TPrate用来衡量正确检测到环境变化的百分比，IGD通过度量真实Pareto前沿与算法获得的Pareto前沿之间的接近程度来评价算法的收敛性与多样性，SS度量Pareto前沿分布均匀程度。

4.3 实验结果及分析

表1 算法性能指标比较

测试函数的环境变化幅度τt=10，环境变化的频率为nt=100，测试函数FDA1、FDA2、FDA3、FDA4、FDA5决策变量的维度分别为20、13、30、12、12。算法终止的条件为迭代1 000次，一共10个环境，对于每个测试函数算法都独立运行10次。DSK-SDMOP算法和DNSGA-Ⅱ-A/B算法都以NSGA-Ⅱ为框架设计的，算法参数做如下设置，种群的大小pop=100，交叉概率pc=0.90，变异概率为pm=0.1。

1)实验结果。将DSK-SDMOP、DNSGA-Ⅱ-A、DNSGA-Ⅱ-B这3种算法在FDA系列5个测试函数上独立运行10次，求得TPrate、mSS、mIGD的均值如表1和图1所示。10个不同的环境下3种算法在不同测试函数上SS、IGD如图2所示。

图1 算法性能评价指标比较Fig.1 Comparison of algorithm performance evaluation indicators

2)结果分析。由表1和图1可知，DSK-SDMOP算法正确检测到环境变化的百分比TPrate在除FDA4之外的四个测试函数上均为100%，而DNSGA-Ⅱ-A/B最高只能达到95%；在FDA4上本文算法检测变化准确率方面为90%，DNSGA-Ⅱ-A/B仅为65%和70%。算法DSK-SDMOP与算法DNSGA-Ⅱ-A/B正确检测到环境变化的百分比TPrate最大差值在40%，最小差值也有5%，说明该算法对环境变化判断的准确性明显高于DNSGA-Ⅱ-A/B；而mSS、mIGD分别用来评价解集内部的解分布的均匀性、算法的收敛性与多样性。在求得解集内部的均匀性以及收敛性与多样性方面，除了FDA3的mSS指标高于DNSGA-Ⅱ-B算法0.000 7，FDA5的mIGD指标高于DNSGA-Ⅱ-A算法0.002 7，稍显逊色以外，DSK-SDMOP算法在指标mSS、mIGD都低于DNSGA-Ⅱ-A/B，表示着DSK-SDMOP算法的收敛性与多样性以及Pareto前沿分布均匀程度都优于算法DNSGA-Ⅱ-A/B。

图2 不同环境下的SS和IGDFig.2 SS and IGD in different environments

由图2可知，DSK-SDMOP算法的SS、IGD指标在每个环境下都保持很小的值，表明它求得的解集内部分布均匀且更接近标准Pareto最优前沿，表现出DSK-SDMOP算法良好的环境适应性。

5 结论

1)针对动态多目标规划问题，笔者提出了一种基于数据流的K-S变化检测的动态多目标规划算法DSK-SDMOP，该算法的环境变化检测机制主要基于数据流中的滑动窗口以及K-S检验，能在没有分布假设的情形中较准确的感知环境所发生的变化，并设计了一种自适应环境应答的机制来判断环境变化的强度并确定多样性引入的比例，使算法更好适应环境，追踪到Pareto最优前沿。

2)动态多目标规划算法FDA系列的标准测试函数仿真实验结果表明，该算法在变化检测的准确性、均匀性以及收敛性方面表现出良好的性能，并且该算法的结构简单，具有较好的迁移能力。