快速非支配排序

快速非支配排序是在\(Pareto支配\)基础上提出的概念。假设有\(k\)个目标函数记为\(f_i(x)\)，其中\(i\)是\(1, 2, … , k\)中的任意整数，\(j\)同样是\(1,2, …, k\)中的任意整数，但\(i≠j\)。若个体\(x_1\)和\(x_2\)对于任意的目标函数都有\(f_i(x_1) < f_i(x_2)\)则称个体\(x_1\)支配\(x_2\)；若对于任意的目标函数都有\(fi(x_1) ≤ fi(x_2)\)且至少有一个目标函数使得\(f_j(x_1) < f_j(x_2)\)成立则称\(x_1\)弱支配\(x_2\)；若既存在目标函数使得\(f_i(x_1) ≤ f_i(x_2)\)成立又存在目标函数满足\(f_j(x_1) > f_j(x_2)\)，则称个体\(x_1\)和\(x_2\)互不支配。

种群中的每个个体都有两个参数\(n_i\)和\(S_i\)，\(n_i\)为种群中支配个体i 的个体数量，\(S_i\)是被个体\(i\)支配的个体的集合,快速非支配排序的步骤如下：

（1）通过循环比较找到种群中所有\(n_i = 0\)的个体，赋予其非支配等级为1，并将这些个体存入非支配集合\(Rank_1\)中。

（2）集合\(Rank1\)中的每一个个体，将其所支配的个体集合中的每个个体的\(n_j\)都减去1，若\(n_j-1=0\)则将个体j存入集合\(Rank_2\)中，并赋予其中的个体非支配等级2。

（3）之后对\(Rank_2\)中的个体重复上述操作，直至所有个体都被赋予了非支配等级。

非支配等级也称作Pareto等级，其中Pareto等级为1的个体由于不受其他个体的支配，叫做非支配解，也叫 Pareto最优解，而解集所形成的曲线叫做Pareto前沿。以有两个目标函数f1和f2为例，假设经过快速非支配排序之后共分成了三个Pareto等级，如图4.1所示。图4.1中用圆圈表示的个体即Pareto等级为1的个体组成的集合为本例的Pareto最优解，这些个体形成的曲线即为本例的Pareto前沿。

img 
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
def QuickSort(index_list:list,value_list:list):
    def isADominateB(a_index,b_index):
        Flag=True
        for i in range(len(value_list[0])):
            if value_list[a_index][i]<value_list[b_index][i]:
                Flag=False
                break
        return Flag
    N=[0]*len(index_list)# 被支配的个数
    Q=[[] for i in range(len(index_list))]# 支配的个体集合
    Rank_Quene=[]
    for i in range(len(index_list)):
        for j in range(len(index_list)):
            if i!=j:
                if isADominateB(i,j):
                    Q[i].append(j)
                    N[j]+=1
    
    Now_Rank_List=[]
    for i in range(len(index_list)):
        if N[i]==0:
            Now_Rank_List.append(i)
    Rank_Quene.append(Now_Rank_List)# 加入Rank0

    while True:
        Now_Rank_List=[]
        for i in Rank_Quene[len(Rank_Quene)-1]:
            for j in Q[i]:
                N[j]-=1
                if N[j]==0:
                    Now_Rank_List.append(j)
        
        if len(Now_Rank_List)==0:
            break
        Rank_Quene.append(Now_Rank_List)
    return Rank_Quene

index_list=[0,1,2,3]
value_list=[(23,414),(123,4114),(11213,424),(22223,22244)]
QuickSort(index_list,value_list)