工具之家 > 现代电子技术 > 偏好MOEAD算法的研究与实现

偏好MOEAD算法的研究与实现

发布时间:2019-07-06 02:15:00 文章来源:工具之家    

 推荐工具:金融理财app工具实用工具

万旭光+毛樟根

摘 要 在科研和工程实践zhong存在着很duoxu要tong时youhuadeliangge或duo个相互冲突de多mubiaoyouhua问ti多shu情kuang下人menshiyong多mu标you化shiweiliaoxun求某yi特dingfang向deParetojiedanchuan统deyou化方fa只能得chufen散de全bujieji不利于辅助juece为此tichuyi种带pianhaode多mu标youhuasuanfa即pianhaoMOEA/Dsuanfa该suan法dehe心思想是jiang一个多目标youhua问tifenjie成多个dan目标优化问题并同时优化在zi问题tongguo相邻子问题信xi优化de过程zhong加ru使yong者pian好最zhong得到方向明确的Pareto解ji经仿真验证该算法具you突出的求解性能便于辅助决策qieyou较高的有xiao性和可拓zhan性

关键词 多目标优化 MOEA/D算法; Pareto解; 信息优化; 辅助决策; quanxiang量

中tu分类hao: TN911.1?34 文献标识码: A 文章编号: 14?373X(2181?0133?06

Abstract: The multi?objective problem that two or more objectives conflicted with each other should be optimized exists in scientific research and engineering practice. The multi?objective optimization is usually used to get the Pareto solution in a certain direction but the traditional optimization method can only get the dispersive whole solution set and isn′t conducive to the assistant decision. A preference?based multi?objective optimization algorithm (preference MOEA/D algorithm is proposed. The core thought of this algorithm is to decompose a multi?objective optimization problem into several single?objective optimization problems and optimize the single?objective optimization problems. The user preference is added into the sub problem in the information optimization process of the adjacent sub problem to get the Pareto solution set with explicit direction. The simulation results show that the proposed algorithm has outstanding solving performance, high efficiency and strong expansibility, and is convenient for assistant decision?making.

Keywords: multi?objective optimization; MOEA/D algorithm; Pareto solution; information optimization; assistant decision?making; weight vector

0 引 言

在科xue技术、经济管理和工程she计等领域的实践中,常会遇到要求多个目标在zhi定方向shang或限定qu域内进行最优化处理的问题,也就是多目标优化问题(Multi?objective Optimization Problems,MOPs)[1]。

在单目标优化中最优解通常是惟一确定的,而多目标优化问题suo研究的多个目标经常是相互矛盾,相互冲突的,因此没youdan一的全局最优解,而是一系列互不支配的解,称为Pareto解或fei支配解ji通常jun匀分bu在解空jian内[2]。

而在实际问题的应用中,决策者往往只对目标空间的某一qu域感兴趣,因此,这就需要在这一特定区域能够得到比较稠密的Pareto解。ben文优化了MOEA/D算法,在该算法的jichu上加入pian好关系模型,改善了传统算法解集jun匀分布的缺点,成功使解集向使用者偏好方向聚集,所得解集对解决问题更有针对性,辅助决策的意义更强,效guo更好。

1 偏好MOEA/D算法的描述

1.1 算法的提出

目qian有很多求解多目标优化的算法,如强duPareto遗传算法(SPEA,SPEA?)、Pareto存档进化算法(PAES)[3]、非劣排序遗传算法(NSGA,NSGA?Ⅱ)[4]等,这些算法的核心目的是在尽量少的jisuan量的情况下,寻求较均匀的Pareto近似解。

本文要改进的是最近提出的MOEA/D算法,运用在第一象限均匀地分配权向量的方法将多目标优化问题分解成一系列单目标优化问题,mei个子问题又有其邻域子问题,为了构造一个xin解,每个子问题需要组合其邻域子问题的当前解的信息,同时每个xinchansheng的解不仅要更新自身的解还要更新其邻域子问题的解[5]。xuan择该方法作為优化对象的原因是:该算法原理简单,yi于与具体问题结合并且容易与本文提出的偏好模型相结合,是一种简单youxiao的进化算法。

目前对MOEA/D算法的改进和优化多集中于算法本身的功能上,很少有将偏好考虑其中的。算法本身在进行优化时,是对全目标空间进行寻优的,这样最zhong得到的Pareto解也是均匀分布的。若在算法寻优的过程中加入使用者的个人偏好shi寻优方向向偏好方向靠拢并最终保持一致,便可在使用者所需要的区域内产生特定需求的Pareto解。endprint

采用先验方falai处理偏好问题,在算法开始之前,you用户提供一个目标空间的偏好区域,该偏好区域首先用权向量[λi]daibiao用户偏好的方向,然后用偏好比lv范围来表示偏好区域的大小。在算法的运行过程中,通过权向量不duandiaozheng达到Pareto解集不断收敛到偏好区域的目的。

1.2 算法的shu学描述

MOEA/D的shu学描述为

[(MOP)minF(x)=f1(x),f2(x),fq(x)s.t. x∈Ω Ω?Rn] (1)

式中:[Ω]是bian量空间;[F(x)]为向量值函数,[F(x)∈Rq;]min表示向量极小化,即向量目标[F(x)=][f1(x), f2(x),…, fq(x)]zhong的各个子目biaohan数都尽可能极小化。

大多数情况下,多目标优化问题(MOP)的最优Pareto解位于目标空间边界。图1gei出了一个二目标最小化目标函数,[xa]和[xb]点分别为问题的两个Pareto最优解,当从[xa]dianyi动到[xb]点时,在函数[f2]上的性能变优,在[f1]上的性能却变差。[xb]点Pareto支配[xc]点。

文献[6]提出fuza的局部偏好关系模型,该模型中,需要决策者给出起始点、终zhidian、无差别阈值向量、否决阈值向量,规避了仅为每个单目标分配0或1的某个权重,即全部否定或全部肯定的决策辅助情况。

本算法的提出受到了局部偏好关系模型的启发,但是本算法只需要用户给出偏好方向上的权向量和偏好比率范围(如图2所示),简化了偏好关系模型的复杂度。偏好方向權向量选定yi0点为向量起始点,终止点选取起始点后的任何点,这里采用最大值作为终止点,限定偏好权向量只有一个,偏好比率范围用yi限定偏好区间,假设Pareto前沿为1那么偏好区间以偏好方向为基点zhanPareto前沿长度的比率作为偏好范围比率(即偏好比率范围为0~1以内的任意值),偏好比率越大则代表偏好范围越大。

1.3 算法框架

目前有许多方法可以将一个多目标优化问题分解为一系列单目标优化问题,本文所采用的分解方法是Tchebycheff分解法[7]。

Tchebycheff分解方法:将多目标问题分解hou其中一个单目标优化问题可以表示成如下形式:

[Minimize gtexλz*=Max1≤i≤mλifi(x)-z*is.t. x∈Ω] (2)

式中:[λ1,λ2,…,λN]是一套均匀分布的权重向量,其中[λi≥0i=1,2,…,m,]并且[i=1mλi=1]。这里[z*=(z*1,z*2,…,z*m)T]是一个参考点,也就是说,对每一个[i=1,2,…,m,]存在[z*=minfi(x)x∈Ω3]对式(1)中每一个Paretozhan优解[x*]存在一个权值向量[λ]使得[x*]是式(2)的最优解;而且每一个式(2)的最优jiedu是式(1)的Pareto占优解,所以能够通过解一系列由Tchebycheff分解方法定义的butong权向量的单目标优化问题来获得不同的Pareto占优解。

以下是基于偏好的MOEA/D算法的主要流程:

输入:

1.多目标优化问题(MOP)

2.终止条件

3.N:MOEA/D分解过程中所考虑子问题的数目

4.均匀分布的N个权重向量:[λ1,λ2,…,λN]

5.T:权重向量的个数

输出:EP(外部种qun)

Step1初始化:

1.1 令Pareto解集 EP=[?;]

1.2 计算任何两个向量间的欧氏距离,然后对每个权重用与其距离最近的T个权重组成其相邻集合;即对每一个i=1,2,…N,有[B(i)={i1,i2,…,iT}],其中[λi1,λi2,…,λiT]就是[λi]的T个最近的权重向量;

1.3 随ji或根ju集体问题产生一个初始化种群[x1,x2,…,xN,]并计算[FVi=F(xi)];

1.4 根据具体问题设zhi初始化,令[z=(z1,z2,…,zm)T]。

Step2 更新:对每个i=1,2,…,N,做如下操作:

2.1 繁殖:从[B(i)]中随机选择两个序号[k,l,]然后对[xk]和[xl]进行遗传操作,产生一个新的解[y;]

2.2 更新改进:根据具体问题对接进行调整/修补,由[y]变成[y;]

2.3 更新[z:]对每一个j=1,2,…,m,如果[zj

2.4 更新相邻集合中的解:对每一个指数[j∈B(i)]的标号,如果有[gteyλj,z≤gtexjλj,z,]则令[xj=y]并且[FVj=F(y)];

2.5 EP的更新:从EP中删除bei[F(y)]支配的所有向量,如果在EP中没有向量支配[F(y)]那么则将[F(y)]加入EP中;

2.6 偏好权向量的调整:根据偏好信息对解进行调整,在偏好区域内在解集最稀疏的地方增加一个权向量,在偏好区域外权向量最密集的地方删除一个权向量。

Step3终止条件:如果满足终止条件那么就停止并输出EP,若不满足则转向第2步。

从上述算法框架中,可以将其分为五大主要模块:输入、初始化、更新、判断、输出,本文的算法将偏好模型加在更新部分,通过不断调整权向量使解集不断收敛于偏好区域。

MOEA/D对多目标中每个分解的子问题建立对应的评价机制,能大大减少计算复杂度,加快群体的收敛su度。同时在MOEA/D算法中融入偏好模型可以将用户的偏好信息加入算法的运行过程,经过每一代权向量的调整和筛选,使得最终jieguo趋近在用户的偏好区域附近。

2 算法仿真jishi验结果分析

本文的算法代码是在VC++ 6.0的平台上运行,运行结束后将得出数据baocun,再运用Matlab作为界面展示,结果形象并易于观察变化。

2.1 ce试函数的选取

本文的主要工作是为了体现优化后的偏好MOEA/D算法的解集聚拢效果,只与传统MOEA/D算法的解集作比较,不与其他多目标优化算法作对比分析。所以测试对象选取了3个两目标函数和2个可展为高维目标的函数[8]。这些测试函数被广泛引用,能较全面地体现某多目标算法的性能。SCH是比较简单的两目标优化问题,其最优Pareto前沿是非lian续的,常用于测试算法在非连续区域的稳定性;ZDT1和ZDT2问题是Zitzler等学者提出的较为复杂的两目标优化问题。ta们的Pareto前沿分别是凸的和非凸的,决策变量维数均为30;DTLZ2heDTLZ3问题由Deb等学者提出,可以扩展为不同目标的多目标优化问题,为了衡量算法的扩展性能,测试了高达8目标DTLZ2和DTLZ3问题。关于这些测试函数的Pareto最优前沿可以参看Coello等学者建立的相关方面网站及文献[9]。这些测试函数的数学定义如下:

1) SCH函数,变量数:1,取值范围:[-5,10],目标函数:

[f1(x)=-x,x≤1-2+x,14f2(x)=(x-5)2]

2) ZDT1函数,变量数:30,取值范围:[0,1],目标函数:

[f1(x)=x1,f2(x)=g(x)1-x1g(x)g(x)=1+9i=2nxin-1]

3) ZDT2函數,变量数:30,取值范围:[0,1],目标函数:

[f1(x)=x1f2(x)=g(x)1-x1g(x)2g(x)=1+9i=2nxin-1]

4) DTLZ2函数,变量数:30,取值范围:[0,1],目标函数:

[f1=1+gxkcosx1π2cosx2π2…cosxk-2π2sinxk-1π2]

[?]

[fk-1(x)=1+gxkcosx1π2sinx2π2fk(x)=1+gxksinx1π2g(xk)=xi∈xkxi-0.52]

5) DTLZ3函数,变量数:[k+x-1,]取值范围:[0,1],目标函数:

[f1=1+gxkcosx1π2cosx2π2…cosxk-2π2cosxk-1π2f2=1+gxkcosx1π2cosx2π2…cosxk-2π2sinxk-1π2 ?]

[fM-1(x)=1+gxkcosx1π2sinx2π2fM(x)=1+gxksinx1π2g(xk)=100*xk+xi∈xkxi-0.52-cos20πxi-0.5]

2.2 实验设置

本文在实验中首先测试了两目标函数问题SCH和ZDT函数系列,然后对目标维数较高的DTLZ2和DTLZ3问题[10]进行相关测试,均设计了不同的偏好方向以及偏好范围参数,具体参数设置见表1。

2.3 实验结果分析

上述函数的测试结果图如图3~图5所示。每个函数给出四个测试图,归类为一组。每组的第一张图为测试在传统MOEA/D算法无偏好情况下被测函数所获得的全部Pareto解集;第二张图给出加上偏好后的解集对比试验结果;第三张图针对偏好,选择当偏好方向相同而偏好区域不同时解集的对比结果;第四张图为偏好区域相同但偏好方向不同时的解集对比结果。

每张图中蓝色的点是偏好MOEA/D方法得到的在偏好区域内的解集,hei色的线代表标准Pareto前沿。

congtu中可以清楚地看出,随设定偏好范围的增大则偏好解集范围增大,改变偏好方向则偏好解集也随之改变方向,从上述的两目标函数中可以发现,无论函数的xingzhuang如何或是否连续,偏好模型在MOEA/D算法中能够有效地使解集收敛并约束在偏好区域以内均匀分布。同时,加入偏好之后函数的解集明显收敛到了偏好区域范围内,并且在Pareto前沿上分布较均匀。随着在测试中改变偏好方向,解集明显以新的偏好方向为中心分布,在测试中改变偏好大小,偏好解集的范围也随之改变。证明了该算法能够根据使用者的决策预期引导算法朝着预先设定的偏好方向进行优化,并能调整偏好范围的大小。

为了测试函数的可扩展性,ji续测试了8目标的DTLZ2和DTLZ3问题[11],测试结果如图6tu7所示。

针对上述2个三维函数,通过改变函数的偏好方向和偏好范围,可以看出函数可以均匀分布于偏好范围内并随着偏好范围大小做出相应改bian验证了算法的可扩展性。

从以上5个测试函数中可以看出,偏好MOEA/D算法能有效地将用户的偏好信息加入算法的进化过程中,根据用户的偏好方向和偏好范围求出相应方向和范围的解集,获得更优的辅助使用者决策的效果。

3 结 论

本文优化了传统的MOEA/D算法,在原有的基础上结合偏好关系模型,产生偏好MOEA/D算法,并介绍了其算法框架,利用具有代表性的两目标函数SCH及ZDT1,ZDT2验证了其有效性,进一步使用八维函数DTLZ2和DTLZ3进行测试以验证其可扩展性。实验结果表明,新算法能够根据用户的偏好区域范围搜索相应的解集,并且具有较快的收敛速度和较好的均匀性保持nengli,辅助决策的意义更强,效果更好。

参考文献

[1] PARETO V. Cours d′economies olitique [M]. Lausanne: Rouge, 1896.

[2] ZHANG Q, LI H. MOEA/D: a multiobjective evolutionary algorithm based on decomposition [J]. IEEE transactions on evolutionary computation, 2007, 6(11): 712?731.

[3] BRANKE J, DEB K, MIETTINEN K, et al. Multiobjective optimization: interactive and evolutionary approaches [M]. New York: Springer, 2008: 405?433.

[4] MOLINA J, SANTANA L V, HERNANDEZ?DIAZ A G, et al. g?dominance: reference point based dominance for multiobjective metaheuristics [J]. European journal of operational research, 2009, 197(2): 685?692.

[5] KIM J, HAN J, KIM Y, et al. Preference?based solution selection algorithm for evolutionary multiobjective optimization [J]. IEEE transactions on evolutionary computation, 2012, 16(1): 20?34.

[6] JASZKIEWICZ A, SLOWINSKI R. The light beam search approach?an overview of methodology and applications [J]. European journal of operation research, 1999, 113(2): 300?314.

[7] 肖晓伟,肖迪lin锦国,等.多目标优化问题的研究概述[J].计算机应用研究,2011,28(3):805?808.

XIAO Xiaowei, XIAO Di, LIN Jinguo, et al. Research overview of multi target application research [J]. Computer optimization problems, 2011, 28(3): 805?827.

[8] 丁大维.基于MOEA/Ddeyou化技术及其在天线优化设计中的应用[D].合肥:中国科学技术大学,2015.

DING Dawei. MOEA/D based optimization technology and antenna optimization design application [D]. Hefei: University of Science & Technology China, 2015.

[9] 张冬梅,龚小胜,戴光明,等.求解复杂多目标优化问题MOEA/D?GEP算法[J].华中科技大学xuebao(自然科学版),2012,40(4):33?36.

ZHANG Dongmei, GONG Victory, DAI Guangming. Solving complex multi?objective optimization problem MOEA/D?GEP algorithm [J]. Journal of Huazhong University of Science and Technology (natural science edition), 2014, 40(4): 33?36.

[10] 神显豪,李军,张祁.基于改进MOEA/D算法的WSN覆盖优化方法[J].计算机应用研究,2016,33(4):1203?1206.

SHEN Xianhao, LI Jun, ZHANG Qi. WSN overlay optimization method based on improved MOEA/D algorithm [J]. Computer application research, 2016, 33(4): 1203?1206.

[11] 胡旺,Gary G.YEN,张鑫.基于Pareto熵的多目标粒子群优化算法[J].软件学报,2014,25(5):1025?1050.

HU Wang, YEN G G, ZHANG Xin. Multi objective particle swarm optimization algorithm based on Pareto entropy [J]. Journal of software, 2014, 25(5): 1025?1050.endprint

现代电子技术 2018年1期

现代电子技术的其tawen章 基于联合迭代检测译码的多中继RA编码协作系统 差分GPS实时数据解调算法研究与实现 基于匹配追踪算法阈值改进的MIMO?OFDM信dao估计研究 卫星天线过顶盲区时机分析 智能电网双层无线接入架构及信道仿真研究 一种EHOPPPA算法改进LTE切换性能的研究
转载请注明来源。原文地址:https://www.5420.com.cn/view/2019/0706/18449/
 与本篇相关的热门内容: