http://www.ma-xy.com
目录
第一章 多目标规划 1
1.1 问题的引入与分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 模型规范化及其理论化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2.1 Pareto 最优解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 KT-有效集与 G-有效集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 最优性条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4
最优化算法
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4.1 线性加权和法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4.2 主要目标法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.3 极小化极大法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.4 理想点法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.5 分层排序法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 MATLAB 应用实例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1
http://www.ma-xy.com
第一章 多目标规划
1.1 问题的引入与分析
考虑在二次规划中引入的组合投资问题
min x
T
Qx
max r
T
x
s.t.
x = 1
0 ⩽ x ⩽ 1
可以发现，上面的引例中有两个优化目标，这种多个目标的规划问题即为多目标规划 (MOP)。
1.2 模型规范化及其理论化
多目标规划 (multi-objective programming, MOP) 是在变量满足给定约束的条件下，研究多
个目标函数同时极小化的问题，其一般形式为
min f(x) = (f
1
(x), f
2
(x), . . . , f
p
(x))
T
s.t.
h
i
(x) = 0 i ∈ E
g
j
(x) ⩾ 0 j ∈ I
其中：x ∈ R
n
为决策变量 (或称优化变量或自变量)。g
j
(x) 和 h
i
(x) 均为约束函数，I, E 为指标
集。I = {1, 2, . . . , m}, E = {1, 2, . . . , n}，f
i
(x) : R
n
→ R ，f 为向量值目标函数。记 MOP 的可
行域为
S = {x|x ∈ R
n
, g
j
(x) ⩾ 0, h
i
(x) = 0, i ∈ E, j ∈ I}
我们把 S 的像集 z = f(S) 称为目标可行域，即因变量域。z 中元素 z = f (x) 称为目标向
量，其中分量 z
i
= f
i
(x) 是第 i 个目标值。若每个 f
i
(i = 1, 2, . . . , p) 都是凸函数，并且可行域 S
是凸集，则 MOP 称为多目标凸规划问题。
T.C.Koopmans(1951) 在其关于数量经济学的工作中，从生产与分配的活动分析的角度提
出了多目标规划问题，并且第一次提出了 Pareto 解的概念。H.W.Kuhn 和 A.W.Tucker(1951)
1
http://www.ma-xy.com
1.2 模型规范化及其理论化 第一章 多目标规划
从数学规划的角度给出了 Pareto 解的概念，并研究了这种解的充分必要条件，奠定了多目标
规划的理论基础。后来，L.Hurwicz(1958) 将多目标规划的研究推广到一般的拓扑向量空间中。
L.A.Zadeh(1963) 从控制论的角度提出了多目标控制问题。
多目标规划的 3 个基本研究方向：(1) 解的概念和性质，从最早研究的有效集、弱有效集以
及 1951 年 Kuhn-Tucker 提出的真有效集开始，迄今，有一定影响的最优解的概念不少于 20 种。
对于每一种解的概念，可以考虑解的存在性、最优性条件、解的连通性与稳定性、以及解与解之
间的关系等；(2) 多目标规划的对偶问题，已存在多种多样的对偶形式。比如 Lagrange 对偶，共
轭对偶等；(3) 不可微多目标规划。已经有多种关于导数的推广概念可以应用于这方向的研究，比
如广义梯度、Dini 次微分等。
在讨论 MOP 最优解的概念之前，先引入下面的记号：∀x, y ∈ R
n
, xy ∈ z 为多目标函数值
x = y ⇔ x
i
= y
i
i ∈ {1, 2, . . . , n}
x ≺ y ⇔ x
i
⩽ y
i
i ∈ {1, 2, . . . , n}
但是，存在某个 j，使得 x
j
< y
j
x ≻ y ⇔ y − x ≺ 0
x ⩽ y ⇔ x
i
⩽ y
i
i ∈ {1, 2, . . . , n}
x ≺ y ⇔ x
i
< y
i
i ∈ {1, 2, . . . , n}
1.2.1 Pareto 最优解
下面，给出 Pareto 最优解的概念。给定一个可行点 x
∗
∈ S，若 ∀x ∈ S，有 f (x
∗
) ⩽ f(x)，
则称 x
∗
为 MOP 的绝对最优解；若不存在 x ∈ S，使得 f(x) ≺ f (x
∗
)，则称 x
∗
为 MOP 的有效
解；若不存在 x ∈ s，使得 f(x) < f(x
∗
)，则称 x
∗
为 MOP 的弱有效解。
MOP 的有效解通常也称为 Pareto 最优解。绝对最优解、有效解、弱有效解的集合分别记为
S
a
, S
p
, S
wp
。
定理 对于 MOP 问题，令 z = f (S)，z 的有效点集和弱有效点集分别记为 Z
p
和 Z
wp
，则
(MOP) 的有效解集 S
p
和弱有效解集 S
wp
由下面式子给出：
(1) S
p
=
f
∗
∈Z
p
{x ∈ S|f(x) = f
∗
}
(2) S
wp
=
f
∗
∈Z
wp
{x ∈ S|f(x) = f
∗
}
至于解集 S
a
, S
p
, S
wp
之间的关系，我们有:
(1) S
a
⊆ S
p
⊆ S
wp
⊆ S
(2) 当 S
a
= ϕ 时，S
a
= S
p
(3) 若 S 为凸集，f 是 S 上严格凸的向量值函数，则 S
p
= S
wp
http://www.ma-xy.com 2 http://www.ma-xy.com
http://www.ma-xy.com
��� ����� 1.3 �����
1.2.2 KT-有效集与 G-有效集
MOP 的绝对最优解、有效解和弱有效解等概念分别是通过关系 ≤, ≺, < 来描述的。如果将
序关系的应用范围加以限定，就可以得到其他形式的最优解概念。比如，∃x
∗
∈ S, δ > 0，使 x
∗
是 f(x) 在变量可行域的子集 S ∩ N(x
∗
, δ) 上的一个有效解，则称 x
∗
是一个局部有效解，相应
地，z
∗
= f (x
∗
) 称为目标可行域 z = f(S) 的局部有效点。
定义 对 MOP 问题，对于 x
∗
∈ S，令积极不等式约束指标集 I(x
∗
) = {i|g
i
(x
∗
) = 0}，若 x
∗
是 MOP 的有效解，并且不等式组
∇f
T
(x
∗
)x < 0
∇g
T
I(x
∗
)
(x
∗
)x ⩾ 0
∇h
T
(x
∗
)x = 0
在 R
n
中无解，其中：∇f
T
, ∇g
T
I(x
∗
)
和 ∇h
T
分别是向量值函数 f(x), g
I(x
∗
)
(x) 和 h(x) 的 Jacobi
矩阵，则称 x
∗
为 MOP 的 Kuhn-Tucker 真有效解。
类似地，若 x
∗
是 MOP 的弱有效解，并且不等式组
∇f
T
(x
∗
)x < 0
∇g
T
I(x
∗
)
(x
∗
)x ⩾ 0
∇h
T
(x
∗
)x = 0
在 R
n
中无解，则 x
∗
称为 MOP 的 Kuhn-Tucker 真弱有效解。
定义 假设 x
∗
∈ S 是 MOP 的有效集，若存在 M > 0，使得对于任意的下标 i(1 ⩽ i ⩽
p), {f
i
(x) < f
i
(x
∗
)} 和 x ∈ S，必存在下标 j，使得 f
j
(x) > f
j
(x
∗
)，并且
f
i
(x
∗
) − f
i
(x) ⩽ M(f
j
(x) − f
j
(x
∗
))
则称 x
∗
为 MOP 的 Georion-真有效集，记其集合为 S
G
p
。并且若 S
a
= ϕ，则 S
a
= S
G
p
= S
p
。
1.3 最优性条件
首先，定义 MOP 的 Lagrange 函数如下：
L(x, β, λ, µ) = β
T
f(x) − λ
T
g(x) − µ
T
h(x)
其中：β ∈ R
p
, λ ∈ R
|I|
, µ ∈ R
|E|
。
定理 (Fritz John 必要条件) 假设向量值函数 f, g, h 在 x
∗
处可微，若 x
∗
是 MOP 的有效
解或弱有效解，则存在向量 β ∈ R
P
+
, λ ∈ R
|I|
+
, µ ∈ R
|E|
+
，使得 (β, λ, µ) = 0，并且
∇
x
L(x
∗
, β, λ, µ) = ∇f(x
∗
)β − ∇g(x
∗
)λ − ∇h(x
∗
)µ = 0 (1.1)
λ
T
g(x
∗
) = 0 (1.2)
http://www.ma-xy.com 3 http://www.ma-xy.com
http://www.ma-xy.com
1.4 最优化算法 第一章 多目标规划
其中：∇f, ∇g, ∇h 分别表示向量值函数在相应点的梯度矩阵 (即 Jacobi 矩阵的转置)。为了保证
目标向量函数的梯度矩阵 ∇f 对应的参数 β = 0，我们需要对约束函数增加一些限制。
¬线性约束规格 (LCQ)：g
j
, h
i
为线性函数；
Mangasarian-Fromowitz 约束规格 (MFCQ)：矩阵 ∇h(x
∗
) 列满秩。
®线性独立约束规格 (LICQ)：向量组 {∇
g
i
(x
∗
), ∇
h
j
(x
∗
), i ∈ I(x
∗
), j ∈ E} 是线性无关的。
对于 x ∈ S 以及 d ∈ R
n
，若向量 d 满足
d
T
∇g
j
(x) ⩾ 0 j ∈ I(x)
d
T
∇h
i
(x) = 0 i ∈ E
其中：I(x) 是积极不等式约束的指标集，则称向量 d 为 g, h 在 x 处的一个线性化可行方向。
约束 g, h 在 x 点的所有线性化可行方向的集合，称为线性化可行方向锥，记为 LF D(x, s)。
对于 x ∈ S, d ∈ R
n
，若存在一个向量序列 {d
k
} 和正数序列 {δ
k
}，使得对 ∀k = 1, 2, · · · ，有
x + δ
k
d
k
∈ S 并且 d
k
→ d, δ
k
→ 0，则称 d 为 S 在 x 处的一个序列化可行方向。集合 S 在 x 点
的所有序列化可行方向的集合，称为序列化可行方向锥，记为 SF D(x, s)。
定理 (KKT 必要条件) 假设 f, g, h 在 x
∗
∈ S 处可微，若 x
∗
是 MOP 的有效解或弱有效解，
并且在 x
∗
点Kuhn-Tucker 约束规格 LF D(x
∗
, s) = SF D(x
∗
, s) 成立，则存在非零向量 β ∈ R
p
+
以及 λ ∈ R
|I|
, µ ∈ R
|E|
并且满足式 (1.1)(1.2)。
定理 (KKT 充分条件) 假设 f, −g 是凸的，在 x
∗
∈ S 处可微，并且 h 是线性函数，若存
在非零向量 β ∈ R
p
+
和 λ ∈ R
|I|
, µ ∈ R
|E|
满足式 (1.1)(1.2)，则 x
∗
是 MOP 的弱有效解。特别
地，当 β > 0 时，x
∗
是 MOP 的有效解。
1.4 最优化算法
对 MOP 而言，计算所有的最优解是困难的，因为确定整个有效解集的问题是 NP 难的。下
面，介绍一些处理 MOP 问题的思想。
1.4.1 线性加权和法
根据 p 个目标函数 f
j
的重要程度，赋予各自一定的权重 λ
j
，然后将所有目标函数 f
j
乘上
权重 λ
j
求和，变为单目标函数
min
x∈R
n
λ
T
f(x) =
j
λ
j
f
j
(x)
s.t.
g(x) ⩾ 0
h(x) = 0
其中：f, g, h 为向量值函数。
注：∀λ > 0,
j
λ
j
= 1，单目标问题的最优解是 MOP 的弱有效解。
http://www.ma-xy.com 4 http://www.ma-xy.com
http://www.ma-xy.com
第一章 多目标规划 1.4 最优化算法
1.4.2 主要目标法
根据实际情况，首先确定一个目标函数为主要目标 (例 f
1
(x))，而把其余 p − 1 个目标函数
f
j
(x) 作为次要目标，然后，再对次要目标选取一定的界限值 µ
j
(j = 2, · · · , p)，将其转化为约束
条件，例
min
x∈R
n
f
1
(x)
s.t.
g(x) ⩾ 0
h(x) = 0
f
j
(x) ⩽ µ
j
j = 2, 3, · · · , p
注：单目标优化问题的最优解都是 MOP 的弱有效解。
1.4.3
极小化极大法
极小化极大法的基本思想是，在 f(x) 的 p 个分量中，极小化 f(x) 的最大分量，即
min
x∈S
max
1⩽j⩽p
f
j
(x)
该问题的最优解作为 MOP 的弱有效解。一般地，可以引入目标函数权向量 λ : λ ⩾ 0,
j
λ
j
= 1
min
x∈S
max
1⩽j⩽p
λ
j
f
j
(x)
注：∀λ ⩾ 0,
j
λ
j
= 1 单目标问题的最优解都是 MOP 的弱有效解。
1.4.4 理想点法
对每个目标函数 f
j
(x)，事先确定一个目标值 f
0
j
，其中
f
0
j
= min
x∈S
f
j
(x)
记理想点为 f
0
= (f
0
1
, · · · , f
0
p
)
T
。然后，求解单目标优化问题
min
x∈S
∥f(x) − f
0
∥
α
注：对于 α ⩾ 1 单目标问题的最优解是 MOP 的有效解。
1.4.5 分层排序法
根据目标的重要程度将它们一一排序，然后，分别在前一个目标的最优解集中，寻找后一个
目标的最优解集，并把最后一个目标的最优解集作为 MOP 的最优解。例如：首先，通过求解单
目标优化问题
min
x∈S
f
1
(x)
http://www.ma-xy.com 5 http://www.ma-xy.com
http://www.ma-xy.com
1.5 MATLAB 应用实例 第一章 多目标规划
得到最优解集 S
1
，然后，对于 j = 2, 3, · · · , p，依次求解单目标优化问题
min
x∈S
j−1
f
j
(x)
得到最优解集 S
j
，然后，将 S
j
(j = P ) 中的点作为 MOP 的最优解。
1.5 MATLAB 应用实例
MATLAB 可以使用 gamultiobj 命令求解多目标规划问题，并且 gamultiobj 使用多目标遗
传算法 IENSGA(XXXV1) 求解多目标问题。gamultiobj 的命令格式如下：
[x,fval]=gamultiobj(tnessfcn,nvars,A,b,Aeq,beq,lb,ub,options)
其中：tnessfun 为目标函数；nvars 为变量个数；A,b 为 Ax ⩽ b；Aeq,beq 为 Aeqx = beq；lb,ub
为 lb ⩽ x ⩽ ub。下面，我们介绍函数 gamultiobj 中的一些基本概念：
¬个体、种群、代、选择、交叉、变异和交叉后代比例等放在 GA 章节中介绍；
支配 (dominate) 与非劣 (non-inferior)：在多目标优化问题中，如果解 x
1
∈ R
n
至少有一个目
标比解解 x
2
∈ R
n
好，而且个体 x
1
的所有目标都不比解 x
2
差，那么称解 x
1
支配解 x
2
，或者
x
1
非劣于 x
2
。
®拥挤距离 (crowding distance)：拥挤距离是用来计算某前端中的某个解 x 与该前端中其它解之
间的距离，用以表征解之间的拥挤程度，且只有处于同一前端的解之间才需要计算拥挤程度。
¯最优前端个体系数 (Pareto Fraction)：最优前端个体系数定义为最优前端中的解在种群中所占
的比例。
作为 MATLAB 的应用实例，多目标遗传算法如下多目标规划问题
min f
1
= x
4
1
− 10x
2
1
+ x
1
x
2
+ x
4
2
− x
2
1
x
2
2
min f
2
= x
4
2
− x
2
1
x
2
2
+ x
4
1
+ x
1
x
2
s.t.
5 ⩽ x
1
⩽ 5
− 5 ⩽ x
2
⩽ 5
求解程序如下
1 fu nc tio n f = mult io bj (x )
2 f ( 1) = x( 1) ^4−10*x (1 )^2+x(1) *x (2 )+x (2)^4−(x (1 ) ^2) *( x( 2) ^2) ;
3 f ( 2) = x( 2) ^4−(x (1) ^2) *(x (2) ^2)+x (1 )^4+x (1) *x (2) ;
4 end
5 f i t n e s s f c n = @multiobj
6 nvars = 2 ;
7 lb = [ −5 , −5];
8 ub = [ 5 , 5 ] ;
9 A= [ ] ; b= [ ] ;
10 Aeq= [ ] ; beq = [ ] ;
11 opti on s = gaoptimset ( ’ ParetoFraction ’ , 0 . 3 , ’ Popu lationSi za ’ ,1 00 , ’ Generations ’ , 200 , ’
StallGenLimit ’ ,200 , ’ TolFun ’ , le −100, ’ PlotFcns ’ , @gaplotpareto ) ;
12 [ x , f v a l ] = gamultiobj ( f i t n e s s f c n , nvars ,A, b , Aeq , beq , lb , ub , o pti on s ) ;
13
http://www.ma-xy.com 6 http://www.ma-xy.com
