【MATLAB第6期】#源码分享|基于MATLAB的精英非支配排序多目标遗传算法NSGA2，非工具箱

## 1 引言

在文献[1]中，作者提出了一种基于非支配排序的多目标进化算法(MOEA)，称为非支配排序遗传算法 II (NSGA-II)，它缓解了进化算法以下三个困难：

• 1. 时间复杂度为$O(MN^3)$，其中$M$为求解目标数，$N$为种群数目
  

• 2. 非精英主义方法

• 3. 需要指定共享参数

具体来说，提出了一种计算复杂度为$O(MN^2)$的快速非支配排序方法。此外，还提出了一个选择算子，它通过结合父母和后代种群并选择最佳（关于适应度和传播）解决方案来创建交配池。对困难测试问题的仿真结果表明，与 Pareto 归档进化策略和强度 Pareto EA 相比，在大多数问题中，所提出的 NSGA-II 能够在真正的 Pareto 最优前沿附近找到更好的解分布和更好的收敛性——另外两个精英 MOEAs 特别关注创造一个多样化的帕累托最优前沿。

原则上，一个问题中存在多个目标会产生一组最优解（主要是称为帕累托最优解），而不是单个最优解。 在没有任何进一步信息的情况下，不能说这些帕累托最优解中的一个比另一个更好。 这要求用户找到尽可能多的帕累托最优解。 经典优化方法（包括多准则决策方法）建议通过一次强调一个特定的帕累托最优解将多目标优化问题转换为单目标优化问题。 当这种方法用于寻找多个解决方案时，必须多次应用，希望在每次模拟运行时找到不同的解决方案。

在过去几十年中，已经提出了许多多目标进化算法 (MOEA)。由于进化算法 (EA) 与大量解决方案一起工作，因此可以扩展一个简单的 EA 以维护一组不同的解决方案。 强调向真正的帕累托最优区域移动，EA 可用于在一次模拟运行中找到多个帕累托最优解。

 N. Srinivas，Kalyanmoy Deb提出的非支配排序遗传算法 (NSGA) 是最早的此类 EA 之一。 多年来，对 NSGA 方法的主要批评如下：

1. 非支配排序计算复杂度高：NSGA非支配排序算法的计算复杂度为$O(MN^3)$（其中$M$为目标数，$N$为种群规模）。 这使得NSGA 对于大种群规模的计算成本很高。 之所以会出现这种大的复杂性，是因为每一代的非支配排序过程都涉及到复杂性。

2. 缺乏精英主义：最近的研究结果表明，精英主义可以显着加快 GA 的性能，这也有助于防止一旦找到好的解决方案就丢失。

3. 需要指定共享参数$\delta_{share}$：确保种群多样性以得到多种等效解决方案的传统机制主要依赖于共享的概念。 共享的主要问题是它需要指定共享参数($\delta_{share}$)。

本文的NSGA-Ⅱ解决了所有这些问题。 从对许多困难测试问题的模拟结果来看，我们发现 NSGA-II 在寻找多样化集合方面优于其他两个当代 MOEA：帕累托存档进化策略 (PAES)和强度帕累托 EA (SPEA)的解决方案，并在真正的帕累托最优集附近收敛。

## 2 算法实现

## 3 参考文献

[1] Deb K , Pratap A , Agarwal S , et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.

## 4 代码免费获取

https://mbd.pub/o/bread/mbd-Y52bl59v