多⽬标进化算法(⼆)——⾮⽀配排序/NSGA-II
上⼀节阐述了多⽬标优化问题及相关的基础知识。并且举例说明了什么是Pareto最优解，也叫⾮⽀配解或⾮劣解。如何⽐较哪个解优秀是上⼀节抛出的话题，本节致⼒于解决这⼀问题。
⽬录
基础知识
⼀个多⽬标优化问题（MOP）可以被描述如下：
pareto 最优边界（PF ）
回顾⼀下上⼀节提到的Pareto最优解与Pareto最优解集。若决策空间中没有解能够⽀配x ，则称x 是⼀个Pareto最优解。所有的Pareto最优解构成Pareto最优解集(Pareto-optimal set, PS)。
⽽Pareto最优边界⼜是什么？实际上就是上节提到的Pareto最优前沿PF。提到这个概念是因为很多定理都和其有关。多⽬标优化是从决策空间到⽬标空间的⼀个映射。PS是决策向量空间的⼀个⼦集（也就是
可⾏域中最优的那部分），PF是⽬标向量空间的⼀个⼦集。定理：在⽬标空间中，最优解是⽬标函数的切点，它总是落在搜索区域的边界上。
举例说明：⾮⽀配关系和⽀配区域
简单说明，我们的⽬标就是到图中的A,B,C,D,E,F这⼏个最优解，⼀般利⽤⾮⽀配排序。需要引⼊⼏个概念辅助讲解。
(1)⽀配区域：对于解C，它的的⽬标空间向量与⽬标空间的坐标轴的所围成的区域即为它的⽀配区域，此区域中的任意解都⽀配C，如上图A 区域所⽰。同理，A 区域的所有解都被C所⽀配。
(2)强⾮⽀配和弱⾮⽀配：当然还存在⼀些强⾮⽀配（⽐如解B和C）和弱⾮⽀配（⽐如和解C在图中同横或竖红线的解，图中没有哈）的概念区别，⼀般⽤得⽐较少。 如何构造Pareto 最优解集：⾮⽀配排序
构造Pareto解集的⽅法有很多：庄家法，擂台赛法，递归⽅法以及⽤快速排序的⽅法。前⾯三种⽅法都⽐较好理解，⽽快速排序的⽅法是⽬前普遍使⽤的算法，本节主要对其进⾏分析。
快速排序构造Pareto 最优解集
定义：个体中⾮⽀配关系⽤符号≺表⽰，X⽀配Y，表⽰为Y ≺X。如果互不⽀配，则两个个体是不相关的，⽤符号≺表⽰，X ≺Y。 如果不太清楚快速排序可以参考这个blog：
提⽰
min F (x )=(f (x ),…,f (x ))1m T
Ω=xϵR ∣h (x )≤0,j =1,…,k
n j 设x =(x ,…,x )是决策变量，Ω=1n Π[l ,u ]⊆i i R ,i =n 0,...,n 为决策空间；
n 为决策变量的个数，l 和u 分别为第i 个决策变量的下限和上限。
i i 式中有m 个⽬标等待优化，表⽰为f (x )=(f (x ),…,f (x ));f (x )将决策空间Ω映射到⽬标空间Π。
1m a a 12d d
进化标记
特别说明“⽐x⼩”的含义：个⼈喜欢这样来理解，在⽬标空间中其适应度⽐x⼩（在进化算法尤其是遗传算法中，会按照适应度优选），当然也可以理解成它们在⽬标空间中⽐x差。简单来说，就是个体处在x的⽀配区域中。
判断是否存在⽀配关系需要从每⼀维⽬标向量空间进⾏⽐较。例如，在上述最⼩化问题中，J点的f 和f 都⼤于x点，因此它被x所⽀配。B点的f x点，但是f ⼩于x点，因此两者之前不存在⽀配关系，值得注意的是这并不代表它们两个都是⾮⽀配解，是否是⾮⽀配解需要和所有的解进⾏⽐较。
简单做个总结
(1) 第⼀轮⽐较：随机选择⼀个个体X作为基准数，使⽤快排根据⽀配关系(相关性，X ≺Y)进⾏⽐较后，即可将种分成⽀配(D集合)和⾮⽀配(non-dominant，ND集合)的两个⼦种。 **(2) 第⼆轮⽐较：在第⼀轮⽐较的基础上，只⽤选择⾮⽀配的⼦种进⾏排序。**如果X于所有个体都不相关那X必然是⾮⽀配解，⽽其他个体不⼀定是⾮⽀配解。为什么？
因为：从快排排序原理来看，我们仅知道经过第⼀轮排序后，D集合中的个体⼀定是被X或者ND集合中的某些个体所⽀配（从上图和⽀配区域也可理解）。注意：并不是ND中的所有解都⽀配D中的解，后⾯会举例说明。⽽ND集合中的元素互相之间的关系并不清楚，因此还需要进⾏⽐较，如上图解A就⽀配E和F。
(3) 如上图经过⼀整轮快速排序后即可知道解之间的⽀配关系。
举例阐述排序流程
我们假设初始种为：{X,A,E,F,B,G,H,C,I,J,K,D}。每次以集合第⼀个元素为基准数进⾏排序。基准数左边表⽰“⼩”的个体。集合中的个体并没有顺序(⽀配关系)。
第⼀轮排序：D1集合：{K,J,D} X ND1集合：{A,E,F,B,G,H,C,I}。我们仅知道{K,J,D} 这些个体被其他所⽀配。X {A,E,F,B,G,H,C,I}之间的⽀配关系并不清楚。
第⼆轮排序：⾸先可知ND1集合中的任何⼀个个体不被X⽀配，但是并不代表ND1中不存在⽀配X的个体（⽐如以I为基准数，只能得到J为⽀配解，并且可以发现B,C,G这些个体都是⽀配I的）。通过X和所有集合ND1中的个体⽐较后，发现X就是⾮⽀配解。然后，我们选取ND1集合中的第⼀个元素为基准数排序：D2集合：{E,F} A ND2集合：{B,G,H,C,I}。
第三轮排序：和第⼆轮排序操作类似，先将A和所有ND2中的个体⽐较。然后，选取ND2集合中的第⼀个元素为基准数排序：D3集合：{G,H,I} B ND3集合：{C}，集合中只有⼀个元素即可停⽌。
经过三轮排序实际上Pareto最优解集就到了，即{A,B,C,X}，它们为第⼀层次⾮⽀配个体，从图中也可以看出。在排序的同时实际上D集合也在同时进⾏排序(操作和上述流程相同)，因为最终我们想要得到的种个体的⾮⽀配层次关系。
D集合排序
D1集合：{K,J,D}排序后：{J}，K，{D} ；
D2集合：{E,F}排序后：E，{F} ；
D3集合：{G,H,I}排序后：{H,I}，G。由于⼀个集合中存在两个个体且并不知道⽀配关系，因此需要继续排序：H，{I}。
对于D集合的排序是否正确？
看起来似乎没有什么问题，但是注意相关性并不存在数学的“传递性”的特征（具体可以参照《多⽬标进化优化》⼀书），不能这样简单进⾏排序。
⽐如J是第⼏层的⾮⽀配解？通过上述⽐较并不知道。究其原因就是因为上述排序的基准数不同。因此，需要按照上⾯⾮⽀配解的流程将集合进⾏整合，重新排序。
注：放在基准数的左边集合为⽀配解，被基准数所⽀配，但是不⼀定被右边集合中的个体所⽀配(⽐如在第⼀轮排序中，左边集合的K并不被右边集合的A⽀配)，不存在传递性。
⾮⽀配层次关系
由于我们选择个体是按照⾮⽀配层次关系进⾏优选的，因此，需要按层次进⾏分类。显⽽易见，同⼀层中的个体互不⽀配。
通过上述⽐较可知，第⼀层⾮⽀配解集：P1= {A,B,C,X};
1212d
继续⽐较D集合：{K,J,D,E,F,G,H,I}，寻第⼆层⾮⽀配解，请读者⾃⾏推导。
第⼆层⾮⽀配解集：P2= {K,E,G,H,I}；可以知道排除第⼀层次个体，它们就是⾮⽀配解；
第三层⾮⽀配解集：P3= {H,I}；
第四层⾮⽀配解集：P4= {J}；
拓展
下节进⾏代码实现。有算法基础的同学可能会思考时间复杂度或者说是否存在冗余⽐较。确实可以优化，⽥野⽼师团队提出了改进算法，有兴趣可以阅读相关⽂献。
注：本⽂图⽚摘⾃《多⽬标进化优化》⼀书，其他的排序⽅法可以查阅此书。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议