精华内容
下载资源
问答
  • 2021-04-24 17:15:30

    快速的非支配排序

    在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

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    deffast_nondominated_sort(P):

    F=[]

    forpinP:

    Sp=[]

    np=0

    forqinP:

    ifp>q:#如果p支配q,把q添加到Sp列表中

    Sp.append(q)

    elseifp

    np+=1

    ifnp==0:

    p_rank=1#如果该个体的np为0,则该个体为Pareto第一级

    F1.append(p)

    F.append(F1)

    i=0

    whileF[i]:

    Q=[]

    forpinF[i]:

    forqinSp:#对所有在Sp集合中的个体进行排序

    nq-=1

    ifnq==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

    {

    for(k=0;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

    {

    F[i][j]=H[j];

    }

    }

    }

    }

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    53

    54

    55

    56

    57

    58

    59

    60

    61

    62

    63

    64

    voidpopulation::nodominata_sort()

    //求pareto解(快速非支配排序)

    {

    inti,j,k;

    indivialH[2*popsize];

    inth_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列表中

    }

    elseif(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

    {

    for(k=0;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

    {

    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

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    %-------非支配排序

    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;

    fori=1:size(functionvalue,1)

    if~d(i)

    forj=i+1:size(functionvalue,1)

    if~d(j)

    k=1;

    form=2:size(functionvalue,2)

    iffunctionvalue_sorted(i,m)>functionvalue_sorted(j,m)

    k=0;

    break

    end

    end

    ifk

    d(j)=true;

    end

    end

    end

    frontvalue(newsite(i))=fnum;

    cz(i)=true;

    end

    end

    end

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

    更多相关内容
  • MATLAB源码集锦-多目标快速非支配排序遗传算法优化代码
  • 20种非支配排序 MATLAB 代码
  • 多路径遗传算法的matlab代码,求解准确,实用,作图美观,具有详细的注释。
  • 代码 多目标快速非支配排序遗传算法优化代码代码 多目标快速非支配排序遗传算法优化代码代码 多目标快速非支配排序遗传算法优化代码代码 多目标快速非支配排序遗传算法优化代码代码 多目标快速非支配排序遗传算法...
  • 资源名:非支配排序遗传算法_MATLAB代码_用于非支配排序遗传算法优化_NSGA 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者...
  • 非支配快速排序算法详解 对NSGA-II的一个学习记录          为易于理解,只用三个点举例子。 Np=3; %三个点 current_vector = [1:1:Np]'; %当前向量 current_pf=1; %先找F1 RANK = zeros(Np,1); %RANK初始化 ...

    非支配快速排序算法详解

    对NSGA-II的一个学习记录
             在这里插入图片描述

    为易于理解,只用三个点举例子。

    Np=3;                       %三个点
    current_vector = [1:1:Np]'; %当前向量
    current_pf=1;               %先找F1
    RANK = zeros(Np,1);         %RANK初始化
    all_perm = [repmat([1:1:Np]',Np',1), reshape(repmat([1:1:Np],Np,1),Np^2,1)];%生成两列
    all_perm(all_perm(:,1)==all_perm(:,2),:) = [];                              %每个点和其余比较
    d=[0 1 0 0 1 1];            %假设支配关系
    dominated_particles = unique(all_perm(d==1,2));%依次找到各个点是否受人支配,不在乎受几个人支配,只要受人支配了,那他就不是当前要找的等级。
    non_dom_idx = ~ismember(current_vector,dominated_particles);%找到非支配的点的位置,这是一个逻辑值
    RANK(current_vector(non_dom_idx)) = current_pf;             %让这些位置成为当前等级
    all_perm(ismember(all_perm(:,1),current_vector(non_dom_idx)),:) = [];%找到以后,删除,因为一个点只能属于一个等级
    all_perm(ismember(all_perm(:,2),current_vector(non_dom_idx)),:) = [];%找到以后,删除,因为一个点只能属于一个等级
    current_vector(non_dom_idx) = [];%当前向量中删除那些非支配点                         
    current_pf = current_pf + 1;     %等级+1,找下一个等级。
    
    

    在这里插入图片描述
    在这里插入图片描述
    思路以及程序实现过程即为上述。其实在非支配快速排序中还要判断是否已经把所有粒子给分好等级了。有两个跳出循环的地方
    1、判断当前向量中是否只有一个点了,要是就一个点了,那他就是最后一个等级了,直接跳出就好了;
    2、判断当前向量中,是否没有更多空间去放等级了。(没看太明白,这块直接跳出了,等级也没加,可能就是一个判断的过程。)不影响分等级。

    有两个函数,快速非支配排序和比较函数

    function [RANK] = FastNonDominatedSorting_Vectorized(fitness)
        % Initialization
        Np = size(fitness,1);
        RANK = zeros(Np,1);
        current_vector = [1:1:Np]';
        current_pf = 1;
        all_perm = [repmat([1:1:Np]',Np',1), reshape(repmat([1:1:Np],Np,1),Np^2,1)];
        all_perm(all_perm(:,1)==all_perm(:,2),:) = []; %每个个体去和别人比。  一个个体有两个目标函数值
        
        % Computing each Pareto Front
        while ~isempty(current_vector)                 %非空,就是我这100个个体还没分完等级呢。
            
            % Check if there is only a single particle
            if length(current_vector) == 1
                RANK(current_vector) = current_pf;
                break;
            end
            
            % Non-dominated particles
                % Note: nchoosek has an exponential grow in computation time, so
                % it's better to take all the combinations including repetitions using a
                % loops (quasi-linear grow) or repmats (linear grow)
                %all_perm = nchoosek(current_vector,2);   
                %all_perm = [all_perm; [all_perm(:,2) all_perm(:,1)]];     
            d = dominates(fitness(all_perm(:,1),:),fitness(all_perm(:,2),:));
            %d是一个逻辑值,他判断了所有个体和单个个体的支配关系。第一列是2到200,第二列全是1,先判断2到200是不是支配了1。以此类推。
            
            
            dominated_particles = unique(all_perm(d==1,2)); 
            % 找到被人支配的,unique就是不管是谁支配了1,不管有几个,我只计数一个
            
    
            % Check if there is no room for more Pareto Fronts
            if sum(~ismember(current_vector,dominated_particles)) == 0
                break;
            end
    
            % Update ranks and current_vector  更新等级
            non_dom_idx = ~ismember(current_vector,dominated_particles); %找出那些没有人支配的所在的位置,然后在current_vector中挑出来,就是第一等级
            RANK(current_vector(non_dom_idx)) = current_pf;              %把这些定为第一等级,其余位置都是0,我不在乎他是第几等级。用逻辑值来判断
            all_perm(ismember(all_perm(:,1),current_vector(non_dom_idx)),:) = [];
            all_perm(ismember(all_perm(:,2),current_vector(non_dom_idx)),:) = [];%判断完的就把剔除出去
            current_vector(non_dom_idx) = [];                                    %判断完的就剔除出去了
            current_pf = current_pf + 1;                                         %找下一等级的去,知道找完了才停下来。
        end
    end
    
    % Function that returns true if x dominates y and false otherwise
    function d = dominates(x,y)
        d = (all(x<=y,2) & any(x<y,2));
    end
    

    只是记录学习,如有错误,请及时指出,谢谢大家。

    参考:mathworks NSGA-II(2019年更新的那版)

    展开全文
  • 多目标优化中的非支配排序算法

    千次阅读 2021-11-14 10:11:04
    多目标优化中的非支配排序算法 以NSGA-II为例 多目标优化指的是针对多个目标函数,去寻找一组最优解,形式如下: 其中*fi(x)*是各单一的目标函数 但是多目标优化问题通常面临多个目标函数无法同时达到最优,为了解决...

    多目标优化中的非支配排序算法
    以NSGA-II为例
    多目标优化指的是针对多个目标函数,去寻找一组最优解,形式如下:
    在这里插入图片描述其中*fi(x)*是各单一的目标函数
    但是多目标优化问题通常面临多个目标函数无法同时达到最优,为了解决这一问题,提出了pareto-Optimality的概念,
    针对pareto-Optimality,有几个概念:
    1.非支配解:假设任何二解S1 及S2 对所有目标而言,S1均优于S2,则我们称S1 支配S2,若S1 的解没有被其他解所支配,则S1 称为非支配解(不受支配解),也称Pareto解
    支配解:若解S2的所有目标均劣于S1,则称S1优于S2,也称S1支配S2,S2为受支配解。
    因此现在的首要任务是寻找解空间里面所有的Pareto解,找到所有Pareto解之后,这些解组成的平面叫做Pareto前沿面(Non-dominated front)。在目标函数较多时,前沿面通常为超曲面。
    非支配解排序(Non-dominated Sorting)

    1. 设所有解的集合为S,现从中找出非支配解集合,记为F1

    2. 令S=S-F1,从S中再找出非支配解集合,记为F2

    3. 重复第二步,直到S为空集

    将每次找出的非支配解进行排序如下:

    {F1,F2,…,Fn}
    例如:有两个目标函数Time(f1(x)),Cost(f2(x)),通过求解,我们获得了一组pareto解集,如下图所示:
    在这里插入图片描述
    对这个解集进行排序:
    第一轮:我们发现A,B,D,F不能被其他解所支配,则这是第一组非支配解集;
    然后我们针对剩余解集,C,E,G,H,I进行排序,C,E,G不能被其他解所支配,组成第二组非支配解集;
    剩余的H,I,不能彼此支配,所以组成第三组非支配解集。
    通过这个过程我们发现,非支配排序实际上就是“不断的剔除非支配解集,将目标值大的保留下来,然后进一步处理”。
    matlab代码实现过程:

    clear all
    close all
    functionvalue=[2 7.5;3 6;3 7.5;4 5;4 6.5;5 4.5;5 6;5 7;6 6.5];%当前的非支配解集
    fnum=0;                                             %当前分配的前沿面编号,就是上述的第一轮,第二轮,第三轮
    cz=false(1,size(functionvalue,1));                  %记录个体是否已被分配编号
    frontvalue=zeros(size(cz));                         %每个个体的前沿面编号
    [functionvalue_sorted,newsite]=sortrows(functionvalue);    %对种群按第一维目标值大小进行排序,第一位目标值相同,
    %就对第二维目标进行排序
     while ~all(cz)
                  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)%将目标值大的解保留下来,来进行下一次排序,
    %该过程通过d(j)=true实现
                                        k=0;
                                        break
                                    end
                                end
                                if k
    k
                                    d(j)=true;
                                end
                             end
                        end
                        frontvalue(newsite(i))=fnum;
                        cz(i)=true;
                    end
                end                                     
             endhon
    
    ```python
    
    本文的数据来源于https://zhuanlan.zhihu.com/p/125161075,感谢该博客的指导
    
    
    展开全文
  • 针对快速非支配排序遗传算法(NSGA-Ⅱ)的精英保留策略会使大量冗余的高排序级别个体同时作为精英保留到下一代,极易发生早熟收敛现象问题,提出了改进的快速非支配排序遗传算法(I-NSGA-Ⅱ),并将其应用于交通信号...
  • 针对带精英策略的非支配排序遗传算法不能根据环境变化自适应地动态调整运行参数,难以实现对解空间的高效搜索,提出一种自适应的非支配排序遗传算法.所提出算法根据运行阶段、运行代数和当前临时种群支配个体数动态...
  • matlab开发-非支配排序遗传算法。进化多目标优化的NSGA-II结构matlab实现
  • 非支配排序遗传算法matlab代码PlatEMO_research 平板电脑 进化多目标优化平台 100多种开源进化算法 120多个开源多目标测试问题 强大的GUI可并行执行实验 一键式生成Excel或LaTeX表格式的结果 最先进的算法将不断被...
  • 多目标优化系列: MOP_1. 多目标优化的相关基本概念 MOP_2. 非支配排序遗传算法 —(NSGA、...1995年,Srinivas和Deb提出了非支配排序遗传算法(Non-dominatedSorting Genetic Algorithms,NSGA)。这是一种基于P...

    1. 非支配排序遗传算法(NSGA)

    1995年,Srinivas和Deb提出了非支配排序遗传算法(Non-dominated Sorting Genetic Algorithms,NSGA)。这是一种基于Pareto最优概念的遗传算法。

    (1) 基本原理

    NSGA与简单的遗传算法的主要区别在于:该算法在选择算子执行之前根据个体之间的支配关系进行了分层。其选择算子、交叉算子和变异算子与简单遗传算法没有区别。

    在选择操作执行之前,种群根据个体之间的支配与非支配关系进行排序:

    首先,找出该种群中的所有非支配个体,并赋予他们一个共享的虚拟适应度值。得到第一个非支配最优层;

    然后,忽略这组己分层的个体,对种群中的其它个体继续按照支配与非支配关系进行分层,并赋予它们一个新的虚拟适应度值,该值要小于上一层的值,对剩下的个体继续上述操作,直到种群中的所有个体都被分层。

    算法根据适应度共享对虚拟适应值重新指定:

    比如指定第一层个体的虚拟适应值为1,第二层个体的虚拟适应值应该相应减少,可取为0.9,依此类推。这样,可使虚拟适应值规范化。保持优良个体适应度的优势,以获得更多的复制机会,同时也维持了种群的多样性。

    (2) 算法流程

    NSGA采用的非支配分层方法,可以使好的个体有更大的机会遗传到下一代;适应度共享策略则使得准Pamto面上的个体均匀分布,保持了群体多样性,克服了超级个体的过度繁殖,防止了早熟收敛。算法流程如图所示:

    (3) 算法缺陷

    非支配排序遗传算法(NSGA)在许多问题上得到了应用。但NSGA仍存在一些问题:

    a) 计算复杂度较高,为O(mN^{3})(m为目标函数个数,N为种群大小),所以当种群较大时,计算相当耗时。

    b) 没有精英策略;精英策略可以加速算法的执行速度,而且也能在一定程度上确保已经找到的满意解不被丢失。

    c) 需要指定共享半径\sigma_{share}

    2. 带精英策略的非支配排序的遗传算法(NSGA-II)

    2000年,Deb又提出NSGA的改进算法一带精英策略的非支配排序遗传算法(NSGA-II),针对以上的缺陷通过以下三个方面进行了改进:

    a) 提出了快速非支配排序法,降低了算法的计算复杂度。由原来的O(mN^{3})降到O(mN^{2}),其中,m为目标函数个数,N为种群大小。

    b) 提出了拥挤度和拥挤度比较算子,代替了需要指定共享半径的适应度共享策略,并在快速排序后的同级比较中作为胜出标准,使准Pareto域中的个体能扩展到整个Pareto域,并均匀分布,保持了种群的多样性。

    c) 引入精英策略,扩大采样空间。将父代种群与其产生的子代种群组合,共同竞争产生下一代种群,有利于保持父代中的优良个体进入下一代,并通过对种群中所有个体的分层存放,使得最佳个体不会丢失,迅速提高种群水平。

    (1) 基本原理

    快速非支配排序法:

    NSGA-II对第一代算法中非支配排序方法进行了改进:对于每个个体 i 都设有以下两个参数 n(i) 和 S(i),

    n(i) 为在种群中支配个体 i 的解个体的数量。(别的解支配个体 i 的数量)

    S(i) 为被个体 i 所支配的解个体的集合。(个体 i 支配别的解的集合)

    1) 首先,找到种群中所有 n(i)=0 的个体(种群中所有不被其他个体至配的个体 i),将它们存入当前集合F(1);(找到种群中所有未被其他解支配的个体)

    2) 然后对于当前集合 F(1) 中的每个个体 j,考察它所支配的个体集 S(j),将集合 S(j) 中的每个个体 k 的 n(k) 减去1,即支配个体 k 的解个体数减1(因为支配个体 k 的个体 j 已经存入当前集 F(1) );(对其他解除去被第一层支配的数量,即减一)

    3) 如 n(k)-1=0则将个体 k 存入另一个集H。最后,将 F(1) 作为第一级非支配个体集合,并赋予该集合内个体一个相同的非支配序 i(rank),然后继续对 H 作上述分级操作并赋予相应的非支配序,直到所有的个体都被分级。其计算复杂度为O(mN^{2}),m为目标函数个数,N为种群大小。(按照1)、2)的方法完成所有分级)

    确定拥挤度:

    在原来的NSGA中,我们采用共享函数以确保种群的多样性,但这需要由决策者指定共享半径的值。为了解决这个问题,我们提出了拥挤度概念:在种群中的给定点的周围个体的密度,用 i_{d} 表示,它指出了在个体 i 周围包含个体 i 本身但不包含其他个体的长方形(以同一支配层的最近邻点作为顶点的长方形)

    如图所示:

    拥挤度比较算子: 

    从图中我们可以看出 i_{d} 值较小时表示该个体周围比较拥挤。为了维持种群的多样性,我们需要一个比较拥挤度的算予以确保算法能够收敛到一个均匀分布的Pareto面上。

    由于经过了排序和拥挤度的计算,群体中每个个体 i 都得到两个属性:非支配序 i(rank) 和拥挤度 i_{d},则定义偏序关系\prec _{n}:当满足条件 i(rank) < i_{d},或满足 i(rank) = i_{d} 且 i_{d}j_{d}。时,定义i\prec _{n}j,。也就是说:如果两个个体的非支配排序不同,取排序号较小的个体(分层排序时,先被分离出来的个体);如果两个个体在同一级,取周围较不拥挤的个体。

    (2) 算法流程

    首先,随机初始化一个父代种群P(0),并将所有个体按非支配关系排序且指定一个适应度值,如:可以指定适应度值等于其非支配序 i(rank),则1是最佳适应度值。然后,采用选择、交叉、变异算子产生下一代种群Q(0),大小为N。

    如图,首先将第 t 代产生的新种群Q(t)与父代P(t)合并组成R(t),种群大小为2N。然后R(t)。进行非支配排序,产生一系列非支配集 F(t) 并计算拥挤度。由于子代和父代个体都包含在 R(t) 中,则经过非支配排序以后的非支配集 F(1) 中包含的个体是 R(t) 中最好的,所以先将 F(1) 放入新的父代种群 P(t+1) 中。如果 F(1) 的大小小于N,则继续向 P(t+1) 中填充下一级非支配集 F(2),直到添加 F(3) 时,种群的大小超出N,对 F(3) 中的个体进行拥挤度排序(sort(F(3),\prec _{n})),取前N-\left | P(t+1)) \right |个个体,使 P(t+1) 个体数量达到N。然后通过遗传算子(选择、交叉、变异)产生新的子代种群 Q(t+1)。

    算法的整体复杂性为O(mN^{2}),由算法的非支配排序部分决定。


    通过介绍非支配排序遗传算法(NSGA)及其改进算法NSGA-II的基本原理和流程,我们了解到NSGA-II解决了NSGA中存在的3个问题:降低了计算复杂度;引入精英策略;采用拥挤度及其比较算子代替了共享半径。使得NSGA-Ⅱ在处理多目标优化问题上有更好的性能。

    NSGA-Ⅱ的matlab程序下载:

    1. 使用积分下载路径:Matlab编写多目标优化算法NSGA-Ⅱ的详解以及论文详解

    2. 单次付费下载路径:Matlab编写NSGA-2多目标优化算法_非支配排序遗传算法-机器学习文档类资源-CSDN下载

    (有读者反映,使用积分下载时,对于没有积分的童鞋一次性买积分费用过高,因此提供单次付费下载路径)


    参考文献:

    非支配排序遗传算法(NSGA)的研究与应用

    带精英策略的非支配排序遗传算法的研究与应用

    展开全文
  • 多目标规划的概念是 1961年由美国数学家查尔斯和库柏首先提出的。多目标最优化思想,最早是在1896年由法国经济学家V.帕雷托提出来的。他从政治经济学的角度考虑把本质上是不可比较的许多目标化成单个目标的最优化...
  • Jan 和 Deb 扩展了众所周知的 NSGA-II 来处理多目标优化问题,使用参考点方法,具有非支配排序机制。 新开发的算法简称为:NSGA-III。 主要参考文件可在此处获得: http : //doi.org/10.1109/TEVC.2013.2281535 。 ...
  • 非支配排序算法

    2017-09-28 14:50:09
    NSGA2英文原文,学习多目标优化入门论文,侵权即删。。。。。。。。。。。。。。。。。。。。。。。
  • NSGA-II非支配排序算法

    2015-07-09 15:33:14
    NSGA-II,多目标优化代码,含有ZDT、DTLZ、WFG测试问题,能直接运行。
  • (matlab代码)带约束条件的非支配排序遗传算法NSGA-II,解决了一个多目标优化问题 (matlab代码)带约束条件的非支配排序遗传算法NSGA-II,解决了一个多目标优化问题 (matlab代码)带约束条件的非支配排序遗传算法...
  • 经典非支配排序详解(原理+举例说明),后续进行代码实现。
  • 非支配排序遗传算法NSGA-II学习笔记

    千次阅读 2022-03-29 22:34:59
    一、多目标优化问题的解 在单目标优化问题中,...注:劣解也称为有效解、非支配解、Pareto最优解或Pareto解。 二、Pareto解集 学习NSGA-II,首先要明白什么是Pareto解集。举个例子,想象一下我们想要设计一款电动
  • 资源名:基于非支配排序遗传算法改编实用型matlab算法程序源码_收敛速度快而且能够避免收敛在局部最优_非支配排序遗传算法_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百...
  • 3非支配排序常见于遗传算法 3.1 解决的问题及三大特点 3.2数学模型 3.3 Pareto 最优解 1 兴趣引入 (1)在生活中,你想买一辆车,又想汽车的性能好,外观不错,价格还比较低,对于这同时满足这三个条件,我们...
  • 遗传算法非支配排序算法,以及差分进化算法
  • 非支配排序遗传算法matlab代码NSGA-III:非支配排序遗传算法,第三版— MATLAB实现 这是MATLAB中NSGA-III(主导排序遗传算法,第三版)的实现。 有关更多信息,请访问以下URL: 引用这项工作 您可以按如下所示引用...
  • 基于Pareto的非支配排序遗传算法II (PESA-II)是一种多目标进化优化算法,它利用了遗传算法的机制以及基于Pareto包络的选择。 PESA-II使用外部存档来存储近似的Pareto解决方案。 基于基于档案成员的地理分布创建的...
  • 代码 多目标快速非支配排序遗传算法优化代码.rar
  • 资源名:非支配排序算法_多目标优化的重要算法_通过交叉、变异,多次迭代产生最优解_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系...
  • 完整代码已上传我的资源:【优化算法】改进的量子遗传算法(IQGA)【含Matlab源码 1615期】 获取代码方式2: 通过订阅紫极神光博客付费专栏,凭支付凭证,私信博主,可获得此代码。 备注: 订阅紫极神光博客付费专栏...
  • 资源名:带精英策略的非支配排序遗传算法matlab 源码 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:新手...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,758
精华内容 1,503
关键字:

快速非支配排序算法