最优化理论 - 多目标优化(DWA、Lattice)

---

版权声明：本文为 DLonng 非原创文章，可以随意转载，但必须在明确位置注明出处！

对 DWA 多目标优化的学习与总结，非原创，参考文末博客！

多目标优化问题背景

现实中很多问题都能最终抽象为多目标优化问题，这是因为现实问题往往比较复杂，在达成目标时一般会权衡很多方面（如 DWA 局部规划会权衡目标方向，自身速度，轨迹跟踪等），也会有很多约束，这天然就是一个多目标优化问题。

多目标优化问题（Multi-Objective Optimization,MOO）

问题定义

• m 个 f(x) 就是要优化的多个目标函数，比如 DWA 的目标代价、航向代价、路径代价、速度代价等。
• 我们优化的目标就是希望能够找到很好平衡全部优化目标的解集。
  • 寻找尽可能接近帕累托（后续介绍）最优前沿面的解集
  • 尽可能增大找到解的多样性

帕累托（Pareto）最优性

• 帕累托改善：给定固有的一群人和可分配的资源，如果从一种分配状态到另一种状态的变化中，在没有使任何人境况变坏的前提下，使得至少一个人变得更好
• 帕雷托最优：是指资源分配的一种理想状态
  • 意思是：不可能再有更多的帕雷托改善的情况
  • 换句话说：不可能在不使任何其他人受损的情况下再改善某些人的境况
    • DWA：改善一个代价函数，其他代价函数肯定会受到影响（效果变差）

多目标优化的解集

变量支配

当 x1 支配 x2 时满足如下条件：

• 对于所有目标函数 x1 的效果好于或者等于 x2
• 至少在一个目标函数上，x1 严格好于 x2

比如上图中点 1 支配点 2：

• 在纵轴方向求最小值：点 1 的值小于点 2，所以 1 比 2 优
• 在横轴方向求最大值：点 1 的值大于点 2，所以 1 还是比 2 优
• 不管是横轴还是纵轴，点 1 的值都严格优与点 2，不会出现等于的情况

因此点 1 支配点 2，同理点 5 支配点 1，但点 1 和点 4 互不支配。

不可支配解集

当一个解集中任何一个解都不能被该集合中其他解支配，那么就称该解集为不可支配解集。

帕累托最优解集

所有可行中的不可支配解集被成为帕累托最优解集。

帕累托最优前沿面

帕累拖最优解集的边界（boundary）被成为帕累托最优前沿面。

多目标优化的经典方法

线性加权法

把每个子目标函数 $f(x)$ 乘以一个权重 $w$ 然后相加作为一个最终要优化的目标函数 $F(x)$ ，权重表示子目标函数的重要程度：

• 优点
  • 简单，DWA 和 Lattice Planner 都用这个方法，应该是常用方法
• 缺点：不能保证得到最优解！
  • 很难设定一个权重向量能够去获得帕累托最优解
  • 在一些非凸情况不能够保证获得帕累托最优解

ε-constraint method

只保留一个目标函数，其他的目标函数被设定的值约束

• 优点：
  • 能够应用到凸函数和非凸函数场景下
• 缺点
  • 函数需要精心选择，需要在独立目标函数的最小值或最大值之内

加权度量法

不太懂，好像用的不多。。

多目标遗传算法

基于遗传算法的多目标优化就是利用遗传算法的原理来搜索帕累托最优前沿面。

不太懂遗传算法。。

参考博客

• 多目标优化的 4 种方法

本文原创首发于微信公号「登龙」，分享机器学习、算法编程、Python、机器人技术等原创文章，扫码即可关注！