非支配排序

假设我们要求最小值问题，且求解问题共有个目标；

解支配解的含义就是：的所有目标值都不大于。

此时如果有个解，我们要对这个解进行排序。

按照支配关系的定义，那么所有解中，不被任何解支配的一组解，就为个解的前沿面，也就是当前这组解的最优解，当然前沿面中的解也是相互不能支配的；

把前沿面的解去掉，在剩余解中很自然也能找到一组解为当前剩余所有解的前沿面，这组解我们称为第二层级的解；

以此递归，最终我们会找到所有层级的解。

如下图，所有解都被归类到各自的层级，也就是多目标优化问题的非支配排序结果。

举个例子：

我们有如下6个解，目标数量为2：

Algorithm1

• 一个很自然的想法就是，将每一个解和其他解都比一遍，找出没有被任何解支配的解，并归类到层级1中；

• 然后将这些解去掉，对剩余的解做同样的操作。

接下来我们就这么干：

通过这一轮比较，除了解、、有被支配的情况，其余解都不被任何解支配，将解、、归类到层级1并移除，然后进行第二轮比较。

此时剩余解为、、。

发现没有任何解支配剩余的解，因此、、都被归类到层级2，非支配排序就结束了，排序结果如下图。

对于目标数为，解的个数为的情况，最坏情况需要比较的次数为:

因此这一算法的时间复杂度为。当稍大的时候，这是一个很耗时的过程。

仔细看上面的比较过程，可以发现很多情况我们重复比较了很多次，第二轮所有的比较情况在第一轮都已经比较过一次。我们自然地想，能不能设计一种算法，使所有解与解之间的比较只进行一次呢？

Algorithm2

• 将每一个解比和其它所有解相比较，得出支配解的解的数量，和解支配的解的集合；

• 为0的解，意味着解不被任何解支配，因此它是当前所有解的前沿面中的解，归入到层级1；

• 遍历当前所有解的前沿面的每一个解，将它们支配的解的集合中的解的支配数减1，如果遍历的过程当中减1后结果为0，则说明支配这个解的解全部在已经归好类的解当中，剩余的解当中没有能够支配这个解的解，因此这个解是剩余所有解的前沿面的解，将其归入到下一层级；

• 以此递归，直到所有解的支配数都等于0，非支配排序结束。

同样以上面的例子为例：

先将每一个解和所有其它解进行比较，得到和；

可得解, ，的为0，将它们归到层级1，然后对它们支配的解的集合进行遍历，执行ni -= 1，剩余的解的也全部变为0，归到层级2，排序结束。

对于目标数为，解的个数为的情况，此算法最坏的情况需要比较的次数为：

因此时间复杂度为，但是因为比较的过程当中要保存每个解的和，空间复杂度上升为。

在算法耗时方面，提升已经非常的大。

上面的算法还有提升的空间吗，或者说每一次的比较是否全是必要的呢？以及有没有可能不存储任何信息，还能以最少的比较次数完成非支配排序呢？

仔细地分析，解和解进行支配关系比较的时候，可能出现的情况可分为以下4种：

1.解支配解，或者解支配解；

• 显然此时它们分别在不同地层级
• 因此，假如解支配解，那么解肯定不在当前前沿面当中，所以为了得到当前前沿面，再将解和其它解进行比较就没有必要，也就是说任何和解的比较都可以跳过。

2.解和解互不支配，而且它们在同一个层级，且此层级为当前前沿面；

• 这两个解的比较是必要的

3.解和解互不支配，而且它们在同一个层级，但是此层级不为当前前沿面；

• 这说明至少存在一个解支配解和一个解支配解，根据情况1，这两个解的比较可以跳过。

4.解和解互不支配，但是它们不在同一个层级。

• 这说明至少有一个解支配这两个解的其中一个，根据情况1，这两个解的比较也可以跳过。

总结来说，如果仅为了得到当前前沿面，将两个解相互比较，如果是一个解支配另一个解的关系，那么另一个解就不用再和其他任何解比较了。

推广到非支配排序问题，假设有个解，如果它们能被分为个层级，且每一层级包含解的数量为，则该层级上的一个解至少有个解支配它，每一个层级都至少有一个解支配它，也就是说要确定该层级上的所有解，最少需要比较的次数为。因此，要确定为不同层级的解，理论上最少需要比较的次数为：；而要确定为同一层级的解，理论上需要的最少比较次数为，。

上面的例子中，序号0、1、5的比较，属于情况分类的第3种情况；

序号2、3、6、7、9、10的比较，属于情况分类的第4种情况。

通过以上分析，这些比较，都有可能是多余的比较。如何避免其中多余的比较呢？

Algorithm3

• 首先对个解按照解的第一个目标以升序进行排序；

• 如果第一个目标值一样，就按第二个目标值，以此类推。
• 事先去重，避免目标值完全一样，如果还存在目标值完全一样，那它们的顺序任意。
• 排好序后，如果，则解不可能支配解。也就是说只存在两种情况：1.解支配解; 2.解和解互不支配

• 然后对排好序的个解，从解到解，一个一个地将它们归类到各自的层级中去

• 由于前面已经按第一个目标值排好序，因此解必然是层级1中的解，因为没有解能够支配它
• 接着看解，显然，除了解，没有解有可能支配解，因此它只需要和解比较，就可以确定它所在的层级：如果解和互不支配，那么解属于层级1；在此分支下看解，分两种情况：1.如果当前层级1没有解能够支配解，则解属于层级1; 2.如果当前层级1存在支配解的情况，则新建层级将解归入层级2; 如果解支配解，那么解属于层级2 在此分支下看解，同样分两种情况：1.先和层级1比较，如果解和解互不支配，那么解归入层级1; 2.如果被解支配，再和层级2比较：如果和解互不支配，归入层级2；如果被解支配，新建层级3，并归入层级3.
• 接下来推广到解，第个解属于哪一个层级呢？首先将解和层级1的解进行比较，如果没有能支配它的解就归入层级1；以此递推，只要遍历到层级k时，没有能够支配它的解，就将解归入层级k。如果每个现有层级都至少存在一个解支配解，就新建一个层级，并归入。由于层级内的解也是按排好序的顺序归入的，因此和每个层级解的比较应从最后一个解开始。

同样以前面的例子为例：首先按第一个目标值按升序排序，结果为：

然后依次将每一个解归类：先将解归入层级1；

排序完成，和Algorithm2相比，完全避免了前面分析的第4种情况的6次比较，比较次数从15次降到了9次，可见对于Algorithm2，属于第4种情况的这6次比较都是多余的。

考虑最坏的情况，此算法的时间复杂度仍然为，但是避免了多余的比较，且它不需要额外存储信息，实际运行效率会高很多。

还有可能更快吗？

Algorithm4

我们知道，如果给定一串排好序的数字，比如：

如果我们要查找某个数，可以简单地从第一个数开始遍历，直到找到它为止，这种算法时间复杂度为；

当然我们可以从这组数的中间开始查找：

• 先和6比较；
• 如果大于6，再和6和11的中间的数9比较；
• 以此递推，直到找到为止。

这就是二分查找法，其时间复杂度为。

为什么是呢？如果把以上的一组数字按照二分查找顺序，如下图树的形式存放（每一个节点的数都大于左边节点且小于右边节点），那查找的次数最多就是树的深度，而数的深度为，默认以2为底。

如果此时我们要将数字8插入到以上的数当中，不改变从小到大的顺序：

• 首先跟树根6比较，大于6
• 则再跟6的右边节点9比较，小于9
• 则跟9左边的7比较，发现大于7
• 则将8插入到7的右边

程序结束，发现插入和查找类似，同样是的时间复杂度。

而非支配排序就是不断将数据插入到对应层级的过程。

我们能把上面的分析推广到多维数据的情形吗？

以下面一组多目标问题的解为例，目标数为，解的数量为，事先对这组解按照第一个目标值，按升序排好序:

• 首先创建一个有一个根节点，三个子节点的空树，如下图：

• 肯定是第一层级的解，将它存入根节点：

• 将解和解比较，发现前三个目标值都不大于解，第4个目标值1小于解的2，因此，它们互不支配，解属于层级1，将解插入子节点中从左往右数第3个子节点中；

• 将解和解比较，发现第三个目标值小于了解，由于解是遍历到第4个目标值才小于解的，则说明解的前3个目标值都不小于解，而解的第3个目标值小于了解，则必然解的第3个目标值小于解，而由于事先按第一个目标值排好序，解不可能支配解，因此解和解必然是互不支配的；所以解不必再和解进行比较，一定属于层级1；由于是第3个目标值小于解，因此插入位置在子节点从左往右数第2个节点；

• 同理，解只需和解比较一次，可知其也属于层级1，且应将解插入如下图位置；

• 接下来将解与解比较，发现第二个目标值小于解，因此也可推断其和解、都互不支配；所以解只需再和解比较，发现解支配解；因此，解不属于层级1，此时新建一个同样的空树，对应层级2，将解存入根节点。

• 最后确定解，先和解比较，发现第3个目标值小于解，因此只需和子节点的第1和第2个节点解和比较，发现都互不支配，因此解属于层级1，又由于第3个目标小于解，且第2个目标值小于解，因此在子节点中第2个节点下新建三个子节点，并将解插入如下图位置。

程序结束，一共比较了8次，如果用Algorithm3，需要比较11次。

如果只考虑最好情况的话，每次插入比较次数只为树的深度，那么它的时间复杂度为。

到此为止了吗？

不了解我们的可以来补课了

非解构 | 数字化技术助力探索结构设计新空间

非解构 | 参数化建筑设计技术路径探讨

非解构 | 对BIM工作流的深度思考

当结构设计遇到遗传算法

当建筑师甩给我一个Rhino模型（一）

当建筑师甩给我一个rhino模型（二）

盈建科，二次开发

PKPM, 二次开发