多目标进化优化的Tchebycheff分解方法

On Tchebycheff Decomposition Approaches for

Multiobjective Evolutionary Optimization

Digital Object Identifier 10.1109/TEVC.2017.2704118

摘要：

Tchebycheff分解是一种极广泛使用的分解方法，其能将一个多目标优化问题转化为一组标量优化子问题。然而，在Tchebycheff分解中，子目标函数的几何属性还没有被详尽地研究。本文通过对方向向量进行

l

p

p

$l_p$
-范式约束提出了一种Tchebycheff分解方法，其中，子目标函数具有明确的几何属性。尤其，对方向向量进行

l

2

2

$l_2$
-范式约束的Tchebycheff分解作为例子被用于说明其优越性。同时，一个新的一元

R

2

2

$R_2$
指标被引入来近似超体积度量（Hyper-volume metric）及证明提出的Tchebycheff分解的有效性。最终，一个基于使用

l

2

2

$l_2$
-范式约束的Tchebycheff分解的多目标优化算法和一个新的种群更新策略被提出来解决多目标优化问题。在基准测试集及现实世界的多目标优化问题上的实验结果表明，相比其他主流多目标优化算法，提出的算法能够获得高质量的解。

索引词

—Tchebycheff分解，基于分解的多目标优化算法，种群更新策略，最大适应值改善，

R

2

2

$R_2$
指标

I. 引言

一个多目标问题（Multi-objective problem，MOP）【1,2】可以用公式描述为：

min

F

(

x

)

=

(

f

1

(

x

)

,

f

2

(

x

)

,

.

.

.

,

f

m

(

x

)

)

(

)

(

)

(

)

(

)

)

$\min F(x) = \left( f_1(x), f_2(x), ..., f_m(x) \right)$
（1）

s

u

b

j

e

c

t

t

o

:

x

∈

Ω

∈

Ω

$subject to: x \in \Omega$

其中，

$x$
为一个决策变量向量，

$Ω$

Ω

$\Omega$
为决策空间，

F

(

x

)

:

Ω

→

R

m

(

)

→

m

$F(x): \Omega \rightarrow R^m$
为

$m$
个目标函数的一个

$m$

m

$m$
-维向量。

令

x

a

a

$x_a$
和

x

b

b

$x_b$
表示两个决策向量，

x

a

a

$x_a$
支配

x

b

b

$x_b$
（表示为

x

a

≺

x

b

≺

b

$x_a \prec x_b$
），当且仅当

∀

i

∈

{

1

,

.

.

.

,

m

}

,

f

i

(

x

a

)

≤

f

i

(

x

b

)

∈

{

}

(

)

≤

(

)

$\forall i \in \left\{ 1, ..., m \right\}, f_i(x_a) \leq f_i(x_b)$
及

F

(

x

a

)

≠

F

(

x

b

)

(

)

≠

(

)

$F(x_a) \neq F(x_b)$
。一个解

x

∗

∈

Ω

∗

∈

Ω

$x^* \in \Omega$
如果不被其他任何解支配，则被称为是Pareto最优的。所有的Pareto最优解组成了Pareto最优集（Pareto optimal set，PS），即，

P

S

=

{

x

∗

|

∄

x

∈

Ω

,

x

≺

x

∗

}

{

∗

∄

∈

≺

∗

}

$PS = \left\{ x^* | \nexists x \in \Omega, x \prec x^* \right\}$
。相应的最优目标向量集称为Pareto最优前沿（Pareto optimal front，PF），即，

P

F

=

{

F

(

x

)

|

x

∈

P

S

}

{

(

)

∈

}

$PF = \left\{ F(x) | x \in PS \right\}$
。

基于分解的多目标优化算法（MOEA/D）已被认为是一种非常有效的估计

P

F

F

$PF$
的方法【3-14】。分解方法是MOEA/D的关键组成。Tchebycheff分解是一种最为广泛使用的分解方法。然而，使用均匀权重向量的Tchebycheff分解所获得的解通常并不是均匀分布的【5-9】。广义分解【5-7】和改进的Tchebycheff分解【9，10】被提出以解决此问题，但在这些Tchebycheff分解方法中的子目标函数的几何属性还没有被详尽地研究。

本文提出一种对方向向量进行

l

p

p

$l_p$
-范式约束的Tchebycheff分解方法（

$p$
-Tch），其中，子目标函数有明确的几何属性。对

$p$

p

$p$
-Tch和其他Tchebycheff分解方法的关系进行了研究。不同的

$p$
值对MOEA/D的子问题施加了不同的竞争压力。使用

$l_{2}$

l_{2}

$l_2$
-范式约束（2-Tch）的Tchebycheff分解被作为例子来说明所提出的分解方法的优点。指标

R

2

t

c

h

2

h

$R^{2tch}_2$
，一种基于2-Tch的

R

2

2

$R_2$
指标【15】的变体，也被引入以近似超体积度量来证实提出的Tchebycheff分解的有效性。

MOEA/D框架中使用了2-Tch及一个新的种群更新策略。在大多数的MOEA/D变体（比如，【4,16-18】）中，进化种群的更新是基于一种局部随机策略。在【19】中，一种基于最小适应值的全局策略被提出。然而，上述策略都是被设计用来优化某些子问题的性能，而不是所有子问题。为解决此问题，本文引入了一种基于最大适应值改善的全局种群更新策略来优化所有子问题的总体性能。最终的算法，MOEA/D-2TCHMFI（基于2-Tch和最大适应值提升的种群更新策略的MOEA/D），在多种基准测试集和现实世界的多目标优化问题上进行了测试。实验结果表明，相比其他多目标优化算法，MOEA/D-2TCHMFI能够得到高质量的解。

在本文的其余部分，第II节回顾了两种密切相关的Tchebycheff分解方法。所提出的对方向向量进行

l

p

p

$l_p$
-范式约束的Tchebycheff分解方法和分解的广义形式在第III节引入。第IV节提出了基于最大适应值改善的种群更新策略。最终的MOEA/D-2TCHMFI算法在第V节被描述。第VI节定义了提出的一元指标

R

2

t

c

h

2

h

$R^{2tch}_2$
。第VII节展示了MOEA/D-2TCHMFI和其他先进多目标优化算法的比较结果。最后，第VIII节对本工作进行了总结。

II. 两种关系密切的Tchebycheff分解方法

在本节，我们回顾了两种关系密切的Tchebycheff分解方法，即，传统Tchebycheff分解【20】和改进Tchebycheff分解【10】。在这两种Tchebycheff分解方法中的子问题目标函数的几何属性被详细研究。

A. 传统Tchebycheff分解

传统Tchebycheff分解将一个MOP分解成一组标量优化子问题，每一个的定义如下：

min

x

∈

Ω

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

max

1

≤

i

≤

m

{

w

i

(

f

i

(

x

)

−

z

∗

)

}

∈

(

)

∗

)

max

≤

{

(

)

−

∗

)

}

$\min \limits_{x\in\Omega} g^{tch} \left( F(x) | w,z^* \right) = \max \limits_{1 \leq i \leq m} \left\{ w_i \left( f_i(x)-z^* \right) \right\}$
（2）

其中，

w

i

=

(

w

1

,

.

.

.

,

w

m

)

(

)

$w_i = \left( w_1, ..., w_m \right)$
满足

∑

m

i

=

1

w

i

=

1

1

$\sum_{i=1}^{m} w_i = 1$
及

w

i

≥

0

≥

0

$w_i \geq 0$
，为一个子问题的权重向量，

z

∗

=

(

z

∗

1

,

z

∗

2

,

.

.

.

,

z

∗

m

)

∗

(

∗

)

$z^* = \left( z^*_1, z^*_2, ..., z^*_m \right)$
满足

z

∗

i

<

min

{

f

i

(

x

)

|

x

∈

Ω

}

∗

min

{

(

)

∈

}

$z^*_i < \min \left\{ f_i(x) | x \in \Omega \right\}$
，为一理想目标向量。

传统Tchebycheff分解中的子问题目标函数的几何属性还没有被研究。据我们所知，本工作首次研究了Tchebycheff分解中的子问题目标函数的几何属性。

命题 2.1：

令

z

∗

=

(

z

∗

1

,

.

.

.

,

z

∗

m

)

∗

(

∗

)

$z^* = \left(z^*_1, ..., z^*_m \right)$
为（1）的一个理想目标向量，

w

=

(

w

1

,

.

.

.

,

w

m

)

(

)

$w=\left(w_1,...,w_m\right)$
为正权重向量。若一个给定的目标向量

F

(

x

)

=

(

f

1

(

X

)

,

.

.

.

,

F

m

(

x

)

)

(

)

(

)

(

)

)

$F(x)=\left(f_1(X), ..., F_m(x) \right)$
位于直线

L

1

:

w

1

(

f

1

(

x

)

−

z

∗

1

)

=

.

.

.

=

w

m

(

f

m

(

x

)

−

z

∗

m

)

(

)

−

∗

)

(

)

−

∗

)

$L_1: w_1 \left(f_1(x) - z^*_1 \right) = ... = w_m \left( f_m(x) - z^*_m \right)$

如图1（a）所示。那么，

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

w

T

(

F

(

x

)

−

z

∗

)

m

(

)

∗

)

(

)

−

∗

)

m

$g^{tch} \left( F(x) | w,z^* \right) = \dfrac{w^T \left( F(x) - z^* \right)}{m}$
（3）

证明

由于

F

(

x

)

(

)

$F(x)$
位于直线

L

1

1

$L_1$
，我们得到

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

=

=

(

2

)

max

1

≤

i

≤

m

{

w

i

(

f

i

(

x

)

−

z

∗

i

)

}

=

=

=

L

1

w

1

(

f

1

(

x

)

−

z

∗

1

)

=

.

.

.

=

w

m

(

f

m

(

x

)

−

z

∗

m

)

=

∑

m

i

=

1

w

i

(

f

i

(

x

)

−

z

∗

i

)

m

=

w

T

(

F

(

x

)

−

z

∗

)

m

■

(

)

∗

)

===

(

)

max

≤

{

(

)

−

∗

)

}

===

(

)

−

∗

)

(

)

−

∗

)

∑

(

)

−

∗

)

(

)

−

∗

)

◼

$g^{tch} \left( F(x) | w,z^*\right) \overset{(2)}{===}\max \limits_{1 \leq i \leq m} \left\{ w_i \left( f_i(x) - z^*_i \right) \right\} \overset{L_1}{===} w_1 \left( f_1(x) - z^*_1 \right) = ... = w_m \left( f_m(x) - z^*_m \right) = \dfrac{ \sum_{i=1}^{m} w_i \left(f_i(x) - z^*_i \right)}{m} = \dfrac{w^T \left( F(x) - z^* \right)}{m}\ \ \ \ \ \ \blacksquare$

公式（3）用于说明

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

(

)

∗

)

$g^{tch} \left( F(x) | w,z^* \right)$
的几何属性，而不是找到

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

(

)

∗

)

$g^{tch} \left( F(x) | w,z^* \right)$
的最优解，即，

min

x

∈

Ω

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

∈

(

)

∗

)

$\min_{x \in \Omega} g^{tch} \left( F(x) | w,z^* \right)$
。以

F

(

x

)

=

(

1

/

2

,

1

/

4

)

(

)

(

)

$F(x) = \left( 1/2,1/4 \right)$
，

z

∗

=

(

0

,

0

)

∗

(

)

$z^* = (0,0)$
及

w

=

(

1

/

3

,

2

/

3

)

(

)

$w=(1/3,2/3)$
为例，如图1（a）所示，我们可以使用等式（3）来解释子问题适应值

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

(

)

∗

)

$g^{tch} \left( F(x) | w,z^* \right)$
，

$w$
，与

$F (x) - z^{*}$

F (x) - z^{*}

$F(x)-z^*$
的关系。式（3）（即

w

T

(

F

(

x

)

−

z

∗

)

/

m

(

)

−

∗

)

m

$w^T \left( F(x)-z^* \right) / m$
）给出了

l

1

1

$l_1$
-范式的加权形式，为

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

(

)

∗

)

$g^{tch} \left( F(x) | w,z^* \right)$
的对偶式【21，pp. 637】。

F

(

x

)

(

)

$F(x)$
不位于

L

1

1

$L_1$
的情形可以如下命题描述。

命题 2.2：

令

z

∗

=

(

z

∗

1

,

.

.

.

,

z

∗

m

)

∗

(

∗

)

$z^* = \left( z^*_1, ..., z^*_m \right)$
为一个（1）的理想目标向量，

w

=

(

w

1

,

.

.

.

,

w

m

)

(

)

$w = \left( w_1, ..., w_m \right)$
为一个正的权重向量。给定一个目标向量

F

(

x

)

=

(

f

1

(

x

)

,

.

.

.

,

f

m

(

x

)

)

(

)

(

)

(

)

)

$F(x) = \left( f_1(x), ..., f_m(x) \right)$
，

F

^

(

x

)

=

(

f

^

1

(

x

)

,

.

.

.

,

f

^

m

(

x

)

)

(

)

(

)

(

)

)

$\hat{F}(x) = \left( \hat{f}_1(x), ..., \hat{f}_m(x) \right)$
可以如下构建：1）

F

^

(

x

)

(

)

$\hat{F}(x)$
与

F

(

x

)

(

)

$F(x)$
有相同的子问题适应值，即，

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

g

t

c

h

(

F

^

(

x

)

|

w

,

z

∗

)

(

)

∗

)

(

)

∗

)

$g^{tch} \left( F(x) | w,z^* \right) = g^{tch} \left( \hat{F}(x) | w,z^* \right)$
；2）

F

^

(

x

)

(

)

$\hat{F}(x)$
位于图1（d）所示的直线

L

1

1

$L_1$
。那么，如下等式可以满足：

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

w

T

(

F

^

(

x

)

−

z

∗

)

m

(

)

∗

)

(

)

−

∗

)

m

$g^{tch} \left( F(x) | w,z^* \right) = \dfrac{w^T \left( \hat{F}(x) - z^* \right)}{m}$
（4）

证明

由

F

^

(

x

)

(

)

$\hat{F}(x)$
的构建，我们得到

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

=

=

1

)

=

=

=

=

=

=

=

2

)

F

^

(

x

)

is in

L

1

w

T

(

F

^

(

x

)

−

z

∗

)

m

■

(

)

∗

)

===

)

=======

)

(

)

is in

(

)

−

∗

)

◼

$g^{tch} \left( F(x) | w,z^* \right) \overset{1)}{===} {\overset{2) \hat{F}(x)\text{ is in }L_1}{=======}} \dfrac{w^T \left( \hat{F}(x) - z^* \right)}{m}\ \ \ \ \ \ \blacksquare$

备注

给定目标向量

F

(

x

)

(

)

$F(x)$
，

F

^

(

x

)

=

(

f

^

1

(

x

)

,

.

.

.

,

f

^

m

(

x

)

)

(

)

(

)

(

)

)

$\hat{F}(x) = \left( \hat{f}_1(x), ..., \hat{f}_m(x) \right)$
实际上是

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

(

)

∗

)

$g^{tch} \left( F(x) | w,z^* \right)$
的等值线与

L

1

1

$L_1$
在目标空间的交点，如图1（d）所示，并且

f

^

i

(

x

)

=

z

∗

i

+

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

w

i

,

i

=

1

,

.

.

.

,

m

(

)

∗

(

)

∗

)

m

$\hat{f}_i(x) = z^*_i + \dfrac{g^{tch} \left( F(x) | w,z^* \right)}{w_i},i=1,...,m$

由于这样的事实：

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

=

=

1

)

g

t

c

h

(

F

^

(

x

)

|

w

,

z

∗

)

=

=

=

2

)

w

1

(

f

^

1

(

x

)

−

z

∗

1

)

=

.

.

.

=

w

m

(

f

^

m

(

x

)

−

z

∗

m

)

■

(

)

∗

)

===

)

(

)

∗

)

===

)

(

)

−

∗

)

(

)

−

∗

)

◼

$g^{tch} \left( F(x) | w,z^* \right) \overset{1)}{===}g^{tch} \left( \hat{F}(x) | w,z^* \right) \overset{2)}{===} w_1 \left( \hat{f}_1(x) - z^*_1 \right) = ... = w_m \left( \hat{f}_m(x) - z^*_m \right)\ \ \ \ \ \ \blacksquare$

以

F

(

x

)

=

(

1

,

1

)

(

)

(

)

$F(x) = (1,1)$
，

z

∗

=

(

0

,

0

)

∗

(

)

$z^*=(0,0)$
，及

w

=

(

1

/

3

,

2

/

3

)

(

)

$w=(1/3,2/3)$
为例，我们能得到：

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

max

{

1

3

(

1

−

0

)

,

2

3

(

1

−

0

)

}

=

2

/

3

(

)

∗

)

max

{

(

−

)

(

−

)

}

3

$g^{tch} \left( {F}(x) | w,z^* \right) = \max \left\{ \dfrac{1}{3}(1-0),\dfrac{2}{3}(1-0) \right\} = 2/3$
，

f

^

1

(

x

)

=

z

∗

1

+

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

w

1

=

0

+

2

/

3

1

/

3

=

2

(

)

∗

(

)

∗

)

2

$\hat{f}_1(x)=z^*_1 + \dfrac{g^{tch} \left( {F}(x) | w,z^* \right)}{w_1} = 0+\dfrac{2/3}{1/3} = 2$
，

f

^

2

(

x

)

=

z

∗

2

+

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

w

2

=

0

+

2

/

3

2

/

3

=

1

(

)

∗

(

)

∗

)

1

$\hat{f}_2(x) = z^*_2 + \dfrac{g^{tch} \left( {F}(x) | w,z^* \right)}{w_2} = 0 + \dfrac{2/3}{2/3} =1$
.

B. 改进Tchebycheff分解

为处理最优解与相应的子问题权重向量之间的非线性关系【5-8,22-24】，研究【10】提出了改进Tchebycheff分解。并没有与（2）中的

w

i

i

$w_i$
相乘，改进Tchebycheff分解通过用

f

i

(

x

)

−

z

∗

i

(

)

−

∗

$f_i(x) - z^*_i$
除以

w

i

i

$w_i$
来构建子问题，如下：

min

x

∈

Ω

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

max

1

≤

i

≤

m

{

f

i

(

x

)

−

z

∗

i

w

i

}

∈

(

)

∗

)

max

≤

{

(

)

−

∗

}

$\min\limits_{x\in\Omega} g^{mtch} \left( F(x) | w, z^* \right) = \max\limits_{1 \leq i \leq m} \left\{ \dfrac{f_i(x) - z^*_i}{w_i} \right\}$
（5）

对改进Tchebycheff分解中的一个子问题目标函数的几何属性的研究如下。

命题 2.3：

令

z

∗

=

(

z

∗

1

,

.

.

.

,

z

∗

m

)

∗

(

∗

)

$z^* = \left( z^*_1, ..., z^*_m \right)$
为（1）中的一理想目标向量，

w

=

(

w

1

,

.

.

.

,

w

m

)

(

)

$w = \left( w_1, ..., w_m \right)$
为一正的权重向量。若一给定的目标向量

F

(

x

)

=

(

f

1

(

x

)

,

.

.

.

,

f

m

(

x

)

)

(

)

(

)

(

)

)

$F(x) = \left( f_1(x), ..., f_m(x) \right)$
位于直线

L

2

:

f

1

(

x

)

−

z

∗

1

w

1

=

.

.

.

=

f

m

(

x

)

−

z

∗

m

w

m

(

)

−

∗

(

)

−

∗

m

$L_2:\ \dfrac{f_1(x) - z^*_1}{w_1} = ... = \dfrac{f_m(x) - z^*_m}{w_m}$

如图1（b）所示。那么，

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

∥

F

(

x

)

−

z

∗

∥

1

(

)

∗

)

‖

(

)

−

∗

‖

1

$g^{mtch} \left( F(x) | w, z^* \right) = \left\| F(x) - z^* \right\|_1$
（6）

证明

由于

F

(

x

)

(

)

$F(x)$
在

L

2

2

$L_2$
上，我们可以得出，

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

=

=

(

5

)

max

1

≤

i

≤

m

{

f

i

(

x

)

−

z

∗

i

w

i

}

(

)

∗

)

===

(

)

max

≤

{

(

)

−

∗

}

$g^{mtch} \left( F(x) | w, z^* \right) \overset{(5)}{===} \max\limits_{1 \leq i \leq m} \left\{ \dfrac{f_i(x) - z^*_i}{w_i} \right\}$

=

=

=

L

2

f

1

(

x

)

−

z

∗

1

w

1

=

.

.

.

=

f

m

(

x

)

−

z

∗

m

w

m

(

)

−

∗

(

)

−

∗

m

$\overset{L_2}{===} \dfrac{f_1(x) - z^*_1}{w_1} = ... = \dfrac{f_m(x) - z^*_m}{w_m}$

=

∑

m

i

=

1

(

f

i

(

x

)

−

z

∗

i

)

∑

m

i

=

1

w

i

=

∥

F

(

x

)

−

z

∗

∥

1

■

∑

(

)

−

∗

)

∑

‖

(

)

−

∗

‖

◼

$= \dfrac{\sum_{i=1}^{m} \left( f_i(x) - z^*_i \right)}{\sum_{i=1}^{m}w_i} = \left\| F(x) - z^* \right\|_1\ \ \ \ \ \ \blacksquare$

以

F

(

x

)

=

(

1

/

4

,

2

/

4

)

(

)

(

)

$F(x) = (1/4,2/4)$
，

z

∗

=

(

0

,

0

)

∗

(

)

$z^* = (0,0)$
，及

w

=

(

1

/

3

,

2

/

3

)

(

)

$w=(1/3,2/3)$
为例，式（6）可以如下计算：

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

max

{

f

1

(

x

)

−

z

∗

1

w

1

,

f

2

(

x

)

−

z

∗

2

w

2

}

(

)

∗

)

max

{

(

)

−

∗

(

)

−

∗

}

$g^{mtch} \left( F(x) | w, z^* \right) = \max \left\{ \dfrac{f_1(x)-z^*_1}{w_1}, \dfrac{f_2(x) - z^*_2}{w_2} \right\}$

=

max

{

1

/

4

−

0

1

/

3

,

2

/

4

−

0

2

/

3

}

=

3

4

=

∥

F

(

x

)

−

z

∗

∥

1

max

{

−

}

‖

(

)

−

∗

‖

1

$= \max \left\{ \dfrac{1/4-0}{1/3}, \dfrac{2/4-0}{2/3} \right\} = \dfrac{3}{4} = \left\| F(x) - z^* \right\|_1$

当

F

(

x

)

(

)

$F(x)$
不在

L

2

2

$L_2$
时，以下命题描述了

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

(

)

∗

)

$g^{tch} \left( F(x) | w, z^* \right)$
的几何属性。

命题 2.4：

令

z

∗

=

(

z

∗

1

,

.

.

.

,

z

∗

m

)

∗

(

∗

)

$z^* = \left( z^*_1, ..., z^*_m \right)$
为（1）中的一理想目标向量，

w

=

(

w

1

,

.

.

.

,

w

m

)

(

)

$w = \left( w_1, ..., w_m \right)$
为一正的权重向量。给定一目标向量

F

(

x

)

=

(

f

1

(

x

)

,

.

.

.

,

f

m

(

x

)

)

(

)

(

)

(

)

)

$F(x) = \left( f_1(x), ..., f_m(x) \right)$
，可以由满足以下两个约束生成

F

~

(

x

)

=

(

f

~

1

(

x

)

,

.

.

.

,

f

~

m

(

x

)

)

(

)

(

)

(

)

)

$\tilde{F}(x) = \left( \tilde{f}_1(x), ..., \tilde{f}_m(x) \right)$
：1）

f

~

(

x

)

(

)

$\tilde{f}(x)$
和

F

(

x

)

(

)

$F(x)$
位于同一等值线上，即，

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

g

m

t

c

h

(

F

~

(

x

)

|

w

,

z

∗

)

(

)

∗

)

(

)

∗

)

$g^{mtch} \left( F(x) | w, z^* \right) = g^{mtch} \left( \tilde{F}(x) | w, z^* \right)$
；及2）

f

~

(

x

)

(

)

$\tilde{f}(x)$
位于直线

L

2

2

$L_2$
上，如图1（e）所示。那么，

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

∥

∥

F

~

(

x

)

−

z

∗

∥

∥

1

(

)

∗

)

‖

(

)

−

∗

‖

1

$g^{mtch} \left( F(x) | w, z^* \right) = \left\| \tilde{F}(x) - z^* \right\|_1$
（7）

证明

据

F

~

(

x

)

(

)

$\tilde{F}(x)$
的情况，我们得到

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

=

=

=

1

)

g

m

t

c

h

(

F

~

(

x

)

|

w

,

z

∗

)

(

)

∗

)

===

)

(

)

∗

)

$g^{mtch} \left( F(x) | w, z^* \right) = \overset{1)}{===} g^{mtch} \left( \tilde{F}(x) | w, z^* \right)$

=

=

=

=

=

=

=

=

=

=

=

=

=

=

=

=

=

=

=

=

2

)

F

~

(

x

)

is in

L

2

{Proposition 2.3}

∥

∥

F

~

(

x

)

−

z

∗

∥

∥

1

■

)

(

)

is in

{Proposition 2.3}

‖

(

)

−

∗

‖

◼

$\overset{2)\ \tilde{F}(x)\text{ is in }L_2\ \text{{Proposition 2.3}}}{====================} \left\| \tilde{F}(x) - z^* \right\|_1\ \ \ \ \ \ \blacksquare$

备注

在几何中，

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

(

)

∗

)

$g^{mtch} \left( F(x) | w, z^* \right)$
等同于

F

~

(

x

)

−

z

∗

(

)

−

∗

$\tilde{F}(x) - z^*$
的

l

1

1

$l_1$
-范式，如图1（e）所示。

F

~

(

x

)

(

)

$\tilde{F}(x)$
为直线

L

2

2

$L_2$
与

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

(

)

∗

)

$g^{mtch} \left( F(x) | w, z^* \right)$
的等值线的交点，如图1（e）所示。

F

~

(

x

)

=

(

f

~

1

(

x

)

,

.

.

.

,

f

~

m

(

x

)

)

=

z

∗

+

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

⋅

w

(

)

(

)

(

)

∗

(

)

∗

)

⋅

w

$\tilde{F}(x) = \left( \tilde{f}_1(x), ..., \tilde{f}_m(x) \right) = z^* + g^{mtch} \left( F(x) | w, z^* \right) \cdot w$

由于

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

=

=

1

)

g

m

t

c

h

(

F

~

(

x

)

|

w

,

z

∗

)

(

)

∗

)

===

)

(

)

∗

)

$g^{mtch} \left( F(x) | w, z^* \right) \overset{1)}{===} g^{mtch} \left( \tilde{F}(x) | w, z^* \right)$

=

=

=

=

=

2

)

L

2

f

~

1

(

x

)

−

z

∗

1

w

1

=

.

.

.

=

f

~

m

(

x

)

−

z

∗

m

w

m

■

)

(

)

−

∗

(

)

−

∗

◼

$\overset{2)\ L_2}{=====} \dfrac{\tilde{f}_1(x) - z^*_1}{w_1} = ... = \dfrac{ \tilde{f}_m(x) - z^*_m}{w_m}\ \ \ \ \ \ \blacksquare$

例如，给定

F

(

x

)

=

(

0.5

,

2

)

(

)

(

0.5

)

$F(x) = (0.5,2)$
，

z

∗

=

(

0

,

0

)

∗

(

)

$z^* = (0,0)$
，及

w

=

(

1

/

3.2

/

3

)

(

3.2

)

$w = (1/3.2/3)$
，我们可以计算

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

=

max

{

0.5

−

0

1

/

3

,

2

−

0

2

/

3

}

=

3

,

(

)

∗

)

max

{

0.5

−

}

,

$g^{mtch} \left( F(x) | w, z^* \right) = \max \left\{ \dfrac{0.5-0}{1/3}, \dfrac{2-0}{2/3} \right\} = 3,$

f

~

1

(

x

)

=

z

∗

1

+

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

⋅

w

1

=

0

+

3

⋅

1

/

3

=

1

,

(

)

∗

(

)

∗

)

⋅

,

$\tilde{f}_1(x) = z^*_1 + g^{mtch} \left( F(x) | w, z^* \right) \cdot w_1 = 0 + 3 \cdot 1/3 = 1,$

f

~

2

(

x

)

=

z

∗

2

+

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

⋅

w

2

=

0

+

3

⋅

2

/

3

=

2.

(

)

∗

(

)

∗

)

⋅

2.

$\tilde{f}_2(x) = z^*_2 + g^{mtch} \left( F(x) | w, z^* \right) \cdot w_2 = 0 + 3 \cdot 2/3 = 2.$

III. 提出的对方向向量进行

l

p

通过对改进Tchebycheff分解进行拓展，本文提出一种新的对方向向量进行

l

p

p

$l_p$
-范式约束的Tchebycheff分解方法，简称为

$p$
-Tch。在

$p$

p

$p$
-Tch中，每个子问题的构建基于一个满足

∥

λ

∥

p

=

1

‖

1

$\left\| \lambda \right\|_p = 1$
的方向向量

$\lambda$
，而不是改进Tchebycheff分解中使用的满足

∥

w

∥

1

=

∑

m

i

=

1

w

i

=

1

‖

∑

1

$\left\|w\right\|_1 = \sum_{i=1}^{m} w_i = 1$
的权重向量

$w$
，即，

$min_{x \in Ω} g^{p t c h} (F (x) | λ, z^{*}) = max_{1 \leq i \leq m} {\frac{f_{i} (x) - z_{i}^{*}}{λ_{i}}}$

min_{x \in Ω} g^{p t c h} (F (x) | λ, z^{*}) = max_{1 \leq i \leq m} {\frac{f_{i} (x) - z_{i}^{*}}{λ_{i}}}

$\min\limits_{x\in\Omega} g^{ptch} \left( F(x) | \lambda, z^* \right) = \max\limits_{1 \leq i \leq m} \left\{ \dfrac{f_i(x) - z^*_i}{\lambda_i} \right\}$
（8）

其中，

λ

=

(

λ

1

,

.

.

.

,

λ

m

)

(

)

$\lambda = \left( \lambda_1, ..., \lambda_m \right)$
满足

∥

λ

∥

p

=

1

‖

1

$\left\| \lambda \right\|_p = 1$
及

λ

1

,

.

.

.

,

λ

m

>

0

0

$\lambda_1, ..., \lambda_m > 0$
。注意，改进Tchebycheff分解（5）是

p

=

1

1

$p=1$
时的

$p$
-Tch的一种特殊形式，近似于Chebyshev近似问题【21，pp. 293】，是

$p$

p

$p$
-Tch（8）的一个同等问题，可用公式描述为：

min

x

∈

Ω

t

∈

t

$\min\limits_{x\in\Omega}\ \ \ t$

s

.

t

.

f

i

(

x

)

−

z

∗

i

λ

i

≤

t

,

i

=

1

,

.

.

.

,

m

(

)

−

∗

≤

m

$s.t.\ \ \ \ \ \dfrac{f_i(x) - z^*_i}{\lambda_i} \leq t, i = 1, ..., m$

A.

$p$
-Tch中的子问题目标函数的几何属性

命题 3.1：

令

$z^{*} = (z_{1}^{*}, . . ., z_{m}^{*})$

z^{*} = (z_{1}^{*}, . . ., z_{m}^{*})

$z^* = \left( z^*_1, ..., z^*_m \right)$
为（1）的一个理想目标向量，方向向量

$\lambda$
为一正向量且满足

∥

λ

∥

p

=

1

‖

1

$\left\| \lambda \right\|_p = 1$
。若一给定的目标向量

F

(

x

)

=

(

f

1

(

x

)

,

.

.

.

,

f

m

(

x

)

)

(

)

(

)

(

)

)

$F(x) = \left( f_1(x), ..., f_m(x) \right)$
位于直线

L

3

:

f

1

(

x

)

−

z

∗

1

λ

1

=

.

.

.

=

f

m

(

x

)

−

z

∗

m

λ

m

.

(

)

−

∗

(

)

−

∗

.

$L_3: \dfrac{f_1(x) - z^*_1}{\lambda_1} = ... = \dfrac{f_m(x) - z^*_m}{\lambda_m}.$

那么

g

p

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

=

∥

F

(

x

)

−

z

∗

∥

p

(

)

∗

)

‖

(

)

−

∗

‖

p

$g^{ptch} \left( F(x) | \lambda, z^* \right) = \left\| F(x) - z^* \right\|_p$
（9）

证明

由于

f

i

(

x

)

−

z

∗

i

≥

0

(

)

−

∗

≥

0

$f_i(x) - z^*_i \geq 0$
并且对于

∀

i

∈

{

1

,

2

,

.

.

.

,

m

}

∈

{

}

$\forall i \in \left\{ 1,2,...,m\right\}$
有

λ

i

>

0

0

$\lambda_i > 0$
，

k

(

x

)

≜

g

p

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

=

=

=

(

8

)

max

1

≤

i

≤

m

{

f

i

(

x

)

−

z

∗

i

λ

i

}

(

)

≜

(

)

∗

)

===

(

)

max

≤

{

(

)

−

∗

}

$k(x) \triangleq g^{ptch} \left( F(x) | \lambda, z^* \right) \overset{(8)}{===} \max\limits_{1 \leq i \leq m} \left\{ \dfrac{f_i(x) - z^*_i}{\lambda_i} \right\}$

=

=

=

L

3

f

1

(

x

)

−

z

∗

1

λ

1

=

.

.

.

=

f

m

(

x

)

−

z

∗

m

λ

m

≥

0

(

)

−

∗

(

)

−

∗

≥

0

$\overset{L_3}{===} \dfrac{f_1(x) - z^*_1}{\lambda_1} = ... = \dfrac{f_m(x) - z^*_m}{\lambda_m} \geq 0$
（10）

由于对于

i

=

1

,

.

.

.

,

m

m

$i = 1, ..., m$
有

f

i

(

x

)

−

z

∗

i

=

λ

i

⋅

k

(

x

)

(

)

−

∗

⋅

(

)

$f_i(x) - z^*_i = \lambda_i \cdot k(x)$
，且

F

(

x

)

−

z

∗

=

k

(

x

)

⋅

λ

(

)

−

∗

(

)

⋅

λ

$F(x) - z^* = k(x) \cdot \lambda$
，我们有

g

p

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

=

k

(

x

)

=

=

=

=

=

∥

λ

∥

p

=

1

k

(

x

)

⋅

∥

λ

∥

p

=

=

=

=

=

=

=

=

k

(

x

)

≥

0

(

10

)

(

)

∗

)

(

)

=====

‖

(

)

⋅

‖

========

(

)

≥

(

)

$g^{ptch} \left( F(x) | \lambda, z^* \right) = k(x) \overset{\left\| \lambda \right\|_p = 1}{=====} k(x) \cdot \left\| \lambda \right\|_p \overset{k(x) \geq 0\ \ (10)}{========}$

∥

k

(

x

)

⋅

λ

∥

p

=

=

=

=

=

=

=

=

=

=

=

k

(

x

)

⋅

=

F

(

x

)

−

z

∗

∥

F

(

x

)

−

z

∗

∥

p

(

)

⋅

‖

===========

(

)

⋅

(

)

−

∗

‖

(

)

−

∗

‖

p

$\left\| k(x) \cdot \lambda \right\|_p \overset{k(x) \cdot = F(x) - z^*}{===========} \left\| F(x) - z^* \right\|_p$
（11）

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \blacksquare$

以

p

=

2

2

$p=2$
，

F

(

x

)

=

(

1

,

2

)

(

)

(

)

$F(x) = (1,2)$
，

λ

=

(

1

/

5

–

√

,

2

/

5

–

√

)

(

)

$\lambda = (1/\sqrt{5}, 2/\sqrt{5})$
，及

z

∗

=

(

0

,

0

)

∗

(

)

$z^* = (0,0)$
为例，我们能得到

g

2

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

=

max

{

f

1

(

x

)

−

z

∗

1

λ

1

,

f

2

(

x

)

−

z

∗

2

λ

2

}

(

)

∗

)

max

{

(

)

−

∗

(

)

−

∗

}

$g^{2tch} \left( F(x) | \lambda, z^* \right) = \max \left\{ \dfrac{f_1(x) - z^*_1}{\lambda_1}, \dfrac{f_2(x) - z^*_2}{\lambda_2} \right\}$

=

max

{

1

−

0

1

/

5

–

√

,

2

−

0

2

/

5

–

√

}

=

5

–

√

=

∥

F

(

x

)

−

z

∗

∥

2

max

{

−

}

‖

(

)

−

∗

‖

2

$= \max \left\{ \dfrac{1-0}{1/\sqrt{5}}, \dfrac{2-0}{2/\sqrt{5}} \right\} = \sqrt{5} = \left\| F(x) - z^* \right\|_2$

命题3.1描述的情形在

p

=

2

2

$p=2$
时可以用图1（c）说明。如图所示，

g

p

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

(

)

∗

)

$g^{ptch} \left( F(x) | \lambda, z^* \right)$
为

p

=

2

2

$p=2$
时的

z

∗

∗

$z^*$
到

F

(

x

)

(

)

$F(x)$
的欧氏距离。

F

(

x

)

(

)

$F(x)$
不位于

L

3

3

$L_3$
的情形可以用如下命题描述。

命题 3.2：

，令

z

∗

=

(

z

∗

1

,

.

.

.

,

z

∗

m

)

∗

(

∗

)

$z^* = \left( z^*_1, ..., z^*_m \right)$
为（1）的一理想目标向量，方向向量

$\lambda$
为满足

∥

λ

∥

p

=

1

‖

1

$\left\| \lambda \right\|_p = 1$
的方向向量。给定一目标向量

F

(

x

)

=

(

f

1

(

x

)

,

.

.

.

,

f

m

(

x

)

)

(

)

(

)

(

)

)

$F(x) = \left( f_1(x), ..., f_m(x) \right)$
，

F

¯

(

x

)

=

(

f

¯

1

(

x

)

,

.

.

.

,

f

¯

m

(

x

)

)

(

)

(

)

(

)

)

$\bar{F}(x) = \left( \bar{f}_1(x), ..., \bar{f}_m(x) \right)$
满足两个约束：1）

F

¯

(

x

)

(

)

$\bar{F}(x)$
与

F

(

x

)

(

)

$F(x)$
具有相同的适应值，即，

g

p

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

=

g

p

t

c

h

(

F

¯

(

x

)

|

λ

,

z

∗

)

(

)

∗

)

(

)

∗

)

$g^{ptch} \left( F(x) | \lambda, z^* \right) = g^{ptch} \left( \bar{F}(x) | \lambda, z^* \right)$
；2）

F

¯

(

x

)

(

)

$\bar{F}(x)$
位于直线

L

3

3

$L_3$
上，如图1（f）所示。那么，

g

p

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

=

∥

∥

F

¯

(

x

)

−

z

∗

∥

∥

p

(

)

∗

)

‖

(

)

−

∗

‖

p

$g^{ptch} \left( F(x) | \lambda, z^* \right) = \left\| \bar{F}(x) - z^* \right\|_p$
（12）

证明

由

F

¯

(

x

)

(

)

$\bar{F}(x)$
的组成，我们能得到

g

p

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

=

=

=

1

)

g

p

t

c

h

(

F

¯

(

x

)

|

λ

,

z

∗

)

=

=

=

=

=

=

=

=

=

=

=

=

=

=

=

=

=

=

2

)

F

¯

(

x

)

is in

L

3

P

r

o

p

o

s

i

t

i

o

n

3.1

∥

∥

F

¯

(

x

)

−

z

∗

∥

∥

p

■

(

)

∗

)

===

)

(

)

∗

)

==================

)

(

)

is in

3.1

‖

(

)

−

∗

‖

◼

$g^{ptch} \left( F(x) | \lambda, z^* \right) \overset{1)}{===} g^{ptch} \left( \bar{F}(x) | \lambda, z^* \right) \overset{2)\ \bar{F}(x) \text{ is in } L_3 \ \ Proposition \ 3.1}{==================} \left\| \bar{F}(x) - z^* \right\|_p \ \ \ \ \ \ \blacksquare$

根据

F

¯

(

x

)

(

)

$\bar{F}(x)$
的两个约束，我们能得到

F

¯

(

x

)

=

(

f

¯

1

(

x

)

,

.

.

.

,

f

¯

m

(

x

)

)

=

z

∗

+

g

p

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

⋅

λ

(

)

(

)

(

)

∗

(

)

∗

)

⋅

λ

$\bar{F}(x) = \left( \bar{f}_1(x), ..., \bar{f}_m(x) \right) = z^* + g^{ptch} \left( F(x) | \lambda, z^* \right) \cdot \lambda$

例如，给定

p

=

2

2

$p=2$
，

F

(

x

)

=

(

0.5

,

2

)

(

)

(

0.5

)

$F(x) = (0.5, 2)$
，

λ

=

(

1

/

5

–

√

,

2

/

5

–

√

)

(

)

$\lambda = ( 1/ \sqrt{5}, 2/\sqrt{5} )$
，及

z

∗

=

(

0

,

0

)

∗

(

)

$z^* = (0,0)$
，我们可以计算

g

2

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

=

max

{

0.5

−

0

1

/

5

–

√

,

2

−

0

2

/

5

–

√

}

=

5

–

√

,

(

)

∗

)

max

{

0.5

−

}

,

$g^{2tch} \left( F(x) | \lambda, z^* \right) = \max \left\{ \dfrac{0.5 - 0}{1/\sqrt{5}}, \dfrac{2-0}{2/\sqrt{5}} \right\} = \sqrt{5},$

f

¯

1

(

x

)

=

z

∗

1

+

g

2

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

⋅

λ

1

=

0

+

5

–

√

⋅

1

/

5

–

√

=

1

,

(

)

∗

(

)

∗

)

⋅

,

$\bar{f}_1(x) = z^*_1 + g^{2tch} \left( F(x) | \lambda, z^* \right) \cdot \lambda_1 = 0 + \sqrt{5} \cdot 1 / \sqrt{5} = 1,$

f

¯

2

(

x

)

=

z

∗

2

+

g

2

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

⋅

λ

2

=

0

+

5

–

√

⋅

2

/

5

–

√

=

2.

(

)

∗

(

)

∗

)

⋅

2.

$\bar{f}_2(x) = z^*_2 + g^{2tch} \left( F(x) | \lambda, z^* \right) \cdot \lambda_2 = 0 + \sqrt{5} \cdot 2 / \sqrt{5} = 2.$

B. 改进Tchebycheff分解与

$p$
-Tch的关系

改进Tchebycheff分解与

$p$

p

$p$
-Tch在构造子问题时具有相似之处，即，

g

p

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

=

=

=

=

=

=

λ

=

w

∥

w

∥

p

g

p

t

c

h

(

F

(

x

)

|

w

∥

w

∥

p

,

z

∗

)

(

)

∗

)

======

‖

(

)

‖

∗

)

$g^{ptch} \left( F(x) | \lambda, z^* \right) \overset{\lambda = \frac{w}{\left\| w \right\|_p}}{======} g^{ptch} \left( F(x) | \dfrac{w}{\left\|w\right\|_p}, z^* \right)$

=

=

=

(

8

)

max

1

≤

i

≤

m

⎧

⎩

⎨

f

i

(

x

)

−

z

∗

i

w

i

∥

w

∥

p

⎫

⎭

⎬

=

∥

w

∥

p

⋅

max

1

≤

i

≤

m

{

f

i

(

x

)

−

z

∗

i

w

i

}

(

)

max

≤

{

(

)

−

∗

‖

}

‖

⋅

max

≤

{

(

)

−

∗

}

$\overset{(8)}{===} \max \limits_{1 \leq i \leq m} \left\{ \dfrac{f_i(x) - z^*_i}{\frac{w_i}{\left\|w\right\|_p}} \right\} = \left\| w \right\|_p \cdot \max\limits_{1 \leq i \leq m} \left\{ \dfrac{f_i(x) - z^*_i}{w_i} \right\}$

=

=

=

(

5

)

∥

w

∥

p

⋅

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

(

)

‖

⋅

(

)

∗

)

$\overset{(5)}{===} \left\| w \right\|_p \cdot g^{mtch} \left( F(x) | w, z^* \right)$
（13）

其中，

$p$
-Tch与改进Tchebycheff分解的不同之处在于产生权重因子

${‖ w ‖}_{p}$

{‖ w ‖}_{p}

$\left\| w \right\|_p$
的方法。

式（13）可以被一般化。更具体来说，若

g

(

F

(

x

)

|

w

,

z

∗

)

(

)

∗

)

$g \left( F(x) | w, z^* \right)$
表示一个分解方法（如，传统Tchebycheff分解，改进Tchebycheff分解，加权和方法【20】或PBI方法【3】）的子问题，那么，那么一个泛化的子问题目标函数可以定义为

c

(

w

)

⋅

g

(

F

(

x

)

|

w

,

z

∗

)

(

)

⋅

(

)

∗

)

$c (w) \cdot g \left( F(x) | w, z^* \right)$
，其中，

c

(

w

)

(

)

$c(w)$
为只依赖于权重向量

$w$
的系数，且对于任何

$w$

w

$w$
有

c

(

w

)

>

0

(

)

0

$c(w) > 0$
。在

$p$
-Tch中，

$c (w) = {‖ w ‖}_{p}$

c (w) = {‖ w ‖}_{p}

$c(w) = \left\| w \right\|_p$
。

这里写图片描述

C. 提出的泛化子问题的优点

泛化子问题相比于原始子问题的优点在于泛化能够调整子问题在竞争中的重要性/权重，这对应其被后代解更新的几率。

1）通过划分可行目标空间调节子问题的重要性：

c

(

w

)

(

)

$c(w)$
能被看作为子问题的权重/重要性。子问题偏好区域的定义可以介绍如下：

Υ

i

=

{

F

(

x

)

|

x

∈

Ω

,

arg

min

1

≤

i

≤

N

{

c

(

w

j

)

⋅

g

(

F

(

x

)

|

w

j

,

z

∗

)

}

=

i

}

{

(

)

∈

arg

⁡

min

≤

{

(

)

⋅

(

)

∗

)

}

}

$\Upsilon^i = \left\{ F(x) | x \in \Omega, \arg\min\limits_{1 \leq i \leq N} \left\{ c\left( w^j \right) \cdot g \left( F(x) | w^j, z^* \right) \right\} = i \right\}$
（14）

其中，

$N$
为子问题的个数。在

$Υ^{i}$

Υ^{i}

$\Upsilon^i$
中，

c

(

w

i

)

⋅

g

(

F

(

x

)

|

w

i

,

z

∗

)

(

)

⋅

(

)

∗

)

$c\left( w^i \right) \cdot g \left( F(x) | w^i, z^* \right)$
为所有

c

(

w

j

)

⋅

g

(

F

(

x

)

|

w

j

,

z

∗

)

,

j

=

1

,

.

.

.

,

N

(

)

⋅

(

)

∗

)

N

$c\left( w^j \right) \cdot g \left( F(x) | w^j, z^* \right),\ j=1,...,N$
中的最小的。其他定义子问题偏好区域的方法可参见【25,26】。

这里写图片描述

基于（14），

c

(

w

)

(

)

$c(w)$
对于用改进Tchebycheff分解划分可行目标空间的影响如图2和表I所示。

在图2，使用了

c

(

w

)

=

∥

w

∥

4

p

(

)

‖

4

$c(w) = \left\| w \right\|^4_p$
且

$p$
在三张子图中分别被设为

$0.1$

0.1

$0.1$
，

$0.5$
，和

$1.5$
。图表表明，提高

$p$
值会缩小边界问题的偏好区域，即，与

$w^{1}$

w^{1}

$w^1$
和

w

3

3

$w^3$
关联的子问题，会增加居间问题的偏好区域，即，与

w

2

2

$w^2$
关联的第二个子问题。表I总结了泛化子问题偏好区域占可行目标空间的比率。

调节

c

(

w

)

(

)

$c(w)$
能调整子问题偏好区域，因此，更多的更新机会会被分配到更感兴趣的子问题从而加速其收敛。例如，MOEA/D用三个子问题在双目标ZDT4【27】和DTLZ4【28】问题的测试如图2所示。广泛使用的模拟二进制交叉（simulated binary crossover，SBX）和多项式变异（polynomial mutation）【29】应用于生成子代。使用

c

(

w

)

(

)

$c(w)$
的不同设定，关联于

w

1

1

$w^1$
的第一个子问题拥有最大的偏好区域，示于图2（a），且收敛最快，示于图3（a）和（b），这对应于

c

(

w

)

=

∥

w

∥

4

0.1

(

)

‖

0.1

4

$c(w) = \left\| w \right\|^4_{0.1}$
。同样地，当

c

(

w

)

=

∥

w

∥

4

1.5

(

)

‖

1.5

4

$c(w) = \left\| w \right\|^4_{1.5}$
时，第二个子问题具有三者中最大的偏好区域，如图2所示，并取得了最快的收敛率，如图3（c）和（d）所示。观察可以得出，具有更大偏好区域的子问题更有可能被频繁更新，不断被改善，这将导致更快的收敛率。

这里写图片描述

提升划分全部子问题改善空间的均匀度：

为阐明这一问题，基于最大适应度提升标准，我们首次如下给出子问题改善区域的定义：

Υ

i

=

{

F

(

y

)

|

y

∈

Ω

,

g

(

F

(

y

)

|

w

i

,

z

∗

)

<

g

(

F

(

x

i

)

|

w

i

,

z

∗

)

,

{

(

)

∈

(

)

∗

)

(

)

∗

)

,

$\Upsilon^i = \left\{ F(y) | y \in \Omega, g \left( F(y) | w_i, z^* \right) < g \left( F\left(x^i \right) | w^i, z^* \right), \right.$

i

=

arg

max

1

≤

j

≤

N

{

c

(

w

)

⋅

[

g

(

F

(

x

i

)

|

w

j

,

z

∗

)

−

g

(

F

(

y

)

|

w

j

,

z

∗

)

]

}

}

arg

⁡

max

≤

{

(

)

⋅

[

(

)

∗

)

−

(

)

∗

)

]

}

}

$\left. i = \arg\max\limits_{1 \leq j \leq N} \left\{ c(w) \cdot \left[ g \left( F \left( x^i \right) | w^j, z^* \right) - g \left( F(y) | w^j, z^* \right) \right] \right\} \right\}$

其中，

x

i

i

$x^i$
为第

$i$
个子问题的当前解。不等式

$g (F (y) | w^{i}, z^{*}) < g (F (x) | w^{i}, z^{*})$

g (F (y) | w^{i}, z^{*}) < g (F (x) | w^{i}, z^{*})

$g \left( F(y) | w^i, z^* \right) < g \left( F(x) | w^i, z^* \right)$
表明子代

$y$
对于第

$i$

i

$i$
个子问题比当前解

$x$
具有更好的适应值。（15）中最后的约束确认取得最大适应值提升的子问题。

这里写图片描述

一个所有子问题提升区域的示例如图4（d）所示。通过使用（15）和改进Tchebycheff分解，

$c (w)$

c (w)

$c(w)$
对所有子问题提升区域的划分的影响示于图4（a）-（c）。使用了

c

(

w

)

=

∥

w

∥

p

(

)

‖

p

$c(w) = \left\| w \right\|_p$
，且在图4（a）-（c）中2，

$p$
分别被设为

$1 / 3$

1 / 3

$1/3$
，

$1$
，和

$3$

3

$3$
。结果表明，提升

$p$
值能提升划分所有子问题提升区域的均匀度。此现象对于可行目标空间的边界区域更为明显，即，图4（a）-（c）中的

$Υ^{1}$

Υ^{1}

$\Upsilon^1$
和

Υ

4

4

$\Upsilon^4$
。

通过

c

(

w

)

(

)

$c(w)$
，算法能够调节提升区域的均匀度以提高算法的性能。一个简单的示例如图4（a）-（c）所示，其中，MOEA/D融合了使用不同

c

(

w

)

(

)

$c(w)$
设定的四个均匀的子问题。双目标ZDT4和DTLZ4问题被选作测试问题。多项式变异和SBX应用于生成子代。第

$i$
个子问题的当前解将被子代

$y$

y

$y$
更新，若其对应的目标向量位于

Υ

i

i

$\Upsilon^i$
。提升区域的均匀划分将使所有的子问题得到更好的一般结果，如图4（e）-（f）所示。

IV. 基于最大适应值改善的种群更新策略

种群更新机制是MOEAs的关键组成，近年来已被充分研究。例如，基于差分进化（differential evolution，DE）【17】的MOEA/D，其限制了一个子代解能更新的父代解的数目。自适应全局替换MOEA/D（MOEA/D with an adaptive global replacement，MOEA/D-AVR）【19】基于最小函数值用一个新生成解替换父代解。基于稳定匹配模型的MOEA/D【30】在更新种群时，使用了一个稳定匹配模型来使每个子问题与一个单一解匹配，因此不同子问题有不同解。为提升种群的多样性，Li等人【31】进一步提出了基于交互关系的选择来选取精英解使其在进化过程中存活。基于一种泛化资源调度策略的MOEA/D【32】使用一种全局替换策略更新子问题解。这些种群更新策略已成功地提升了MOEA/D的性能，然而，它们大多是设计用于只是优化了一部分子问题的表现【17】【19】【32】。

这里写图片描述

为提升算法性能，本文提出了一种基于最大适应值提升的全局种群更新策略，示于算法1。尤其，对于目标子问题给定一般解

$\mathbf{y}$
，在算法1的前两步，

$\mathbf{y}$
能够取得最大适应值提升的子问题

$l$
可以识别如下

$l = \underset{1 \leq i \leq N}{\arg max} {g^{p t c h} (F (x^{i}) | λ^{i}, z^{*}) - g^{p t c h} (F (y) | λ^{i}, z^{*})}$

l = \underset{1 \leq i \leq N}{\arg max} {g^{p t c h} (F (x^{i}) | λ^{i}, z^{*}) - g^{p t c h} (F (y) | λ^{i}, z^{*})}

$l=\underset{1 \leq i \leq N}{\arg \max} \left\{ g^{ptch} \left( \mathbf{F} \left( \mathbf{x}^i \right) | \mathbf{\lambda}^i, \mathbf{z}^* \right) - g^{ptch} \left( \mathbf{F} \left( \mathbf{y} \right) | \mathbf{\lambda}^i, \mathbf{z}^* \right) \right\}$
(16)

之后，在第3步，相应的解

x

l

l

$\mathbf{x}^l$
被

$\mathbf{y}$
替换，若

$\mathbf{y}$
在子问题

$l$
的表现优于

$x^{l}$

x^{l}

$\mathbf{x}^l$
。最后，为提升所提出的算法的鲁棒性，少量的父代解（不超过一个预定义的数目

n

r

−

1

−

1

$n_r-1$
）同样被随机选择并被

$\mathbf{y}$
替换，如第4步所示。使用不同

$p$
-Tchs的影响在实验研究中被考察，其基于如下公式：

$g^{p t c h} (F (x^{i}) | λ^{i}, z) - g^{p t c h} (F (y) | λ^{i}, z) {======}_{w^{i} = λ^{i} / ‖ λ^{i} ‖_{1}}^{(13)} ‖ w^{i} ‖_{p} \cdot [g^{m t c h} (F (x^{i}) | w^{i}, z) - g^{m t c h} (F (y) | w^{i}, z)]$

g^{p t c h} (F (x^{i}) | λ^{i}, z) - g^{p t c h} (F (y) | λ^{i}, z) {======}_{w^{i} = λ^{i} / ‖ λ^{i} ‖_{1}}^{(13)} ‖ w^{i} ‖_{p} \cdot [g^{m t c h} (F (x^{i}) | w^{i}, z) - g^{m t c h} (F (y) | w^{i}, z)]

$g^{ptch} \left( \mathbf{F} \left( \mathbf{x}^i \right) | \mathbf{\lambda}^i, \mathbf{z} \right) - g^{ptch} \left( \mathbf{F} \left( \mathbf{y} \right) | \mathbf{\lambda}^i, \mathbf{z} \right) {======}_{\mathbf{w}^i={\lambda}^i/\|\lambda^i\|_1}^{(13)} \|\mathbf{w}^i\|_p \cdot \left[ g^{mtch} \left( \mathbf{F} \left( \mathbf{x}^i \right) | \mathbf{w}^i, \mathbf{z} \right) - g^{mtch} \left( \mathbf{F} \left( \mathbf{y} \right) | \mathbf{w}^i, \mathbf{z} \right) \right]$

算法1给出的种群更新策略基于

$p$
-Tch，但是，在实验研究中使用的是2-Tch。选择

$p = 2$

p = 2

$p=2$
的原因是，首先

$p$
应该大于1，以提升子问题更新区域的均匀度，并且，

$p = 2$

p = 2

$p=2$
优于

p

>

2

2

$p>2$
，因为，相比于其他更大的

$p$
值，在2-Tch中，对于欧氏距离来说，子问题目标函数具有一个更加清晰的几何属性。2-Tch的一个子问题定义如下：

$min_{x \in Ω} g^{2 t c h} (F (x) | λ, z^{*}) = max_{1 \leq i \leq m} {\frac{f_{i} (x) - z_{i}^{*}}{λ_{i}}}$

min_{x \in Ω} g^{2 t c h} (F (x) | λ, z^{*}) = max_{1 \leq i \leq m} {\frac{f_{i} (x) - z_{i}^{*}}{λ_{i}}}

$\min\limits_{\mathbf{x} \in \Omega} g^{2tch} \left( \mathbf{F} \left( \mathbf{x} \right) | \mathbf{\lambda}, \mathbf{z}^* \right) = \max\limits_{1 \leq i \leq m} \left\{ \frac{f_i \left( \mathbf{x} \right) - z^*_i}{\lambda_i} \right\}$
(17)

其中，

λ

=

(

λ

1

,

…

,

λ

m

)

(

…

)

$\mathbf{\lambda} = \left( \lambda_1, \ldots, \lambda_m \right)$
且

∥

λ

∥

2

=

1

‖

1

$\| \mathbf{\lambda} \|_2 = 1$
及

λ

1

,

…

,

λ

m

≥

0

…

≥

0

$\lambda_1, \ldots, \lambda_m \geq 0$
。

这里写图片描述

在算法1中，适应值的提升使用

g

p

t

c

h

(

F

(

x

i

)

|

λ

i

,

z

)

−

g

p

t

c

h

(

F

(

y

)

|

λ

i

,

z

)

(

)

−

(

)

)

$g^{ptch} \left( \mathbf{F} \left( \mathbf{x}^i \right) | \mathbf{\lambda}^i, \mathbf{z} \right) - g^{ptch} \left( \mathbf{F} \left( \mathbf{y} \right) | \mathbf{\lambda}^i, \mathbf{z} \right)$
进行计算。此适应值提升在2-Tch的相应的几何属性示于图5。按照命题6，适应值提升计算如下：

g

2

t

c

h

(

F

(

x

i

)

|

λ

i

,

z

)

−

g

2

t

c

h

(

F

(

y

)

|

λ

i

,

z

)

=

∥

F

¯

¯

¯

¯

(

x

i

)

−

z

∥

2

−

∥

F

¯

¯

¯

¯

(

y

)

−

z

∥

2

=

∥

F

¯

¯

¯

¯

(

x

i

)

−

F

¯

¯

¯

¯

(

y

)

∥

2

(

)

−

(

)

‖

(

)

−

‖

−

‖

(

)

−

‖

(

)

−

(

)

‖

2

$g^{2tch} \left( \mathbf{F} \left( \mathbf{x}^i \right) | \mathbf{\lambda}^i, \mathbf{z} \right) - g^{2tch} \left( \mathbf{F} \left( \mathbf{y} \right) | \mathbf{\lambda}^i, \mathbf{z} \right) = \| \overline{\mathbf{F}} \left( \mathbf{x}^i \right) - \mathbf{z} \|_2 - \| \overline{\mathbf{F}} \left( \mathbf{y} \right) - \mathbf{z} \|_2 = \| \overline{\mathbf{F}} \left( \mathbf{x}^i \right) - \overline{\mathbf{F}} \left( \mathbf{y} \right) \|_2$

其中

F

¯

¯

¯

¯

(

x

i

)

=

z

+

g

2

t

c

h

(

F

(

x

i

)

|

λ

i

,

z

)

⋅

λ

i

(

)

(

)

⋅

i

$\overline{\mathbf{F}} \left( \mathbf{x}^i \right) = \mathbf{z} + g^{2tch} \left( \mathbf{F} \left( \mathbf{x}^i \right) | \mathbf{\lambda}^i, \mathbf{z} \right) \cdot \lambda^i$

F

¯

¯

¯

¯

(

y

)

=

z

+

g

2

t

c

h

(

F

(

y

)

|

λ

i

,

z

)

⋅

λ

i

(

)

(

)

⋅

i

$\overline{\mathbf{F}} \left( \mathbf{y} \right) = \mathbf{z} + g^{2tch} \left( \mathbf{F} \left( \mathbf{y} \right) | \mathbf{\lambda}^i, \mathbf{z} \right) \cdot \lambda^i$

其实，这是

F

¯

¯

¯

¯

(

y

)

(

)

$\overline{\mathbf{F}} \left( \mathbf{y} \right)$
到

F

¯

¯

¯

¯

(

x

i

)

(

)

$\overline{\mathbf{F}} \left( \mathbf{x}^i \right)$
的距离，如图5所示。

与其他两种具有代表性策略，即MOEA/D-AGR使用的基于最小适应值的策略与MOEA/D使用的随机提升策略，所提出的基于最大适应值提升的策略具有如下优点：

这里写图片描述

好的子代个体在提出的策略中能够存活更长时间。为解释这一点，适应值提升与适应值的区别首先可以使用一个双目标优化问题在图6进行说明。比如，在用一个子代

$\mathbf{y}$
更新了一个特定子问题

$i$
之后，相应的适应值提升

$g^{2 t c h} (F (x^{i}) | λ^{i}, z) - g^{2 t c h} (F (y) | λ^{i}, z)$
提出的策略提升了在所有子问题上的泛化性能，即，

∑

N

i

=

1

g

2

t

c

h

(

F

(

x

i

)

|

λ

i

,

z

∗

)

令所有三个比较的策略由同一初始种群

$\mathbf{A}$
开始，一个新生成的子代解

$\mathbf{y}$
用于只替换一个父代解。不失一般性，提出的基于最大适应值提升的策略应该更新子问题

$l$
，而其他两种策略更新子问题

$j$

j

$j$
。根据（16）中最大适应值提升的定义，很明显：

g

2

t

c

h

(

F

(

x

l

)

|

λ

l

,

z

)

−

g

2

t

c

h

(

F

(

y

)

|

λ

l

,

z

)

≥

g

2

t

c

h

(

F

(

x

j

)

|

λ

j

,

z

)

−

g

2

t

c

h

(

F

(

y

)

|

λ

j

,

z

)

(

)

−

(

)

≥

(

)

−

(

)

)

$g^{2tch} \left( \mathbf{F} \left( \mathbf{x}^l \right) | \mathbf{\lambda}^l, \mathbf{z} \right) - g^{2tch} \left( \mathbf{F} \left( \mathbf{y} \right) | \mathbf{\lambda}^l, \mathbf{z} \right) \geq g^{2tch} \left( \mathbf{F} \left( \mathbf{x}^j \right) | \mathbf{\lambda}^j, \mathbf{z} \right) - g^{2tch} \left( \mathbf{F} \left( \mathbf{y} \right) | \mathbf{\lambda}^j, \mathbf{z} \right)$

相应地，更新子问题

$l$
得到的新种群的适应值和小于或等于更新子问题

$j$

j

$j$
的，即：

(

)

−

(

)

(

)

≤

(

)

−

(

)

(

)

)

$g^{2tch} \left( \mathbf{F} \left( \mathbf{A} \right) | \mathbf{D}, \mathbf{z} \right) - g^{2tch} \left( \mathbf{F} \left( \mathbf{x}^l \right) | \mathbf{\lambda}^l, \mathbf{z} \right) + g^{2tch} \left( \mathbf{F} \left( \mathbf{y} \right) | \mathbf{\lambda}^l, \mathbf{z} \right) \leq g^{2tch} \left( \mathbf{F} \left( \mathbf{A} \right) | \mathbf{D}, \mathbf{z} \right) - g^{2tch} \left( \mathbf{F} \left( \mathbf{x}^j \right) | \mathbf{\lambda}^j, \mathbf{z} \right) + g^{2tch} \left( \mathbf{F} \left( \mathbf{y} \right) | \mathbf{\lambda}^j, \mathbf{z} \right)$

换句话说，提出的策略能够在所有子问题上得到更好的一般性能，相比于另外两种在MOEA/D和MOEA/D-AGR使用的更新策略。

V. 提出的MOEA/D-2TCHMFI的细节

这里写图片描述

2-Tch与提出的基于最大适应值改进的种群更新策略被组合到MOEA/D框架中，以组成新算法，称为MOEA/D-2TCHMFI。MOEA/D-2TCHMFI致力于就解的收敛性而言，提升MOEA/D，在算法2进行了概述。权重向量/方向向量的选择对于寻找在PF均匀分布的解是关键的。对于一个分解方法，权重的一种最优分布能够根据【5】-【7】得到，若一个MOP的PF的几何形状是事先知道的，且提供了分布良好的Pareto最优解集的清晰定义的话。

这里写图片描述

在算法2中，步骤1设置方向向量

{

λ

1

,

…

,

λ

N

}

…

}

$\left\{ \lambda^1, \ldots, \lambda^N \right\}$
如下：

λ

i

=

w

i

∥

w

i

∥

2

,

i

=

1

,

…

,

N

‖

…

N

$\lambda^i = \frac{\mathbf{w}^i}{\| \mathbf{w}^i \|_2},\ i=1,\ldots,N$

其中，

{

w

1

,

…

,

w

N

}

…

}

$\left\{\mathbf{w}^1,\ldots,\mathbf{w}^N \right\}$
为由【3】中建议的方法随机生成的权重向量。均匀权重向量

{

w

1

,

…

,

w

N

}

…

}

$\left\{\mathbf{w}^1,\ldots,\mathbf{w}^N \right\}$
及相应的方向向量

{

λ

1

,

…

,

λ

N

}

…

}

$\left\{\mathbf{\lambda}^1,\ldots,\mathbf{\lambda}^N \right\}$
的可视化在图8中。步骤2仅选择了

⌊

N

/

5

⌋

⌋

$\lfloor N/5 \rfloor$
子问题，这基于它们在每一代生成子代的最近的表现。步骤3使用2-Tch与基于最大适应值提升标准的种群更新策略来迭代地进化选择的子问题。尤其地，在步骤3.1中，每个子问题通过主要来自其邻域的子问题的信息进行优化。参考点

$\mathbf{z}$
在步骤3.2更新，父代解在步骤3.3根据算法1进行更新。在步骤3.4中，若代数

g

e

n

n

$gen$
可以被

$30$
整除，子问题

$i$
的适应值在近30代的相应的减少计算如下：

$Δ_{i} = \frac{g^{2 t c h} (F (x^{i, g e n - 30}) | λ^{i}, z) - g^{2 t c h} (F (x^{i, g e n}) | λ^{i}, z)}{g^{2 t c h} (F (x^{i, g e n - 30}) | λ^{i}, z)}$

Δ_{i} = \frac{g^{2 t c h} (F (x^{i, g e n - 30}) | λ^{i}, z) - g^{2 t c h} (F (x^{i, g e n}) | λ^{i}, z)}{g^{2 t c h} (F (x^{i, g e n - 30}) | λ^{i}, z)}

$\Delta_i = \frac{g^{2tch} \left( \mathbf{F} \left( \mathbf{x}^{i,gen-30} \right) | \mathbf{\lambda}^i, \mathbf{z} \right) - g^{2tch} \left( \mathbf{F} \left( \mathbf{x}^{i,gen} \right) | \mathbf{\lambda}^i, \mathbf{z} \right)}{g^{2tch} \left( \mathbf{F} \left( \mathbf{x}^{i,gen-30} \right) | \mathbf{\lambda}^i, \mathbf{z} \right)}$

其中，

x

i

,

g

e

n

n

$\mathbf{x}^{i,gen}$
与

x

i

,

g

e

n

−

30

−

30

$\mathbf{x}^{i,gen-30}$
分别为在当前代与代数

g

e

n

−

30

−

30

$gen-30$
时子问题

$i$
的解。根据【16】，MOEA/D-2TCHMFI基于

$Δ_{i}$

Δ_{i}

$\Delta_i$
更新每个子问题

π

i

,

i

=

1

,

…

,

N

…

N

$\pi_i,\ i=1,\ldots,N$
，如下：

π

i

=

1

,

i

f

Δ

i

>

0.001

0.001

$\pi_i = 1, if\ \Delta_i > 0.001$

π

i

=

(

0.95

+

0.05

×

Δ

i

0.001

)

×

π

i

,

o

t

h

e

r

w

i

s

e

(

0.95

0.05

0.001

)

e

$\pi_i = \left( 0.95 + 0.05 \times \frac{\Delta_i}{0.001} \right) \times \pi_i, otherwise$

最后，在步骤4，若达到预定义的最大适应值评估次数，算法终止。

VI. 基于2-Tch的一元

R

2

为证实所提算法的有效性，本节介绍了一种基于2-Tch的

R

2

2

$R_2$
指标。

R

2

2

$R_2$
首先由Hanson与Jaszkiewicz【15】在1998年提出。最近，

R

2

2

$R_2$
指标日益吸引到了研究兴趣【33】-【38】。

R

2

2

$R_2$
指标的大多数研究【15】，【34】-【38】是基于传统的Tchebycheff分解的，少数【33】基于改进的Tchebycheff分解。然而，基于这两种Tchebycheff分解方法的

R

2

2

$R_2$
指标的几何属性并不易懂。在这里，具有更清晰的几何属性的新的

R

2

2

$R_2$
指标被提出以估计超体积度量，如下：

R

2

t

c

h

2

(

A

|

z

∗

)

=

∫

λ

∈

Λ

min

F

(

x

)

∈

A

{

g

2

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

}

d

u

∫

Λ

d

u

(

∗

)

∫

∈

min

(

)

∈

{

(

)

∗

)

}

∫

u

$R_2^{2tch} \left( \mathbf{A} | \mathbf{z}^* \right) = \frac{\underset{\lambda \in \Lambda}{\int} \underset{\mathbf{F} \left( \mathbf{x} \right) \in \mathbf{A}}{\min} \left\{ g^{2tch} \left( \mathbf{F} \left( \mathbf{x} \right) | \lambda, \mathbf{z}^* \right) \right\} du}{\int_{\mathbf{\Lambda}}du}$
(18)

其中

Λ

=

{

λ

=

(

λ

1

,

…

,

λ

m

)

|

λ

i

≥

0

,

i

=

1

,

…

,

m

,

∥

λ

∥

2

=

1

}

{

(

…

)

≥

…

‖

}

$\Lambda = \left\{ \lambda = \left( \lambda_1,\ldots,\lambda_m \right) | \lambda_i \geq 0, \ i=1,\ldots,m,\ \|\lambda\|_2=1 \right\}$

且

d

u

u

$du$
为在

$\Lambda$
上的Lebesgue度量【39】。若没有决策者（DM）的参考信息，可以合理地假定方向向量

$\lambda$
服从

$\Lambda$
上的一个均匀分布。

∫

Λ

d

u

u

$\int_{\mathbf{\Lambda}}du$
等于

2

−

m

−

m

$2^{-m}$
倍的

$m$
维单位超球的表面积，因为

$Λ$

Λ

$\Lambda$
为单位超球表面在第一象限的部分，其中，

$m$
为目标函数的数目。子问题目标函数

$g^{2 t c h} (F (x) | λ, z^{*})$

g^{2 t c h} (F (x) | λ, z^{*})

$g^{2tch} \left( \mathbf{F} \left( \mathbf{x} \right) | \lambda, \mathbf{z}^* \right)$
可看作为DM的一个效用函数/参照【20】。给定种群

$\mathbf{A}$
的所有个体中的选择权，DM倾向于选择具有

min

F

(

x

)

∈

A

{

g

2

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

}

(

)

∈

{

(

)

∗

)

}

${\min}_{\mathbf{F} \left( \mathbf{x} \right) \in \mathbf{A}} \left\{ g^{2tch} \left( \mathbf{F} \left( \mathbf{x} \right) | \lambda, \mathbf{z}^* \right) \right\}$
的那一个，示于图9（a）。

R

2

t

c

h

2

(

A

|

z

∗

)

(

∗

)

$R_2^{2tch} \left( \mathbf{A} | \mathbf{z}^* \right)$
越小，DM所期望的效用/参照就越好。

这里写图片描述

所提出的

R

2

t

c

h

2

h

$R_2^{2tch}$
度量的几何属性示于图9（b）。尤其，一个点

P

¯

¯

¯

¯

i

i

$\overline{\mathbf{P}}^i$
被引入以便于

min

F

(

x

)

∈

A

{

g

2

t

c

h

(

F

(

x

)

|

λ

i

,

z

∗

)

}

(

)

∈

{

(

)

∗

)

}

${\min}_{\mathbf{F} \left( \mathbf{x} \right) \in \mathbf{A}} \left\{ g^{2tch} \left( \mathbf{F} \left( \mathbf{x} \right) | \lambda^i, \mathbf{z}^* \right) \right\}$
的计算，即：

min

F

(

x

)

∈

A

{

g

2

t

c

h

(

F

(

x

)

|

λ

i

,

z

∗

)

}

=

∥

P

¯

¯

¯

¯

i

−

z

∗

∥

2

(

)

∈

{

(

)

∗

)

}

‖

−

∗

‖

2

$\underset{\mathbf{F} \left( \mathbf{x} \right) \in \mathbf{A}}{\min} \left\{ g^{2tch} \left( \mathbf{F} \left( \mathbf{x} \right) | \lambda^i, \mathbf{z}^* \right) \right\} = \|\overline{\mathbf{P}}^i - \mathbf{z}^* \|_2$

很容易证明：

R

2

t

c

h

2

(

A

|

z

∗

)

≈

∑

M

i

=

1

min

F

(

x

)

∈

A

{

g

2

t

c

h

(

F

(

x

)

|

λ

i

,

z

∗

)

}

M

(

∗

)

≈

∑

min

(

)

∈

{

(

)

∗

)

}

M

$R_2^{2tch} \left( \mathbf{A} | \mathbf{z}^* \right) \approx \frac{\sum_{i=1}^M \underset{\mathbf{F} \left( \mathbf{x} \right) \in \mathbf{A}}{\min} \left\{ g^{2tch} \left( \mathbf{F} \left( \mathbf{x} \right) | \lambda^i, \mathbf{z}^* \right) \right\}}{M}$

=

∑

M

i

=

1

∥

P

¯

¯

¯

¯

i

−

z

∗

∥

2

M

∑

‖

−

∗

‖

M

$= \frac{\sum_{i=1}^M \|\overline{\mathbf{P}}^i - \mathbf{z}^* \|_2}{M}$

其中，

$M$
为方向向量集的大小。因此，所提出的

$R_{2}^{2 t c h} (A | z^{*})$

R_{2}^{2 t c h} (A | z^{*})

$R_2^{2tch} \left( \mathbf{A} | \mathbf{z}^* \right)$
指标的几何属性实际上为连接

z

∗

∗

$\mathbf{z}^*$
与

P

¯

¯

¯

¯

i

i

$\overline{\mathbf{P}}^i$
的线段的平均长度。

P

¯

¯

¯

¯

i

i

$\overline{\mathbf{P}}^i$
的分布很适合估计集

A

=

{

x

1

,

x

2

,

x

3

,

x

4

}

{

}

$\mathbf{A} = \left\{ \mathbf{x}^1,\mathbf{x}^2,\mathbf{x}^3,\mathbf{x}^4 \right\}$
的超体的表面。按【35】的建议，

R

2

t

c

h

2

(

A

|

z

∗

)

(

∗

)

$R_2^{2tch} \left( \mathbf{A} | \mathbf{z}^* \right)$
能够用于估计集

$\mathbf{A}$
的超体积。（20）中的一个简化的形式的解释提供于补充材料的附录A中。如补充材料的附录B所证明，所提出的一元指标

R

2

t

c

h

2

h

$R_2^{2tch}$
（DM所期望的效用/参考）是对于Pareto占优严格单调的，这对于一种评估指标【40】是必要的。

这里写图片描述

基于2-Tch的

R

2

2

$R_2$
指标对于另外两种基于传统Tchebycheff分解和改进的Tchebycheff分解的指标的优势示于图10。通过分别用

g

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

(

)

∗

)

$g^{tch} \left( \mathbf{F} \left( \mathbf{x} \right) | \mathbf{w}, \mathbf{z}^* \right)$
与

g

m

t

c

h

(

F

(

x

)

|

w

,

z

∗

)

(

)

∗

)

$g^{mtch} \left( \mathbf{F} \left( \mathbf{x} \right) | \mathbf{w}, \mathbf{z}^* \right)$
替换（18）中的

g

2

t

c

h

(

F

(

x

)

|

λ

,

z

∗

)

(

)

∗

)

$g^{2tch} \left( \mathbf{F} \left( \mathbf{x} \right) | \lambda, \mathbf{z}^* \right)$
，可以令

R

t

c

h

2

(

A

|

z

∗

)

(

∗

)

$R_2^{tch} \left( \mathbf{A} | \mathbf{z}^* \right)$
与

R

m

t

c

h

2

(

A

|

z

∗

)

(

∗

)

$R_2^{mtch} \left( \mathbf{A} | \mathbf{z}^* \right)$
分别表示这两种指标。图10展示了

R

2

t

c

h

2

(

A

|

z

∗

)

(

∗

)

$R_2^{2tch} \left( \mathbf{A} | \mathbf{z}^* \right)$
，

R

t

c

h

2

(

A

|

z

∗

)

(

∗

)

$R_2^{tch} \left( \mathbf{A} | \mathbf{z}^* \right)$
与

R

m

t

c

h

2

(

A

|

z

∗

)

(

∗

)

$R_2^{mtch} \left( \mathbf{A} | \mathbf{z}^* \right)$
在一个双目标优化问题中的几何含义。

R

2

t

c

h

2

(

A

|

z

∗

)

(

∗

)

$R_2^{2tch} \left( \mathbf{A} | \mathbf{z}^* \right)$
，

R

t

c

h

2

(

A

|

z

∗

)

(

∗

)

$R_2^{tch} \left( \mathbf{A} | \mathbf{z}^* \right)$
与

R

m

t

c

h

2

(

A

|

z

∗

)

(

∗

)

$R_2^{mtch} \left( \mathbf{A} | \mathbf{z}^* \right)$
分别为从理想点

z

∗

∗

$\mathbf{z}^*$
到曲线1-3的平均距离。可以从图10（a）看出，

R

2

t

c

h

2

(

A

|

z

∗

)

(

∗

)

$R_2^{2tch} \left( \mathbf{A} | \mathbf{z}^* \right)$
表示从理想点

z

∗

∗

$\mathbf{z}^*$
到非占优解集的超体表面的的平均距离。相比而言，

R

t

c

h

2

(

A

|

z

∗

)

(

∗

)

$R_2^{tch} \left( \mathbf{A} | \mathbf{z}^* \right)$
与

R

m

t

c

h

2

(

A

|

z

∗

)

(

∗

)

$R_2^{mtch} \left( \mathbf{A} | \mathbf{z}^* \right)$
均不能表明与非占优解集的分布的直观关系，示于图10（b）和（c）中。

VII. 实验研究

这里写图片描述

参考文献

这里写图片描述

摘要：

索引词

I. 引言

II. 两种关系密切的Tchebycheff分解方法

A. 传统Tchebycheff分解

B. 改进Tchebycheff分解

III. 提出的对方向向量进行 l p l p l_p -范式约束的Tchebycheff分解

A. p p p -Tch中的子问题目标函数的几何属性

B. 改进Tchebycheff分解与 p p p -Tch的关系

C. 提出的泛化子问题的优点

IV. 基于最大适应值改善的种群更新策略

V. 提出的MOEA/D-2TCHMFI的细节

VI. 基于2-Tch的一元 R 2 R 2 R_2 指标

VII. 实验研究

参考文献

你可能也喜欢

III. 提出的对方向向量进行

l

p

A.

$p$
-Tch中的子问题目标函数的几何属性

B. 改进Tchebycheff分解与

$p$
-Tch的关系

VI. 基于2-Tch的一元

R

2