多目标优化（I）：偏好与支配

在多目标优化问题中，我们通常会得到一组解，这些解被称为帕累托解（Pareto solutions），它们组成的集合被称为权衡面（tradeoff surface）。选择最优解的过程通常需要考虑决策者的偏好。

一般而言，有两种模拟决策者偏好的理论：多属性效用理论（multi-attribute utility theory）和多标准决策辅助理论（multicriteria decision aid theory）。这两种理论的主要区别在于它们对决策者偏好的处理方式。

• 多属性效用理论：假设每个决策者都会试图最大化一个效用函数（utility function）。这种方法假设决策者在所有可能的解之间有一个明确的偏好顺序，即不接受等级相等的解。这种理论的一个关键假设是：决策者的偏好可以被一个效用函数完全描述。
  
• 多标准决策辅助理论：这种理论试图模拟一个或多个决策者的选择过程。这种方法允许存在多个同样好的解。它的关键假设是决策者的偏好可能会随着情境的变化而变化，因此可能无法被一个单一的效用函数完全描述。
  

• 先验（priori）优化方法：在执行优化方法之前就确定了我们希望在目标函数之间进行的权衡。这种方法的优点是我们只需要进行一次搜索就可以找到解，但是在找到这个结果之前需要建模权衡。
  
• 渐进（progressive）优化方法：在优化过程中向决策者提问，以便将搜索重新定向到可能包含决策者现在希望执行的目标函数之间的权衡的解的区域。这个方法的缺点是它们需要决策者在整个优化过程中保持注意，如果评估目标函数所需时间太长则难以适用。
  
• 后验（posteriori）优化方法：寻找一组在解空间中同等的次优解。我们的直接目标是将这些解展示给决策者，以便通过评估各种提出的解来选择最满意的解。虽然不再需要建模决策者的偏好，但是是需要生成一组同等的次优解。这个任务不仅困难，而且可能需要更多的执行时间。
  

在多目标优化中，我们说一个解 支配（Domination）另一个解 ，如果对于所有的目标 ， 在目标 上的性能不比 差，且至少有一个目标 ， 在目标 上的性能比 好：

其中， 是目标数量， 是第 个目标函数。

极端情况下，一个解被认为是 Extremal optimality 的，如果没有其他解在所有目标上都严格的优于它。这与支配的概念相似，只是在判断优劣时更为严格，要求一个解在所有目标上都不比另一个解差。

支配是一种基本的比较方法，但它的定义并没有太多的自由度，比如说它无法在定义中包含对某个目标函数的偏好。

为了克服这种缺乏灵活性，人们发展出了一些从支配关系派生出来的关系，例如

该方法使用预先定义的目标优先级来确定解的优劣。首先，比较第一个优先级的目标，如果有一个解在这个目标上更好，那么这个解就更优。如果两个解在第一个优先级的目标上一样好，那么就比较第二个优先级的目标，依此类推。优劣取决于目标的优先级顺序。

锥优化是一种考虑方向的优化方法。在锥优化中，我们不仅要找到最优解，还要确定这个解在哪个方向上是最优的。这就像我们在山上寻找最高点，不仅要找到最高点，还要确定从哪个方向上山是最快的。

在某些情况下，我们可能对目标之间的权衡有一些先验的知识。例如，我们可能知道，我们愿意牺牲一些目标 ，以获得其他目标 的改进。这可以通过一个权重向量 来表示。

在这种情况下，一个解 是锥优的，如果不存在另一个解 ，使得 在锥 中严格优于 。这可以写作：

这意味着，无论我们如何权衡不同的目标（即，无论 是什么），我们都找不到一个解 ，它在 的加权下优于 。这意味着， 是一个相对于所有可能的权重向量 的锥优解。

a-支配是一种考虑权重的优化方法。在a-支配中，我们给每个目标函数一个权重，然后找到一种解决方案，使得加权后的目标函数值最优。

对于两个可行解 和 ，如果存在一个 和一个参考点 ，使得以下条件满足：

对于所有的目标 ，我们就说解 按比例支配解 。这里的 是第 个目标函数。

参考点 是在目标空间中的一个参考点，可以是一个特定的解或者是一个期望的解。主要目的是为了在这个多目标优化问题中引入一种优化的导向。参考点 可以是我们期望的解，或者是我们认为在所有目标上都比较平衡的解。通过将参考点 引入到优化过程中，我们可以引导优化过程朝着我们期望的方向前进，以获得在所有目标上都比较平衡的解。

换句话说，参考点 为我们提供了一种在多个目标之间进行权衡的方法。在按比例支配的概念中，我们希望找到的解 不仅在每个单独的目标上优于或等于另一个解 ，而且还在参考点 的方向上进行了一定程度的改进。

如果不引入参考点 ，那么我们只是在比较解 和解 在各个目标上的表现，没有考虑到这些解在所有目标上的整体表现。这可能会导致我们找到的解在一个目标上特别好，但在其他目标上特别差，这通常不是我们想要的。

而 是一个介于 0 和 1 之间的系数，用来表示我们允许的解 和解 在目标空间中的距离。更具体地说， 可以被看作是在目标 上，我们允许解 相比于参考点 的程度。如果 较小，那么我们希望解 与解 在目标空间中相对较接近；如果 较大，那么我们允许解 与解 在目标空间中有更大的距离。

在多目标优化中，通常我们不能找到一个解可以在所有目标上都最优，但是我们可以找到一些解，使得改进任何一个目标都会导致其他目标的劣化，这些解被称为 Pareto optimal solutions（Pareto最优解）。

现在，考虑两个相邻的 Pareto 最优解 和 。假设我们从 移动到 。那么，在该过程中，某些目标会改善，某些目标会劣化。让我们看一个具体的例子：

假设我们有两个目标， 和 。当我们从 移动到 时，假设 改善（即， ），那么，由于 和 都是 Pareto 最优的， 必然劣化（即， ）。

那么，我们可以计算在这个过程中， 的改善与 的劣化之间的比率：

这个比率表示为了使 改善的程度，我们必须接受多大程度的 劣化。

现在，问题的关键在于：这个比率是有限的。这意味着，无论我们如何从 移动到 ，我们总是可以计算出一个比率来度量目标之间的权衡。这是因为 和 都是 Pareto 最优的。如果存在无界的比率，那么我们就可以通过在某个目标上无限制的改善，来在另一个目标上实现任意小的劣化，这就违反了 Pareto 最优的定义。

因此，无论我们如何从 移动到 ，目标之间的权衡都是有界的。换句话说，所有目标的变化量的比值是有限的。即

Proper Pareto optimal solutions have bounded tradeoff considering their objectives.