[模型]多目标规划模型

大家好，欢迎来到IT知识分享网。

文章目录

• 视频链接
• 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)

视频链接

1 多目标规划模型的概念

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

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

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

2.1 定义一

对最小化问题，一个向量$u=(u_1,u_2,\dots ,u_m)$称为支配(优于)另一个向量$v=(v_1,v_2,\dots ,v_m)$，当且仅当$u_i\le v_i,i=1,2,\dots ,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 = (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}$ 

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),\dots ,f_m(x_1))$支配(优于)向量$(f_1(x_2),f_2(x_2),\dots ,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}$ 

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，右下角的点与之相反，所以无法进行比较，可以认为一样优(好)。

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 多目标规划模型的一般形式

$$\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\}$ 

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

传统的处理多目标优化问题的方法包括：
（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 智能优化算法的简介

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

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

学习ing…

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

画图

非劣排序

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

灵敏度分析