多目标非支配排序遗传算法

本博客将详细介绍 NSGA-II算法的实现过程，对比分析约束与非约束条件下NSGA-II实现方法，另后期本博客还将添加基于偏好的 NSGA-II算法分析。本人对于智能优化算法/元启发式优化算法是初学，若有不当/错误之处，还望告知

首先，我提前在文章的上半部分列出本文撰写时所参考的论文及博客，望读者多多阅读，慢慢体会文章及博客所要表达的算法含义，相信读者将收益匪浅。

论文： [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. [2]: Siinivas N, Deb K.N. Muiltiobj ective optimization using nondominated sorting in genetic algorithms[J]. 1994,2(3):221-248. [3]: Deb K, Sundar J, Rao N UB. Chaudhuri S. Reference point based multi-objective optimization using evolutionary algorithms2006,2(3):273-286. [4] Matlab Help, Global optimization toolbox. [5] Deb K, Thiele L, Laumanns M, et al. Scalable Test Problems for Evolutionary Multi-Objective Optimization[C]. Piscataway, New Jersey: 2002. [6] Lin S. NGPM – a NSGA-II program in Matlab (Version 1.4). [7] 李莉, 基于遗传算法的多目标寻优策略的应用研究[D].无锡: 江南大学，2008.

英文论文一并打包，请自行下载。 ————————————————

博客： 多目标优化算法（一）NSGA-Ⅱ（NSGA2） 作者：晓风wangchao

多目标遗传算法NSGA 作者：kiding_k

NSGA-II入门C1 作者：WUST许志伟

NSGA 和 NSGA-II 学习笔记 作者：royce_feng

NSGA-II YARPIZ NSGA-II Kalyanmoy Deb NGPM Song Lin

在对NSGA-II展开之前，我们先了解一下多目标优化算法中的一些概念。何为支配，何为非支配？从字面意思上, A 支配B，表明A的权利更大。 举个不恰当的例子，导师支配博士学生，博士学生支配硕士学生，则优先级导师>博士>硕士。 当我们讲支配与非支配放到多目标优化中，则会出现一定程度的不同，“支配”含义在多目标优化中更多表示被支配的解集（学生），非支配则表示不能被支配的解集（导师）。老师跟学生的支配与被支配关系在于导师拥有更高的科研能力（也就是，多目标优化中拥有较大/小目标函数值），进而老师这一群体获得的成就一般都会大于学生，成为学术的引领者（最优解集）。

非劣解：非劣解(noninferior solution)是多目标规划的基本概念之一，对于包括有定量和定性属性的多指标决策问题，其非劣解是指在所给的可供选择的方案集中，已找不到使每一指标都能改进的解。在多目标规划中，它即指有效解和较多最优解。

一般来说多目标规划问题(VP)的绝对最优解是不存在的。当绝对最优解不存在时，需要引入新的“解”的概念——非劣解( non-inferior solution)，又称非控解(non-dominance solution)、有效解（efficient solution）、巴列托最优解(Pareto-optimal solution)、锥最优解( cone-optimal solution)

非劣解即指在可行方案集中再也找不到一个各目标的属性值都不劣于A方案,而且至少有一个目标属性比A优的方案,那么方案A就是非劣解。换句话说，各目标函数值在A方案下是最大/最小的了。 多目标决策问题中没有最优解,但通常有一个以上的非劣解。如何理解？既然没有不劣于方案的方案了，那为什么还有一个以上的非劣解？

我个人理解的：目标函数不同，无法平行对比，即使有个别目标函数存在优于非劣解，但其它的目标函数值仍差于非劣解，因此这样的解不能纳入非劣解集中；反过来讲，非劣解集中的解已经找不到所有目标函数值都优于它们的解了，也就是说，它们都是最优的且它们之间已经没法平行对比。

Pareto 解集，Pareto 前沿：多目标优化问题的目标往往量纲不同、互相冲突，难以像单目标优化问题一样直接比较目标值来确定最优解。Pareto占优思想是一种评价多目标问题解优劣的处理方法，Pareto最优解集是指可行域中 所有非劣解 的集合（就是你所说的约束变量（x1、x2、……xn）的集合），Pareto最优前沿是 Pareto最优解集对应目标值的集合（就是你所说的目标函数空间的值(f1 f2… fn)的集合）。（参考：Pareto解集、Pareto前沿，到底是指的x还是y?）

关于遗传算法，本人在之前的博客中转载介绍过，具体请参照 遗传算法详解。 非支配排序遗传算法（NSGA）由Kalyanmoy Deb于1994年提出，NSGA的提出跟同期的进化算法（EAs）一样，主要目的用于求解多目标优化的问题。

在这里，我多提一下多目标优化问题的本质：我个人认为传统的多目标优化转换为单目标优化问题实则违背了多目标优化问题的本质，也与现实多目标问题所存在的不确定性相冲突。传统方法给予决策者一个所谓的优化解，这种解决方式严重依赖对于目标函数权重的设置，决策者较难认可该优化解的可靠性，更别说是处理该问题的全局最优解了。因此，给予决策者一组可行性的优化解，不同的决策者对问题分析、权衡可能会选择不同决策方案。当然，给予的可行性优化解并不一定是全局最优的，但现实社会就是这样的，社会的进步也并不是总以全局最优的方式前进的。这也是为什么要求解Pareto优化解集的原因了。

NSGA算法与一般GA算法相比，仅在选择部分有着不同的操作。在一般GA算法中是通过轮盘赌方式来进行概率选择的，轮盘赌的原理请参考遗传算法详解。实现过程可通过代码来说明：