快速非支配排序 python版

过程

         

1. 为每个个体 i=1->N:
   计算它支配的解集合spi，支配它的个数npi。 复杂度O（N）
   同时记录处于第一前沿的解集合F1（其实就是npi=0的解放在F1中） 这一大步复杂度 O（MN2）

2. 现在开始分配前沿，初始化当前前沿等级=1。现在F1中所有解都没有其他解可以支配他们。所以他们是当前的最前沿，分配好了，接下来就把F1中的所有解都处理一下，做如下操作
             a、每个个体不都对应一个sp吗。遍历sp，对于每一个它支配的解x，我们把np-1（因为我们已经把这个解分配好了，自然要释放它支配的解），如果np=0了，说明没有其他解支配这个解了，那就说明它要变成下一次的最前沿了，所以先记录下来。放到集合Q里面
             b、遍历完了，说明这个前沿等级的都处理完了，前沿等级加一，然后开始处理下一前沿等级的解
             c、把Q赋值给F1，继续处理操作

直到所有的解都分配好了

代码

import numpy as np

def compare(p1, p2):
    # return 0同层 1 p1支配p2  -1 p2支配p1
    D = len(p1)
    p1_dominate_p2 = True  # p1 更小
    p2_dominate_p1 = True
    for i in range(D):
        if p1[i] > p2[i]:
            p1_dominate_p2 = False
        if p1[i] < p2[i]:
            p2_dominate_p1 = False

    if p1_dominate_p2 == p2_dominate_p1:
        return 0
    return 1 if p1_dominate_p2 else -1

def fast_non_dominated_sort(P):
    P_size = len(P)
    n = np.full(shape=P_size, fill_value=0)    # 被支配数
    S = []    # 支配的成员
    f = []    # 0 开始每层包含的成员编号们
    rank = np.full(shape=P_size, fill_value=-1)  # 所处等级

    f_0 = []
    for p in range(P_size):
        n_p = 0
        S_p = []
        for q in range(P_size):
            if p == q:
                continue
            cmp = compare(P[p], P[q])
            if cmp == 1:
                S_p.append(q)
            elif cmp == -1:  # 被支配
                n_p += 1
        S.append(S_p)
        n[p] = n_p
        if n_p == 0:
            rank[p] = 0
            f_0.append(p)
    f.append(f_0) 

    i = 0
    while len(f[i]) != 0:  # 可能还有i+1层
        Q = []
        for p in f[i]:  # i层中每个个体
            for q in S[p]:  # 被p支配的个体
                n[q] -= 1
                if n[q] == 0:
                    rank[q] = i + 1
                    Q.append(q)
        i += 1
        f.append(Q)
    rank +=1
    return rank,f


if __name__ == '__main__':
    P = np.array([[2,2,5],[2,1,3],[1,2,3],[3,1,4],[2,1,4],[1,3,5],[1,3,3]])
    rank, f = fast_non_dominated_sort(P)
    f.pop()         # 去掉最后的空集
    print(rank)
    print(f)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65