天天看点

阅读Book: MultiObjective using Evolutionary Algorithms (4) --- 3 种方法find Non-dominated set

上一节设计各种关于pareto的定义。 通过那些我们知道对于多目标我们第一步找的是Pareto-optimal set。 而Pareto-optimal set是non-domiated set的一个子集。 所以我需要先从非支配解集入手,然后去除local non-dominated set。

在一些方法中会举例子: 说明 具具体的过程,假设有五个个体分别如下图:

阅读Book: MultiObjective using Evolutionary Algorithms (4) --- 3 种方法find Non-dominated set

方法1:  Naive and Slow

阅读Book: MultiObjective using Evolutionary Algorithms (4) --- 3 种方法find Non-dominated set

具体的实例的过程:

阅读Book: MultiObjective using Evolutionary Algorithms (4) --- 3 种方法find Non-dominated set
阅读Book: MultiObjective using Evolutionary Algorithms (4) --- 3 种方法find Non-dominated set
通过例子很显然知道step 2 的复杂度是n*M ,n个个体每一个都分别计算目标相比较,而step 4 是step 2 的返回。 故而总的复杂度就变成了step 4 n*n*M---------O(n*n*M)

方法2: Continuously Updated

阅读Book: MultiObjective using Evolutionary Algorithms (4) --- 3 种方法find Non-dominated set

具体的实例:

阅读Book: MultiObjective using Evolutionary Algorithms (4) --- 3 种方法find Non-dominated set
阅读Book: MultiObjective using Evolutionary Algorithms (4) --- 3 种方法find Non-dominated set

通过实例就是比方法1 简单了很多啊。  分析复杂度: 需要对比的次数: 1+2+3+..+(n-1)  = O(n*n)

每一个个体要计算目标函数:                      总体复杂度(最坏情况)------- O(n*n*M)

但是实际中的运算量是方法1 的一半。

方法3: Kung et al.'s Efficient Methods

阅读Book: MultiObjective using Evolutionary Algorithms (4) --- 3 种方法find Non-dominated set

具体的实例:  

阅读Book: MultiObjective using Evolutionary Algorithms (4) --- 3 种方法find Non-dominated set
计算复杂度:
阅读Book: MultiObjective using Evolutionary Algorithms (4) --- 3 种方法find Non-dominated set

三种方法在M= 10 ,个体数目和计算量之间的关系

阅读Book: MultiObjective using Evolutionary Algorithms (4) --- 3 种方法find Non-dominated set

通过以上的三种方法我们看到的都是通过已有的解,然后通过诸葛的比较各个目标函数的值进行非支配的分析,

方法三是分来来进行的。

有一种方法可以使得简单的通过对比按照个目标的排名顺序,然后得到非支配pareto-optimal 吗?还是我异想天开?

继续阅读