MOEA/D Qingfu Zhang and Hui Li阅读笔记

摘要
分解是传统多目标优化的基本策略,然而它还没有广泛应用于多目标进化优化算法中。这篇文献提出了基于分解的多目标进化算法。It decomposes a multiobjective optimization problem into a number of scalar optimization subproblems(标量优化子问题 什么鬼?) and optimizes them  simultaneously.  
[[答疑]:scalarizing就是将向量变为标量,意思就是将多目标问题分解为多个子问题(子问题可以是多目标或单目标),每个子问题的最优解就是多目标优化问题的Pareto optimal solution]
每个子问题只通过由它的相邻子问题(several neighboring subproblems)得到的信息来进行优化,从而大大降低了它的计算复杂度相较于MOGLS和NSGA-II.实验结果证明基于一个简单分解方法的MOEA/D算法在多目标0-1背包问题和连续多目标优化问题的表现胜过或相近于MOGLS和NSGA-II.It has been shown that MOEA/D using objective normalization(目标归一化 如何实现 can deal with disparately-scaled objectives(规模不同的目标 具体实例, and MOEA/D with an advanced decomposition method can generate a set of very evenly distributed solutions(均匀分布的解) for 3-objective test instances. MOEA/D针对小规模(small population)的能力及其敏感性(sensitivity)也在论文中得到了研究。
一、引言
多目标优化问题(MOP)的目标函数如下:
maximize F(x)=(f1(x),f2(x),…,fm(x))T (1)
s.t. x∈Ω
-x是决策变量,
-Ω是决策空间(decision space),
-F:Ω->Rm 由m个实值目标函数组成,Rm 是目标空间(objective space)。
-可获取的目标集合定义为集合{F(x)|x∈Ω},
如果x是n维向量,所有的目标是连续的,则Ω可表示如下:
Ω = {x∈Rn |hj(x)<=0,j =1,}
hj(x)是连续函数,则MOP为continuous MOP。
通常多目标优化问题的目标之间是相互对立的(contradict),在决策空间中没有一个点能同时最优化所有目标。所以我们要平衡它们,而目标之间最好的权衡(tradeoffs)就是Pareto optimality。
一个重要的概念:Let u,vRm (u,v是目标向量 ) ,u dominate v当且仅当 ui>=vi for i in {1,…,m}且至少有一个j in {1,…,m}使得uj>vj.(换句话说u和v(m维向量)都是得到的优化结果,u dominate v的意思就是向量u的每一个分量都大于等于v的每一个分量且不全部等于,即至少u有一个分量是大于v的对应分量—u在各个目标上的表现都大于等于但不全等于v)注:u dominate v:u>=v(max目标函数),u<=v(min目标函数
Pareto optimal :在x∈Ω中没有一个决策变量x所得到的结果F(x) dominate 决策变量x*的得到的结果F(x*)时(F(x*)dominate除了PF上的所有点,PF上的所有点谁也不dominate谁),x*称为Pareto optimal point。F(X*)称为Pareto optimal (objective) vector.
换句话说,对于一个Pareto optima**l vector,如果使一个目标得到提升则至少一个其他目标的表现就会变差,即不可能在不使其他目标受损的情况下再改善某些目标。Pareto optima**l point的集合称为Pareto set(PS)Pareto optimal (objective) vector的集合称为Pareto front(PF)

MOEA/D Qingfu Zhang and  Hui Li阅读笔记

MOEA/D Qingfu Zhang and  Hui Li阅读笔记
Example of Pareto frontier, given that lower values are preferred to higher values. Point C is not on the Pareto Frontier because it is dominated by both point A and point B.—参考自维基百科:https://zh.wikipedia.org/wiki/帕累托最优
如上图有两个目标f1和f2,A,B都是Pareto optimal (objective) vector,其对应的点x*称为Pareto optimal point

多目标优化在实际生活中有很多应用,一个PF的近似对于决策者来选择一个最终偏好的解非常有用。大多数多目标问题可能有很多甚至接近于无限个Pareto optimal vector,所以想要获得完整的PF是很花费时间的,甚至是不可能的。另一方面,由于信息爆炸,决策者对处理过多的Pareto optimal vector也没有兴趣。因此,很多的多目标优化算法都是寻找可控数量的且在PF上均匀分布的Pareto optimal vector,这样就能很好的表示完整的PF。一些研究者在努力使用数学模型去近似PF。
众所周知,在温和条件下(什么是温和条件?),多目标问题的一个Pareto optimal solution可能是目标是fi的集合的标量优化问题(scala optimization problem)的一个最优解(It‘s wellknown that a Pareto optimal solution to a MOP ,under mild conditions,could be an optimal solution of a scalar optimization in which the objective is an aggregation of fi’s)。因此PF的近似可以被分解为一系列标量优化目标子问题(scala objective optimozation subproblem)
这是很多近似PF的数学编程方法背后的基本idea。一些构建聚合函数(constructing aggression functions)的方法(即分解方法)可以在文献[1]中找到,其中最流行的方法就是权重和法(weight sum approch)和切比雪夫方法。最近,the boundary intersection methods吸引了很多人的注意力[9]-[11].
[2]-[4][12]-[19]这些致力于多目标进化算法(MOEAs)的文献中没有涉及到分解方法,这些算法都把一个MOP看作一个整体。他们没有把每一个个体解与任何特定的标量优化问题联系起来。在一个标量优化目标问题中,所有解可以通过目标函数值来比较,而且一个标量目标进化算法的任务通常是找到一个单一的最优解。在多目标问题中,domination并不能把目标空间的解很好地排序,而且MOEAs致力于产生一系列尽可能多样性的Pareto optimal solutions以更好地近似表达完整的PF。因此,传统的原本就是为标量优化(scalar optimization)设计的选择算子方法不能直接应用于nondecompsiton MOEAs 中。按理来说,假如有一种将分配给个体解一个relative fitness value来反映选择能力的适应度分配方法(fitness assignment scheme)的话,那么scalar optimization EAs能够被很容易地被扩展来解决MOPs,尽管其他的techniques例如mating restriction,diversity maintaining,some properities of MOPs仍然需要应用于提高这些扩展算法的性能。正是由于这个原因,适应度分配(fitness assignment)是现在MOEA研究中的一个重要的issue。最流行的适应度分配策略包括altenating objectives-based fitness assignment
例如VEGA,还有domination-based适应度分配例如PAES,SPEA-II,NSGA-II.
decomposition的想法在解决MOPs的几个元启发式算法中有一定范围的应用。如TPLS、MOGLS等。
在这篇文献中,作者提出了MOEA/D。MOEA/D明确地把MOP分解为N个标量优化子问题(scalar optimization subproblems)。它同时(simutaneously)求解这些子问题 by evolving a population of solutions。在每一次迭代中,population由到目前为止发现的每一个子问题的最优解组成。这些subproblems中的neighborhood relations是基于它们的aggregation coefficient vector之间的distance定义的。两个neiborhood subproblems的the optimal solutions应该是非常相似的.每一个MOEA/D的subproblem(scalar aggregation function)使用从它的neighborhood subproblems中得到的信息来进行优化。MOEA/D有如下几个特征:
- MOEA/D提供了一种简单且有效的把decompositon引入到多目标进化计算的方法。decomposition是经常在数学规划领域发展的方法,在MOEA/D框架中它可以轻松地与EAs结合来解决MOPs.
  • 由于MOEA/D优化N个标量子问题而不是直接将MOP当作一个整体来优化,相比于不是基于分解的MOEAs,一些问题比如适应度分配(fitness assignment?)和多样性保持(diversity maintainance?)的解决难度在MOEA/D框架中将会大大降低。

  • 相比于NSGA-II和MOGLS,MOEA/D在每一次迭代过程中拥有较低的计算复杂度。总的来说,在使用0-1多目标背包测试样例进行测试时,当两种算法都使用相同的分解方法时,从解的质量上来看,MOEA/D比MOGLS表现更好。使用切比雪夫分解方法的MOEA/D与NSGA-II解决一系列连续MOP测试用例的效果相近。使用更先进的分解方法的MOEA/D在解决3目标连续测试用例的表现比NSGA-II更好。当MOEA/D使用小种群时,能够产生少量分布非常均匀的解。

  • Objective normalization techniques(?)能被应用于MOEA/D中来处理disparately scaled objectives。

  • 在MOEA/D中使用标量优化方法(scalar optimization methods)是非常自然的,因为每个解都与一个标量优化问题密切相关。与之相反,不基于分解的MOEAs的一大缺点就是没有一个简单的方法能构充分利用标量优化方法(scalar optimization methods?)。

二、多目标优化的分解方法
有很多方法将近似PF问题转换为一系列标量优化子问题(scalar optimization subproblems)。接下来作者介绍了三种用于他们实验中的方法,分别是权重求和法切比雪夫方法边界交叉聚合方法(Boundary Intersection)
1.权重求和法(Weight Sum Approch)  这种方法适用于不同目标的凸组合。(It works for convex PF.转化后的标量优化问题:
MOEA/D Qingfu Zhang and  Hui Li阅读笔记
它的最优解就是(1)式的一个Pareto optimal solution。为了产生一系列不同的Pareto optimal vector我们要使用不同的权重向量。这种方法只适用于convex PF。为了克服这个缺点,有人作出努力把其他技术嵌入其中,例如ε-constraint[1].若MOP(1)是min,上图也改为min

2.切比雪夫方法(Tchebycheff Approach)
z*是参考MOEA/D Qingfu Zhang and  Hui Li阅读笔记点。对于每一个Pareto optimal point x*,总存在一个权重向量λ使得x*是上式的最优点,而每一个上式的最优点都是(1)式的Pareto optimal solution。因此我们可以获得不同的Pareto optimal vector通过改变权重向量λ。这种方法的一个缺点是它的aggregation function处理连续MOPs时不够smooth。然而这种方法仍然可以用在本文提出的EA框架中,因为因为我们的算法并不需要计算aggregation function的微分。注:若MOP(1)是min,则z*i =min{fi(x)|x∈Ω},切比雪夫不等式的形式不会变。
3.边界交叉聚合方法(Boundary Intersection)

三、MOEA/D的框架
A.通用框架(General Framework)
拿应用切比雪夫方法的MOEA/D为例,MOP的聚合函数:min gte (x|λ,z*)=max1<=i<=mi|fi(x)}-z*i|}

MOP被分解为N个标量子问题,则第j个标量子问题的目标函数表示如下:min gte (x|λj,z*)=max1<=i<=mji |fi(x)}-z*i|}
MOEA/D在一次运行过程中同时优化这N个目标函数.
gte 是关于λ的连续函数,两个邻居(λjλi 与彼此离得很近)的解是非常相似的。因此,任何带有与λi相近的权重向量的gte的信息对于优化gte (x|λi,z*)都是有用的,这是MOEA/D的一个主要思想。
在{λ1λN}中一系列离λi最近的权重向量称为λi的neighborhood
MOEA/D Qingfu Zhang and  Hui Li阅读笔记
第i个subproblem的neighbohood由所有带有λi的邻居权重向量的子问题组成。The population 由迭代到当前的所有子问题的最优解组成。一个子问题只利用当前它的所有邻居子问题的解来进行优化。
在每一次迭代过程t中,使用切比雪夫方法的MOEA/D包含:
- 由N个点x1,x2,…xN∈Ω组成的population,xi是第i个子问题的当前解;
  • FV1,FV2,…FVN ,FVi是xi的F-value;

  • z=(z1,z2,…,zmT,zi是到目前为止找到的目标fi的最好值。

  • 一个外部种群(EP), 它用来储存搜索过程中的不被支配的解(non-dominated),即Parato optimal points(solutions)。

算法工作流程如下:
INPUT:
- MOP
  • 停止迭代准则

  • N:MOEA/D分解的子问题个数

  • N个权重向量:λ1λN

  • T:每个权重向量的邻居权重向量个数

OUTPUT:EP
流程图:截取自:https://xijunlee.github.io/2017/08/29/多目标优化方法之MOEA-D/
MOEA/D Qingfu Zhang and  Hui Li阅读笔记
B.DISCUSSIONS
1.N是有限的,决策者只需要有限数量均匀分布的Pareto solutions。
2.分解方法和权重向量的选择影响解的多样性和均匀分布。
3.邻向量个数T过小,算法不能有效的探索到搜索空间的新区域;T过大,xk和xl对子问题的性能变差,它们的子代y‘也会变差,同时还会增加计算复杂度。
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。

评论