假设我们要求最小值问题,且求解问题共有 个目标;
解 支配解 的含义就是: 的所有目标值都不大于 。
此时如果有 个解,我们要对这 个解进行排序。
按照支配关系的定义,那么所有解中,不被任何解支配的一组解,就为 个解的 前沿面 ,也就是当前这组解的最优解,当然前沿面中的解也是相互不能支配的;
把前沿面的解去掉,在剩余解中很自然也能找到一组解为当前剩余所有解的前沿面,这组解我们称为第二层级的解;
以此递归,最终我们会找到所有层级的解。
如下图,所有解都被归类到各自的层级,也就是多目标优化问题的非支配排序结果。
举个例子:
我们有如下6个解,目标数量 为2:
: (5, 4)
: (6, 3)
: (7, 2)
: (1, 6)
: (2, 5)
: (3, 1)
一个很自然的想法就是,将每一个解和其他解都比一遍,找出没有被任何解支配的解,并归类到层级1中;
然后将这些解去掉,对剩余的解做同样的操作。
接下来我们就这么干:
比较 | 结果 | 操作 |
---|---|---|
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 归入到层级1中 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 归入到层级1中 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 无 |
, | 互不支配 | 归入到层级1中 |
通过这一轮比较,除了解 、 、 有被支配的情况,其余解都不被任何解支配,将解 、 、 归类到层级1并移除,然后进行第二轮比较。
此时剩余解为 、 、 。
比较 | 结果 | 操作 |
---|---|---|
, | 互不支配 | 无 |
, | 互不支配 | 归入到层级2中 |
, | 互不支配 | 无 |
, | 互不支配 | 归入到层级2中 |
, | 互不支配 | 无 |
, | 互不支配 | 归入到层级2中 |
发现没有任何解支配剩余的解,因此 、 、 都被归类到层级2,非支配排序就结束了,排序结果如下图。
对于目标数为 ,解的个数为 的情况,最坏情况需要比较的次数为:
因此这一算法的时间复杂度为 。当 稍大的时候,这是一个很耗时的过程。
仔细看上面的比较过程,可以发现很多情况我们重复比较了很多次,第二轮所有的比较情况在第一轮都已经比较过一次。我们自然地想,能不能设计一种算法,使所有解与解之间的比较只进行一次呢?
将每一个解 比和其它所有解相比较,得出支配解 的解的数量 ,和解 支配的解的集合 ;
为0的解,意味着解 不被任何解支配,因此它是当前所有解的前沿面中的解,归入到层级1;
遍历当前所有解的前沿面的每一个解,将它们支配的解的集合 中的解的支配数 减1,如果遍历的过程当中减1后结果为0,则说明支配这个解的解全部在已经归好类的解当中,剩余的解当中没有能够支配这个解的解,因此这个解是剩余所有解的前沿面的解,将其归入到下一层级;
以此递归,直到所有解的支配数 都等于0,非支配排序结束。
同样以上面的例子为例:
先将每一个解和所有其它解进行比较,得到 和 ;
序号 | 比较 | 结果 | 左 | 右 | 左 | 右 |
---|---|---|---|---|---|---|
0 | , | 互不支配 | 0 | 0 | {} | {} |
1 | , | 互不支配 | 0 | 0 | {} | {} |
2 | , | 互不支配 | 0 | 0 | {} | {} |
3 | , | 互不支配 | 0 | 0 | {} | {} |
4 | , | 支配 | 1 | 0 | {} | { } |
5 | , | 互不支配 | 0 | 0 | {} | {} |
6 | , | 互不支配 | 0 | 0 | {} | {} |
7 | , | 互不支配 | 0 | 0 | {} | {} |
8 | , | 支配 | 1 | 0 | {} | { , } |
9 | , | 互不支配 | 0 | 0 | {} | {} |
10 | , | 互不支配 | 0 | 0 | {} | {} |
11 | , | 支配 | 1 | 0 | {} | { , , } |
12 | , | 互不支配 | 0 | 0 | {} | {} |
13 | , | 互不支配 | 0 | 0 | {} | {} |
14 | , | 互不支配 | 0 | 0 | {} | {} |
可得解
,
,
的
为0,将它们归到层级1,然后对它们支配的解的集合进行遍历,执行 ni -= 1
,剩余的解的
也全部变为0,归到层级2,排序结束。
对于目标数为 ,解的个数为 的情况,此算法最坏的情况需要比较的次数为:
因此时间复杂度为 ,但是因为比较的过程当中要保存每个解的 和 ,空间复杂度上升为 。
在算法耗时方面,提升已经非常的大。
上面的算法还有提升的空间吗,或者说每一次的比较是否全是必要的呢?以及有没有可能不存储任何信息,还能以最少的比较次数完成非支配排序呢?
仔细地分析,解 和解 进行支配关系比较的时候,可能出现的情况可分为以下4种:
1.解 支配解 ,或者解 支配解 ;
2.解 和解 互不支配,而且它们在同一个层级,且此层级为当前前沿面;
3.解 和解 互不支配,而且它们在同一个层级,但是此层级不为当前前沿面;
4.解 和解 互不支配,但是它们不在同一个层级。
总结来说,如果仅为了得到当前前沿面,将两个解相互比较,如果是一个解支配另一个解的关系,那么另一个解就不用再和其他任何解比较了。
推广到非支配排序问题,假设有 个解,如果它们能被分为 个层级,且每一层级 包含解的数量为 ,则该层级上的一个解至少有 个解支配它,每一个层级都至少有一个解支配它,也就是说要确定该层级上的所有解,最少需要比较的次数为 。因此,要确定为不同层级的解,理论上最少需要比较的次数为: ;而要确定为同一层级的解,理论上需要的最少比较次数为 , 。
上面的例子中,序号0、1、5的比较,属于情况分类的第3种情况;
序号2、3、6、7、9、10的比较,属于情况分类的第4种情况。
通过以上分析,这些比较,都有可能是多余的比较。如何避免其中多余的比较呢?
首先对 个解按照解的第一个目标以升序进行排序;
然后对排好序的 个解,从解 到解 ,一个一个地将它们归类到各自的层级中去
同样以前面的例子为例:首先按第一个目标值按升序排序,结果为:
: (1, 6)
: (2, 5)
: (3, 1)
: (5, 4)
: (6, 3)
: (7, 2)
然后依次将每一个解归类:先将解 归入层级1;
序号 | 比较 | 结果 | 操作 |
---|---|---|---|
0 | , | 互不支配 | 归入层级1 |
1 | , | 互不支配 | 无 |
2 | , | 互不支配 | 归入层级1 |
3 | , | 被支配 | 新建层级2并归入 |
4 | , | 被支配 | 无 |
5 | , | 互不支配 | 归入层级2 |
6 | , | 被支配 | 无 |
7 | , | 互不支配 | 无 |
8 | , | 互不支配 | 归入层级2 |
排序完成,和Algorithm2相比,完全避免了前面分析的第4种情况的6次比较,比较次数从15次降到了9次,可见对于Algorithm2,属于第4种情况的这6次比较都是多余的。
考虑最坏的情况,此算法的时间复杂度仍然为 ,但是避免了多余的比较,且它不需要额外存储信息,实际运行效率会高很多。
还有可能更快吗?
我们知道,如果给定一串排好序的数字,比如:
如果我们要查找某个数,可以简单地从第一个数开始遍历,直到找到它为止,这种算法时间复杂度为 ;
当然我们可以从这组数的中间开始查找:
这就是二分查找法,其时间复杂度为 。
为什么是 呢?如果把以上的一组数字按照二分查找顺序,如下图树的形式存放(每一个节点的数都大于左边节点且小于右边节点),那查找的次数最多就是树的深度,而数的深度为 , 默认以2为底。
如果此时我们要将数字8插入到以上的数当中,不改变从小到大的顺序:
程序结束,发现插入和查找类似,同样是 的时间复杂度。
而非支配排序就是不断将数据插入到对应层级的过程。
我们能把上面的分析推广到多维数据的情形吗?
以下面一组多目标问题的解为例,目标数 为 ,解的数量 为 ,事先对这组解按照第一个目标值,按升序排好序:
: (1, 3, 4, 2)
: (2, 4, 4, 1)
: (3, 5, 3, 2)
: (4, 1, 3, 2)
: (5, 2, 4, 3)
: (6, 4, 2, 1)
程序结束,一共比较了8次,如果用Algorithm3,需要比较11次。
如果只考虑最好情况的话,每次插入比较次数只为树的深度 ,那么它的时间复杂度为 。
到此为止了吗?
0人已收藏
0人已打赏
免费0人已点赞
分享
结构资料库
返回版块41.19 万条内容 · 374 人订阅
阅读下一篇
一套标准的房屋加固流程,工程人须收藏了!有很多人只知道房屋建筑加固一些大概的情况,却不知道,该如何细致性地了解加固工程。一套规范的加固流程,不仅仅能提升整个工程加固的项目进度,还能有很好的规范制度可执行。 加固流程的规范: 一.鉴定和抗震鉴定 在进行建筑加固工程开展前,先要对它进行勘察,这也是对建筑的原结构进行房屋安全鉴定后出具结构鉴定报告,然后再根据结构的具体病害,进行有效的加固措施。 二.考虑建筑加固的一些方法 针对不同的房屋出现的问题,选用不同的建筑加固方法,下面来列举下几个常见的建筑加固方法。
回帖成功
经验值 +10
全部回复(0 )
只看楼主 我来说两句抢沙发