NSGA-II

INTRODUCTION

非支配排序遗传算法（NSGA-II）是一种多目标优化算法，它通过在遗传算法的基础上引入非支配排序和拥挤度计算，以平衡多目标优化问题中的多个目标。NSGA-II是遗传算法的一种改进版本，它在遗传算法的基础上引入了非支配排序和拥挤度计算，以平衡多目标优化问题中的多个目标。本文将简要介绍NSGA-II的关键点和实现。

非支配排序

支配和非支配关系

设p和q是两个解，称p支配q，当且仅当，1. 对于所有的子目标，p的目标值都不劣于q的目标值；2. 至少有一个子目标，p的目标值优于q的目标值。

非支配排序

Non-dominated Sorting 是一种用于多目标优化的排序算法，它将解按照支配关系划分为多个非支配集合。

初始化：将所有解放入一个初始非支配集合中。
对每个解计算两个属性：（1）$n_i$:解 $i$ 被其他解支配的次数；（2）$s_i$:解 $i$ 支配的解的集合。
然后找到 $n_i = 0$ 的解，将其放入一个新的集合 $F_1$ 中，此时 $F_1$的等级为1

对 $F_1$ 中的每个解 $i$，将其从 $s_i$ 中删除，然后对 $s_i$ 中的每个解 $j$，计算 $n_j = n_j - 1$，如果 $n_j = 0$，则将其放入 $F_2$ 中，此时 $F_2$ 的等级为2。依此类推，直至所有解被分类。

实现

def fast_non_dominated_sort(population):
    """
    非支配排序
    """
    fronts = [[]]
    for p in population:
        # 计算p的支配关系
        p.dominated_solutions = []
        p.domination_count = 0
        for q in population:
            if (p.f1 < q.f1 and p.f2 < q.f2) or (p.f1 <= q.f1 and p.f2 < q.f2) or (p.f1 < q.f1 and p.f2 <= q.f2):
                p.dominated_solutions.append(q)
            elif (q.f1 < p.f1 and q.f2 < p.f2) or (q.f1 <= p.f1 and q.f2 < p.f2) or (q.f1 < p.f1 and q.f2 <= p.f2):
                p.domination_count += 1
        if p.domination_count == 0:
            p.rank = 1
            fronts[0].append(p)
    i = 0
    # 计算每个解的等级
    while len(fronts[i]) > 0:
        next_front = []
        for p in fronts[i]:
            for q in p.dominated_solutions:
                q.domination_count -= 1
                if q.domination_count == 0:
                    q.rank = i + 2
                    next_front.append(q)
        i += 1
        fronts.append(next_front)
    fronts.pop()  
    return fronts

拥挤度计算

Crowding Distance 是一种用于多目标优化的度量方法，它用于评估解在非支配排序中的拥挤程度。

拥挤度指目标空间上的每一点与同等级相邻两点之间的局部拥挤距离

使用这一测度可使Pareto解集在目标空间分布比较均匀。
具体实现：

def calculate_crowding_distance(front):
    """
    计算拥挤距离
    """
    if not front:
        return
    l = len(front)
    for individual in front:
        individual.crowding_distance = 0.0

    for m in ['f1', 'f2']:
        front.sort(key=lambda x: getattr(x, m))
        # 设置边界点的拥挤距离为无穷大
        setattr(front[0], 'crowding_distance', float('inf'))
        setattr(front[-1], 'crowding_distance', float('inf'))
        m_values = [getattr(ind, m) for ind in front]
        min_m = min(m_values)
        max_m = max(m_values)
        if max_m == min_m:
            continue  
        for i in range(1, l - 1):
            distance = (front[i + 1].__dict__[m] - front[i - 1].__dict__[m]) / (max_m - min_m)
            front[i].crowding_distance += distance

模拟二进制交叉

Simulated Binary Crossover (SBX) 是一种用于遗传算法中的交叉操作的方法，它模拟了二进制编码中实数的交叉操作。关键是在交叉过程中，根据交叉概率和分布索引来控制交叉的程度。

首先，从当前解集中选择两个父代个体。
然后，生成两个均匀分布的随机数 $r_1$ 和 $r_2$。通常设置一个交叉概率 $p_c$，如果 $r_1 \leq p_c$，则执行交叉操作，否则直接复制父代个体。

计算交叉参数

1 2	beta = 1.0 + (2.0 * (x_min) / (x_max - x_min)) alpha = 2.0 - math.pow(beta, -(eta + 1))

计算交叉后的子代个体

# 如果rand小于等于1/alpha
betaq = math.pow(rand * alpha, 1.0 / (eta + 1))
# 否则
betaq = math.pow(1.0 / (2.0 - rand * alpha), 1.0 / (eta + 1))
c1 = 0.5 * ((x_min + x_max) - betaq * (x_max - x_min))
c2 = 0.5 * ((x_min + x_max) + betaq * (x_max - x_min))

实现

def sbx_crossover(parent1, parent2, eta=20):
    """
    模拟二进制交叉
    """
    child1 = copy.deepcopy(parent1)
    child2 = copy.deepcopy(parent2)
    for i in range(len(parent1.chromosome)):
        if random.random() <= 0.9:
            x1 = parent1.chromosome[i]
            x2 = parent2.chromosome[i]
            if abs(x1 - x2) > 1e-14:
                x_min = min(x1, x2)
                x_max = max(x1, x2)
                rand = random.random()
                beta = 1.0 + (2.0 * (x_min) / (x_max - x_min))
                alpha = 2.0 - math.pow(beta, -(eta + 1))
                if rand <= 1.0 / alpha:
                    betaq = math.pow(rand * alpha, 1.0 / (eta + 1))
                else:
                    betaq = math.pow(1.0 / (2.0 - rand * alpha), 1.0 / (eta + 1))
                c1 = 0.5 * ((x_min + x_max) - betaq * (x_max - x_min))
                beta = 1.0 + (2.0 * (1.0 - x_max) / (x_max - x_min))
                alpha = 2.0 - math.pow(beta, -(eta + 1))
                if rand <= 1.0 / alpha:
                    betaq = math.pow(rand * alpha, 1.0 / (eta + 1))
                else:
                    betaq = math.pow(1.0 / (2.0 - rand * alpha), 1.0 / (eta + 1))
                c2 = 0.5 * ((x_min + x_max) + betaq * (x_max - x_min))
                c1 = min(max(c1, 0.0), 1.0)
                c2 = min(max(c2, 0.0), 1.0)
                child1.chromosome[i] = c1
                child2.chromosome[i] = c2
    return child1, child2

多项式变异

Polynomial Mutation (PM) 是一种用于遗传算法中的变异操作的方法，它模拟了二进制编码中实数的变异操作。

实现

def polynomial_mutation(individual, eta=20, mutation_prob=1.0/30):
    """
    多项式变异
    """
    for i in range(len(individual.chromosome)):
        if random.random() <= mutation_prob:
            x = individual.chromosome[i]
            delta1 = (x - 0.0) / (1.0 - 0.0)
            delta2 = (1.0 - x) / (1.0 - 0.0)
            rand = random.random()
            mut_pow = 1.0 / (eta + 1.)
            if rand < 0.5:
                xy = 1.0 - delta1
                val = 2.0 * rand + (1.0 - 2.0 * rand) * math.pow(xy, (eta +1))
                deltaq = math.pow(val, mut_pow) -1.0
            else:
                xy = 1.0 - delta2
                val = 2.0 * (1.0 - rand) + 2.0 * (rand -0.5) * math.pow(xy, (eta +1))
                deltaq = 1.0 - math.pow(val, mut_pow)
            x = x + deltaq
            x = min(max(x, 0.0), 1.0)
            individual.chromosome[i] = x
    return individual

Refs

[1] Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182-197.

[2] [遗传算法]模拟二进制交叉SBX与多项式变异

[3] NSGA-II-in-python