上一节设计各种关于pareto的定义。 通过那些我们知道对于多目标我们第一步找的是Pareto-optimal set。 而Pareto-optimal set是non-domiated set的一个子集。 所以我需要先从非支配解集入手,然后去除local non-dominated set。
在一些方法中会举例子: 说明 具具体的过程,假设有五个个体分别如下图:
方法1: Naive and Slow
具体的实例的过程:
通过例子很显然知道step 2 的复杂度是n*M ,n个个体每一个都分别计算目标相比较,而step 4 是step 2 的返回。 故而总的复杂度就变成了step 4 n*n*M---------O(n*n*M)
方法2: Continuously Updated
具体的实例:
通过实例就是比方法1 简单了很多啊。 分析复杂度: 需要对比的次数: 1+2+3+..+(n-1) = O(n*n)
每一个个体要计算目标函数: 总体复杂度(最坏情况)------- O(n*n*M)
但是实际中的运算量是方法1 的一半。
方法3: Kung et al.'s Efficient Methods
具体的实例:
计算复杂度:
三种方法在M= 10 ,个体数目和计算量之间的关系
通过以上的三种方法我们看到的都是通过已有的解,然后通过诸葛的比较各个目标函数的值进行非支配的分析,
方法三是分来来进行的。
有一种方法可以使得简单的通过对比按照个目标的排名顺序,然后得到非支配pareto-optimal 吗?还是我异想天开?