[模型]多目标规划模型

文章目录

• 视频链接
• 1 多目标规划模型的概念
• 2 多目标规划模型的相关概念
• • 2.1 定义一
  • 2.2 定义二
  • 2.3 定义三
  • • 判断自变量向量的优劣
• 3 引言与引例
• • 3.1 引言
  • 3.2 引例
  • • 3.2.1 引例1 -- 生产计划问题
    • 3.2.2 引例2 -- 种植方案问题
• 4 多目标规划模型的适用场景
• 5 多目标规划模型的一般形式
• 6 多目标规划模型的求解方法
• • 6.1 传统的数学规划方法
  • • 6.1.1 主要目标法
    • 6.1.2 分层序列法
    • 6.1.3 加权法
    • 6.1.4 理想点法
    • 6.1.5 传统数学规划方法的缺陷
  • 6.2 智能优化算法
  • • 6.2.1 智能优化算法的简介
    • 6.2.2 基于精英策略的快速非支配排序遗传算法(NSGA-II)

---

视频链接

根据视频整理
视频链接：
7.9数模国赛培训 多目标优化

1 多目标规划模型的概念

多目标规划法（Multi-objective programming，MOP）是一类考虑多因素约束与多目标组合，将定性分析与定量分析相结合的分析决策模型${}^{[1]}$。其基本模型包括目标函数和约束条件两部分。

[1] 张业涌,刘德平,邹敏科,梁禧健.基于聚类分析与多目标规划的新疆旅游线路优化设计与研究[J].甘肃科技纵横,2022,51(01):64-68.

2 多目标规划模型的相关概念

2.1 定义一

对最小化问题，一个向量$u=(u_1,u_2,...,u_m)$称为支配(优于)另一个向量$v=(v_1,v_2,...,v_m)$，当且仅当$u_i\le v_i,i=1,2,...,m$，且 ∃ j ∈ { 1 , 2 , ⋯   , m } , u j < v j \exists j \in\{1,2, \cdots, m\}, u_{j}<v_{j} ∃j∈{1,2,⋯,m},uj​<vj​。

向量u和v为多目标规划问题的解集。
一个解集优于另一个解集，(以最小值为例)需要满足一个解集中的所有解小于等于另一个解集中的所有解，同时还要满足较优的那个解集存在一个解小于小于另一个解集中的一个解。

$u = (u_{1}, u_{2}, ..., u_{m})$
$v = (v_{1}, v_{2}, ..., v_{m})$
$u_{i} \le v_{i}, i = 1, 2, ..., m$
$\exists j \in\{1,2, \cdots, m\}, u_{j}<v_{j}$
1
2
3
4

2.2 定义二

对于任意两个自变量向量$x_1,x_2\in \Omega$，如果下列条件成立：
{ f i ( x 1 ) ≤ f i ( x 2 ) , ∀ i ∈ { 1 , 2 , ⋯   , m } f j ( x 1 ) < f j ( x 2 ) , ∃ j ∈ { 1 , 2 , ⋯   , m } \left\{

$$\begin{array}{l} f_{i}\left(x_{1}\right) \leq f_{i}\left(x_{2}\right), \forall i \in\{1,2, \cdots, m\} \\ f_{j}\left(x_{1}\right)<f_{j}\left(x_{2}\right), \exists j \in\{1,2, \cdots, m\} \end{array}$$ \right. {fi​(x1​)≤fi​(x2​),∀i∈{1,2,⋯,m}fj​(x1​)<fj​(x2​),∃j∈{1,2,⋯,m}​
即向量$(f_1(x_1),f_2(x_1),...,f_m(x_1))$支配(优于)向量$(f_1(x_2),f_2(x_2),...,f_m(x_2))$，则称$x_1$支配(优于)$x_2$。

$\Omega$为在约束条件下，自变量可以取到的值组成的集合，即可行解组成的集合，也叫决策空间。

向量$x_1$与$x_2$为多目标规划问题的各个自变量(最优解的影响因素)组成的向量。
自变量向量$x_1$优于$x_2$，是指当影响因素的取值为$x_1$时，所有目标函数的取值都要小于等于当影响因素的取值为$x_2$时的目标函数的取值，同时其中任意一个目标函数的取值需要满足取值为$x_1$值小于取值为$x_2$。

$x_{1}, x_{2} \in \Omega$
$$\left\{\begin{array}{l}
f_{i}\left(x_{1}\right) \leq f_{i}\left(x_{2}\right), \forall i \in\{1,2, \cdots, m\} \\
f_{j}\left(x_{1}\right)<f_{j}\left(x_{2}\right), \exists j \in\{1,2, \cdots, m\}
\end{array}\right.$$
$(f_{1}(x_{1}), f_{2}(x_{1}), ..., f_{m}(x_{1}))$
$(f_{1}(x_{2}), f_{2}(x_{2}), ..., f_{m}(x_{2}))$
$x_{1}$
$x_{2}$
1
2
3
4
5
6
7
8
9

2.3 定义三

如果$\Omega$中没有支配（优于）$x$ 的解，则称 $x$ 是问题的一个 Pareto最优解（非劣解、有效解、非支配解)。

Pareto最优解的全体被称作Pareto最优解集；Pareto最优解集在目标函数空间的像集称为Pareto Front(Pareto前沿，阵(界)面)。

如图所示：

在A,B,C,D,E,F,H,G中，H点和G点是最优的：它们相应的自变量向量没有被任何其它的自变量向量所支配。这也就意味着在任何一个目标上它们都不能被其它个体支配。这样的解被称为Pareto最优解，有时也称作非劣最优解，非支配解。

判断自变量向量的优劣

以需要判断的自变量向量所在的点(如，B点)为原点绘制坐标轴：

假设目标函数求解的为最小值。

图中，阴影取内的点所代表的自变量向量都优于B，而左下角的点所代表的自变量向量都劣于B；左上角的点所代表的自变量向量与右下角的点所代表的自变量向量和B点无法进行比较，是由于左上角的点在横坐标上优于B在纵坐标上劣于B，右下角的点与之相反，所以无法进行比较，可以认为一样优(好)。

3 引言与引例

3.1 引言

在实际问题中，经常遇到需要 使多个目标在给定区域上均尽可能最佳的优化问题 。

例如：
设计一辆汽车，既要安全(重量大)，又要经济(油耗小)。
设计一个导弹，既要射程最远，又要燃料最省，还要精度最高。

这种 多于一个的目标函数在给定区域上的最优化问题 就称为多目标优化(multi-objective optimization）问题。

不同于单目标优化，在多目标优化中， 各目标之间是互相冲突的 ，导致 不一定存在在所有目标上都是最优的解 。某个解可能在一个目标上是最优的但在另一个上是最差的。( 判断多目标优化问题的关键 )

如果在一个目标上越优，在另一个目标上也越优，可以通过变换转换为单目标优化，所有该种情况不为多目标优化。

例如：
要使汽车安全性高，必然重量大，从而油耗高，经济性差；
要使汽车经济性好，即油耗小，必然要求重量轻，从而安全性低。

因此，多目标优化问题通常存在一个解的集合，它们之间不能简单地比较好坏，这样的解称为非支配解（有效解）或Pareto最优解。

非支配解（有效解）或Pareto最优解 在 多目标规划模型的相关概念 中有相关的定义。

单目标优化只有一个最优解，而多目标优化是一个解的集合，即多目标优化存在多个解。

3.2 引例

3.2.1 引例1 – 生产计划问题

注意能耗的单位；
注意单位的统一。

$x_1$小于等于100，是由于每周的最大销售量为40000，而布料$A_1$每个小时生产400，所以$x_1$小于等于100，$x_2$与$x_3$同理。

约束条件一定要写完整，约束条件可能会在题目中直接给出，也可能会隐藏在题目中。

求解最值问题，通常转化为最小值问题，最大值转化为最小值，前面加负号；同理，最小值转化为最大值，也是前面加负号。

F(x) 为目标函数向量。

3.2.2 引例2 – 种植方案问题

4 多目标规划模型的适用场景

同时存在多个最大化或是最小化的目标函数，并且，这些目标函数并不是相互独立的，也不是相互和谐融洽的，它们之间会存在或多或少的冲突，使得不能同时满足所有的目标函数。

适用场景：基于问题所构建的优化目标函数不唯一，且目标函数之间存在冲突。如，金融投资领域，要求风险更小，收益更大。

5 多目标规划模型的一般形式

一般地，多目标规划的数学模型如下：
min ⁡ F ( x ) = ( f 1 ( x ) , f 2 ( x ) , ⋯   , f m ( x ) ) S . t . x ∈ Ω

$$\begin{array}{l} \min F(x)=\left(f_{1}(x), f_{2}(x), \cdots, f_{m}(x)\right) \\ S.t. \quad x \in \Omega \end{array}$$ minF(x)=(f1​(x),f2​(x),⋯,fm​(x))S.t.x∈Ω​
其中$x=(x_1,x_2,...,x_n)$所在的空间 $\Omega$ 称为问题的决策空间(可行解空间），m维向量$F(x)$所在的空间称为问题的目标空间。
Ω = { x ∈ R n ∣ g i ( x ) ≤ 0 , i = 1 , 2 , ⋯   , p } \Omega=\left\{x \in R^{n} \mid g_{i}(x) \leq 0, i=1,2, \cdots, p\right\} Ω={x∈Rn∣gi​(x)≤0,i=1,2,⋯,p}。

$$\begin{array}{l}
\min F(x)=\left(f_{1}(x), f_{2}(x), \cdots, f_{m}(x)\right)
\\
S.t. \quad x \in \Omega 
\end{array}$$
$x = (x_{1}, x_{2}, ..., x_{n})$
$\Omega$
$F(x)$
$\Omega=\left\{x \in R^{n} \mid g_{i}(x) \leq 0, i=1,2, \cdots, p\right\}$
1
2
3
4
5
6
7
8
9

6 多目标规划模型的求解方法

多目标优化模型的算法大体上分为两类方法：
（1）传统的数学规划方法
（2）智能优化方法

传统的处理多目标优化问题的方法包括：
（1）主要目标法
（2）分层序列法
（3）加权法
（4）约束法
（5）目标规划法
（6）极小极大法
（6）理想点法
（7）……
其特点是通过各种方式将多目标优化问题转化为单目标优化问题，然后用单目标优化方法求解。

下面介绍四种传统数学规划方法，再介绍一种智能优化算法。

6.1 传统的数学规划方法

由于传统的数学规划方法较麻烦，且求解过程较慢、较繁琐，所以这里只放置方法的截图。

由于传统的数学规划方法是将多目标规划问题转换为单目标规划问题进行求解，所以每次使用传统的数学规划方法求出的最优解只是多目标规划问题解集中的一个解。因此，使用传统的数学规划方法求解多目标规划问题，需要进行多次求解。

6.1.1 主要目标法

6.1.2 分层序列法

6.1.3 加权法

加权法的局限性：
加权法适合于
图像为(即图像不存在非凸部分的最优值)：

的最值求解。
不适合于
图像为(图像非凸部分的最优值)：

的最值求解。

6.1.4 理想点法

理想点法可以求解非凸部分的最优值。

6.1.5 传统数学规划方法的缺陷

1. 每次运行只产生一个解，求多个解时需要运行多次，效率较低；
2. 多次运行也无法得到均匀分布的Pareto最优解集；
3. 有些方法对Pareto前沿比较敏感，当Pareto前沿是凹的或者不连续时，这些方法失效；
4. 要求目标和约束函数的可微性。

6.2 智能优化算法

6.2.1 智能优化算法的简介

智能优化算法由于其具有并行性、不需要求导或其它辅助知识、一次产生多个解和简单易于实现等优点，被视为求解多目标优化问题的有效方法。

使用智能优化算法解决多目标优化问题的优点在于：
（1）能在一次算法过程中找到Pareto最优集中的多个解；
（2）不局限于Pareto前沿的形状和连续性，易于处理不连续的、凹形的Pareto前沿。

6.2.2 基于精英策略的快速非支配排序遗传算法(NSGA-II)

学习ing…

.
.
.
.
.
.

优化问题：
设变量
目标函数
约束函数

只有 x1 2 3 无约束优化(自变量约束)，加上其他条件，约束优化

画目标函数的图形

画图

非劣排序

一般取交叉概率大，变异概率小

灵敏度分析