【调度算法】共享函数vs拥挤距离

【声明】文章大部分内容是gpt写的，发现有问题的地方我都按照自己的理解修改了，但不保证没有其他未排查出来的错误，谨慎阅读。如发现错误也欢迎指出。

在多目标遗传算法（MOGA）和多目标优化中，共享函数方法是一种用于维护种群多样性的技术。这个方法的目标是在遗传算法的演化过程中促进种群中的解决方案分布均匀，以便更好地探索 Pareto 前沿。原始的非支配排序遗传算法（NSGA，Non-dominated Sorting Genetic Algorithm）使用了这种共享函数方法，以帮助维护多样性。

共享函数方法

1. 距离度量：首先，对于种群中的每个解决方案，计算它与其他解决方案之间的距离。这通常是欧几里得距离或其他距离度量方式。这个距离用于表示解决方案之间的相似性或互斥性。

2. 共享值计算：接下来，对于每个解决方案，计算一个共享值，这个值考虑了解决方案周围的其他解决方案的数量以及它们之间的距离。这个共享值表示了解决方案所处的拥挤程度。通常，距离越远的解决方案将具有更大的共享值，而距离较近的解决方案将具有较小的共享值。

3. 适应值调整：最后，根据计算的共享值，调整每个解决方案的适应值。这样，具有高共享值的解决方案将受到一定程度的适应值减小，而具有低共享值的解决方案将受到一定程度的适应值提高。这鼓励算法在选择解决方案时倾向于选择具有更高共享值的解决方案，以维持多样性。

通过引入共享函数方法，NSGA 旨在确保多目标遗传算法在演化过程中保持种群多样性，从而更好地探索 Pareto 前沿的各种解决方案。共享函数方法的性能通常受其参数的设置影响，因此需要仔细选择和调整这些参数以适应特定问题的需求。这个方法有助于避免种群陷入局部最优解，尤其是在多目标优化问题中。

拥挤距离

拥挤距离（Crowding Distance）是一种用于多目标优化问题中的概念，旨在帮助维持种群中解决方案的多样性和分布均匀性。在多目标优化中，通常有多个目标函数，因此不再有一个单一的最优解，而是存在一组解构成的 Pareto 前沿，其中没有解可以在所有目标函数上优于其他解。

拥挤距离用于度量解决方案在目标空间中的相对密度。它考虑了解决方案与其周围解决方案之间的距离，以确定哪些解决方案在目标空间中更为拥挤，哪些更为稀疏。拥挤距离的计算通常涉及以下步骤：

1. 对每个目标函数值排序：首先，将种群中的解决方案按照每个目标函数的值进行排序。这意味着对于每个目标函数，都会对解决方案进行排序。

2. 计算拥挤距离：对于每个解决方案，计算其在目标空间中的拥挤距离。拥挤距离通常是通过将该解周围的邻近解之间的距离进行累积计算而得出。这可以是在目标函数值上的距离，也可以是其他距离度量。

3. 分配边界解的距离值：通常，对于每个目标函数，将具有最小和最大函数值的解分配一个无穷大的拥挤距离值。这是因为这些解通常位于 Pareto 前沿的边界上。

4. 计算中间解的拥挤距离：对于其他中间解，根据其在排序后的位置，计算其拥挤距离，通常是使用相邻解的目标函数值差异来计算。

5. 综合拥挤距离：对于每个解决方案，将其在各个目标函数上的拥挤距离进行综合，以获得综合的拥挤距离值。

拥挤距离的目标是帮助遗传算法或其他多目标优化算法选择那些在 Pareto 前沿上分布均匀的解决方案，从而维持多样性。拥挤距离方法通常在多目标优化问题中使用，以帮助算法选择适当的解决方案，以获得全面的 Pareto 前沿覆盖。

共享函数vs拥挤距离

在非支配排序遗传算法 II（NSGA-II）和原始的非支配排序遗传算法（NSGA）中，拥挤距离和共享函数都是用于维持种群多样性的方法。尽管它们的目标相似，但在实现上存在一些区别：

1. 拥挤距离（Crowding Distance）：

   • 定义：拥挤距离是指每个个体与其邻近个体之间的平均距离。在NSGA-II中，拥挤距离是通过对每个个体的目标空间位置进行排序，然后计算它与其相邻个体之间的距离得到的。
   • 使用：拥挤距离用于帮助选择的时候平衡个体的多样性和适应值。在选择过程中，会优先选择拥挤距离大的解决方案，以便保持多样性。

2. 共享函数（Sharing Function）：

   • 定义：共享函数是通过计算解决方案之间的距离和相邻解决方案的数量来衡量解决方案之间的拥挤程度。它被用于修改解决方案的适应值，以便更好地维持多样性。
   • 使用：共享函数被用于调整解决方案的适应值。通过共享函数，距离较近的解决方案将被惩罚，适应值较高的解决方案将被降低。这样，选择操作倾向于选择那些具有更高共享值的解决方案，以保持多样性。

主要区别：

• 拥挤距离主要用于选择操作，通过选择具有较大拥挤距离的解决方案来保持多样性。
• 共享函数则是一种适应值调整方法，用于在选择前对解决方案进行排序，调整解决方案的适应值，以便在选择过程中考虑多样性。

虽然拥挤距离和共享函数都是用于维持多样性的技术，但它们的应用方式和实现细节有所不同，这使得它们在不同的多目标优化问题中可能表现得更为有效。选择哪种方法通常取决于问题的特性和算法的性能需求。

伪代码

共享函数方法伪代码：

# 共享函数计算
function compute_shared_fitness(solution, solutions, distance_threshold):
    shared_fitness = 0.0
    
    for other_solution in solutions:
        # 计算解决方案之间的距离
        distance = calculate_distance(solution, other_solution)
        
        if distance < distance_threshold:
            # 如果距离小于阈值，增加共享值
            shared_fitness += 1 - (distance / distance_threshold)
    
    return shared_fitness

# 示例使用
solutions = [solution1, solution2, solution3, ...]  # 种群中的解
distance_threshold = 2.0  # 共享距离阈值

# 计算每个解的共享函数值
shared_fitness_values = []
for solution in solutions:
    shared_fitness = compute_shared_fitness(solution, solutions, distance_threshold)
    shared_fitness_values.append(shared_fitness)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

拥挤距离方法伪代码：

# 拥挤距离计算
function compute_crowding_distance(solutions, objectives):
    n = number of solutions
    m = number of objectives
    crowding_distances = [0] * n
    
    # 对每个目标函数值进行排序
    for obj_index in range(m):
        sorted_solutions = sort_solutions_by_objective(solutions, obj_index)
        
        # 最小值和最大值的拥挤距离设置为无穷大
        crowding_distances[sorted_solutions[0]] = infinity
        crowding_distances[sorted_solutions[n-1]] = infinity
        
        # 计算中间解的拥挤距离
        for i in range(1, n - 1):
            crowding_distances[sorted_solutions[i]] += (
                (objectives[sorted_solutions[i + 1]][obj_index] - objectives[sorted_solutions[i - 1]][obj_index])
                / (objectives[sorted_solutions[n - 1]][obj_index] - objectives[sorted_solutions[0]][obj_index])
            )
    
    return crowding_distances

# 示例使用
solutions = [solution1, solution2, solution3, ...]  # 种群中的解
objectives = [objective_values1, objective_values2, objective_values3, ...]  # 解的目标函数值

# 计算拥挤距离
crowding_distances = compute_crowding_distance(solutions, objectives)
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

复杂度比较：

• 共享函数方法的复杂度主要由距离计算和共享值计算组成，两者都需要O(N²)的计算，其中N是解的数量。因此，共享函数方法的复杂度通常是O(N²)。
• 拥挤距离方法的复杂度取决于排序操作，对每个目标函数进行排序需要O(N log N)的时间，然后计算拥挤距离需要O(N)的时间。因此，拥挤距离方法的复杂度通常是O(N log N)。

虽然拥挤距离方法的排序操作具有较高的时间复杂度，但在实践中通常表现得更为稳健，因为它不需要显式设置距离阈值。同时，拥挤距离方法适用于多目标优化问题，而共享函数方法通常在单目标优化问题或双目标问题中更为常见。