控制与决策  2019, Vol. 34 Issue (6): 1307-1318  
0

引用本文 [复制中英文]

耿焕同, 周山胜, 陈哲, 韩伟民. 基于分解的预测型动态多目标粒子群优化算法[J]. 控制与决策, 2019, 34(6): 1307-1318.
[复制中文]
GENG Huan-tong, ZHOU Shan-sheng, CHEN Zhe, HAN Wei-min. Decomposition-based predictive dynamic multi-objective particle swarm optimization algorithm[J]. Control and Decision, 2019, 34(6): 1307-1318. DOI: 10.13195/j.kzyjc.2017.1604.
[复制英文]

基金项目

国家重点研发计划项目(2017YFC1502104);“青蓝工程”基金项目(2016);南京大气科学联合研究中心项目(NJCAR2018MS05)

作者简介

耿焕同(1973-), 男, 教授, 博士生导师, 从事计算智能与约束多目标优化、气象资料预处理与资料同化等研究, E-mail: htgeng@nuist.edu.cn;
周山胜(1992-), 男, 硕士生, 从事多目标优化的研究, E-mail: sszhou710@126.com;
陈哲(1992-), 男, 硕士生, 从事多目标优化的研究, E-mail: q953387601@163.com;
韩伟民(1992-), 男, 硕士生, 从事多目标优化的研究, E-mail: hanweimin1@163.com

通讯作者

耿焕同, E-mail: htgeng@nuist.edu.cn

文章历史

收稿日期:2017-11-28
修回日期:2018-08-31
基于分解的预测型动态多目标粒子群优化算法
耿焕同 , 周山胜 , 陈哲 , 韩伟民     
南京信息工程大学 计算机与软件学院,南京 210044
摘要:针对动态多目标问题求解, 提出一种基于分解的预测型动态多目标粒子群优化算法.首先借助分解思想, 将目标问题划分为多个不同的子问题, 当问题动态变化时, 选择对应于不同子问题的优化个体检测环境变化程度, 以提高算法对不同动态问题的适应与响应能力; 然后, 设计一种群体预测策略, 通过将目标空间中相同收敛方向上不同时刻的个体位置转换为时间序列, 引入时间序列预测方法预测下一刻位置, 从而提高预测种群的多样性和有效性, 进而有效减少算法在问题变化后的收敛时间; 最后, 为避免问题发生变化后个体与子问题不匹配, 设计一种再匹配策略, 以提高预测策略的准确性.实验结果表明, 在6个标准动态多目标测试问题上, 与2个动态多目标优化算法进行比较, 所提出算法在收敛性、分布性与稳定性上均具有显著优势.
关键词动态多目标优化    预测    粒子群优化    分解    
Decomposition-based predictive dynamic multi-objective particle swarm optimization algorithm
GENG Huan-tong , ZHOU Shan-sheng , CHEN Zhe , HAN Wei-min     
College of Computer & Software, Nanjing University of Information Science & Technology, Nanjing 210044, China
Abstract: In order to solve the dynamic multi-objective problems, a predictive dynamic multi-objective particle swarm optimization algorithm based on decomposition is proposed. Firstly, the target problem is divided into several sub-problems by decomposing. When the problem changes, the optimized individuals corresponding to different sub-problems are chosen to detect the severity of changes to improve the ability of the algorithm to adapt and respond to different dynamic problems. Then, a group prediction strategy, which converts individual positions at different moments in the same convergence direction of the target space into time series, is designed to improve the diversity and validity of the prediction population by introducing the time series prediction method and forecasting the position of the next moment, which can effectively improve the algorithm convergence speed after the problem changes. Finally, in order to avoid the mismatch between individuals and subproblems after the environment changes, a rematching strategy is designed to effectively improve the accuracy of the prediction strategy. The experimental results show that compared with the four dynamic multi-objective optimization algorithms, the proposed algorithm has significant advantages in convergence, distribution and stability over six standard dynamic multi-objective problems.
Keywords: dynamic multi-objective problem    prediction    particle swarm optimization    decomposition    
0 引言

随着社会的不断进步, 在工业设计和科学研究中普遍存在各类动态目标优化问题.当优化问题超过一个目标时, 该类问题被称为动态多目标优化问题(DMOPs).例如, 在机场调度过程中, 受到天气条件、飞机故障、乘客事故等因素的影响, 乘客滞留时间、运行成本、飞行安排等问题需同时进行优化.不同于静态优化问题, DMOPs存在多个依赖时间相互冲突的目标, 并且Pareto最优解随时间而不断变化, 这使得解决此类问题的复杂度大大提高, 因此, DMOPs正受到国内外学者的广泛关注.

自2004年, Farina等[1]首次提出动态多目标优化算法以来, 针对动态多目标优化问题的研究从未间断, 并且取得了许多研究成果. 2007年, Deb等[2]在NSGA-Ⅱ的基础上提出了DNSGA-Ⅱ; 随后, Greeff等[3]提出了向量评估粒子群算法以求解动态多目标优化问题; Koo等[4]采用历史记忆法, 提出了动态多目标梯度搜索算法以改善种群的分布性; 武燕等[5]通过对最优解的预测提出了一种新的多目标遗传算法, 利用历史信息进行最优解的预测; 郑金华等[6]提出了基于引导个体的预测策略以求解动态多目标优化问题, 指导种群更好地搜索; Gan等[7]提出了一种混合分集维护方法, 提高了环境变化后Pareto前沿面的预测精度.

尽管上述算法对于解决动态问题有着相对不错的效果, 但文献[3]算法对前沿面高度敏感; 文献[5]算法根据有代表性的解预测环境变化后的解集, 当环境变化较大时, 预测的解集易出现偏差; 文献[6]算法在动态变化环境中表现的适应性并不理想.

以上问题都在一定程度上对解决动态问题产生了不利影响.为此, 在对上述算法研究及分析的基础上, 本文提出一种基于分解的预测型动态多目标粒子群优化算法(DDMOPSO).在算法中, 选取对前沿面曲线更具低敏感度的基于惩罚的边界交叉方法(PBI), 将MOP分解为N个标量子问题, 并在粒子种群进化的同时优化所有子问题.与此同时, 算法采用基于群预测方法的时间预测策略, 进一步提升进化过程中的算法自适应性, 降低动态环境对粒子进化的影响, 从而全面提高算法的分布性和收敛性.

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

不失一般性, 以最小化优化问题为例, 动态多目标优化问题可形式化描述如下:

(1)

其中: xn维实数空间的向量, t为时间变量, 定义为决策可行域.目标函数F(x, t)由m个不同的目标函数组成.式(1)中定义的DMOPs可转换为一系列稳定的静态多目标优化问题(MOPs).当影响MOPs的环境发生变化时, 优化目标即为不断追踪变化的PF.

1.2 粒子群优化算法

粒子群优化(PSO)算法最初由Eberhart等[8]提出, 用来解决连续的和非约束的线性优化问题.在PSO中, 一个粒子代表一个解xiRn, 一个种群可以被定义为一个或多个粒子群.粒子在进化过程中通过式(2)和(3)来更新速度向量vt+1和位置向量xt+1, 即

(2)
(3)

其中: w≥0是惯性权重系数; c1, c2≥0表示加速系数; r1r2是(0, 1)均匀分布的随机数; vitxpbest, ixgbest, i分别表示第i个粒子的速度、局部最优解和全局最优解.

1.3 分解方法

在所有分解方法中, 权重聚合和切比雪夫这两种方法得到广泛使用.文献表明, 基于惩罚的边界交叉方法(PBI)在处理复杂多目标优化和高维多目标优化问题时更具优势[9].

PBI方法使用一个权重向量w和惩罚值θ来优化解F(x)(见图 1)到理想向量的距离d1和到权重向量的方向误差d2, 其数学描述如下:

(4)
(5)
图 1 基于惩罚的边界交叉方法
2 基于分解的预测型动态多目标粒子群优化算法(DDMOPSO) 2.1 DDMOPSO算法流程

DDMOPSO算法的总框架如下.

1) 初始化:设置步长t = 0, 初始化粒子群Pt = {x1, ..., xN}, 初始化粒子速度vi = 0;生成大小为N的均匀权重向量W = {w1, ..., wN}; 定义局部最优粒子和全局最优粒子, 定义历史观测数据K = {Gbest1, ..., Gbestτ}.

2) 优化迭代:

3) For i = 1, 2, ..., N do

4) t = t+1;

5) If Change(t) then

维持记忆集:将Gbest添加到记忆集K;

再评估:评估GbestPt;

再匹配权重向量:将权重向量集W与粒子群Pt再匹配.

6) 预测: Gbest = prediction(K, W, Gbest).

7) 选择:从Gbest中随机选择粒子作为xgbest, i.

8) 更新:通过式(2)和(3)更新速度vit+1和位置xit+1;

9) 修复边界:重置粒子边界xit+1;

10) 评估粒子和更新z*:得到F(xit+1, t). If fj(xit+1, t) < zj*, then zj* = fj(xit+1, t).

11) 使用PBI更新局部最优粒子: If g(xit+1|wi, z*)≤ g(xpbest, i|wi, z*), then xpbest, i = xit+1.

12) 更新全局最优粒子:从S = GbestPt+1中进行外部归档集的更新, 得到Gbest.

13) 终止准则:若没达到算法终止条件, 则转2).

14) 输出: Gbest.

为了更好地理解本文所提出的DDMOPSO算法, 本文将对算法中的外部归档集更新、群预测和再匹配等3类核心策略进行详细叙述.

2.2 外部归档集更新策略

在本文中, 传统的基于Pareto支配被基于分解的弱支配所取代.首先, 群Pt+1Gbest结合组成新的大小为2N的集合S, 将Gbest设置为空集; 然后, Gbest会不断地迭代并被填充, 直到达到N.每个周期内, 随机选择尚未配对的权重向量vS中最合适的粒子配对.因为S中每一个粒子代表一个子问题的解, 就分布性而言, 均匀分布的权重向量集W将会控制子问题的收敛方向, 因此, 粒子优化子问题时将会自动维持一个很好的分布性.根据式(4), 再次利用PBI方法为权重向量v得到全局最合适的极小值领导粒子g(xi|v, z*), 然后, 将vxi分别从尚未配对的权重向量集合和临时粒子群S中删掉, 并将xi插入到Gbest中.重复上述步骤, 直到将Gbest填满, 输出Gbest.

2.3 群预测策略

由于DMOPs的性质, 一个动态环境可通过时间窗口划分为一系列静态环境E = {e1, ..., ek, ..., eτ}, ek表示第k个时间窗口.理想情况下, 在同一时间窗口, 假定问题的函数形式、约束和参数等都不会发生改变.为此, 一个动态优化算法只需解决当前环境中的静态问题, 而不需考虑其他环境中的联系.但是, 由于时间窗口非常短, 只有两个或者更多的连续的环境{..., ek-1, ek, ...}之间才会有一些联系.基于上述分析, 充分利用之前环境信息来预测新环境ek+1Gbest的初始位置, 这样, 算法可以在全局搜索阶段节省更多的时间用来局部搜索.因此, 如何有效利用历史环境信息以尽可能准确地预测新环境下的初始前沿位置是解决DMOPs的关键.

在本文中, 环境序列E构成一个时间序列, 时间序列预测技术能够充分用来预测Gbest的下一个初始位置.本文采用自回归模型Auto-Regressive Model(AR)[10]作为群预测策略.该策略与其他预测策略有两个根本的区别: 1)群预测策略基于不同权重向量预测新环境下的子问题的解, 整个预测过程分为多个独立并行的过程, 将子问题视为不同环境间的联系, 并且能消除与其他子问题之间的噪声; 2)在其他预测或响应策略中, 选择用来响应的解的比例是固定的, 解过多或过少都会有不利的影响.本文提出将变化程度进行量化的新策略, 这个比例将随环境变化程度自适应变化.变化越大, 两个连续的环境之间关联性越小, 这个比例越大.

在这个主要循环中, 首先评估第k+1个环境变化程度μk+1, 再根据μk+1生成一组均匀分布的权重向量V.然后基于AR模型, 在V中选到权重向量的收敛方向预测初始位置.主要预测过程可分为以下3个步骤.

Step 1:将环境变化程度量化.

Pik为上一个环境ek的近似Pareto前沿面, Pik+1为新环境ek+1的再评估Pareto前沿面.于是

(6)
(7)

其中: distance(Pik+1, Pik)表示Pik+1中解i与Pareto前沿Pik之间最小的欧几里得距离, severitymin和severitymax分别是迄今为止环境变化的最小值和最大值.在这种情况下, 环境变化程度与μ是正相关. μk+1 = 0表示Pareto前沿没有变化, μk+1 = 1表示环境变化是迄今为止最剧烈的.

Step 2:选择.

根据μk+1生成一系列均匀分布的权重向量V, V的大小是, 对于每一个权重向量vi, 从历史观测数据K:{Gbest-L, ..., Gbestk}中选择最近的历史局部序列obs = {xk-L, ..., xk}, xk-L代表Gbestk-L中最小值g(xk-L|vi, z*)的粒子(L为之前环境记录的最大长度).使用序列obs来预测由vi表示的收敛方向的位置.

3) Step 3:自回归模型AR(p).

xk = (x1k, ..., xnk)T, xk+1可以通过AR(p)模型预测, 具体步骤见文献[10].

在得到每个子问题vi的预测位置后, 即可得到一个全局最优集, 然后将添加到预测存储K'中.

算法1  Prediction(K, K', W, Gbest).

1) 输入:

2) 历史观测数据集K;

3) 权重向量集W;

4) 当代全局最优解集Gbest.

5) 定义一个临时集合Ω = ∅.

6) 通过上述Step 1量化环境变化程度μ.

7) 通过Step 2产生一个均匀分布的权重向量集V.

8) For i = 1, 2, ..., |V| do

9) 从{Gbestk-L, ..., Gbestk}中选择有最小值g(xk-L|vi, z*)的obs = {xk-L, ..., xk}.

10) 根据上述Step 3生成AR(p)模型.

11) 利用AR(p)模型在新环境ek+1中预测初始化位置.

12) 根据2.2节策略更新Gbest.

13) 输出: Gbest.

对比其他的策略, 本文中所提出策略具有如下优势: 1)量化了环境变化程度, 有助于提升环境变化后预测解的准确性; 2)不同子问题之间的预测极大地消除了来自于其他收敛方向的预测噪声; 3)不同粒子各自存储一系列的历史位置和历史预测位置, 各自预测可并行, 从而提高了优化效率.

2.4 再匹配策略

在以MOEA / D为代表的分解型算法中, 解与子问题的匹配是此类算法设计的关键问题之一.究其原因是EA和PSO算法等均是随机算法, 每一步搜索进化都是带方向的随机过程, 从而导致无效解区域的搜索概率会很高, 尤其在进化早期; 同时, 变异算子也会导致后代解产生很大的变化.因此, 解决基于分解算法的不匹配问题显得尤为重要.

在本文中, 将匹配问题转化为二分图匹配问题.将权重向量集W和粒子群Pt视为分别独立的集合, 尽可能让权重与粒子群Pt中的解进行匹配, 从全局角度出发, 调和匹配过程中的冲突配对, 使配对的解符合整体最优, 然后寻找到最佳匹配.

匹配方式如下:

1) 在本文中, 一个权重向量vi偏好一个粒子xj, 表示在vi的收敛方向和分布方向上, xj是靠近vi的.算法根据式(4)计算权重向量vi的粒子的PBI聚合函数值, 并放在矩阵Pw中.

2) 算法通过对矩阵中的每一行Pw(i, j)排序, 得到每个粒子的权重向量偏好程度以及偏好矩阵Θ.在Θ中, Θ(i, j)表示权重向量vi对粒子xj的偏好, ij表示WPt的索引.与上面相似, 得到粒子对权重向量的偏好矩阵Ψ.

在得到偏好矩阵ΘΨ后, 定义一个配对矩阵.选择一个尚未配对的向量vi, 然后为vi找到最高偏好的粒子xj.如果xj并没有被匹配(Λ(i, j) = 0), 则Λ(i, j) = 1;如果xj已经与另外一个向量vk匹配, 当Ψ(j, i) < Ψ(j, k)时, vi将会替代vk而与xj匹配.

3 实验仿真及结果分析

为了验证本文提出的基于分解的预测型动态多目标粒子群优化算法的有效性, 这里选取4个动态多目标优化标准测试问题FDA[11]和2个非线性相关的DMOPs[12]进行仿真. 4个FDA问题分别为FDA1(下文简称F1)、FDA2(F2)、FDA3(F3)和FDA4 (F4), 两个dMOP问题分别为dMOP1(F5)和dMOP2 (F6).对比算法选择DVEPSO[13]和dMOPSO[14].

3.1 测试问题

在动态多目标的类型中[11], 问题在基于Pareto最优前沿面(PF)和Pareto最优解(PS)的变化上可归结为4类.类型1:在这些测试函数上, PS将会改变, PF不会随时间变化, 但是这个决策空间、目标空间和可行域的边界都固定不变; 类型2: PF和PS都会改变; 类型3与类型1相反, PF改变而PS固定; 类型4与类型2相反, 即PF和PS都不会改变.

测试问题定义如下:

(8)

其中nTτT表示环境变化的程度和频率.由于G(t)和H(t)的正弦函数的特性由nT决定, 相同的PS会周期性地再次出现.需要指出的是, nT越小, 不同的PS数量越少, 因此nTτT都必须是正数, 否则, nT为0或者为负数都会导致超出范围的量级的变化.同样, τT越大, 表示算法将会得到更多的时间来优化这个问题.

3.2 性能指标

为了评估算法获得的解集的多样性和收敛性, 实验中采用广泛用于评估多目标进化算法多样性的反世代距离IGD[15]和容错率ER[16]作为性能评估指标.

首先, IGD是用来评估静态多目标优化的.在IGD指标的基础上, 本文提出改进的MIGD指标, 用来评估动态多目标. Pt*是环境t中真实Pareto前沿面的解集, Pt是算法得到的近似前沿面Pt*的解集.这两个指标的定义如下:

(9)
(10)

其中distance(Pit*, Pt)表示Pit*Pt之间的最小欧氏距离.因此, 对于每一个Pit*Pt, IGD都将会选择Pt中最近的点.在这种情况下, 只有均匀分布的和收敛性很好的Pt才会得到较低的IGD值.而Pit*越大, 所需要耗费的时间越多.

其次, 容错率(ER)将被引入, 用于评估静态MOP中近似Pareto前沿与真实Pareto前沿之间的收敛性.本文提出一种MER的ER的修改版, 用于评估DMOPs. MER定义为运行中整个环境ER度量的平均值, MER越小, 收敛性越强.该度量的定义如下:

(11)
(12)

其中: eri = 0表示解i是在真实Pareto前沿上, eri = 1则表示不在真实前沿上.因此, 只有一个收敛很好的Pt才能得到一个较低的值.

3.3 参数设置

问题和算法参数设置如下:

1) 问题参数设置.变化程度nT设置为10, 变化频率τT设置为20.测试问题的维度设置为n = 20.对于2目标问题的种群规模设置为100, 3目标问题设置为150.在粒子群优化中, 惯性权重定义为0.72;对于c1c2, 惯性系数设置为0.72.

2) DDMOPSO中的参数.在AR(p)模型中, 序列p = 3, 历史点序列长度M = 20.在初始种群中, 从预测模型中选出10 %, 其余选自以前的种群.

3) 评价次数.对2目标问题最高评价次数为3 000, 对3目标问题最高评价次数为6 000.

4) 变化检测.从种群中随机选择5 %的个体进行重新评估, 以检测所有策略的环境变化.

5) 运行次数和终止条件.每个算法将独立运行测试问题20次.当t≥160时, 算法停止, 这表明一次运行中的环境数为160.

3.4 实验结果及分析

表 1表 2给出了DDMOPSO算法以及4个对比算法优化6个测试函数得到的MER和MIGD评价指标的统计, 结果按照时间t分成两个部分: 0≤ t < 40和40≤ t < 160 (表 1表 2中, +(-)表示支持(不支持) DDMOPSO在95 %显著等级上表现优于比较算法的假设, 加粗标记为最佳结果). 图 2图 3给出了对比算法的ER和IGD指标值趋势图集, 每个算法在不同的时间里所得到的种群如图 4所示.

表 1 算法在F1 ~ F6上独立运行20次的MER的平均值和标准差值比较
表 2 算法在F1 ~ F6上独立运行20次的MIGD的平均值和标准差值比较
图 2 3种算法在F1 ~ F6实例上独立运行20次的平均ER值
图 3 3种算法在F1 ~ F6实例上独立运行20次的平均IGD值
图 4 3种算法在一次运行中t = 130,135,140,145和150时所得到的最终种群

表 1图 2可以看出, 在MER值方面, DDMOPSO算法与其他所有比较的算法都有着更好的收敛性.在t = 40之前, 各种算法的差异主要是因为在更新粒子群时将局部最优和全局最优考虑在内.因此, PSO比其他的交叉和变异算子具有更好的收敛性, 同时, 群预测策略能够找到有用的粒子来加速收敛.当40≤ t < 160时, 除了F4的MER值与dMOPSO持平外, DDMOPSO均优于其他算法. F4函数是一个比较困难的3目标问题, 而从图 2(d)中可以看出, 这两种基于分解的算法性能相似.另外, 在表 2的F4函数上, DDMOPSO的MIGD值显然低于dMOPSO.

图 2可以看出, DDMOPDO算法的ER值随时间的变化呈现出很强的周期性和波动性, 同时, 除了F5之外, 其他算法的ER值在所有的实例运行中都在1左右.

结合表 1表 2图 2 ~ 图 4的统计结果进行综合分析, 可以很容易得出结论: DDMOPSO在求解DMOPs方面比DVEPSO和dMOPSO具有更好的收敛性和多样性; 当变化程度为20, 变化频率为10时, 新算法对不同类型的DMOPs在F1 ~ F6上具有更好的稳定性和适应性.

3.5 变化程度nT的影响分析

不同的变化程度参数设置可能会影响算法的性能, 为此, 进行另外两组实验.参数nT分别设置为10和15, 变化频率设置为20, 因此, (nT, τT)被设置为(10, 20)和(15, 20), 其他参数设置与3.3节相同.

图 5中的第2、4、5行分别给出了3种算法在独立运行20次后, 参数nT分别为(10, 15, 20)设置下得到的MER值的盒图.当τT固定时, 随着nT的增加, 显然: 1)所有算法的MER值都降低; 2)由DDMOPSO获得的MER值比其他值小.因此, DDMOPSO的收敛能力在3种算法中是最好的.

图 5 3种算法在不同设置nTτT下独立运行20次的MER值(每个分图中, Ⅰ是DDMOPSO, Ⅱ是DVEPSO, Ⅲ是dMOPSO)

图 6中的第2、4、5行分别给出了3种算法在独立20次运行后, 参数分别为(10, 15, 20)的设置下得到的MIGD值的盒图.显然: 1) nT越大, 所有算法得到的MIGD越低; 2) DDMOPSO得到的MIGD值明显优于其他对比算法.

图 6 3种算法在不同设置nTτT下独立运行20次的MIGD值~ (每个分图中, Ⅰ是DDMOPSO, Ⅱ是DVEPSO, Ⅲ是dMOPSO)

综上所述, 本文提出的DDMOPSO在MER指标和MIGD指标上的表现均优于对比算法DVEPSO和dMOPSO, 而且, DDMOPSO对不同程度的变化表现出较低的敏感度.

3.6 变化频率τT的影响分析

不同的变化频率参数设置可能会影响算法的性能, 为此, 又进行两组实验.参数τT分别设置为10和40, 变化程度固定为10, 因此, (nT, τT)被设置为(10, 10)和(10, 40), 其他参数设置与3.3节相同.

图 5图 6的第1、2、3行分别给出了3种算法在独立运行20次后, 参数τT分别为(10, 20, 40)的设置下得到的MER值和MIGD值的盒图.通过分析可得出以下结论: 1)从收敛性来看, 不同算法得到的MER值都随着τT的增加而下降; 2)从分布性来看, MIGD值的变化趋势与MER相同; 3)显然, DDMOPSO在MER值和MIGD值方面都优于其他算法; 4)就MER而言, DDMOPSO的表现显著上升; 5)在MIGD方面, DDMOPSO算法与其他对比算法相比性能稳定, 其值总是在0附近.综上所述, 本文所提出的DDMOPSO比DVEPSO和dMOPSO具有更低的灵敏度.

4 工业应用

IEEE30节电力系统优化问题是在满足电力需求和线路最小化损耗的条件下, 求解发电成本以及环境污染最小化的一类静态优化问题[17].在实际生活中, 电力需求是动态变化的, 且存在周期性, 因此, 问题的形式以及问题的解都会随着时间变化而变化, 这就形成了带约束的动态优化问题.

4.1 问题定义

假设有n台发电机, 每台发电机的实际电力输出xi代表优化问题的决策值, 决策向量x = x1, ..., xn表示发电机的实际输出电力.问题有两个目标, 分别为最小总成本F(x)和最小化环境影响C(x), 具体如下:

(13)
(14)

其中: aibici为发动机组的成本计算参数, αiβiδiθiλi分别为环境影响计算参数.越低的总成本使用的往往是对环境高污染燃烧物以及设备, 因此, 问题之间存在着明显的冲突性.

此外, 优化问题中还有能量守恒等式约束和线路老化损耗不等式约束.其中守恒等式约束如下:

(15)

Er表示实际需求电量.系统线路损耗的计算公式为

(16)

Bijdie均为设备以及线缆的损耗系数. Er的计算公式如下:

(17)

t为时间变量, τ为当前迭代次数, nT为问题变化程度, τT为问题变化频率, 而其余函数模型均参照静态环境下的函数模型.

4.2 评价指标

本文采用3种评价指标, 分别为最优成本消耗平均值avgc、最低环境影响平均值avge和综合最优解的平均值μ, 即

(18)
(19)
(20)

其中: T为环境变化总次数; 最优解的μ值计算参照文献[18], 在此不再赘述.

4.3 实验参数设置

本问题的决策空间维数为n = 6, 决策空间的上边界依次为(0.5, 0.6, 1, 1.2, 1, 0.6), 下边界均为0.5, 目标个数为2, 其余参数参照文献[19].环境变化总次数为48, 变化程度nT和变化频率τT分别为(8, 20), (8, 30)和(12, 30).选取与DVEPSO算法对比, 种群规模均为100, 其余参数设置与3.3节相同.

4.4 实验结果与分析

表 3展示了两种算法在变化程度nT和变化频率τT分别为(8, 20), (8, 30)和(12, 30)时, 30轮独立实验中获得的avge、avgc和μ的平均值. 图 7展示了两种算法在t = 40, 42, 43, 44, 45, 47时, 得到的部分近似Pareto前沿.由表 3中avge和avgc可知, DDMOPSO算法相较于对比算法, 在成本和环境影响两个目标上其收敛性均占优. μ值表明算法选取的最优解综合成本与环境影响最优.结合图 7可以看出, 在每一次变化环境中, DDMOPSO算法具有更好的分布性.

表 3 算法在不同变化程度和变化频率下独立运行30次avgc、avge和μ值比较
图 7 算法DDMOPSO与DVEPSO在t = 40, 42, 43, 44, 45, 47时获得的最优解集

综上, 本文提出的基于分解的预测型动态多目标粒子群优化算法在求解IEEE30节电力系统时, 3项指标均优于对比算法, 说明本文算法在收敛性以及分布性上更优, 且在解决实际动态问题上具有更强的适应能力.通过观察在不同时刻算法获得的解集分布性, 当电力的实际需求量在2.721 65时有最低环境影响方案, 当实际需求电量在3.641 67时有最低成本方案.因此, 当发电量在2.72左右时对环境污染最低, 而当发电量在3.65时有最低的发电成本.本文算法在每一次环境变化时都可以为决策者提供一个最合理的解, 从而有助于做出更有效的决定.

5 结论

为了平衡动态多目标优化算法的收敛性和分布性, 本文提出了一种基于分解的预测型多目标粒子群优化算法DDMOPSO.首先, 将基于分解的策略引入粒子群优化中, 使种群中的粒子优化转化为由加权向量表示的子问题以提升种群进化效率; 为了跟踪移动的Pareto前沿, 提出了群预测策略, 同时, 设计了一种计算Pareto前沿变化前后的平均IGD作为量化环境变化程度的方法; 将群体自适应地分为两部分, 且两者的大小由变化程度动态地控制; 最后, 为解决动态问题产生的子问题与粒子之间的不匹配问题, 提出了再匹配策略, 最终形成了基于分解的预测型多目标粒子群优化算法.将DDMOPSO与DVEPSO和dMOPSO等算法进行了比较, 实验结果表明, 所提出的算法具有更优的收敛性、分布性和稳定性.同时, 将本文算法应用于解决实际动态多目标问题, 表明了算法的有效性和可行性.下一步工作是考虑更准确地评估环境变化的程度, 以提高算法的性能以及扩展AR模型来提高处理高维问题的能力.

参考文献
[1]
Farina M, Deb K, Amato P. Dynamic multiobjective optimization problems: Test cases, approximation, and applications[J]. IEEE Trans on Evolutionary Computation, 2004, 8(5): 425-442.
[2]
Deb K, Karthik S. Dynamic multi-objective optimization and decision-making using modified NSGA-Ⅱ: A case study on hydro-thermal power scheduling[C]. Evolutionary Multi-criterion Optimization. Berlin: Springer, 2007: 803-817.
[3]
Greeff M, Engelbrecht A P. Solving dynamic multi-objective problems with vector evaluated particle swarm optimisation[C]. Evolutionary Computation. Piscataway: IEEE, 2008: 2917-2924.
[4]
Koo W T, Chi K G. A predictive gradient strategy for multiobjective evolutionary algorithms in a fast changing environment[J]. Memetic Computing, 2010, 2(2): 87-110. DOI:10.1007/s12293-009-0026-7
[5]
武燕, 刘小雄. 动态多目标优化的预测遗传算法[J]. 控制与决策, 2013, 28(5): 677-682.
(Wu Y, Liu X X. Predictive multiobjective genetic algorithm for dynamic multiobjective optimization problems[J]. Control and Decision, 2013, 28(5): 677-682.)
[6]
郑金华, 彭舟, 邹娟, 等. 基于引导个体的预测策略求解动态多目标优化问题[J]. 电子学报, 2015, 43(9): 1816-1825.
(Zheng J H, Peng Z, Zou J, et al. A predication strategy based on guide-individual for dynamic multi-objective optimization[J]. Acta Electronica Sinica, 2015, 43(9): 1816-1825. DOI:10.3969/j.issn.0372-2112.2015.09.021)
[7]
Gan R, Yu J, Zhen J. The effect of diversity maintenance on prediction in dynamic multi-objective optimization[J]. Applied Soft Computing, 2017, 58(9): 631-647.
[8]
Eberhart R, Kennedy J. A new optimizer using particle swarm theory[C]. Proc of the 6th Symposium on Micro Machine & Human Science. Nagoya, 2002: 39-43.
[9]
Zhang Qing-fu, Li Hui. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Trans on Evolutionary Computation, 2007, 11(6): 712-731.
[10]
Zhou Ai-min, Jin Yao-chu, Zhang Qing-fu. A population prediction strategy for evolutionary dynamic multiobjective optimization[J]. IEEE Trans on Cybernetics, 2014, 44(1): 40-53. DOI:10.1109/TCYB.2013.2245892
[11]
Hatzakis Iason, David Wallace. Dynamic multi-objective optimization with evolutionary algorithms: A forward- looking approach[C]. Proc of the 8th Annual Conf on Genetic and Evolutionary Computation. Berlin: Springer-Verlag, 2006: 1201-1208.
[12]
Goh C K, Tan K C. Acompetitive-cooperative paradign fer dynamic multiobjective optimization[J]. IEEE Trans on Evolutionary Computatio, 2009, 13(1): 103-127.
[13]
Helbig Mardé, Andries P. Population-based metaheuristics for continuous boundary-constrained dynamic multi-objective optimization problems[J]. Swarm and Evolutionary Computation, 2014, 14(4): 31-47.
[14]
Zapotecas Martínez Saúl, Carlos A Coello Coello. A multi-objective particle swarm optimizer based on decomposition[C]. Proc of the 13th Annual Conf on Genetic and Evolutionary Computation. Dublin, 2011: 12-16.
[15]
Schuetze O, Equivel X. Some comments on GD and IGD and relations to the Hausdorff distance[J]. Proc of Genetic & Evolutionary Computation Conf, 2010, 161(1): 1971-1974.
[16]
Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Trans on Evolutionary Computation, 2002, 6(2): 182-197. DOI:10.1109/4235.996017
[17]
Abido M A. Multiobjective evolutionary algorithms for electric power dispatch problem[J]. IEEE Trans on Evolutionary Computation, 2006, 10(3): 315-329.
[18]
Zhang Y, Gong D W, Ding Z. A bare-bones multi-objective particle swarm optimization algorithm for environmental/economic dispatch[J]. Information Science, 2012, 192(6): 213-227.
[19]
Wu Y, Jin Y, Liu X. A directed search strategy for evolutionary dynamic multiobjective optimization[J]. Soft Computing, 2015, 19(11): 3221-3255.