多目标优化之比大小

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已经缩小了。

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

方法1扩展  - 在pareto前沿中新增向量并重新确定pareto前沿

不过笔者后来又遇到了一个需求：在多目标粒子群算法中，每次迭代计算后都要新增一些结果向量到pareto前沿中，并重新确定pareto前沿。

解决上述问题可以将 新增向量集合 和 旧pareto前沿 混合后重新计算 新pareto前沿 ，但是这样 浪费了旧pareto前沿已互不支配的信息 。于是考虑复用上一段提到的解法1。

注意到，pareto前沿中的向量互不支配，这与方法1中的临时pareto前沿 的性质一致， 始终维持互不支配的特性。因此对于新增向量集合的需求，可以直接把旧pareto前沿放入 中作为初始条件（方法1中一开始为空），然后步骤和方法1一样，遍历新增向量集合。

测试

随机生成指定维度的若干数量的向量，并使用timeit模块统计50次平均结果。

1. 向量数量m=500，向量维度d=3

维度较小时，pareto前沿的向量数量较少，方法2先遍历所有向量能够快速减少待比较向量的数量，使得平均情况下时间复杂度能够逼近 。

2. 向量数量m=1000，向量维度d=10

维度较高时，两种方法都接近一般平均状态，性能接近。

3. 最差情况，互不支配的向量数量m=1000，向量维度d=10

两种方法最差情况的时间复杂度都是 ，符合预期。