【调度算法】快速非支配排序算法

这段代码实现的是快速非支配排序算法（Fast Non-dominated Sorting Algorithm）。

算法输入和输出：
这个函数的输入是两个列表 values1 和 values2，分别表示多目标优化问题中每个解在两个目标函数下的取值。输入的两个列表应该具有相同长度，即每个解在两个目标函数下均有取值。

这个函数的输出是一个二维列表 front，其中包含 Pareto 前沿中每层非支配解的索引。具体而言，front[i] 表示第 i 层 Pareto 前沿中非支配解的索引列表。前沿的层数不确定，因此 front 列表中的子列表数量也不确定，需要根据具体的解集确定。每个非支配解只会出现在其中的一个 Pareto 前沿层级中。

举个例子，如果返回结果是 [[1, 4], [0, 3], [2]]，表示在多目标优化问题中存在三个 Pareto 前沿层级。其中第一层包含解索引 1 和 4，第二层包含解索引 0 和 3，第三层包含解索引 2。

算法思路：
快速非支配排序算法是一种用于多目标优化问题的非支配解搜索算法。所谓“非支配解”指的是在多个优化目标下，无法找到一个解集中的解，比这个解更好。

具体实现过程：
首先，算法输入两个向量 values1 和 values2，对于其中的每一个解 p，在 values1 和 values2 上进行比较寻找支配解 q，如果 p 被 q 支配，那么就将 p 加入到 q 的被支配集合 S[q] 中。同时记录下 q 被支配的次数，即 n[q]，表示有多少个解与 q 相比，更优秀或者等价。如果一个解 p 的 n[p] 为 0，那么它就是一个非支配解，将其放入 Pareto 前沿的第一层 front[0] 中。

接下来，将 front[0] 中的所有非支配解从解集中删除，并将其加入到 Pareto 前沿的列表 front 中。循环处理直到没有解可以放入前沿。

最后，返回计算得到的 Pareto 前沿集合 front，其中的元素是按照被支配的关系排列的。

python代码：

def fast_non_dominated_sort(values1, values2):
    # 初始化 S, front, n 和 rank 列表
    S = [[] for i in range(0, len(values1))]  # 记录每个解的被支配解集合
    front = [[]]  # 记录 Pareto 前沿层级
    n = [0 for i in range(0, len(values1))]  # 记录每个解被支配的次数
    rank = [0 for i in range(0, len(values1))]  # 记录每个解所处的 Pareto 前沿层级

    # 对每个解计算被支配解集合 S 和支配该解的次数 n
    for p in range(0, len(values1)):
        S[p] = []
        n[p] = 0
        for q in range(0, len(values1)):
            if (values1[p] > values1[q] and values2[p] > values2[q]) or (
                    values1[p] >= values1[q] and values2[p] > values2[q]) or (
                    values1[p] > values1[q] and values2[p] >= values2[q]):
                if q not in S[p]:
                    S[p].append(q)
            elif (values1[q] > values1[p] and values2[q] > values2[p]) or (
                    values1[q] >= values1[p] and values2[q] > values2[p]) or (
                    values1[q] > values1[p] and values2[q] >= values2[p]):
                n[p] = n[p] + 1
        # 如果一个解没有被任何其他解支配，则将其归为 Pareto 前沿的第一层
        if n[p] == 0:
            rank[p] = 0
            if p not in front[0]:
                front[0].append(p)

    # 循环计算 Pareto 前沿集合
    i = 0
    while (front[i] != []):
        Q = []
        for p in front[i]:
            # 遍历被支配解集合 S，更新其 n 值
            for q in S[p]:
                n[q] = n[q] - 1
                # 如果某个解 q 不被其他解支配，则将其归为下一层 Pareto 前沿
                if (n[q] == 0):
                    rank[q] = i + 1
                    if q not in Q:
                        Q.append(q)
        i = i + 1
        # 将下一层 Pareto 前沿加入到 front 中
        front.append(Q)

    # 删除最后一个空元素
    del front[len(front) - 1]
    # 返回 Pareto 前沿集合
    return front
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

用例测试：
假设有以下输入：

values1 = [5, 2, 9, 3, 7, 4]
values2 = [6, 4, 8, 2, 5, 3]
1
2

那么根据该测试用例，函数的返回结果应该是：

[[2], [0, 4], [1, 5], [3]]
1

解释一下返回结果的含义：返回列表中的第一个子列表 [2] 表示 Pareto 前沿的第一层，其中的解索引是 2 。这表示在给定的输入中，解 2 是非支配解且无法被其他解支配。返回列表中的第二个子列表 [0, 4] 表示 Pareto 前沿的第二层，其中的解索引分别是 0 和 4。这表示在给定的输入中，解 2 支配解 0和 4 ，解 0和 4 之间是非支配解。返回列表中的第三个子列表 [1, 5] 表示 Pareto 前沿的第三层，其中的解索引分别是 1 和 5。这表示在给定的输入中，解 0 和解 4 支配解 1和 5 ，解 1 和 5 之间是非支配解。其余类推。