EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
什么是NSGA-II Non dominated sorting genetic algorithm -II
" r2 {" _1 Z3 f7 A5 ~: f. ?NSGA-Ⅱ是目前最流行的多目标遗传算法之一，它降低了非劣排序遗传算法的复杂性，具有运行速度快，解集的收敛性好的优点，成为其他多目标优化算法性能的基准。
I- u& d# W# {$ F; v' bNSGA-Ⅱ就是在第一代非支配排序遗传算法的基础上改进而来，其改进主要是针对如上所述的三个方面：4 X: I$ C* k( ]+ c
①提出了快速非支配排序算法，一方面降低了计算的复杂度，另一方面它将父代种群跟子代种群进行合并，使得下一代的种群从双倍的空间中进行选取，从而保留了最为优秀的所有个体；
- p) `+ A9 H% [) F②引进精英策略，保证某些优良的种群个体在进化过程中不会被丢弃，从而提高了优化结果的精度；
: {+ w. }% }1 `& u- X4 I: b③采用拥挤度和拥挤度比较算子，不但克服了NSGA中需要人为指定共享参数的缺陷，而且将其作为种群中个体间的比较标准，使得准Pareto域中的个体能均匀地扩展到整个Pareto域，保证了种群的多样性。 算法目的:针对当前M个个体，选取N个个体(M>N)。: X- c+ w" I) g2 m; D3 G8 u
NSGA-II关键算法（步骤）
l* h5 o; E2 A$ F/ ?6 \ g) ]8 @1.先对M个个体求pareto解。然后得到F1，F2……等这些pareto的集合。
! K$ \8 x# F, ^" T' {: e" n2.把F1的所有个体全部放入N，若N没满，继续放F2，直到有Fk不能全部放入已经放入F1、F2、…、F(k-1)的N（空间）。此时对Fk进行求解。
0 V7 v4 B: b8 Q9 l) e; C3 f3.对于Fk中的个体，求出Fk中的每个个体的拥挤距离Lk(crowding distance)，在fk中按照Lk递减排序，放入N中，直到N满。 NSGA-II关键子程序算法 k% K/ |6 c. h3 n
1. 快速非支配排序算法4 ?' ~; s3 m; B% @; f
多目标优化问题的关键在于求取Pareto最优解集。NSGA-II快速非支配排序是依据个体的非劣解水平对种群M进行分层得到Fi，作用是使得解靠近pareto最优解。这是一个循环的适应值分级过程，首先找出群体中的非支配解集，记为F1，将其所有个体赋予非支配序irank=1（其中irank是个体i的非支配序值），并从整个群体M中除去，然后继续找出余下群体中的非支配解集，记为F2，F2中的个体被赋予irank=2,如此进行下去，知道整个种群被分层，Fi层中的非支配序值相同。
- v3 ]$ ]9 a8 t5 B) p4 X& L. B2 w2.个体拥挤距离: w5 n5 ~9 q" _! T2 r- c# ^
在同一层Fk中需要进行选择性排序，按照个体拥挤距离(crowding distance)大小排序。个体拥挤距离是Fk上与i相邻的个体i+1和i-1之间的距离，其计算步骤为：
! P! s+ M: Q- e9 R8 ~①对同层的个体距离初始化，令Ld=0（表示任意个体i的拥挤距离）。 a- `' @0 E4 q; f+ Y
②对同层的个体按照第m个目标函数值升序排列。
" L3 T0 V; j8 [6 b- u! h" s9 G# D8 g③对于处在排序边缘上的个体要给予其选择优势。
7 d2 t8 k5 E4 I; [④对于排序中间的个体，求拥挤距离：
（其中：L[i+1]m为第i+1个体的第m目标函数值fmax，fmin分别为集合中第m目标函数的最大和最小值。）
( q/ y- g6 s5 k! g7 ?2 o( L/ T⑤对于不同的目标函数，重复②到④的步骤，得到个体i的拥挤距离Ld，有限选择拥挤距离较大的个体，可以是计算结果在目标空间均匀地分布，维持群体的多样性。- H6 i8 ?- \8 w2 n4 P
3.精英策略选择算法
2 |, {: r0 M$ h" J6 r1 w保持父代中优良个体直接进入子代，防止Pareto最优解丢失。
" f' i( c/ v1 r$ Q$ v8 p3 _选择指标对父代Ci和子代Di合成的种群Ri进行优选，组成新父代Ci+1.
: }6 _1 W4 J7 P- g5 w9 X1 ?先淘汰父代中方案检验标志不可行的方案，接着按照非支配序值irank从低到高将整层种群依次放入Ci+1，直到放入某一层Fk超过N的限制，最后，依据拥挤距离大小填充Ci+1直到种群数量为N。 注释：
5 P0 F: ]2 N% n7 L多目标规划中，由于存在目标之间的冲突和无法比较的现象，一个解在某个目标上是最好的，在其他的目标上可能比较差。Pareto 在1986 年提出多目标的解不受支配解(Non-dominated set)的概念。其定义为：假设任何二解S1 及S2 对所有目标而言，S1均优于S2，则我们称S1 支配S2，若S1 的解没有被其他解所支配，则S1 称为非支配解（不受支配解），也称Pareto解。这些非支配解的集合即所谓的Pareto Front。所有坐落在Pareto front 中的所有解皆不受Pareto Front 之外的解（以及Pareto Front 曲线以内的其它解）所支配，因此这些非支配解较其他解而言拥有最少的目标冲突，可提供决策者一个较佳的选择空间。在某个非支配解的基础上改进任何目标函数的同时，必然会削弱至少一个其他目标函数。 5 ~+ h# e! I* I" O
| 
/1 
发表于 2020-8-17 15:32
收藏
淘帖
支持！
反对！