没有合适的资源?快使用搜索试试~ 我知道了~
一种基于目标空间转换权重求和的超多目标进化算法.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 20 浏览量
2023-02-23
16:48:10
上传
评论
收藏 1.66MB DOCX 举报
温馨提示
试读
33页
一种基于目标空间转换权重求和的超多目标进化算法.docx
资源推荐
资源详情
资源评论
现实应用中存在各种各样的多目标优化问题(Multi-objective optimization problems,
MOPs), 如电能分配
[1]
、污水处理控制
[2]
、服务质量优化
[3]
、车辆路径规划
[4]
、软件项目管理
[5]
、微电网管理
[6]
, 等等. 由于 MOPs 的不同目标函数之间通常相互冲突, MOPs 的最优解集
不是单一的解而是一组折衷解, 即帕累托最优解集(Pareto optimal set). 虽然一些性能优越的
多目标进化算法(Multi-objective evolutionary algorithms, MOEAs), 如 NSGA-II
[7]
, SPEA2
[8]
和
MOEA-PPF
[9]
等能很好的处理 MOPs, 但在解决超多目标优化问题(Many-objective
optimization problems, MaOPs)时, 上述算法的性能将显著下降. 原因是随着目标函数的增
加, 非支配个体在种群中所占的比例将呈指数式增长, 基于帕累托关系的算法会逐渐丧失收
敛压力
[10]
. 为解决该问题, 学术界从不同角度对超多目标进化算法(Many-objective
evolutionary algorithms, MaOEAs) 进行了较广泛的探讨
[11-15]
, 大致可分为以下四类: 1) 基于
放松支配. 该类算法的主要思想是通过扩大支配范围来增强种群往 PF 方向收敛的压力. 代
表性方法有 ϵϵ 支配
[16]
, LL 支配
[17]
和模糊支配
[18-19]
等; 2) 基于指标. 该类算法将个体的指标值
作为环境选择的衡量标准, 如 IBEA
[20]
, HypE
[21]
和 ARMOEA
[22]
等; 3) 基于分解. 该类算法将
MaOPs 分解为多个单目标优化问题(Single-objective optimization problems, SOPs)
[23]
, 随后在
进化框架下同时优化这些 SOPs, 如 MOEA/D
[24]
, NSGAIII
[25]
和 SPEAR
[26]
等. 4)混合型. 该类
算法采用两种或者两种以上的方法来实现对超多目标问题的优化, 如 Two_arch2
[27]
和
HpaEA
[28]
均融合了基于支配和基于指标的方法, SRA
[29]
则采用了多指标的策略. 在上述算法
中, 基于分解的 MaOEAs 受到了学术界的高度关注, 该类算法的核心是对参考向量和分解
方法的设计.
参考向量主要影响种群在 PF 上分布的均匀性, 即多样性. 在经典的分解类算法
MOEA/D 中, 采用一组均匀分布在目标空间上的向量集作为参考向量. 该参考向量在规则
PF 问题上能取得优越的性能, 但不能很好地处理退化、不连续、凹凸混合等不规则 PF 问
题. 原因在于不规则 PF 上参考向量的分布不均匀, 进而造成种群在 PF 上分布不均匀. 针对
该问题, 学术界提出了很多对均匀分布的参考向量进行调整的方法, 如 CA-MOEA
[30]
通过层
次聚类方法来调整每代的参考向量, MOEA-AWA
[31]
则根据种群中的精英个体来对参考向量
进行调整, 类似的调整方法还有 g-DBEA
[32]
和 DDEANS
[33]
等. 然而, 由于频繁调整参考向量,
参考向量调整类算法的性能在处理规则 PF 问题时容易恶化
[34]
.
分解方法主要影响种群的搜索效率, 即收敛性. 现有研究表明
[35-37]
, 切比雪夫方法可有
效处理各种 PF 形状的问题但搜索效率很低, 权重求和方法虽然不能处理好非凸 PF 问题但
搜索效率却很高. 为此, Ishibuchi 等提出了两种改进方案, 分别为自适应切比雪夫和权重求
和方法 AS
[37]
, 同时使用切比雪夫和权重求和方法 SS
[38]
, 以综合切比雪夫和权重求和各自的
优势. 此外, Wang 等提出了局部权重求和方法 LWS
[39]
, 在综合性能上取得了显著的效果.
但由于 LWS 加入了局部的思想, 一定程度上降低了权重求和方法的搜索效率.
总体而言, 虽然学术界已对基于分解的 MaOEAs 进行了较广泛研究, 但该类方法的性
能仍存在较大提升空间. 为尽可能不损害权重求和方法搜索效率高的优势, 同时又能处理好
各类 PF 为非凸型的问题, 本文从改进现有分解方法的角度, 提出了一种基于目标空间转换
权重求和的超多目标进化算法, 简称 NSGAIII-OSTWS. 其中目标空间转换权重求和
(Objective space transformation based weighted sum, OSTWS)将各种类型问题的 PF 转换为凸
型曲面, 再利用权重求和方法对问题进行优化. 具体地, 首先利用预估 PF 的形状计算个体
到预估 PF 的距离; 然后, 根据该距离值将个体映射到目标空间中预估凸型曲面与理想点之
间的对应位置; 最后, 采用权重求和函数计算出映射后个体的适应值, 据此实现对问题的优
化. 为验证 OSTWS 的有效性, 本文在 NSGAIII 框架的基础上, 将 OSTWS 与现有的 7 个分
解方法在 WFG、DTLZ 和 LSMOP 测试问题集上进行了对比, 同时将所提的 NSGAIII-
OSTWS 与 9 个具有代表性的 MaOEAs 进行了对比, 实验结果表明 NSGAIII-OSTWS 具备
良好的竞争性能.
本文的内容安排如下. 第 1 节介绍与本文相关的背景知识. 第 2 节阐述目标空间转换
权重求和方法 OSTWS, 以及基于 OSTWS 的超多目标进化算法 NSGAIII-OSTWS. 第 3 节
介绍实验设计、实验结果, 并进行相关讨论. 最后对本文进行总结并指出未来的研究方向.
1. 背景知识
1.1 多目标优化问题
一般来说, 一个 MOP 的数学定义可表述为:
minF(x)=(f1(x),f2(x),⋯,fm(x))s.t.x∈ΩminF(x)=(f1(x),f2(x),⋯,fm(x))s.t.x∈Ω
(1)
其中, x 是决策空间 ΩΩ 中的 nn 维决策向量, mm 是目标函数的个数, RmRm 是目标空
间. FF: Ω→RmΩ→Rm 组成 mm 个目标函数. 目标数 mm 大于 3 的 MOPs 也被称为超多目
标优化问题, 即 MaOPs. 假设 x 和 y 是决策空间中的两个不同候选解, x 支配 y (记为 x ≺≺ y)
当且仅当∀i∈{1,2,⋯,m}∀i∈{1,2,⋯,m}, fifi(x)≤fi≤fi(y)且∃i∈{1,2,⋯,m}∃i∈{1,2,
⋯,m}, fifi(x)<fi<fi(y). 如果候选解 x 不被任何其他解所支配, 则称候选解 x 为帕累托最优解.
所有帕累托最优解的集合称为帕累托最优解集(Pareto optimal set, PS), 即
PS={x/∃y∈Ω,PS={x⧸∃y∈Ω,x≻y}x≻y}. 所有帕累托最优解对应的目标向量构成帕累托最优
前沿(Pareto optimal front, PF), 即 PF = {F(x)|x∈PS}{F(x)|x∈PS}.
1.2 分解方法
分解方法决定了基于分解的 MaOEAs 的搜索效率, 对算法的性能有着重要影响. 研究
者们设计了许多不同的分解方法, 并在各种 MaOPs 上展现出了优越的性能. 常见的分解方
法有以下三种:
1)权重求和(Weighted sum, WS)法: WS 方法通过加权的方式将所有目标组合成一个单
一的目标, 其数学定义如下:
gWS(x|w)=∑i=1m(wifi(x))s.t.x∈ΩgWS(x|w)=∑i=1m(wifi(x))s.t.x∈Ω
(2)
其中, w=[w1,w2,⋯,wm]w=[w1,w2,⋯,wm]为一个参考向量. 在本文中, 满足 wi>0wi>0,
并且∑mi=1(wi)2=1∑i=1m(wi)2=1. 如图 1(a)所示, 采用 WS 方法构造的子问题通过在不同的
参考向量 w 上进行搜索, 可以快速得到一组近似 PF 点. 在 PF 为凸的情况下, WS 方法能获
得一组均匀的 PF 点, 但在 PF 为非凸的情况下, 该方法则会丢失 PF 中的大部分点
[24]
, 从而
严重损失种群的多样性, 即 WS 方法不能处理好 PF 为非凸的问题.
图 1 分解方法 WS, TCH 和 PBI 在参考向量 w 上的二维示意图, 其中虚线为等高线
Fig. 1 Illustration of the decomposition methods WS, TCH and PBI on reference vector w, where
dashed lines are contour lines
下载: 全尺寸图片 幻灯片
2)切比雪夫(Techebycheff, TCH)法: TCH 方法将 MaOP 转化为一个 SOP 的数学定义如
下:
gTCH(x|w,z∗)=max1≤i≤m(1wi|fi(x)−z∗i|)s.t.x∈ΩgTCH(x|w,z∗)=max1≤i≤m(1wi|fi(x)−zi∗|)s.t.x∈Ω
(3)
其中, z∗=[z∗1,z∗2,⋯,z∗m]z∗=[z1∗,z2∗,⋯,zm∗]为理想点. 在实际应用中, 如果 wiwi = 0,
则将 10−410−4 赋值给 wiwi, 以此来避免除法的不合理情况. 此外, 为进一步提升所获得解
集分布的均匀性, 可将式(3)中的 1/wiwi 用 wiwi 替代
[40]
. 图 1(b)为 TCH 方法的二维示意图.
与 WS 方法相比, TCH 方法能处理好任意 PF 形状的 MaOPs. 因此, TCH 方法被广泛应用在
各种基于分解的算法中
[41-42]
.
3)基于惩罚的边界交叉(Penalty-based boundary intersection, PBI)法: PBI 方法构造子问
题的数学定义如下:
gPBI(x|w,z∗)=d1+θd2s.t.x∈Ωd1=∥∥(F(x)−z∗)wT∥∥||w||,d2=∥∥∥F(x)−(z∗+d1w||w||)∥∥∥gPBI(x|w,z∗)=d1+θd2s.t.x∈Ωd1=‖(F(x)−z∗)wT‖||w||,d2=‖F(x)−(z∗+d1w||w||)‖
(4)
其中, θθ(θ>0θ>0) 为一个事先设定的惩罚因子, d1d1 为向量(F(x)−z∗)(F(x)−z∗)在权重
向量 w 上的投影长度, d2d2 为 F(x)F(x)到 w 的垂直距离. 图 1(c)为 PBI 方法的示意图. 由
PBI 的定义(式(4))和图 1(c)可知, θθ 是平衡收敛性(用 d1d1 衡量)和多样性(用 d2d2 衡量)的
关键性参数. 近来有研究表明
[43-44]
, 当 PBI 处理 PF 为凸的问题时, 较大的 θθ 可以获得较好
的种群分布, 而较小的 θθ 值有利于种群更好地收敛到 PF.
2. NSGAIII-OSTWS 算法
2.1 动机
在基于分解的算法中, 分解方法将 MaOP 转化为若干个 SOPs, 然后在进化框架下以协
同的方式优化每个 SOPs. 如果没有选择合适的分解方法, 或者使用的分解方法不能很好地
将 MaOP 转化为 SOPs, 基于分解的 MaOEAs 最终获得的种群就有可能无法逼近 PF.
目前, 上节介绍的三种分解方法, 即 WS、TCH 和 PBI, 已在基于分解的 MaOEAs 中
被广泛应用. 图 1 是这三种方法在二维目标空间下的示意图. 每个子图中的等高线将目标空
间划分为两个区域, 位于同一条等高线上的解具有相同的质量, 靠近理想点 z∗z∗区域的解
质量则要优于另外一区域. 如图 1(a)所示, WS 的等高线是一条经过候选解且垂直于参考向
量的直线, 其优越区域
[39]
占整个区域的 1/2. 从图 1(b)可以看出, TCH 的等高线则为经过候
选解和参考向量的两条相互垂直的直线, 其优越区域为 1/2m1/2m, 随着目标函数 mm 的增
加, 该值会显著减小. 图 1(c)中, PBI 的等高线是经过候选解和参考向量的两条相交直线, 它
的优越区域由惩罚因子 θθ 决定. θθ 值越大, 则优越区域的面积越小, 通常情况下该区域的
面积小于整个区域面积的 1/2. 由上述分析可知, WS 的优越区域是最大的. 换言之, 采用
WS 可以更大概率搜索到比目前更优的解, 即收敛速度最快. 然而, 当采用 WS 处理非凸问
题时, PF 中的大部分点会被丢失
[24]
, 从而严重损失种群的多样性
[39]
. 综上所述, 相比 TCH
和 PBI 而言, WS 具有更强的收敛性但却不能处理好非凸问题.
为充分发挥 WS 搜索效率高的优势, 同时又能处理好各类 PF 形状为非凸的问题, 研究
者们提出了一些 WS 的改进方法, 如 AS
[37]
和 SS
[38]
等. 然而, 这些方法的主要思想仅是利用
TCH 方法来处理 WS 不能处理好的凸型 PF 问题, 并未对 WS 方法本身进行改进. 最近,
Wang 等
[39]
提出了一种新颖的 WS 方法, 即局部权重求和方法 LWS. 该方法的主要思想是对
于每个搜索方向, 只在其相邻解中挑选最优解. LWS 方法能够较好处理包括 PF 非凸在内的
各类型 PF 问题, 但由于 LWS 在求解最优解时加入了局部的思想, 也在一定程度上降低了
WS 方法搜索效率高的优势. 为验证该结论, 本文将 LWS 方法和 WS 方法分别嵌入到基于
分解的算法 NSGAIII
[25]
, 形成算法 NSGAIII-WS 和 NSGAIII-LWS. 图 2 为这两个算法在 PF
为凸的测试问题 ZDT1
[45]
上的最终种群分布图. 其中, 运行次数为 20 次, 迭代次数为 120
代, 种群大小为 200, 决策变量数的大小参照文献[45]设置, 其它参数与 NSGAIII 保持一致.
从图 2 可以看出, NSGAIII-WS 算法获得的种群具有更好的收敛性. 为尽可能发挥权重求和
方法搜索效率高的优势, 同时又能处理好非凸型 PF 问题, 本文提出了一种新颖的方法——
目标空间转换权重求和方法.
图 2 NSGAIII-WS 和 NSGAIII-LWS 算法在 ZDT1 上获得的最终种群分布
Fig. 2 The final population distribution obtained by NSGAIII-WS and NSGAIII-LWS algorithm
on ZDT1
下载: 全尺寸图片 幻灯片
2.2 目标空间转换权重求和方法
目标空间转换权重求和方法 OSTWS 的核心思想, 是将各种问题的 PF 转换为凸型曲
面, 并基于该凸型曲面进行求解. OSTWS 方法的伪代码如算法 1 所示.
算法 1. OSTWS 方法
输入. U (种群), NN(种群大小), W (参考向量集), CC(曲率)
输出. gwdgwd(个体的适应值)
1)归一化种群 U;
2)预估出 PF 的形状: pp = estimate_PFshape(U);
剩余32页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3675
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功