专栏首页图灵技术域NSGA-II快速非支配排序算法理解

NSGA-II快速非支配排序算法理解

快速的非支配排序

在NSGA进行非支配排序时,规模为N的种群中的每个个体都要针对M个目标函数和种群中的N-1个个体进行比较,复杂度为O(MN),因此种群中的N个个体都比较结束的复杂度为O(MN2),即每进行一次Pareto分级的时间复杂度为O(MN2)。在最坏的情况下,每个Pareto级别都只含有一个个体,那么需要进行N次分级所需要的时间复杂度则会上升为O(MN3)。鉴于此,论文中提出了一种快速非支配排序法,该方法的时间复杂度为O(MN2)。

该算法需要保存两个量:

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

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

下面是fast_nondominated_sort的伪代码

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

下面是C++实现:

C++

void population::nodominata_sort()
//求pareto解(快速非支配排序)
{
    int i,j,k;
    indivial H[2*popsize];
    int h_len=0;
    for(i=0;i<2*popsize;i++)
    {
        R[i].np=0;//支配个数np
        R[i].is_domied=0;//被支配的个数
        len[i]=0;//初始化
    }
    for(i=0;i<2*popsize;i++)
    {
        for(j=0;j<2*popsize;j++)
        {
            if(i!=j)//自己不能支配自身
            {
                if(is_dominated(R[i],R[j]))
                {
                    R[i].domi[R[i].is_domied++]=j;
                    //如果i支配j,把i添加到j的is_domied列表中
                }
                else if(is_dominated(R[j],R[i]))
                    R[i].np+=1;
                    //如果i被j支配,则把np加1
            }
        }
        if(R[i].np==0)//如果该个体的np为0,则该个体为Pareto第一级
        {
            len_f=1;
            F[0][len[0]++]=R[i];//将R[i]归并
        }
    }
    i=0;
    while(len[i]!=0)
    {
        h_len=0;
        for(j=0;j<len[i];j++)
        {
            for(k=0;k<F[i][j].is_domied;k++)
            //对所有在is_domied集合中的个体进行排序
            {
                R[F[i][j].domi[k]].np--;
                if( R[F[i][j].domi[k]].np==0)
                //如果该个体的支配个数为0,则该个体是非支配个体
                {
                    H[h_len++]=R[F[i][j].domi[k]];
                    R[F[i][j].domi[k]].rank=i+1;
                }
            }
        }
        i++;
        len[i]=h_len;
        if(h_len!=0)
        {
            len_f++;
            for(j=0;j<len[i];j++)
            {
                F[i][j]=H[j];
            }
        }
    }
}

matlab代码:

MATLAB

%-------非支配排序        
 
        fnum=0;                                             %当前分配的前沿面编号
        cz=false(1,size(functionvalue,1));                  %记录个体是否已被分配编号
        frontvalue=zeros(size(cz));                         %每个个体的前沿面编号
        [functionvalue_sorted,newsite]=sortrows(functionvalue);    %对种群按第一维目标值大小进行排序
        while ~all(cz)                                      %开始迭代判断每个个体的前沿面,采用改进的deductive sort
            fnum=fnum+1;
            d=cz;
            for i=1:size(functionvalue,1)
                if ~d(i)
                    for j=i+1:size(functionvalue,1)
                        if ~d(j)
                            k=1;                            
                            for m=2:size(functionvalue,2)
                                if functionvalue_sorted(i,m)>functionvalue_sorted(j,m)
                                    k=0;
                                    break
                                end
                            end
                            if k
                                d(j)=true;
                            end
                        end
                    end
                    frontvalue(newsite(i))=fnum;
                    cz(i)=true;
                end
            end
        end

NSGA2具体算法实现还在编写中。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • NSGA-II多目标遗传算法概述

    Non dominated sorting genetic algorithm -II NSGA-Ⅱ是目前最流行的多目标遗传算法之一,它降低了非劣排序遗传算法...

    里克贝斯
  • NSGA-Ⅱ算法Matlab实现(测试函数为ZDT1)

    NSGA-Ⅱ就是在第一代非支配排序遗传算法的基础上改进而来,其改进主要是针对如上所述的三个方面: ①提出了快速非支配排序算法,一方面降低了计算的复杂度,另一方...

    里克贝斯
  • Jmetal 4+ 使用指南一以NSGA-II为例

    演化计算与人工智能
  • matlab多目标优化算法之NSGA-Ⅱ【含源代码】

    当优化问题的目标函数为两个或两个以上时,该优化问题就是多目标优化。不同于单目标优化问题,多目标问题没有单独的解能够同时优化所有目标,也就是目标函数之间存在着冲...

    matlab爱好者
  • NSGA-Ⅱ算法C++实现(测试函数为ZDT1)

    https://www.omegaxyz.com/2017/04/14/nsga-iiintro/

    里克贝斯
  • NSGA-II入门

    在遗传算法在解决多目标优化遇到瓶颈时,许多学者花费了不少时间和精力在多目标优化的遗传算法上,Goldberg首先将Pareto最优解的概念与适应度值概念相关联,...

    演化计算与人工智能
  • 动态多目标优化研究综述

    转载自http://cjc.ict.ac.cn/online/onlinepaper/lrc-20207694828.pdf

    演化计算与人工智能
  • Jmetal 4+ 使用指南三使用Jmetal进行试验

    演化计算与人工智能
  • 遗传算法系列之五:多目标遗传算法和遗传编程

    在遗传算法深入研究的阶段,人们提出将各种将遗传算法应用到更广泛领域,从而产生了一些有趣的后续工作。这些后续工作中,多目标遗传算法和遗传编程由于它们重要...

    AlgorithmDog
  • Jmetal 4+ 使用指南七-并行算法

    演化计算与人工智能
  • 论文研读-多目标自适应memetic算法

    演化计算与人工智能
  • 多目标P系统进化算法中文期刊研读第一期

    杨世品,陆小华,薄翠梅,等. 多目标P系统仿生优化算法[J]. 北京工业大学学报,2016,42(10):35-41. DOI:10.11936/bjutxb2...

    演化计算与人工智能
  • Jmetal 4+ 使用指南二

    并且生成四个文件,分别是目标函数值,决策变量值,log日志文件 这种方式指定的问题是写在main方法中的problem = new ZDT3("ArrayRea...

    演化计算与人工智能
  • ​多目标优化拥挤距离计算

    [1]支配关系: https://blog.csdn.net/u013555719/article/details/91356078

    演化计算与人工智能
  • Jmetal 4+ 使用指南四使用Jmetal进行试验-NSGAIIStudy(一)

    演化计算与人工智能
  • 基于稀疏化鲁棒LS-SVR与多目标优化的铁水硅含量软测量建模

    今天跟大家分享一篇之前发表的文章,《基于稀疏化鲁棒LS-SVR与多目标优化的铁水硅含量软测量建模 》。 摘要: 针对高炉炼铁过程的关键工艺指标——铁水硅含量[...

    昱良
  • Jmetal 4+ 使用指南六 Experimentation example: StandardStudy

    演化计算与人工智能
  • Jmetal 4+ 使用指南五 使用Jmetal进行试验-Running the experiments

    这是因为相对地址在我目前的环境下win10+R下读不出来,因此此处换成绝对地址。在java环境中这种写法是正确的的,但是在R语言的环境中,这是有错误的 有两个地...

    演化计算与人工智能
  • 论文研读-基于决策变量聚类的大规模多目标优化进化算法

    演化计算与人工智能

扫码关注云+社区

领取腾讯云代金券