一种快速精英化多目标遗传算法：NSGA—Ⅱ

韩蕊

【摘要】NSGA是一种流行的基于非支配的遗传算法，用于多目标优化。是一种非常有效的算法，但由于其计算复杂度低、缺乏精英性以及需要预先确定共享参数σshare而被诟病。NSGA-II提出了一种更好的排序算法，该算法采用了精英主义，不需要选择共享参数。

【中图分类号】TP18 【文献标识码】A 【文章编号】2095-3089（2018）03-0025-02

一、NSGA-II概况

种群按照通常的方式被初始化。初始化了的种群基于非支配进入种群进行排序，并被分配适应度值，同时还定义了一个新的参数：拥挤距离。拥挤距离是衡量一个个体到另一个个体之间距离，值越大种群的多样性越好。

通过基于等级和拥挤距离的二元竞争选择，从群体中选择父辈。所选种群从交叉和变异算子中生成子代。对具有当前种群和当前种群子代的種群进行再排序，根据非支配原则，只选择最佳的N个个体，其中N是种群的大小。选择的依据是等级和最后一条线上的拥挤距离。

二、NSGA-II操作步骤

1.初始化种群。根据问题范围和约束初始化种群。

2.初始种群是根据非支配排序。快速排序算法如下：

对于主种群P中的每个个体p，执行以下操作：1.初始化Sp=?；此集合将包含所有被p支配的个体。2.初始化np=0。这将是支配p的个体数量。3.对于种群P中的每个个体q。If p支配q，则：增加q到Sp集合中，即Sp=Sp∪{q}；Or if q支配p，则增加p的控制计数器，即np=np+1。4.如果np=0，即没有个体支配p，则p属于第一前沿，则单个p的集合非劣等级为1，即prank=1。更新第一前沿的集合通过添加p到前沿，即F1=F1∪{P}。

这是针对主种群中每一个个体运行的。将前面的计数器初始化为1。即i=1。在第i前沿为非空的情况下进行如下操作，即Fi≠ ?；

1.Q= ?；用于存储第（i+1）线的个体的集合。2.对于Fi前沿的每一个个体p，对于Sp中的每个个体q。——nq=nq-1，减少个体的支配数。——若nq=0，那么在随后的前沿将支配q，因此设置qrank=i+1。更新Q用具有个体q的集q，即Q=Q∪q。3.把前面的前沿增大一个。集合Q是下一个前线，因此Fi=Q。

该算法优于原NSGA算法，由于它利用了关于个人支配的集合（Sp）和受个体支配的个体数目（np）。

3.拥挤距离

一旦非支配排序完成，拥挤距离就会被分配。由于个体是根据等级和拥挤距离来选择的，种群中的所有个体都被分配了一个拥挤距离值。计算如下：

对于每一个前线Fi，n是个体的数量。

（1）初始化所有个体的距离为零，即Fi（dj）=0，其中j对应于前线Fi中的Jth个体。（2）对于每个目标函数m。基于目标m，对前沿个体进行排序，即I=sort（Fi；m）；给Fi中每一个个体分配无限大的边界值。即I（d1）= ∞，I（dn）= ∞；for k = 2 to （n +1）

I（dk）= I（dk）+（ I（k + 1）·m -I（k -1）· m）/（fmmax-fmmin）

其中，I（k ）· m是I中第k个个体在第m个目标函数的值。

拥挤距离的基本思想是基于m维的m个目标在前线中的每个个体之间的相互关系。边界中的个体总是被选中的，因为他们影响距离分配。

4.选择

一旦这些个体根据非支配和在指定拥挤距离的情况下，选择使用一个拥挤比较运算符（fi（Dq），即拥挤距离应该更远。个体是通过使用二元竞赛选择和比较运算符来选择的。

5.遗传算子

实数编码遗传算法使用模拟二进制交叉、交叉算子和多项式变异算子。

（1）模拟二元交叉。模拟二元交叉是模拟自然界中的交叉，如下所示。

c1，k =1/2[（1 +?k）p1，k + （1 + ?k）p，k]

c2，k =1/2[（1 + ?k）p1，k + （1+?k）p2，k]

其中ci，k是kth分量的第一个子代；Pi，k是选择的父代；?k是从具有密度的随机数生成的样本。

p（?）=1/2（ηc+ 1）?ηc 0< ?≤1

?>1

该分布可以从（0，1）之间的均匀采样的随机数获得。ηc是交叉的分布指标。

（2）多项式突变。

其中，ck是子代，Pk是父代，pku是父代种群的上边界，pkl是父代种群的下界。δk是由多项式分布计算的小变差。

rk是（0，1）之间的一个均匀抽样随机数。ηm是变异分布指数。

6.重组和选择。

重组是当前遗传种群和子代进行重组；选择是形成下一代种群个体的集合。因为以前和现在最好的个体组成新种群，精英主义得到了保证。种群现在是根据非支配排序。如果通过添加所有的个体在Fj前面，种群超过N，然后选择前面Fj中的个体。它们的拥挤距离是递减的，直到种群规模达到N。因此，这个过程会重复产生后代。

三、结语

NSGA-II由于其新的基于分级的快速非支配解排序方法将计算复杂度降低；该算法提出了拥挤距离的概念，采用拥挤距离比较算子代替NSGA中的适值度共享方法，时间复杂度降低；同时引入了精英保留机制，经选择后参加繁殖的个体所产生的后代与其父代个体共同竞争来产生下一代种群，有利于提高种群的整体进化水平。因此NSGA-II得到了广泛应用。

参考文献：

[1]Kalyanmoy Deb and R.B.Agarwal.Simulated Binary Crossover for Continuous Search Space.Complex Systems，9：115- 148，April 1995.