多目标非支配排序遗传算法-NSGA-II（一)_多目标快速非支配排序遗传算法

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

1. 参考文献及博客

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

论文：
[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

2. 源码

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

3. 支配与非支配解

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

4. 何为非劣解，Pareto解集，Pareto前沿？

非劣解：非劣解(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?）

5 NSGA与NSGA-II算法

(1）NSGA算法

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

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

1）实现过程

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

%如何选择新的个体
%输入变量：pop二进制种群，fitvalue：适应度值
%输出变量：newpop选择以后的二进制种群
function [newpop] = selection(pop,fitvalue)
%构造轮盘
[px,py] = size(pop); %px是种群个数
totalfit = sum(fitvalue);
% 取最大值的原因在这里，fitvalue越大，概率越大，是根据适应度获取的概率
p_fitvalue = fitvalue/totalfit;
p_fitvalue = cumsum(p_fitvalue);%概率求和排序
ms = sort(rand(px,1));%从小到大排列
fitin = 1;
newin = 1;
while newin<=px
    if(ms(newin))<p_fitvalue(fitin)
        newpop(newin,:)=pop(fitin,:);
        newin = newin+1;
    else
        fitin=fitin+1;
    end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

此处求解的是最大-$Maxf$，则适应度值（目标函数值）越大，在轮盘中所占的概率也就越大，然后随机概率下被选中的概率也就越大，进而实现选择过程。

NSGA算法在选择过程中主要进行了以下几方面的修改和完善：
#1).种群分层，划分非支配解集等级
在NSGA算法中通过支配与非支配关系，实现了种群个体间的等级划分，等级越低的个体将拥有更大的选择的的权利，反之，被选择的权利将会减小。那么如何获得等级的非支配解集呢？在讲解NSGA算法非支配解等级划分之前，有必要先了解清楚算法对于非支配解的概念界定。

这里我们直接给出论文 （Siinivas N and Deb K.N,1994）中所给予的定义。

概括来讲，在最小化目标函数问题中，$x_1$是非支配解集满足两点 ($x_1,x_2\in X$，均为解集)：
① 对任意的$x_2\in X，f_i(x_1)<f_i(x_2)$; 则此时$x_1⊰x_2$; （强支配）
② 对任意的$x_2\in X，f_i(x_1)\le f_i(x_2)$，且存在至少一个$f_i(x_1)<f_i(x_2)$; 则此时$x_1⊰x_2$; （弱支配）
③若对任意的$x_2\in X$，存在 $f_i(x_1)＜f_i(x_2)$，且存在至少一个$f_i(x_1)＞f_i(x_2)$; 则此时$x_1$与$x_2$不存在支配关系;
不好意思，我又邪性了，学术圈强支配上图。

Pareto Optimal及Weakly Pareto Optimal定义如下：


也就是说，存在至少一个目标函数变好，其它目标函数不变的最优解。
#2). 基于shared niche (共享小生境)的共享适应度值计算
种群在非支配等级分层结束后，NSGA算法给每级指定一个虚拟适应度值，级别越小，说明其中的个体
越优，赋予越高的虚拟适应值，反之级别越大，赋予越低的虚拟适应值。此方式的目的保证了虚拟适度值较大或等级较小的非支配个体有更多的机会进入下一代，使得算法以最快的速度收敛于最优区域。比如第一级非支配层的个体标上虚拟适应值为 1，第二级非支配层的个体标上虚拟适应值为 0.9(或其他)，以此类推，直到所有的个体都被标上虚拟适应值，同一非支配层的虚拟适度值是一样的，表明它们具有相同的复制再生（遗传）能力。但此方式也产生一个问题，同一级非支配层中的个体拥有相同的适应度值，某些个体在遗传操作中可能被遗弃，从而导致最优解集缺乏多样性。为了得到分布均匀的 Pareto 最优解集，NSGA 算法还引入了基于拥挤策略的共享小生境(Niche)技术，对同一级上原先指定的虚拟适应度值进行重新指定。然后再进行接下来的遗传操作。

说明：图中图面来源百度图片，本博客对图片进行了修改

那么这个小生境到底如何实现呢？本文参考了李莉硕士论文对于NSGA部分的介绍，截图部分已经说的很清楚了。



#3).NSGA 算法整体实现流程
NSGA算法具体的实现流程如下图所示。

说明一点，我认为图中的 reproduction accroding to dummy fitness实则说的是共享适度值。
(该图引自 Siinivas N and Deb K.N,1994)

2）缺陷

随着，对于NSGA的应用，研究学者发现NSGA同类似的EA算法一样，存在着以下缺陷：
#1). 非支配排序的高计算复杂度 ( High computational complexity of nondominated sorting)，也就是我们所说的时间复杂度，NSGA算法为 $O(M{N}^3)$;
#2). 缺乏精英策略（Lack of elitism）；
#3). NSGA需要指定共享参数${\sigma }_{share}$。
此外，我个人认为所谓的虚拟适度值也是很随机的一种指定方式，这对寻找最优解集也有一定的影响。
因NSGA算法已更新了多个版本，原NSGA算法代码很难从网上找到，因此，本文不再对NSGA代码进行分析了。

(2) NSGA-II算法

对于NSGA算法的讲解，我们很清楚的认识到NSGA所存在的缺陷，其中#1）和#3) 我相信大家已经很清楚。但是，缺乏精英策略是什么鬼？NSGA-II算法对于NSGA算法又进行了哪些修改？接下来，我们便一一解释。

1）精英主义策略

NSGA-II中的精英策略即保留父代（上代），然后让父代和经过选择、交叉、变异后产生的子代共同组成一个群体，其目的就是为了防止父代中可能存在的最优解被遗落，最后经过再次选择操作，获得与初始种群同样规模的群落。其实，这个思想还是蛮好理解的，我们不妨再上图说明。

熟悉龙珠的朋友，相信已经明白了精英主义的策略。号称最强的赛亚人，被弗利沙干掉了，剩下的卡卡罗特及贝吉塔活了下来，而且由于他们拥有超强的赛亚人血液及男主光环，他们生下了孩子，有了孙子，而且他们还一直活着，这些人成了地球的精英人群。 这里体现父代保留这一特性，至于父代跟子代交叉、变异啥的请忽略