点击上方“进修编程”，选择“星标”公众号
超级无敌干货，第一时间送达！！！
非支配排序遗传算法 II (NSGA-II) 是一种广泛使用的多目标优化算法。它以处理大量群体的效率和保持解决方案多样性的能力而闻名。NSGA-II 采用快速非支配排序方法、精英主义和拥挤距离机制来确保帕累托前沿分布良好。
本文将探讨遗传算法和多目标优化的基础概念，强调 NSGA-II 的重要性。并用python一步一步实现。
理解多目标优化
多目标优化涉及同时优化两个或多个相互冲突的目标。与专注于寻找单个最佳解决方案的单目标优化不同，多目标优化旨在寻找一组代表目标之间最佳权衡的解决方案。这些解决方案构成了所谓的帕累托前沿，其中没有一个解决方案可以被认为比另一个更好，除非以牺牲另一个目标为代价来改善至少一个目标。
遗传算法可以通过修改其选择机制来适应多目标优化。这种适应通常涉及使用非支配排序和拥挤距离技术，以确保沿帕累托前沿的解决方案集多样化且分布良好。
什么是非支配排序遗传算法 2（NSGA-II）？
非支配排序遗传算法 II (NSGA-II) 由 Kalyanmoy Deb 和他的同事于 2000 年开发。它旨在解决其前身 NSGA 的局限性，特别是在计算效率和保持解决方案多样性的能力方面。
NSGA-II 中的关键概念
1. 非支配排序
非支配排序是一种将解决方案群体划分为不同级别的帕累托前沿的技术。如果群体中没有其他解决方案在所有目标上都比它更好，则该解决方案被称为非支配解决方案。第一个前沿包含非支配解决方案，后续前沿通过移除先前前沿的解决方案并找到下一组非支配解决方案来形成。这种排序对于在多目标优化中识别和保留高质量解决方案至关重要。
非支配排序过程
初始化：为每个解决方案分配一个初始等级，并为每个前沿创建一个空列表。
支配检查：对于每个解决方案，确定有多少个解决方案支配它以及它支配哪些解决方案。
前沿分配：不被其他方案支配的解决方案被分配到第一个前沿。通过删除已经分配的解决方案，对后续前沿重复该过程。
2. 拥挤距离
拥挤距离是一种用于保持帕累托前沿内解决方案多样性的度量。它通过优先考虑那些不太拥挤的区域来确保解决方案在目标空间中均匀分布。这有助于避免解决方案聚集并提供更全面的权衡解决方案集。
拥挤距离计算
初始化：将所有解决方案的拥挤距离设置为零。
排序：对于每个目标，根据目标值对解决方案进行排序。
边界分配：为边界解决方案分配无限拥挤距离。
距离计算：对于每个解决方案，根据邻近解决方案的目标值的归一化差异计算拥挤距离。
3.快速非支配排序算法
快速非支配排序算法有效地将种群排序到帕累托前沿，与传统方法相比降低了计算复杂度。所涉及的步骤如下：
初始化前沿：为每个帕累托前沿创建一个空列表。
主导计数：对于每个解决方案，计算主导它的解决方案的数量，并列出它主导的解决方案。
第一前沿分配：将具有零优势计数的解决方案分配给第一前沿。
后续前沿：对于当前前沿中的每个解决方案，减少其主导的解决方案的主导计数。如果任何解决方案的主导计数变为零，则将其分配给下一个前沿。
重复：继续该过程，直到所有解决方案都分配到一个前沿。
NSGA-II的工作原理
非支配排序遗传算法 II (NSGA-II) 是一种广泛用于解决多目标优化问题的算法。以下步骤概述了其工作机制：
步骤 1：初始化种群
随机生成初始个体种群。
每个个体由一条染色体（决策变量的向量）表示。
第 2 步：适应度函数评估
根据多个目标函数评估每个个体的适应度。
确定每个个体需要最小化或最大化的目标值。
步骤 3：非支配排序
将人口划分为不同的非统治层级（战线）。
第一个阵线由不受任何其他个体支配的个体组成。
第二阵线仅由第一阵线中的个体所主导，依此类推。
步骤4：计算拥挤距离
计算每个前沿内每个个体的拥挤距离。
拥挤距离度量客观空间中特定个体周围的个体密度。
具有较大拥挤距离的个体更受青睐，以促进多样性。
步骤 5：选择交叉的亲本
使用二元锦标赛选择来选择交叉的父母：
随机选择两个人。
比较他们的等级（非统治级别）。
选择排名较高的个体。
如果都属于同一阵面，则选择拥挤距离较大的那个。
步骤 6：交叉和变异算子的应用
交叉：
对选定的父母进行交叉以产生后代。
父母之间交换部分染色体以创造新的个体。
突变：
通过在后代的染色体中引入微小的随机变化来对其施加突变。
保持遗传多样性并探索解决方案空间的新领域。
第七步：创造下一代
将亲代种群和子代种群结合起来形成一个中间种群。
对合并后的群体进行非支配排序。
根据非支配等级和拥挤距离选择最佳个体形成下一代。
步骤 8：终止标准
重复选择、交叉、变异和生成更新的过程，直到满足终止标准。
常见的终止标准包括固定的代数、收敛阈值或最大计算预算。
最终的群体包含代表目标之间最佳权衡的帕累托最优解。
使用 Python 实现 NSGA-II
以下代码演示了非支配排序遗传算法 II (NSGA-II) 在Python中的实现。我们将代码分解为几个步骤以便于更好地理解。
步骤 1：导入库
导入数学计算、随机数生成和绘图所需的库。
import mathimport randomimport matplotlib.pyplot as plt
第 2 步：定义目标函数
定义我们要优化的目标函数。这里我们使用两个函数进行演示。
# First function to optimizedef function1(x):return -x**2# Second function to optimizedef function2(x):return -(x-2)**2
步骤 3：辅助函数
定义辅助函数来查找值的索引、按值排序并执行非支配排序。
# Function to find the index of a value in a listdef index_of(a, list):try:return list.index(a)except ValueError:return -1# Function to sort by valuesdef sort_by_values(list1, values):sorted_list = []values_copy = values[:]while len(sorted_list) != len(list1):min_index = index_of(min(values_copy), values_copy)if min_index in list1:sorted_list.append(min_index)values_copy[min_index] = math.infreturn sorted_list
步骤 4：快速非支配排序
实现快速非支配排序算法，将群体划分到不同的帕累托前沿。
# Function to carry out NSGA-II's fast non dominated sortdef fast_non_dominated_sort(values1, values2):S = [[] for _ in range(len(values1))]front = [[]]n = [0 for _ in range(len(values1))]rank = [0 for _ in range(len(values1))]for p in range(len(values1)):S[p] = []n[p] = 0for q in range(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]):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] += 1if n[p] == 0:rank[p] = 0if p not in front[0]:front[0].append(p)i = 0while front[i]:Q = []for p in front[i]:for q in S[p]:n[q] -= 1if n[q] == 0:rank[q] = i + 1if q not in Q:Q.append(q)i += 1front.append(Q)del front[-1]return front
步骤5：拥挤距离计算
计算拥挤距离以保持每个帕累托前沿内的多样性。
# Function to calculate crowding distancedef crowding_distance(values1, values2, front):distance = [0 for _ in range(len(front))]sorted1 = sort_by_values(front, values1[:])sorted2 = sort_by_values(front, values2[:])distance[0] = distance[-1] = float('inf')for k in range(1, len(front) - 1):distance[k] += (values1[sorted1[k + 1]] - values1[sorted1[k - 1]]) / (max(values1) - min(values1))distance[k] += (values2[sorted2[k + 1]] - values2[sorted2[k - 1]]) / (max(values2) - min(values2))return distance
第六步：遗传算子
定义交叉和变异函数来产生新的后代。
# Function to carry out the crossoverdef crossover(a, b):r = random.random()if r > 0.5:return mutation((a + b) / 2)else:return mutation((a - b) / 2)# Function to carry out the mutation operatordef mutation(solution):mutation_prob = random.random()if mutation_prob < 0.1:solution = min_x + (max_x - min_x) * random.random()return solution
步骤 7：初始化
使用指定范围内的随机值初始化群体。
# Main program starts herepop_size = 20max_gen = 50# Initializationmin_x = -55max_x = 55solution = [min_x + (max_x - min_x) * random.random() for _ in range(pop_size)]gen_no = 0# Tracking progress for visualizationprogress = []
步骤8：NSGA-II算法循环
运行 NSGA-II 算法指定代数。
while gen_no < max_gen:function1_values = [function1(solution[i]) for i in range(pop_size)]function2_values = [function2(solution[i]) for i in range(pop_size)]non_dominated_sorted_solution = fast_non_dominated_sort(function1_values[:], function2_values[:])print(f"The best front for Generation number {gen_no} is")for value in non_dominated_sorted_solution[0]:print(round(solution[value], 3), end=" ")print("\n")progress.append((function1_values, function2_values))crowding_distance_values = []for i in range(len(non_dominated_sorted_solution)):crowding_distance_values.append(crowding_distance(function1_values[:], function2_values[:], non_dominated_sorted_solution[i][:]))solution2 = solution[:]while len(solution2) != 2 * pop_size:a1 = random.randint(0, pop_size - 1)b1 = random.randint(0, pop_size - 1)solution2.append(crossover(solution[a1], solution[b1]))function1_values2 = [function1(solution2[i]) for i in range(2 * pop_size)]function2_values2 = [function2(solution2[i]) for i in range(2 * pop_size)]non_dominated_sorted_solution2 = fast_non_dominated_sort(function1_values2[:], function2_values2[:])crowding_distance_values2 = []for i in range(len(non_dominated_sorted_solution2)):crowding_distance_values2.append(crowding_distance(function1_values2[:], function2_values2[:], non_dominated_sorted_solution2[i][:]))new_solution = []for i in range(len(non_dominated_sorted_solution2)):non_dominated_sorted_solution2_1 = [index_of(non_dominated_sorted_solution2[i][j], non_dominated_sorted_solution2[i]) for j in range(len(non_dominated_sorted_solution2[i]))]front22 = sort_by_values(non_dominated_sorted_solution2_1[:], crowding_distance_values2[i][:])front = [non_dominated_sorted_solution2[i][front22[j]] for j in range(len(non_dominated_sorted_solution2[i]))]front.reverse()for value in front:new_solution.append(value)if len(new_solution) == pop_size:breakif len(new_solution) == pop_size:breaksolution = [solution2[i] for i in new_solution]gen_no += 1
步骤 9：可视化
绘制最终前沿和几代人的进展，以可视化优化过程。
# Let's plot the final frontfunction1_values = [function1(solution[i]) for i in range(pop_size)]function2_values = [function2(solution[i]) for i in range(pop_size)]# Visualize the final frontplt.xlabel('Function 1', fontsize=15)plt.ylabel('Function 2', fontsize=15)plt.title('Final Front')plt.scatter(function1_values, function2_values)plt.show()# Visualize the progress over generationsfor gen, (f1_vals, f2_vals) in enumerate(progress):plt.figure(figsize=(10, 6))plt.scatter(f1_vals, f2_vals)plt.xlabel('Function 1', fontsize=15)plt.ylabel('Function 2', fontsize=15)plt.title(f'Generation {gen}')plt.show()
输出：
NSGA-II 的优势
效率和速度：快速非支配排序和精英主义提高了计算效率和解决方案的质量。
多样化的解决方案：拥挤距离确保了一组分布良好的帕累托最优解决方案。
灵活性：适用于各个领域的广泛多目标问题。
无共享参数：通过使用拥挤距离而不是共享参数来简化实现。
广泛采用：已在学术界和工业界得到验证的性能和广泛的应用。
精英策略：保留最佳解决方案，加速融合。
约束处理：有效地管理约束，优先考虑可行的解决方案。
NSGA-II 的局限性
计算复杂性：对于大量群体或许多目标来说，计算成本和内存使用量很高。
参数敏感性：性能取决于交叉、突变率和种群大小的适当设置。
缺乏适应性：固定参数在动态环境中可能无法表现良好。
高维挑战：在具有许多目标的问题中难以保持多样性和有效收敛。
结论
NSGA-II 是一种强大的多目标优化工具，以其高效性、保持多样性的能力和跨领域的灵活性而闻名。尽管它存在一些局限性，例如计算复杂性和参数敏感性，但它的优势和广泛的应用使其成为进化多目标优化领域的领先算法。
matlab\python程序设计找我
— 完 —
