欢迎访问一起赢论文辅导网
本站动态
联系我们

手机:15327302358
邮箱:peter.lyz@163.com

Q Q:
910330594  
微信paperwinner
工作时间:9:00-24:00

SCI期刊论文
当前位置:首页 > SCI期刊论文
偏好多目标进化算法研究综述
来源:一起赢论文网     日期:2020-05-23     浏览数:108     【 字体:

 h team systematically describe the preference multi-objective evolutionaryalgorithms from two aspects:the preference setting methods and the performance of the algorithms.In the setting of preferences,we summarize the multi-objective evolutionary algorithms incorporatingpreference information from the four aspects:dominance relationship,angle relationship,weightvector and preference set.Firstly,we summarize the preference multi-objective evolutionaryalgorithms based on the dominance relationship.The core idea behind it is to modify the Paretodominance relationship,enhance the selection pressure of the algorithms and guide the algorithmsto quickly converge to the preference region.Secondly,we summarize the preference multi-objec-tive evolutionary algorithms based on angle relationship.The core idea is to use the anglerelationship between the solutions to guide the evolution of the population,while using the angleto control the range of the preference region to obtain the preference solutions.Thirdly,we sum-marize the preference multi-objective evolutionary algorithms based on weight vector.The coreidea is to transform the decision-maker’s preference information into a set of weight vectorscarrying preference information,and then decompose the multi-objective optimization probleminto several single-objective optimization sub-problems according to the weight vectors.We lastlyintroduce the preference multi-objective evolutionary algorithms based on preference sets.Thecore idea is coevolving a set of randomly generated preference sets together with population.Then,in the algorithm performance,two kinds of preference multi-objective evolutionary algorithms areselected from each of the four methods to perform simulation experiments.In addition,in orderto verify the robustness of the eight algorithms in different preference regions.Our research teamselect two different reference points in the feasible region and the infeasible region for experimentalcomparison.Next,we carry out a systematic comparison of the eight algorithms from threeaspects:the effectiveness of the preference strategy,the overall performance of the solution set,as well as the complexity of the algorithm,and analyzed their advantages and disadvantages indepth.Finally,our research team end up with discussing some potential trends in preference-based multi-objective evolutionary algorithms’future development from the six aspects:preferenceinformation conversion, preference learning,implicit preference construction, performanceindicators of preference algorithms,visualization problem and practical application.Keywords  multi-objective optimization;preference setting;dominance relationship;anglerelationship;weight vector;preference set1 引 言在科学研究和实际应用中通常存在多个目标同时 优 化 的 问 题,这 些 问 题 称 为 多 目 标 优 化 问 题MOPs(Multi-Objective Optimization Problems).MOPs的最优解并不是单个的最优解,而是一组由Pareto最 优 解 组成的最 优 解 集合[1].现 阶 段 求 解MOPs的主要方法是多目标进化算法(Multi-ObjectiveEvolutionary Algorithms,MOEAs).根据进化机制的不同,又可以将 MOEAs分为以下三类:(1)基于支配关系的 MOEAs,其基本思想是利用基于 Pareto的适应度分配策略,从当前种群中找出所有非支配个体.Deb等人[2]提出的 NSGA-II(Non-dominated Sorting Genetic Algorithm-II)、Zitzler等人[3]提出的 SPEA2(Strength Pareto EvolutionaryAlgorithm 2)和 Corne 等 人[4]提 出 的 PESA-II(Pareto Envelop-based Selection Algorithm-II)是该类算法的三种典型代表.然而传统 Pareto支配关系随目标维度的增加而迅速恶化,通过修改 Pareto支配关系能有效增强对个体的选择压力.Laumanns等人[5]提出的ε-支配通过修正因子ε来修改 Pareto支配关系;Pierro等人[6]提出用优先排序方法取代了传统的非 支 配 排 序 方 法;Wang 等 人[7]和 He等2109 计  算  机  学  报 2019年支配关系设计新的排序策略;Yang等 人[9]提 出 基 于 网 格 的 进 化 算 法 (Grid-based Evolutionary Algorithm,GrEA),通 过 调 整网格大小来 选 择 优 先 级 较 高 的 非 支 配 解;Antonio等人[10]通过交替使用收益函数和ε-支配方法来提高算法性能;Li等人[11]提 出基 于 偏 移 的 密 度 估 计策略,对算法中的多样性维持机制进行改进,使基于Pareto支配的算法更适用于求解 MOPs;Cheng等人[12]通 过 引 入 DD(Directional Diversity)和 FC(Favorable Convergence)指标来衡量算法的收敛性和多样性,在交叉变异阶段,将FC指标与 Pareto支配方法相结合以提高算法的收敛性,在选择阶段,提出一种多样性维持策略以平衡算法的多样性和收敛性.最近,学者们提出在支配关系的基础上引入偏好信息以提高算法的选择压力,如 Wang等人[13]提出的基于目标向量偏好集协同进化算法(Preference-Inspired Co-evolutionary Algorithm Using Adap-tively Generated Goal Vectors,PICEA-g)和 Zhang等人[14]提出的基于 Knee点驱动的进化算法(KneePoint Driven Evolutionary Algorithm,KnEA)等.(2)基于指标的 MOEAs,其基本思想是使用性能评价 指 标 来 引 导 搜 索 过 程 和 对 解 的 选 择 过 程.IBEA(Indicator-Based Evolutionary Algorithm)[15]、HypE(Hypervolume Based Evolutionary Algorithm)[16]和 SMS-EMOA(S-Metric Selection Based Evolu-tionary Multi-Objective Algorithm)[17]是三种 广 泛使用的该类算法.IBEA 是一种基于评价指标的算法框架,可 以 与 任 意 指 标 相 结 合,而 SMS-EMOA和 HypE 则 是 利 用 超 体 积 值 对 个 体 进 行 选 择.Gerstl等人[18]提 出 一 种 基 于 Δp 指 标 的 算 法 (Δpindicator-based algorithm,Δp-EMOA),其 中 Δp为近似解集与真实 Pareto前沿间的 Hausdorff距离;Villalobos和 Coello[19]将 Δp 指标与差 分 进 化相结合,以解决10维的 MOPs;Lopez等人[20]提出IGD+-EMOA(Inverse Generational Distance PlusEvolutionary Algorithm)算法,通过建立参考集以评估搜索过程中得到的解的质量.(3)基于分解的 MOEAs,其基本思想是将复杂的 MOP 分 解 为 单 目 标 子 问 题 (Single-ObjectiveProblems,SOPs)或多个简单的 MOPs进行求解.Zhang等人[21]将传统的数学规划方法与进化算法相结合提出基于分解的 MOEA/D(Multi-ObjectiveEvolutionary Algorithm Based on Decomposition)算法;在此 基 础 上,众 多 学 者 对 MOEA/D 进 行 改进,提 出 许 多 MOEA/D 的 改 进 算 法[22-25];此 外,Cheng等 人[26]提 出 的 RVEA (Reference Vectorguided Evolutionary Algorithm)算 法 也 是 通 过 将MOP分解为多个SOPs进行求解.Liu等人[27]提出的 MOEA/D-M2M (Decomposition of a Multiob-jective Optimization Problem into a Number ofSimple Multiobjective Subproblems)算 法 将 整 个目标空间划分为若干子区域从而进行求解;Deb等人[28]提 出 的 NSGA-III(An Evolutionary Many-Objective Optimization Algorithm Using Reference-point Based Non-dominated Sorting Approach)算法,将 NSGA-II中的非支配分层机制和 MOEA/D中的分解机制相结合,避免了 Pareto支配带来的退化问题,同时保证种群的多样性.随着目标维度的增加,传统 MOEAs的搜索机制迅速陷入瓶颈,算法性能急剧下降,使其面临极大的挑战[29]:(1)逼近整个 Pareto前沿所需解的数量呈指数级增长,使 得算法的 计 算复杂度 明 显增大;(2)种群中非支配解的比例急剧增长,严重削弱了传统 Pareto支配关系对种群的选择压力,导致算法的收敛性能严重恶化;(3)增加了解集可视化的难度,使得决策者(Decision Maker,DM)难以从大量的非支配解中选择其满意的最优解.针对传统 MOEAs求解高维目标问题面临的诸多困难,学者们提出了许多改进方法:(1)降低目标维度.Zhou等人[30]和 Zitzler等人[31]都通过删除冗余目标的方法以达到目标降维的目的.Murata等人[32]运用目 标 函数加权 法对冗余目标进行加权,可 有效防 止 重要信息 的 丢失.然而,目标降维的前提是优化问题中必须存在多个冗余目标.但在实际优化问题中往往不存在多个冗余目标且冗余目标的确定需要花费巨大的计算资源.(2)使用指标函数.在 MOEAs中,需要运用评价指标对算法的性能进行评价,因此可以直接利用性能评价指标指导算法的搜索方向.其中,超体积指标(HyperVolume,HV)[33]是最常用的指标函数.然而在高维目标空间中,HV 指标的计算复杂度很大,这也限制了该方法的广泛应用.(3)修改 Pareto支配关系.目前已提出众多新的支配关系,如ε-支配关系[5]、排序支配关系[6]、模糊支配关系[7-8]等.虽然新的支配关系能增强种群在进化过程中的选择压力,但其重复利用目标函数的信息使得算法的计算复杂度明显增大.(4)结合 DM 偏好.Fleming等人[34]运用偏好6期 王丽萍等:偏好多目标进化算法研究综述2119],通过逐渐缩小搜索区域来获得偏好解.Deb等人[36]将参考点的偏好信息纳入到 NSGA-II算 法 中 以 获 得 非 支 配 解 集.Molina等人[37]提出给定参考点的g-占优方法(ReferencePoint Based Dominance for Multi-objective Meta-heuristics,g-dominace),将参考点作为偏好信息引导种群的搜索趋势和前沿的逼近方向.其中,参考点是目标空间中由 DM 定义的点,用于表示 DM 对每个目标不同的期望程度.由于该类方法只需要搜索DM 感兴趣的区域,不仅提高 MOEAs的求解效率,还能帮助 DM 选择其偏好解,因而受到研究者们的广泛关注.本文第1节引言部分简要介绍 MOEAs主流研究者和研究团队的工作概况;第2节偏好多目标进化算法,着重介绍了偏好 MOPs的相关概念,从占优关系、角度关系、权重向量和偏好集四个方面对偏好的设置方法进行详细分析;第3节偏好多目标进化算法性能对比分析,从四类偏好设置方法中各选取两种代表性的偏好算法进行仿真实验,从偏好策略的有效性、解集的整体性以及算法的复杂度三个方面进行实验对比并深入分析其优缺点,并给出了专门用于评价偏好 MOEAs性能的指标;第4节结语,提出了偏好 MOEAs有待进一步研究的若干方向.2 偏好多目标进化算法在现实问题中,DM 通常只对 MOPs的 Pareto前沿部分区域感兴趣.而随目标维度的增加,种群中非支配解的比例急剧增长,这将导致算法的性能衰减严重[38].若能结合 DM 的偏好信息,将算法的搜索集中在 Pareto前沿的特定区域,便能降低算法的计算复杂度,提高收敛性能.因此如何结合 DM 的偏好信息以及如何利用偏好信息引导种群的搜索成为当前的研究热点.2.1 偏好多目标优化问题相关概念多目标优化是指同时优化多个目标使其达到最优,然而各个目标间往往是相互冲突的,因此 MOPs的解是一 组 折 中 的 最 优 解 集 合.本 文 以 最 小 化 问题为例,对于一个具有 m 个目标,n 维 决策变 量 的MOPs,其数学模型描述如下: Min y=F(x)=(f1(x),f2(x),…,fm(x))Tgi(x)0,i=1,2,…,phj(x)0,j=1,2,…,烅烄烆 q(1)其中,x=(x1,x2,…,xn)∈X,x 为决策变量,y=(y1,y2,…,ym)∈Y,y 为优化目标,X 为n 个决策变量构成的决策空间,Y 为m 个优化目标构成的目标空间,F(x)为目标向量,gi(x)和hj(x)分别为问题的约束条件.定义1(Pareto支配). 设x 和y 是种群中任意两个个体,需满足如下约束条件,则称x 支配y,记作xy.fi(x)fi(y), i=1,2,…,mfj(x)<fj(y),j=1,2,…,烅烄烆m(2)定义2(非支配解). 设x 是集合Q 中的任意解,需满足式(3),则称x 为集合Q 中的非支配解./y∈Q:yx (3)定义3(Pareto最优解). 设可行域R 中任意两个个体x与y,需满足式(4),则称个体x为Pareto最优解./y∈R:yx (4)定义4(Pareto最优解集). 可行域 R 中所有的 Pareto 最 优 解 组 成 Pareto 最 优 解 集 (ParetoSet,PS).S={x|x∈R 且x 是Pareto最优解} (5)定义5(Pareto前沿). Pareto最优解集中所有Pareto最优解在目标空间上的映射,称为:Pareto前沿(Pareto Front,PF).PF={f(x)∈R|x∈PS} (6)定义6(决策偏好). 在多准则决策(MultipleCriteria Decision Making,MCDM)领域,决策偏好是指决策者在面对几个选项或备择方案时选择其中某一选项或备择方案的倾向[39].定义7(偏好表示). DM 通常将参考 点的位置信息作为偏好信息的载体,不同参考点的位置信息代表 DM 不同的偏好要求[40].此外,由参考点确定的参考方向、光束搜索等方法也用来表示 DM 的偏好信息[41].定义8(偏好支配). 设种群中任意两个个体x与y,若个体x偏好支配y,当且仅当满足如下2个条件之一,记作xry,r为 DM 偏好.(1)x支配y;(2)x与y 互不支配,x在偏好意义上占优y.定义9(偏好最优解). 设可行域 R 中的个体x,若不存在任意个体y,使得yrx,则称个体x为偏好最优解.由偏好最优解组成的最优解集合为偏好最优解集.2.2 偏好的理论研究多准则决策(MCDM)主要解决具有多个相互冲2129 计  算  机  学  报 2019年出 版 日 期:2019-01-06.本 课 题 得 到 国 家 自 然 科 学 基 金 项 目 (61472366,61379077)、浙 江 省 自 然 科 学 基 金(LY17F020022)、浙江省重点研发计划项目(2018C01080)资助.王丽萍(通信作者),博士,教授,中国计算机学会(CCF)会员,主要研究方向为计算智能、决策优化.E-mail:wlp@zjut.edu.cn.丰美玲,硕士研究生,主要研究方向为计算智能、决策优化.邱启仓,硕士,主要研究方向为智能控制.章鸣雷,硕士,主要研究方向为计算智能.邱飞岳(通信作者),博士,教授,主要研究方向为智能控制、深度学习.E-mail:qfy@zjut.edu.cn.偏好多目标进化算法研究综述王丽萍1),2) 丰美玲2) 邱启仓3) 章鸣雷2) 邱飞岳4)1)(浙江工业大学计算机科学与技术学院 杭州 310023)2)(浙江工业大学信息智能与决策优化研究所 杭州 310023)3)(之江实验室 杭州 311100)4)(浙江工业大学 杭州 310023)摘 要 多目标优化需要同时优化若干相互冲突的目标,其目的是获得均匀分布于整个 Pareto前沿上的最优解集.然而在实际多目标优化问题中,决策者通常只对目标空间中部分区域内的 Pareto最优解感兴趣,因此将决策者的偏好信息与多目标优化方法相结合成为进化计算领域的研究热点.偏好多目标进化算法通过引入决策者的偏好信息,将算法的搜索集中在决策者感兴趣的偏好区域,有效利用算法的计算资源,提高算法的求解效率,降低计算复杂度,同时有利于决策者高效地做出最终决策.本文从偏好的设置方法和算法性能两个角度介绍偏好多目标进化算法.在偏好的设置上,从占优关系、角度关系、权重向量和偏好集四个方面综述融入偏好信息的多目标进化算法;在算法性能上,从上述四类偏好的设置方法中各选取两种偏好算法进行仿真实验,从偏好策略的有效性、解集的整体性以及算法的复杂度三个方面进行实验对比并深入分析其优缺点.最后,总结了偏好多目标进化算法的未来发展趋势.关键词 多目标优化;偏好设置;占优关系;角度关系;权重向量;偏好集中图法分类号 TP391   DOI号 10.11897/SP.J.1016.2019.01289Survey on Preference-Based Multi-Objective Evolutionary AlgorithmsWANG Li-Ping1),2) FENG Mei-Ling2) QIU Qi-Cang3) ZHANG Ming-Lei 2) QIU Fei-Yue4)1)(College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023)2)(Institute of Information Intelligence and Decision Optimization,Zhejiang University of Technology,Hangzhou 310023)3)(Zhejiang Lab,Hangzhou 311100)4)(Zhejiang University of Technology,Hangzhou 310023)Abstract  Multi-objective optimization needs to optimize several conflicting objective simultaneously.The aim of the optimization algorithms is to obtain the optimal solution sets which uniformlydistributed on the whole Pareto front.However,decision makers usually are only interested inthe Pareto optimal solutions in some regions of the objective space in practical multi-objectiveoptimization problems.Therefore,combining decision maker’s preference information withmulti-objective optimization methods is gradually becoming a hot survey topic in the research fieldof evolutionary computing.Combining the decision maker’s preference information with themulti-objective evolutionary algorithms,the search process of the algorithms can be concentratedin the preference region.This can not only use the computational resources effectively andimprove the efficiency of the algorithms to solve the optimization problems,but also can reducethe computational complexity and help decision makers make the final decision efficiently.In this].MCDM 包括适用于解决有限 离 散 问 题 的 多 属 性 决 策 (Multiple AttributeDecision Making,MADM)和 适 用 于 连 续 问 题 的多目标决策 (Multiple Objective Decision Making,MODM).目前已有许多求解 MCDM 问题的方法,如理想点法、主成分分析法、加权平方和法等,这些方法 大 多 需 要 给 出 各 指 标 的 权 重,即 DM 的 偏好[43].权重是各个准则相对于总准则作用的量化,能反映每个准则的相对重要性.在 MCDM 领域中,偏好 的表示方法主要有以下三种:序数法、不确定法和基数法[44].序数法主要用于处理序数关系值类的偏好信息,即 DM 给出对多个方案的排序信息.不确定法一般用于决策过程中存在不确定因素时的偏好信息表示.基数法是指能够明确度量 DM 偏好、决策规则以及效用函数时的决策信息表示方法.根据以上三种表示方法,决策偏好的表示形式一般有序关系值、效用值、互反偏好关系、模糊偏好关系等[45].Sindhya等人[46]将 MCDM 与 MOEA 相 结 合的 方 法 归 纳 为 两 类:MOEAs 融 入 到 MCDM 和MCDM 融入到 MOEAs.MOEA 融入到 MCDM 是指应 用 MOEAs 求 解 MCDM 方 法 中 的 SOPs,MOEAs可以帮助 MCDM 解决数学规划(Mathe-matical Programming,MP)方法难以处理的难题.MCDM 融入到 MOEAs是指将 DM 的偏好信息以先验或交互的方式结合到 MOEAs中,将算法的搜索集中在偏好区域,可以有效利用算法资源,同时降低计算复杂度,提高算法的求解效率[47].2.3 偏好的设置方法通过将 DM 的 偏 好 信 息 融 入 到 MOEAs框 架中,可以将算法的搜索集中在 Pareto前沿的期望区域.基于以上思想,学者们提出了许多偏好的设置方法,有效地将 DM 的偏好信息融入到 MOEAs框架中.本文根据偏好的设置方 法从占优关系、角 度 关系、权重向量以及偏好集这四个角度,综述融入偏好的 MOEAs.2.3.1 占优关系除偏好信息外,偏好设置方法的不同也在很大程度上影响算法的性能.根据 DM 给定的参考点,通过修改 Pareto占优关系,在一定程度上增强解之间的选择压力,引导算法快速向 DM 的偏好区域搜索.同时,基于占优关系的设置方法实现简单,能容易地融入到其他的 MOEAs中.Molina等人[37]提出了一种基于 DM 给定参考点的g-占优方法.该方法根据参考点划分搜索空间,定义了搜索的优先区域,通过修改 Pareto占优关系,使算法的搜索区域集中在该参考点附近.定义Flagg(x)如下:Flagg(x)=1, gixi,i=1,2,…,m1, gixi,i=1,2,…,m0,烅烄烆其他(7)其中,g为 DM 给定的参考点,x 是目标空间中的任意一点.从以上定义可得,参考点 g 将目标空间划分为Flag=0和 Flag=1两部分,如图1所示[37].利用式(7)可以定义如下支配关系.图 1 g-占优[37]定义10(g-占优). 可行域中任意2个个体x和y要满足x g -占优y 当且仅当满足如下2个条件之一:(1)Flagg(x)>Flagg(y);(2)Flagg(x)=Flagg(y)且有xPareto支配y.g-占优机制能容易地将 DM 的偏好信息融入到 MOEAs中,且在2、3维优化问题上种群能较好地收敛到偏好区域.但该算法存在两个明显的不足:(1)参考点严格控制了优先区域,种群容易丢失多样性,使得算法在局部最优较多的问题上收敛性差;(2)参考点位置对算法的影响很大,当参考点设置在距离 Pareto前沿附近时,算法性能表现得十分不稳定,甚至导致算法不收敛.为解决g-占优机制在高维 MOPs上不收敛和对参考点 位 置 敏 感 等 问 题,Said 等 人[48]提 出 了 一种r-占 优 (Reference Solution Based Dominance,r-dominance)方法,该方法通过在 Pareto非支配解集上建立严格的偏序集,引导算法朝偏好区域进行搜索.与g-占优相比,r-占优受偏好点位置的影响较小,但r-占优只能保证弱 Pareto支配的最优性,特别是在不连续 Pareto前沿的问题中会产生大量的弱 Pareto最优解,即所得解集中存在大量的非支配解,这将严重影响算法的收敛性能.定义11(r-占优). 可行域中任意2个个体x6期 王丽萍等:偏好多目标进化算法研究综述2139且仅当满足如下2个条件之一:(1)xPareto支配y;(2)x与y是Pareto互不支配的,且D(x,y,g)<-δ,δ∈[0,1].其中,D(x,y,g)=Dist(x,g)-Dist(y,g)Distmax-Distmin,Distmax=Maxz∈PDist(z,g),Distmin=Minz∈PDist(z,g),Dist(x,g)=∑mi=1wifi(x)-fi(g)fmaxi-fmin( )i槡2(8)wi∈[0,1],∑mi=1wi=1,g为参考点,δ∈[0,1]为控制偏好区域大小的参数.邱飞岳等人[41]同时考虑 DM 的正、负偏好信息,提出了双极偏好占优机制,并将其融入到 NSGA-II中,形成2p-NSGA-II算法.该算法在非支配解间建立更为严 格 的 占 优 关 系,能 有 效 解 决 在 高 维 目 标空间中因非支配解的比例急剧增长导致算法性能衰减严重的问题.首先定义正、负参考点 P+和 P-,在种群Pop中其他任意个体i到正、负参考点的距离分别为d+i和d-i,如图2所示[41].为了综合考虑个体i到正参考点的贴近度和到负参考点的远离度定义如下贴近度计算公式:Ci=d-id+i+d-i(9)图 2 双极偏好占优[41]定义12(双极占优). 在种群 Pop中任意两个个体x,y∈Pop,DM 给定正负参考点P+、P-,定义x双极占优y,当且仅当满足如下3个条件之一(其中Flag 计算方法同g-占优):(1)Flag+p(x)>Flag-p(y);(2)Flag+p(x)=Flag-p(y)且xPareto支配y;(3)当(1)和(2)都不成立,Cx>Cy.2p-NSGA-II算法提高对种群的选择压力,引导种群快速向靠近正参考点同时远离负参考点的偏好区域收敛.但该算法只考虑了正、负偏好点间的相对距离,算法的求解效果并不理想,且在不同的测试函数上算法的表现差异较大,算法的鲁棒性较差.当DM 设置的正参考点远离 Pareto前沿,负偏好点靠近 Pareto前沿时,该算法容易陷入局部最优而丢失部分偏好最优解.Jaimes等人[49]定义新的偏好占优关系,该偏好占优关系将整个目标空间划分为两个子空间,其中一个子空间的个体使用强化的 Pareto支配关系进行比较,另 一 个 子 空 间 的 个 体 使 用 收 益 标 量 函 数(Achievement Scalarizing Function,ASF)进 行 比较,如图3(a)所示[49].通过设定参考点,利用新的偏好关系 引 导 种 群 向 偏 好 区 域 进 化,如 图 3(b)所示[49],定义解z1占优解z2.随后,将新的偏好占优关系以交互的方式嵌入到优化过程中,在每个交互点处向 DM 提供当前的近似 Pareto解,以便 DM 指导后续搜索的进行.该偏好占优关系其优点在于,不仅可以根据 DM 的需求直观的设置参数,与 DM 进行实时交互,而 且在高 维 上也能获 得 较 优 的 解.ASF函数定义如下:Min Sg(f(x))= maxi=1,2,…,m{wi(fi(x)-gi)}+λ∑pi=1(fi(x)-gi) (10)其中,λ>0 是一个很小的增量系数,i代表第i 个目标,wi为第i个目标上的权重即重要程度,gi为参考点第i维的值.图 3 定义新的偏好占优关系[49]2.3.2 角度关系基于占优关系的偏好设置方法虽实现简单,但其不能灵活控制偏好区域的范围,且在高维目标优化问题上表现较差.而通过角度引入 DM 的偏好信息,根据参考点和角度值确定偏好区域,利用个体间的角度关系引导算法的进化,增强算法的选择压力,同时利用角度控制偏好区域的范围,最终获得 DM的偏好解.Zheng等人[50]提出一种基于个体间角度关 系2149 计  算  机  学  报 2019年 Dominated NSGA-II)算法.该算法通过重新定义个体间支配关系和聚集距离,优先保留距离偏好点近的个体,引导种群朝偏好区域进行搜索.偏好点仅用于搜索种群中离其最近的点,以最近点为基点使用角度控制偏好区域,因此算法的性能不会受偏好点位置的影响.如图4(a)所示[50],DM 首先设置一个偏好点p,然后求得种群中距离偏好的最近点 N,其中α 为 DM 指定的角度范围,θ是 DM 定义的角度下界用于避免个体过度集中.对于种群中的其他个体,采用离偏好最近点 N最近的个体优先保留策略.其中,利用角度信息引入DM 偏好的相关定义如下.图 4 角度偏好关系[50-51]定义13(个体间角度). 种群中任意两个个体x与y 间的角度:Angle(x,y)=F(x)cosF(x)·F(y)F(x)× F(y( ))(11)F(x)=((x1-pi)/(fmax1-fmin1),…,(xm-pm)/(fmaxm-fminm)),F(y)=((y1-pi)/(fmax1-fmin1),…,(ym-pm)/(fmaxm-fminm)) (12)定义14(偏好角度支配). 设种群中任意两个个体x 与y,若个体x 偏好角度支配y 当且仅当满足如下2个条件之一:(1)xPareto支配y;(2)x 与y 是Pareto互不支配的,且Angle(y,N)-Angle(x,N)α,其中,N 为距离偏好最近的点,α为 DM 指定的角度范围.定义15(偏好聚集距离).  非支配排序后,对处于同一层级的个体,优先选择距离偏好点近的个体进入下一代.重新定义个体间的聚集距离如下,其中,B 是一个很大的正数. Crowd(x)= B-Angle(x,p),if Min(Angle(x,y))>θMin(Angle(x,y{))(13)AP-ε-MOEA(AP-ε-multi-objective evolutionaryalgorithm)[51]算法通过参考点及角度值来引入 DM的偏好信息.首先将目标空间划分为偏好区域和非偏好区域两部分,使算法在 DM 的偏好区域进行搜索,有效提高算法搜索效率;随后利用 DM 定义的角度值控制偏好区域的大小,如图4(b)所示[51].进而,在 Pareto最优解中利用 AP-ε 支配策略建立更为严格的偏序关系,从而区分非支配解中的偏好解和非偏好解.该支配策略可以通过角度值有效控制偏好解集的分布范围,并且支持多偏好区域的搜索,同时算法能以较快的速度收敛到 Pareto前沿且搜索到 DM 感兴趣的偏好解.定义16(ε支配策略). 设种群中任意两个个体x 与y,若个体x 和y 满足如下公式,则称xε 支配y,记作xεy.Bi(x)Bi(y), i=1,2,…,mBj(x)<Bj(y),j=1,2,…,烅烄烆m(14)其中,向量B(x)表示个体x 在目标空间中的格子位置,定义为Bi(x)=[(fi(x)-fmini)/εi] (15)fmini为第i个目标的最小值,εi为第i 个目标的偏差强度值.定义17(AP-ε 支配策略).  可行域中任意 2个个体x 和y 要满足x AP-ε 支配y 当且仅当满足如下2个条件之一:(1)个体 x 和y 同属于偏好区域或非偏好区域,且xε 支配y;(2)个体x属于偏好区域,y属于非偏好区域.ADA (Adaptive angle based pruning Algo-rithm)[52]是一种自适应角度修剪算法,该算法根据DM 提供的角度信息修剪 Pareto最优解.ADA 算法首先根据 MOEA 获得 Pareto最优解,然后根据DM 提供的最大角度阈值,运用自适应角度修剪机制对上一阶段所得到的 Pareto最优解进行修剪.自适应修剪机制通过计算每个目标上每对解之间的角度且与最大角度阈值相比较来确定占优关系,然后使用拥挤距离策略维持解集的多样性.其基本原理是通过扩大每个目标上每对解间的角度,增强解之间的选择压力,以消除那些仅在某些目标上占优但在其他目标上显著更差的解.如图5(a)所示[52],根据传统 Pareto支配关系,A、B 两点互不支配.然而在图5(b)中[52],根据自适应角度修剪机制对 A、B 两点分别进行角度扩展,A、B 两点两侧扩展的角度为α 和β,经角度扩展后,A 点明显支配B 点,其中δ为最大角度阈值,α、β分6期 王丽萍等:偏好多目标进化算法研究综述2159角度修剪算法[52]别为修剪的角度值.通过对 A、B 两点进行角度扩展,重新定义了两点间的支配关系,增强了对优秀解集的选择压力,引导解集朝 Pareto前沿上的偏好区域收敛.随后,Sudeng等人[53]对 ADA 算法进行改进,提出了基于特定角度偏差参数的修剪算法 (Anglebased with Specific bias parameter pruning Algorithm,ASA).该算法首先使用反正切函数计算每对解间的角度,然后引入偏差强度参数计算角度阈值,从而在偏好区域内确定偏好解,其中可以根据偏好信息在不同的目标上对偏差强度参数进行适当的调整.将基于特定角度偏差参数的修 剪机制应用于获得Pareto最优解阶段,可以帮助 DM 获得鲁棒性更强的 Pareto最优偏好解.i-ASA-NSGA-II(Interactive Preference-basedMulti-objective Optimization Evolutionary Algorithm)[54]是一种基于 DM 偏好信息的交互式算法.该算法首先根据参考点及扩展角度确定 DM 的偏好区域,然后应用 偏 好 信 息 扩 展 角 度 的 支 配 策 略 来 替 换 原始 NSGA-II中的拥 挤 距 离 策 略.在 种 群 进 化 过 程中,多次与 DM 进行交互,使用 ASA 算法对得到的解集进 行 修 剪,直 到 最 终 获 得 DM 满 意 的 偏 好 最优解.图 6 i-ASA-NSGA-II算法模型[54]i-ASA-NSGA-II算法的模型如图6所示[54],由i-ASA-NSGA-II算法产生初始的近似解集呈现给DM,DM 根据初始解集以及其偏好要求通过给定参考点的形式确定偏好区域,随后算法将划定的偏好区域呈现给 DM,若偏好区域满足 DM 的要求,则通过 ASA 角度修剪机制对偏好区域内的解集进行修剪,将修剪后的偏好解集再次呈现给 DM,直到最终满足 DM 的要求.2.3.3 权重向量参考向量和权重向量在聚合功能上相似,但因其物理意义不同,在搜索过程中对算法有不同的影响.通常,参考向量表示解向量的方向,权重向量表示不同目标的重要性;参考向量在目标空间中,权重向量在权重空间中.参考点是以结构化方式预先定义或由 DM 定义的点[38].参考向量和参考点都能表示目标的期望或重要性,且参考点、参考向量与权重向量之间可以相互转换[39].如 RVEA[26]中的参考向量和 NSGA-III[28]中的参考点都是由均匀分布的权重向量转换而来.Mohammadi等人[55]提出的 R-MEAD(ReferencePoint Based Multi-objective Optimization ThroughDecomposition)算法通过引入分解机制,将参考点的位置信息和 DM 的偏好信息转化为一组携带偏好信息的权重向量,随后这组权重向量将 MOPs分解为若干个单目标优化子问题进行求解.该算法通过计算每个个体与每个参考点的距离,将距离参考点最近的个体所对应的权重向量作为初始权重,在初始权重向量附近重新生成一组新的权重向量,动态调整权重向量使其逐渐靠近 DM 的偏好区域.由于 R-MEAD 从 MOEA/D 中继承了 单格子点设计方 法 进 行 初 始 化 权 重,使 得 种 群 的 大 小 受到目标 维 度 的 约 束.Mohammadi等 人[56]提 出 了R-MEAD2以解决 R-MEAD 在权重初始化时存在的问题.R-MEAD2采用均匀随机数生成方法产生权重向量 代替 R-MEAD 中的单 格子点 设 计 方 法,并且在权重生成的过程中不断重构调整权重向量,这不仅消除了目标维度对种群大小的约束,而且能够在高维目标空间中产生均匀分布的权重向量.图7[56]所示为算法在进化过程中权重向量的重构示意图.图7[56]左侧的黑色方块表示在第t次迭代前的解,灰色方块表示经过算法迭代后的解,箭头表示由权重向量和每个解所决定的更新方向,r 为DM 设定的偏好区域.其中,与参考点最接近的解所对应的权重向量被视为最优权重 Wb.一旦确定最优权重,则使用均匀随机数生成法生成一组新的围绕最优权重的权重向量,如图7[56]中心处的方框所示,权2169 计  算  机  学  报 2019年重Wb生成.随后,将这些权重分配回上次迭代中所获得的解.最后,使用新生成的权重进行算法优化.如图7[56]右侧所示,由五角星标记的新解在参考点的方向上逐渐收敛于偏好区域.图 7 权重向量重构[56]Li等人[57]在 MOEA/D-STM(Stable Matching-Based Selection in Evolutionary MultiobjectiveOptimization)算法的基础上,提出了应用权重向量引入 DM 偏好信息的r-MOEA/D-STM 算法.该算法首先根据 DM 提供的参考点,使用单格子点设计方法生成大量的权重向量,然后选择距离参考点最近的若干权重向量作为 DM 的偏好区域.Zheng等人[58]提出一种基于权重迭代的 偏 好多目标分解算法 MOEA/D-PRE(Preference-basedAnd Decomposition-based MOEA),该算法首先利用权重迭代方法产生一组均匀分布的权重向量,随后利用该权重向量对偏好区域进行映射,消除参考点位置对算 法 性 能 的 影 响,如 图 8 所 示[58].MOEA/D-PRE算法还提出了一种新型的偏好区域模型,该模型可以根据 DM 的偏好信息动态调整偏好区域的大小.此外,在高维问题上,MOEA/D-PRE 算法也具有优越的性能.图 8 MOEA/D-PRE算法[58]Hu等人[59]提 出 的 基 于 权 重 向 量 选 择 机 制 的P-NSGA-II(A Preferencebased Multi-objectiveEvolutionary Algorithm using Preference SelectionRadius)算法,有效缓解了基于 Pareto占优关系的偏好算法随目标维度增加算法整体性能急剧下降的问题.该选择机制分为两部分,首先根据权重向量及偏好半径构建偏好区域,将整个目标空间划分为偏好区域和非偏好区域两部分;其次通过 Pareto支配关系在偏好区域中选择最优解,若所获得偏好解的数量未达到 DM 的要求,则依次在非偏好区域内选择与参考向量距离最小的解直到满足 DM 的要求,如图9(a)所示[59].Zhang等人[60]提出一种基于权重向量的偏 好MOEA,该算法首先将均匀分布的权重向量映射到偏好点附近,随后根据映射后的权重向量搜索偏好点附近的 Pareto最优解.然而,映射后的权重向量并不能 搜 索 到 偏 好 点 附 近 的 Pareto 最 优 解.文中证明了解的搜索方向不是映射后权重向量 w′i=(w′i1,…,w′im)的 方 向,而 是 沿 着λi= (1/w′i1,…,1/w′im)方向进行搜索.为能有效搜索到偏好点附近的 Pareto最优解,需要将映射到偏好点附近的权重向量w′i=(w′i1,…,w′im)修改为λi=(λi1,…,λim),其中λ′i=1/w′i,λi=λ′i/∑mi=1λ′i,如图9(b)所示[60]是由权重向量w 的方向搜索到的偏好解.图 9 权重向量调整[59-60]RVEA(A Reference Vector Guided EvolutionaryAlgorithm for Many-Objective Optimization)[26]是一种由参考向量引导的偏好 MOEA.该算法产生若干个均匀分布的权重向量,将目标空间划分为与权重向量数量相等的若干个子空间,通过精英选择策略和角度惩罚距 离 APD(Angle-Penalized Distance)机制在各个子空间中进行搜索,使得子种群中的最优解能够快速向 Pareto前沿收敛.同时结合基于偏好的参考向量生成方法,根据 DM 的要求确定中心参考向量vc和偏好半径r,通过式(16)的变换生成若干子空间中的参考向量.v′i=r·vi+(1-r)·vcr·vi+(1-r)·vc(16)其中,vc是单位向量,半径r∈(0,1),vi是均匀分布的参考向量,v′i是由vi转化得到的子空间中的参考向量,DM 的偏好区域由vc和r 确定.通过参考向量6期 王丽萍等:偏好多目标进化算法研究综述2179

[返回]
上一篇:一种带自适应学习率的综合随机梯度下降
下一篇:敏捷开发环境中的回归测试优化技术