第5章
基于分解的多目标
分布估计算法
5.概述
1

.................... 

在现实生活中,很多的问题都具有多个优化目标。一般地,这些目标是相互冲突的。
也就是说,试图提高一个目标会导致其他目标质量的下降。对于多目标优化问题,我们希
望获得尽可能多的非支配的解,以供决策者根据实际情况选择最终的方案。演化算法是
基于种群的元启发式算法,这一特性使得演化算法适用于解决多目标优化问题。近年来, 
演化多目标算法得到了广泛重视,研究人员设计了很多适用于多目标问题的演化算法,这
些算法已经解决很多实际问题[45-47]。本章主要介绍一种改进的多目标分布估计算法,称
为s-MEDA/D(scaleAdaptiveDecompositionbasedMulti-objectiveEstimationof 
DistributionAlgorithm,基于问题规模自适应分解的多目标分布估计算法)。MEDA/D 
在经典多目标演化算法———基于分解的多目标演化算法(MOEA/D)的基础上,利用概率
向量对每个分解后的子问题建模。本章将利用遗传算法范式的MOEA/D改进为利用分
布估计范式的MEDA/D。在此基础上,本章基于概率向量提出了规模自适应的生成算
子。最后,本章通过在多目标0-1背包问题上的实验说明算法的有效性。

本章的结构安排如下:5.首先介绍权重分解方法和切比雪夫分

2节介绍MOEA/D, 
5.解方法,随后完整地描述MOEA/D框架和MEDA/D;3节详细介绍规模自适应生成算
子,并证明该算子保持多样性的能力;4节介绍多目标的01背包问题和sMEDA/D在
9个实例上的实验结果;5.5.-

5节总结本章内容。

5.基于分解的多目标演化算法框架
2

.................................................. 

2.分解方法
5.1 
1. 
权重分解方法
通过对每个目标赋予不同权重,可以将多目标问题转化为多个单目标问题。目标函


演化机器学习(第
2 
版) 

数的权重和定义如下: 

x|λ)λfi(

maxgw 
(= Σ(m) ix)

i=1

subjecttox 
∈
Ω 
(5-1) 
其中,λ1λ2…λm 
]T 权重向量
λ 
应当满足归一化条件和正定条

λ=[是权重向量。通常, 

m 

件。也就是说,对于所有i∈{1,2,…,m},Σλi=1并且λi≥0 。在满足这个条件的前

1≤i≤
m 

提下,理论已经证明:如果原问题是凸的,所有帕累托最优解都可以通过加权分解方法得
到[48];如果原问题是非凸的,上述结论并不成立。一个权重向量对应于一个子问题。在
MOEA/D中,在算法的初始化阶段就生成算法所需要的所有权重向量,这些向量在整个
计算过程中保持不变。

2. 
切比雪夫分解方法
为了介绍切比雪夫分解方法,首先给出理想目标向量(和空想

idealobjectivevector) 
目标向量(utopianobjectivevector)的定义[49]。对于理想目标向量,每个分量的值为对应
目标函数所有可能取值的最大值,即对每一个i∈{1,2,…,m}都有
z 
*=supx∈Ωfi 
()。空想目标向量定义如下,对于所有i∈{1,2,…,m},**=z*+..并且..i(i) >0 。这两个向量(x) 都可以作为参考向量使用[49]。一个多目标问题的切比(z) 雪夫(i) 分解(i) 方法遵循如下形式:(i) 

mingx|λ,=max{i|fi(x)

t(
z 
*)λzi 
*} 
subjecttox 
∈
Ω 
(5-2) 
其中,λ1λ2…λm 
T 是权重向量。理论已证明,当参考点是空想目标向量时,对于任

λ=[]
意一个帕累托最优解
x 
*∈Ω,都存在一个向量0<w∈Rm 
使得
x 
*是这个加权切比雪夫
问题的解[48]。一般地,理想目标向量是未知的。因此,在MOEA/D中,参考点在每轮迭
代中都需要更新。参考点的每一分量都被设定为当前所有目标向量对应分量的最大值。

5.2 
MOEA/
D 
框架
2.
MOEA/D[50]框架如算法5-1所示。该算法的具体过程描述如下。第1~5行是初始
化部分。MOEA/D也采用精英策略,在算法的整个计算过程中,维护一个外部种群用于
存储算法发现的所有非支配解。这个外部种群(ExternalPopulation,EP)最终作为算法
的输出结果。因此算法的第1行初始化外部种群。因为在计算的开始时还没有任何解, 
外部种群被初始化为空集。作为基于分解的多目标演化算法,MOEA/D需要采用某种
分解方法将原问题分解为多个单目标的问题。无论使用权重分解方法还是使用切比雪夫
48
分解方法都需要一组权重向量。在第3行,算法初始化一组权重向量。令
K 
表示权重向


第
5 
章基于分解的多目标分布估计算法


λ1,}。在第3行, 
出和它最邻近的
T 
个向量,参数
T 
称作邻域大小。例如,对于λi,将和它最邻近的
T 
个
向量的下标保存在B(i)中。若λj 
是λi 
的最邻近向量, i)。然后, 

量的数量,并且这组权重向量记为Λ={λ2,…,λK 
对每个权重向量,找

那么j∈B(用随机的或
基于问题的方法生成一个初始种群,并对该种群中的每个个体计算其适应度。如果算法
使用权重方法分解问题,并不需要参考点,因此不需要第5行。如果算法使用切比雪夫分
解方法,需要根据目前得到的目标向量重新计算参考点。第6~13 行是算法的主循环。
在每一轮迭代中,MOEA/D按顺序处理所有子问题。在一个子问题中,算法利用其邻域
中的解生成一个新解y。MOEA/D使用遗传算子生成新解。在本章提出算法中,新解由
规模自适应生成算子生成,这个算子将在5.

3节中阐述。生成的解需要利用与问题相关
的方法提高质量。若生成的新解并不在可行域内,也需要使用与问题相关的方法修复这
个解。和第5步一样,如果涉及参考点,需要在第10 步更新参考点。因为每个新生成的
解来自一个子问题的邻域,利用了这个邻域中其他子问题的相关信息,所以,在生成一个
新解后,应该更新邻域中的子问题的解。用g(表示式(-中的gw 
(λ) 52)中
的gt(
z 
*)。若g(y)≥g(), 那么令xxj 
=
) 
y。第12 
51
行更新外部种群
) x|或者式
。这一步包含
(

x|λ,xj
然后将F(加入到外部种群中。两个子步骤:首先删除所有被F(y)支配的解; y) 

算法5-
1 
MOEA/D框架

1:初始化外部种群为空集
2:初始化一组权重向量
3:对每一个权重向量,找出和它最邻近的权重向量
4:生成初始种群并且计算种群中个体的适应度
5:根据需要,初始化参考点
z 
6:while未达到终止条件do 
7: fori=1,2,…,
T 
d
8: 对第
i 
个子生成一个新解x问题,(o) 
9: 利用问题相关的方法提高
x 
的质量
10: 根据需要,更新参考点
11: 更新邻域中子问题的解
12: 更新外部种群
13: endfor 
14:endwhile 
5.规模自适应生成算子
3

.................................... 

本章设计的规模自适应生成算子适用于0-1编码问题。这个算子使用了概率向量作

49

演化机器学习(第2 版) 
50 
为概率模型。对于第i 个子问题,对应的概率向量记为
pi =[pi1
pi2
…pi
n] (5-3) 
其中,n 为问题的维度。第i 个子问题的相邻向量的下标记录在集合B (i)={i1,i2,…, 
ir}中。分量pi
j 定义如下: 
pi
j =ΣT 
l=1
xil j +ξ 
T +2ξ (5-4) 
其中,T 表示邻域大小。令xil j 表示对应第il 个子问题当前解的第j 个分量。式(5-4)中ξ 
表示附加到概率向量上的一个较小的量。这个附加量用于提高多样性,其具体定义如下: 
ξ= Ts 
n -2s (5-5) 
其中,参数s 是规模自适应生成算子的参数。通过采样pi,可以得到一个新解yi =[y1 
y2…yn]T。
yi = 1, rand(0,1)<pi
j 
0, 其他{ (5-6) 
其中,rand(0,1)表示一个能生成在0~1均匀分布的随机函数。
规模自适应生成算子如算法5-2所示。
算法5-2 规模自适应生成算子
1:procedureReproduce(X,B(i),ynew) 
2: P←0 
3: foreachl∈B(i)do 
4: forj=1,2,…,n do 
5: ifxl
j =1then 
6: pj ←pj +1 
7: endif 
8: endfor 
9: endfor 
10: ξ←(Ts)/(n-2ξ) 
11: forj=1,2,…,n do 
12: pj ←(pj +ξ)/(T +2ξ) 
13: ifrand(0,1)<pjthen 
14: yjnew←1 
15: else 
16: yjnew←0 
17: endif 
18: endfor 
19:endprocedure

第5 章 基于分解的多目标分布估计算法 
51 
式(5-5)中的参数s 决定了从pi 新生成的解中最小变异个数的数学期望。对于一个
子问题,即使其邻域中所有的解都相同,通过规模自适应生成算子生成的新解也会有一些
分量和其父代不同,变异个数的数学期望为s。证明如下。
证明:假设对于所有l∈B(i),xl =x* =[x1* x2* …xn* ]T,即邻域中所有的解都相
同。将式(5-5)代入式(5-4)可得
pj = 
(n -2s)ΣT 
l=1
xil j +Ts 
(n -2s)T +2Ts = (n -2s)Tx* j +Ts 
(n -2s)T +2Ts = (n -2s)x* j +s 
n (5-7) 
如果x* j =0,那么pj=s/n,结合式(5-6)可以得到
P(yj =1|x* j =0)=s
n (5-8) 
如果x* j =1,那么pj=(n-s)/n,结合式(5-6)可以得到
P(yj =0|x* j =1)=1-n -s 
n =s
n (5-9) 
因此,对于解中的一个分量,采样得到的结果和原始值不同的概率是s/n。概率向量假设
各变量是相互独立的。令N 表示变化比特的个数,N 是一个服从参数为n 和s/n 的二项
分布的随机变量,即N ~B(n,s/n),那么N 的数学期望为s。
因此,一个新解与其父代不同的概率为
Pchange =1- 1-s
n 
.
è .
.
. ÷n (5-10) 
当n.s 时(由于问题的规模通常远大于参数s,因此该条件在一般情况下均成立),Pchange 
基本不受参数n 的影响。证明如下。
证明:令ε=s/n,ε 接近0。将式(5-10)改写为
Pchange =1- 1-s
n 
.
è .
.
. ÷
n 
=1- (1-ε)s/ε (5-11) 
在0点附近,对ε 计算泰勒级数可得
Pchange(ε)=1- (1-ε)s/ε =1-e-s +ο(ε2)≈1-e-s (5-12) 
其中,ο(ε2)是二阶小量。因此,Pchange基本不随n 的变化而变化。
如果直接使用ξ 作为规模自适应生成算子的参数,也可以达到提高计算中种群多样
性的目的。但是,这个参数的作用会随着问题的规模而变化,而且它没有直观、明确的物
理意义。作为一种防止概率向量收敛的方法,其实质和变异算子相似。在文献[20]中对
PBIL的实验说明,将概率向量和变异算子结合可以提高算法的性能。但是变异算子是一
个基于遗传算法范式设计的算子,按照分布估计范式,本章将遗传算子集成到概率模型
中。当s 设定为0时,式(5-5)中的ξ=0,此时规模自适应生成算子和MOED/A 中使用

演化机器学习(第2 版) 
52 
的一样[51]。
5.4 测试与实验
........................ 
5.4.1 测试问题 
单目标0-1背包问题作为经典的组合优化问题已经获得广泛的关注和研究[33]。单
目标0-1背包问题可以扩展为任意多目标问题。多目标0-1背包问题描述如下:给定n 
个物品和m 个背包。每个物品都有重量和价值两个属性,同时每个背包具有一定的容
量。如果选择了一个物品,需要将其放入一个背包中。算法的目标是在保证每个背包中
的物品的总重量小于其容量的条件下找到一个可以最大化所有物品总价值的方案。
多目标0-1背包问题的形式化定义如下: 
maxF(x)=[f1(x)f2(x)…fm (x)]T 
fi(x)=Σn 
j=1
pijxi,i=1,2,…,m 
subjecttoΣn 
j=1
wijxi ≤ci,i=1,2,…,m (5-13) 
其中,pi,j和wi,j分别为第i 个背包中的第j 个物品的价值和重量,ci 是第i 个背包的容
量。对所有的j∈(1,2,…,n),x=[x1x2…xn ]T,xj ∈{0,1}即为问题的一个解。和单
目标0-1背包的编码方案一样,xj =1表示选取了第j 个物品。如果在算法运算的过程
中产生的解不是可行解,那么需要修复算子修复这个解。在本章中,算法使用与
MOGLS[52]和MOEA/D[50]中相同的修复算子,如算法5-3所示。
算法5-3 多目标0-1背包问题修复算子
1:procedurerepairOperator(x) 
2: whilex 不满足条件do 
3: J={j|1≤j≤n,xi=1} 
4: I= i|1≤j≤m ,Σn 
j=1 
{ wijyj >ci} 
5: k =argmin j∈J g(x)-g(xj-)/Σi∈I
wij 
6: xk =0 
7: endwhile 
8:endprocedure 
其中,g(x)是目标函数,xj- 是x 将j 个分量改写为0后的解。这个修复算子使用贪

第5 章 基于分解的多目标分布估计算法 
53 
心算法,不断移除价值低但重量大的物品,直到满足限制条件[50]。
为了测试算法并和MOEA/D比较,本章使用了多目标0-1背包问题的9个实例作
为测试问题。包含3种不同的目标和3种不同问题规模的组合。每个实例记为KN-n-m, 
其中,n 表示物品的数量,m 表示目标的个数,即背包的数量。
5.4.2 参数研究
本节主要研究参数s 的影响。在5.3节中已经证明,参数s 具有明确的物理意义。
s 不应该取过大的值,否则算法将倾向于随机搜索。即使一个较小的s 也可以显著提
高解的质量。例如,当s=0.4时,问题的规模是n=500,生成的解与父代不同的概率
至少为
Pchange =1- 1-0.4 
500 
.
è .
.
. ÷
500 >32% (5-14) 
需要指明的是,这是在极端情况下取得的结果,也就是所有邻域中的解都相同的时候。邻
域中的解一般并不相同,那么由算子生成不同的解的概率更大。在探究参数s 的影响时, 
本节使用Hypervolume作为评价指标。这是因为Hypervolume不需要其他算法作为参
考。在本节中,测试s∈{0,0.2,0.4,0.6,0.8,1.0}。图5-1为算法性能随参数s 的变化情
况。图5-1(a)是使用权重分解方法时的结果,而图5-1(b)是使用切比雪夫分解方法时的
结果。在
计算Hypervolume时,同样选取了原点作为计算的参考点。对于不同目标个数的
问题,Hypervolume的变化范围很大(1×107~1×1018),因此要对结果进行归一化,从而
使得结果可以直观地比较。将所得到的结果除以相同问题下s=0时的结果。那么y 轴
为相对值,因此对于所有实例,结果都从1.00开始。从图5-1中可以看出,改进的算子相
对于MEDA/D是有效的,s-MEDA/D 得到的结果要优于MEDA/D 得到的结果。对于
二目标问题,随着s 的增加,Hypervolume也增加;对于三目标问题,算法的性能在s=0.8 
时达到最大,当s=1.0时性能出现下降。s-MEDA/D 对参数并不敏感,所以得到的结果
波动较小。
5.4.3 实验设置与性能指标
在MOEA/D框架中,首先需要分解多目标问题。无论使用上述的权重分解方法还
是切比雪夫分解方法,都需要生成一组权重向量。权重向量的数量由参数H 决定。对于
每一个权重向量,其分量的值从以下集合中选取: 
0H
,1H
,…,H
H { } (5-15)

演化机器学习(第
2 
版) 


图5-
1 
算法性能随参数
s 
的变化

m-1

这种方式产生的权重向量的个数为
N 
=CH 
+m-。为了实现公平的比较,本章算法中的权
重向量的生成方式与MOEA/D和MEDA/D是(1) 相同的。具体的设置如下:对于两目标
问题的3个不同规模的实例,权重向量的数量分别为150 、200 和250 。对于三目标问题, 
参数
H 
设定为25;对于四目标问题,
H 
设定为12 。在MOEA/D框架中,还有一个重要
的参数T,即向量的邻域大小。对于所有实例,邻域大小取T=10,这个设置与MOEA/D[50] 
一样。MOEA/D中变异算子的变异概率为0.01 。s-MEDA/D中参数
s 
设定为0.

4。

实验中,算法在达到最大评价次数时终止。本章实验所使用的终止条件与
MOGLS[52]和MOEA/D[50]中使用的终止条件一致。对于每一组实例都进行30 次独立
实验。本章实验参数如表5-1所示。给定两个包含近似帕累托最优解的集合
A 
和B,通
过计算覆盖指标C(A,B)可以反映两组解的优劣。C(A,B)表示被
A 
中解支配的解在


54 


第
5 
章基于分解的多目标分布估计算法


B 
中所占的比例,其定义如下: 
|{su}|C(A,B)=
u 
∈B|.
v 
∈A:vdominate(5-16)|B| 

Zitzler等人[53]使用解集所覆盖的区域的大小作为解集的评判标准,称为
Hypervolume[53]。Hypervolume 最大的优势在于可以独立评价一个解集的质量。但是
Hypervolume 需要一个参考点。在本章的实验中,对于所有的实例,都使用原点作为参
考点。对于不同算法的实验结果,使用显著性为95% 的威尔科克森符号秩检验计算算法
得到结果是否存在的显著差异。

表5-
1 
本章实验参数

实例
N 
最大评价数
(×103) 
T 
Pmutation 
(MOEA/D) 
s 
(s-MOEA/D)
KN-250-2 
KN-500-2 
KN-750-2 
KN-250-3 
KN-500-3 
KN-750-3 
KN-250-4 
KN-500-4 
KN-750-4 
150 
200 
250 
351 
351 
351 
455 
455 
455 
75 
100 
125 
150 
125 
150 
125 
150 
175 
10 0.1 0.4 

5.4 
实验结果
4.
表示
s
。
-MEDA/D和MOEA/D实验结果比较如表5-2所示。具有显著差别的结果用粗体

从表5-2可以得出如下结论。对于覆盖指标,s-MEDA/D在9个实例上都优于
MOEA/D。对于问题规模为250 的3个实例,C(在85% 左右,而

s-MEDA/D,MOEA/D)
C(MOEA/D,s-MEDA/D)小于10% 。对于问题规模为750 的3个实例,C(-MEDA/D, 
大于99.而C(MOEA/D,为0。这说明在这3(s) 个实例上,

MOEA/D) 5%, s-MEDA/D) 
s-MEDA/D得到的绝大多数解都支配了MOEA/D得到的解,而MOEA/D得到的结果
中没有任何解支配了s-MEDA/D得到的解。对于Hypervolume 指标,除了KN-250-2以
外,其他所有的结果都表明s-MEDA/D显著优于MOEA/D。


55 


演化机器学习(第
2 
版) 

56
!!"#!!"$%&'!&"$(%'!&#$%&'(
)*"
#"+,)*+,-./012,+,
#!!"$%&'!&"$(%'!&##!$(%'!&"!"$%&'!&#!"$%&'&$(%'!&
!"#$%&
!"#$%&
$345667689343:67;!&'&(&)*+,&'&%$*)(!-'*)$%$),&'&+&*.%#/0&.!-'*))$1*,&'&&($&%#/0&.
)3458;#669343<##8<&'&)(&)*,&'&+%-+)!84#6:#;!934338<::#%=77!-'$1&1(%,&'&&(.$+#/0++
1345;7;!89343<66<:&'&$*.1),&'&+&*(-!5433:5;;9343386#5#%=7!!.'-)((+.,&'&&(*.1#/0+%
!"#%&&
$3485<56!93437<686&'&&&$.-,&'&&+&11!;43:7;6#93433#653#%=35!1'&%)-%%,&'&&$*((#/0&*
)3488;87593433!7;6&'&&&)-.,&'&&&-&-!64::!388934335:<8#%=7#!.'%*+-11,&'&&(-%+#/0+$
134858;<#93433;!37&'&&&$$(,&'&&&)$$!74<<!75393433#367#%=76!+')&(**),&'&&$&)$#/0+.
!"#.%&
$3488:5;7934335;:6&'&&&&&&,&'&&&&&&!548337:393433:5:6#%=35!*'*%)+.$,&'&&.$1*#/0&*
)348886!!9343373<!&'&&&&&&,&'&&&&&&!#4:8<37;93433#5!7#%=7<!$'(1-&(*,&'&&)++(#/0+)
134888#:#934333;65&'&&&&&&,&'&&&&&&!643#83<693437786!#%=76!('..**-$,&'&+(()+#/0+.
!"'()*%&
!"#$%&
$345!3!5593435;7!6&'&-&$-+,&'&%((%+!-'*$-(*$,&'&+11-1#/0&.!-'*))$(-,&'&&..1$#/0&.
)345836:!9343;3;;3&'&)-%&$,&'&$&)&(!84#663##93433875;#%=77!-'$)--(+,&'&&(--&#/0++
1345<!!:69343<<;<#&'&)+$.-,&'&+)$($!5433!86:93437333:#%=7!!.'-)(&&&,&'&+&&$-#/0+%
!"#%&&
$34865:5!9343#;3;<&'&&&-.(,&'&&$.-.!;43:353;93433<!5!#%=35!1'&(&*&1,&'&&)%*%#/0&*
)3488!5:#93433;363&'&&&$.),&'&&&%%+!64:::7:;934336875#%=7#!.'%*%1+%,&'&&*)%$#/0+$
13485568793433!#<8&'&&&1$-,&'&&++.$!74<<;<<393433#3#<#%=76!+')&()&&,&'&&+(**#/0+.
!"#.%&
$34885;:393433<8;6&'&&&&&&,&'&&&&&&!5483#7!!93433!<65#%=35!*'*%)-.(,&'&&(*&-#/0&*
)34888:569343335!3&'&&&&&&,&'&&&&&&!#4:8<;<793433#<#5#%=7<!$'(1-)(+,&'&&))(-#/0+)
1348887;;934333:5!&'&&&&&&,&'&&&&&&!643#5<!<934373366#%=76!('.*&)-&,&'&+*1&-#/0+.