NSGA2算法中文版详细介绍

该算法需要保存两个量：

(1).支配个数np。该量是在可行解空间中可以支配个体p的所以个体的数量。

(2).被支配个体集合SP。该量是可行解空间中所有被个体p支配的个体组成的集合。

排序算法的伪代码如下：

def fast_nondominated_sort( P ):
    F = [ ]
    for p in P:
        Sp = [ ]
         np = 0
         for q in P:
             if p > q:                #如果p支配q，把q添加到Sp列表中
                 Sp.append( q )
             else if p < q:        #如果p被q支配，则把np加1
                 np += 1

        if np == 0:
            p_rank = 1        #如果该个体的np为0，则该个体为Pareto第一级
      F1.append( p )
    F.append( F1 )
    i = 0
    while F[i]:
        Q = [ ]
        for p in F[i]:
            for q in Sp:        #对所有在Sp集合中的个体进行排序
                nq -= 1
                if nq == 0:     #如果该个体的支配个数为0，则该个体是非支配个体
                    q_rank = i+2    #该个体Pareto级别为当前最高级别加1。此时i初始值为0，所以要加2
                    Q.append( q )
        F.append( Q )
        i += 1

在上面伪代码中，第一部分循环为二重循环，时间复杂度为O(N2)，第二部分循环中，我们可以假设共有x个级别，而每个级别中最多有（N-N/x）各个体，每个个体的支配集合中也最多有（N- N/x）各个体。由此可得出循环次数为x*（N-N/x）*（N-N/x）=（（x-1）2/x2）N2M，即时间复杂度为O(MN2)。

原始的NSGA算法中使用共享函数的方法来维持物种的多样性，这种方法包含一个共享参数，该参数为所求解问题中所期望的共享范围。在该范围内，两个个体共享彼此的适应度。但是该方法有两个难点：

(1).共享函数方法在保持多样性的性能很大程度上依赖于所选择的共享参数值。

(2).种群中的每个个体都要与其余的个体相比较，因此该方法的全局复杂度为O(N2)。

在NSGA2中使用了排挤算法和精英策略来代替共享函数算法。而要实现这两种方法，首先我们需要定义两个操作：密度估算和排挤算子。

(1).密度估算

    要对拥挤距离进行计算，则需要根据每个目标函数对种群中的所有个体按升序进行排序。第一个和最后一个个体的拥挤距离设为无穷大，第i个个体的拥挤距离则设为第i+1和第i个体的所有目标函数值之差的和。具体方法如下面伪代码：

def crowding_distance_assignment( I )
        nLen = len( I )        #I中的个体数量
    for i in I:
                i.distance = 0    #初始化所有个体的拥挤距离
    for objFun in M:        #M为所有目标函数的列表
                I = sort( I, objFun )    #按照目标函数objFun进行升序排序
                I[0] = I[ len[I]-1 ] = ∞    #对第一个和最后一个个体的距离设为无穷大
                for i in xrange( 1, len(I) - 2 ):
                        I[i].distance = I[i].distance + ( objFun( I[i+1] ) - objFun( I[i-1] ) )/(Max(objFun()) - Min(objFun()) )

    伪代码中的objFun( i )是对个体i求其目标函数值。Max(objFun())为目标函数objFun()的最大值，Min(objFun())为目标函数objFun的最小值。其复杂度为O(MNlogN)。

(1).随机初始化开始种群P0。并对P0进行非支配排序，初始化每个个体的rank值。

(2). t = 0

(3).通过二进制锦标赛法从Pt选择个体，并进行交叉和变异操作，产生新一代种群Qt。

(4) 计算新种群的obj值，

(5).通过合并Pt 和 Qt 产生出组合种群Rt =  Pt UQt 。

(6).对Rt进行非支配排序，并通过排挤和精英保留策略选出N个个体，组成新一代种群Pt+1。

(7).跳转到步骤3，并循环，直至满足结束条件。

步骤5的具体操作可见下图：



伪代码如下：

while condition:
    Rt = Pt + Qt
    F = fast_nondominate_sort( Rt )
    Pt+1 = [ ]
    i = 0
    while len(Pt+1) + len( F[i] ) < N:
        crowding_distance_assignment( F[i] )
        Pt+1 += F[i]
        i += 1
    Pt+1 += F[i][0:N-len(Pt+1)]
    Qt+1 = make_new_generation( Pt+1 )
    t = t+1

(1).非支配排序，最差复杂度为O(M(2N)2)。

(2).拥挤距离估算赋值，最差复杂度为O(M(2N)log(2N))。

(3).拥挤操作排序，最差复杂度为O(2Nlog(2N))。