优化入门+多目标规划
- 优化入门知识
- 什么是优化问题
- 如何判断是不是优化问题
- 优化模型建模
- 求解器
- 优化问题的分类
- 多目标规划
优化入门知识
什么是优化问题
优化问题:求最优,例如获利最大、最少损失、最短路径、最小化风险等等。
例如:之前文章提到华为杯2019F题多约束条件下智能飞行器航迹快速规划,其中第一问就涉及求飞行器从A点到B点带约束下的最短路径。
如何判断是不是优化问题
题目带有优化、规划、最值、安排、分配、最合理等等。
题目涉及到图,例如三维空间飞行、二维地图上旅行。
优化模型建模
优化模型格式:决策变量+目标函数+约束条件。
决策变量:能够对目标结果产生影响的变量。
x
i
,
i
=
1
,
2
,
.
.
.
,
n
x_i,i=1,2,...,n
xi,i=1,2,...,n
目标函数:通常都是一个Min或者Max求某个决策变量的函数表达式。例如:
M
i
n
(
o
r
M
a
x
)
z
=
f
(
x
)
,
x
=
(
x
1
,
.
.
.
,
x
n
)
T
Min(or Max)z=f(x),x=(x_1,...,x_n)^T
Min(orMax)z=f(x),x=(x1,...,xn)T
约束条件:以s.t.为开头,后面写上约束条件。
s
.
t
.
{
g
1
(
x
)
⩽
0
g
2
(
x
)
⩽
0
.
.
.
g
n
(
x
)
⩽
0
s.t. \begin{cases} g_1(x)\leqslant0\\ g_2(x)\leqslant0\\ ...\\ g_n(x)\leqslant0\\ \end{cases}
s.t.⎩
⎨
⎧g1(x)⩽0g2(x)⩽0...gn(x)⩽0
求解器
优化模型建立好之后,选择什么样的算法去解模型是比赛的关键。
求解器:用来求解模型的程序、算法之类的,在matlab里面求解器填写的其实就是函数模型。
优化问题的分类
从目标函数的个数来说:可以分成单目标和多目标。
从问题的类型来说:可以分为规划类、图论和动态规划。
规划类按照决策变量在目标函数和约束条件中是否线性:可以分为线性规划和非线性规划。
规划类中,比较特殊的是决策变量为整数的“整数规划”,和决策变量只能取0或者1的“0-1规划”。
非线性规划中比较特殊的是二次规划,目标函数是关于决策变量的二次函数,约束条件是线性函数。
图论中常见的问题有:最短路、最小生成树、网络流和排队论。
多目标规划
条件:线性规划和非线性规划只有一个目标函数,多目标函数有多个目标函数( f i ( x ) f_{i}(x) fi(x)),讲究一个既要还要。
方法:多目标转化为单目标。
- 优先因子:可以主观上给目标函数进行一个重要性排序,来使得整体的完成情况尽量好,也就是优先因子,相当于权重(
P
i
P_i
Pi)。
m i n ∑ P i f i ( x ) min\sum P_{i}f_{i}(x) min∑Pifi(x) - 平方加权:知道每个目标理想值的情况下,可以求每个目标函数和理想值的平方和,可以带上权重。
m i n ∑ λ i [ f i ( x ) − f i ∗ ] 2 min\sum \lambda_{i}[f_{i}(x)-{f_i}^*]^2 min∑λi[fi(x)−fi∗]2 - 乘除法:如果每个目标重要程度一样。
m i n f 1 ( x ) f 2 ( x ) . . . f k ( x ) f k + 1 ( x ) f k + 2 ( x ) . . . f n ( x ) min\frac{f_{1}(x)f_{2}(x)...f_{k}(x)}{f_{k+1}(x)f_{k+2}(x)...f_{n}(x)} minfk+1(x)fk+2(x)...fn(x)f1(x)f2(x)...fk(x) - 分开求最优解对比:有时候单独最优解之间差距可能不是很大,例如之前华为杯2019F题,有个论文就是分别求最优路径和最少矫正点,然后对比。
特殊:问题中存在刚性约束和柔性约束。刚性约束就是必须要满足的,否者就是不可行解。柔性约束就是可以存在偏差的,例如使目标f(x)尽可能不少于5,可以在5左右有正负偏差。这个正负偏差可以记作
d
+
和
d
−
d^+和d^-
d+和d−,
d
+
=
m
i
n
{
f
(
x
)
−
f
∗
,
0
}
,
d
−
=
−
m
i
n
{
f
∗
−
f
(
x
)
,
0
}
d^+=min\{f(x)-f^*,0\},d^-=-min\{f^*-f(x),0\}
d+=min{f(x)−f∗,0},d−=−min{f∗−f(x),0}。
例子:三个目标函数
f
1
(
x
)
、
f
2
(
x
)
、
f
3
(
x
)
f_1(x)、f_2(x)、f_3(x)
f1(x)、f2(x)、f3(x),三个目标是柔性约束,1尽量不超过、2尽量等于、3尽量不少于,会发现柔性约束都有“尽量”两个字作为修饰。最终的多目标规划函数可以写成:
min
{
P
1
d
1
+
+
P
2
(
d
2
−
+
d
2
+
)
+
P
3
d
3
−
}
\min{\{P_1{d_1}^++P_2({d_2}^-+{d_2}^+)+P_3{d_3}^-\}}
min{P1d1++P2(d2−+d2+)+P3d3−}
扩展一下格式:
m
i
n
∑
P
i
(
w
i
+
d
i
+
+
w
i
−
d
i
−
)
min\sum {P_i({w_{i}}^+{d_{i}}^++{w_{i}}^-{d_{i}}^-)}
min∑Pi(wi+di++wi−di−)文章来源:https://uudwc.com/A/0k11A
总结:多目标规划,可以转换成为单目标问题,然后单目标去看符合单目标中那种取套,根据情况套回规划类、图论和动态规划中。文章来源地址https://uudwc.com/A/0k11A