多目标优化之比大小

1维情况下的比大小

（为了方便理解，本篇中更优指更大。）

在优化问题中计算出一系列结果后，需要通过比较大小找到最优解。而比大小，确定2>1，在我们的认知中是再简单不过的事情。比如，对于数的集合 [1,10,8,5,7]，我们能很轻松判断该集合中元素的大小关系，从而寻找最优或排序。

1维情况下的排序用的就是耳熟能详的冒泡、插入、选择、快速等排序算法。

多维情况下的比大小 – 支配

然而，如果我们要比大小的不是数呢？

这就是多目标优化中要考虑的问题。多目标优化问题的目标往往量纲不同、无法确定谁更重要，每次计算得到的结果是多个数。如 [2,3]、[1,6]、[0,1]，他们共同形成了一个向量集合 [[2,3], [1,2], [0,6]]，也可以理解为点的集合。这个时候，比大小就不是2>1这样显而易见的事情了。

为了进行向量之间的比较，(pareto)支配的概念被提了出来。

其实多目标比较在生活中经常出现，比如纠结买什么手机的时候，要对价格、屏幕尺寸、续航、拍照等各个因素进行考虑，通常也很难找到一款全方面令人满意的手机，最终，各有优劣的几个手机型号共同成为最终的备选方案。

将其与1维情况类比，我们能更快理解这个概念。在不考虑完全相等的情况下，两个向量比较可以有如下结果：

支配指向量1所有分量均优于向量2，如[2,3]支配[0,1]。类比数的比大小，就是大于关系。

被支配指向量1所有分量均劣于向量2，如[0,1]被[2,3]支配。类比数的比大小，就是小于关系。

互不支配指向量1与向量2互相未在所有分量上优于对方，因此不能认为两者有优劣关系。相比于数的比大小，互不支配就是新产生的概念。

简单来说，支配就是一种以向量为单位的比大小方法。

支配概念引起的变化

由于互不支配这种概念的存在，在多目标问题中，求得结果后（一堆目标函数值向量），我们从结果中寻找最优或排序时会发生什么变化？显而易见的是，最优可能不再是一个数，而是一个向量集合（称为pareto前沿）。如果进行排序，也会有多个向量的大小关系处于同一层级。

多目标粒子群算法等只需要求pareto前沿，而多目标遗传算法等需要进行非支配排序。由于篇幅有限，本文主要对寻找pareto前沿的思路进行讲解。

理清逻辑以后，我们应该怎么去实现寻找最优呢？

实现寻找pareto前沿

笔者刚接触这个问题时，在CSDN上看到一段用双层for循环解决的代码，直接嗅到一丝烂代码的味道。其将所有向量两两比较，并标记被支配的向量，最后所有未被标记的向量就组成了pareto前沿，这个方法的时间复杂度固定是。

问题描述

输入：一个向量集合（向量数量为m）

输入（最差情况）：一个向量集合（向量数量为m），且所有向量已经互不支配。

输出：一个向量集合（向量数量为n，n<=m），且所有向量互不支配。

方法1 – 类比1维情况

其实这个问题很简单，在1维比大小时我们怎么做，对于多维情况也这么做。1维时，只需要使用一个空间存放当前（每次遍历）的最优值，然后遍历数组即可。多维时，同样使用类似思路：

划出一个空间用于存放（每次遍历）的临时pareto前沿，称为，一开始为空。
遍历集合中的每个向量，与比较。中被支配的向量会被删除，当前遍历的向量如果没有被支配，会直接加入。

方法2 – 利用只找pareto前沿的特性

注意到，如果只考虑寻找pareto前沿而不考虑排序，当一个向量与其他向量比较后都没有被支配，那这个向量一定是最后的pareto前沿的其中一个。

另一方面，一个向量一旦被支配过，那它就不可能在pareto前沿中，可以不用再和其他向量进行比较。

依照这个思想，我们设定一个可变的向量集合，称为waiting_set，里面是所有还未进行过比较的向量。每次首先选择一个向量，称为pivot向量，和waiting_set中的其他向量进行比较，如果pivot向量直到最后都没有被支配过，将其直接置入最终的pareto前沿集合。而在这个比较过程中waiting_set中被支配的向量将会从waiting_set中删除，这样下一次遍历时waiting_set已经缩小了。

（图中虚线无箭头表示互不支配，虚线箭头表示支配者指向被支配者）