精华内容
下载资源
问答
  • 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具体算法实现还在编写中。

    更多相关内容
  • 20种非支配排序 MATLAB 代码
  • MATLAB源码集锦-多目标快速非支配排序遗传算法优化代码
  • 资源名:非支配排序遗传算法_MATLAB代码_用于非支配排序遗传算法优化_NSGA 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者...
  • 非支配排序算法

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

    千次阅读 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,感谢该博客的指导
    
    
    展开全文
  • matlab开发-非支配排序遗传算法。进化多目标优化的NSGA-II结构matlab实现
  • 针对带精英策略的非支配排序遗传算法不能根据环境变化自适应地动态调整运行参数,难以实现对解空间的高效搜索,提出一种自适应的非支配排序遗传算法.所提出算法根据运行阶段、运行代数和当前临时种群支配个体数动态...
  • 非支配排序遗传算法matlab代码PlatEMO_research 平板电脑 进化多目标优化平台 100多种开源进化算法 120多个开源多目标测试问题 强大的GUI可并行执行实验 一键式生成Excel或LaTeX表格式的结果 最先进的算法将不断被...
  • NSGA-II非支配排序算法

    2015-07-09 15:33:14
    NSGA-II,多目标优化代码,含有ZDT、DTLZ、WFG测试问题,能直接运行。
  • 非支配快速排序算法详解 对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年更新的那版)

    展开全文
  • 多路径遗传算法的matlab代码,求解准确,实用,作图美观,具有详细的注释。
  • 遗传算法非支配排序算法,以及差分进化算法
  • 资源名:非支配排序算法_多目标优化的重要算法_通过交叉、变异,多次迭代产生最优解_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系...
  • 代码 多目标快速非支配排序遗传算法优化代码代码 多目标快速非支配排序遗传算法优化代码代码 多目标快速非支配排序遗传算法优化代码代码 多目标快速非支配排序遗传算法优化代码代码 多目标快速非支配排序遗传算法...
  • 非支配排序算法NSGA-Ⅱ(Matlab)

    千次阅读 2020-04-28 20:18:17
    算法本人未用C#实现,将其博主https://blog.csdn.net/joekepler/article/details/80820240中的代码加以更改,本算法原理参考博主https://blog.csdn.net/qq_40434430/article/details/82876572。亲测有效。现将源码...

    该算法本人未用C#实现,将其博主https://blog.csdn.net/joekepler/article/details/80820240中的代码加以更改,本算法原理参考博主https://blog.csdn.net/qq_40434430/article/details/82876572。亲测有效。现将源码粘贴如下(请读者先弄懂原理,再读懂代码,方可加以改进):

    %初始化代码
    function f=initialize_variables(N,M,V,min_range,max_range)%f是一个由种群个体组成的矩阵
      min=min_range;
      max=max_range;
      K=M+V;
      for i=1:N
            for j=1:V
    		    f(i,j)=min(j)+(max(j)-min(j))*rand(1);
    		end
    		f(i,V+1:K)=evaluate_objective(f(i,:),M,V);
      end
    end
    
    
    %快速非支配排序和拥挤度计算代码
    %%对初始种群开始排序  快速非支配排序
    %%使用非支配排序对种群进行排序,该函数返回每个个体对应的排序值和拥挤距离,是一个两列矩阵
    %%并将排序值和拥挤距离添加到染色体矩阵中
    function f=non_domination_sort_mod(x,M,V)
        [N,~]=size(x);%%%N为矩阵x的行数,也是种群数量
    	clear m
    	front=1;
    	F(front).f=[];
    	individual=[];
    	for i=1:N
    	    individual(i).n=0;%%%n是个体i被支配的个体数量
    		individual(i).p=[];%%%p是被个体i支配的个体集合
    	    for j=1:N
    		    dom_less=0;
    			dom_equal=0;
    			dom_more=0;
    			for k=1:M %%%判断个体i和个体j的支配关系
    			    if(x(i,V+k)<x(j,V+k))
    				    dom_less=dom_less+1;
    				elseif(x(i,V+k)==x(j,V+k))
    				    dom_equal=domequal+1;
    				else 
    				    dom_more=dom_more+1;
    				end
    			end
    			if(dom_less==0&&dom_equal~=M) %%%说明i受j支配,相应的n加1
                    individual(i).n=individual(i).n+1;
    			elseif(dom_more==0&&dom_equal~=M)%%%说明i支配j,把j加入i的支配集合中
    			    individual(i).p=[individual(i).p j];
    			end
    		end
    		if(individual(i).n==0)%%%个体i非支配等级排序最高,属于当前最优解集,相应染色体中携带代表排序数的信息
    		    x(i,M+V+1)=1;
    			F(front).f=[F(front).f i];%%%等级为1的非支配解集
    		end
    	end
    	%%上面的代码是为了找出等级最高的非支配解集
    	%%下面的代码是为了给其他个体进行分级
    	while ~isempty(F(front).f)
    	    Q=[];%存放下一个front集合
    		for i=1:length(F(front).f)%%%循环当前支配解集中的个体
    		    if(~isempty(individual(F(front).f(i)).p))%%%个体i有自己所支配的解集
    			    for j=1:length(individual(F(front).f(i)).p)%%%循环个体i所支配解集中的个体
    				    individual(individual(F(front).f(i)).p(j)).n=individual(individual(F(front).f(i)).p(j)).n-1;%%%个体j的被支配数-1
    					if(individual(individual(F(front).f(i)).p(j)).n==0)%%%如果是非支配解集,则放入集合Q中
    					    x(individual(F(front).f(i)).p(j),M+V+1=front+1;%%%个体染色体中加入分级信息
    						Q=[Q individual(F(front).f(i)).p(j)];
    					end
    				end
    			end
    		end
    		front=front+1;
    		F(front).f=Q;
    	end
    	[temp,index_of_fronts]=sort(x(:,M+V+1));%%%对个体排序等级的列向量进行升序排序,index_of_fronts表示排序后的值对应原来的索引
    	for i=1:length(index_of_fronts)
    	    sorted_based_on_front(i,:)=x(index_of_front(i),:);%%%sorted_based_on_front中存放的是x矩阵按照排序等级升序排序后的矩阵
    	end
    	current_index=0;
    	
    	%%Crowding distance 计算每个个体的拥挤度
    	for front=1:(length(F)-1)%%%这里减一是因为代码55行这里,F的最后一个元素为空,这样才能跳出循环
    	    distance=0;
    		y=[];
    		previous_index=current_index+1;
    		for i=1:length(F(front).f)
    		    y(i,:)=sorted_based_on_front(current_index+i,:)%%%y中存放的事排序等级为front的集合矩阵
    		end
    		current_index=current_index+i;%%%current_index=i
    		sorted_based_on_objective=[];存放给予拥挤距离排序的矩阵
    		for i=1:M
    		    [sorted_based_on_objective,index_of_objectives=sort(y(:,V+i));按照目标函数值排序
    			sorted_based_on_objective=[];
    			for j=1:length(index_of_objectives)
    			    sorted_based_on_objective(j,:)=y(index_of_objectives(j),:);%%%sorted_based_on_objective存放按照目标函数值排序后的x矩阵
    			end 
    				f_max=sorted_based_on_objective(length(index_of_objectives),V+i);%%%目标函数最大值
    				f_min=sorted_based_on_objective(1,V+i);%%%目标函数最小值
    				y(index_of_objectives(length(index_of_objectives)),M+V+1+i)=Inf;对排序后的第一个个体和最后一个个体的距离设为无穷大
    				y(index_of_objectives(1),M+V+1+i)=Inf;
    				for j=2:length(index_of_objectives)-1 %%%循环集合中除第一个和最后一个个体
    				    next_obj=sorted_based_on_objective(j+1,V+i);
    					previous_obj=sorted_based_on_objective(j-1,V+i);
    					if(f_max-f_min==0)
    					    y(index_of_objectives(j),M+V+1+i)=Inf;
    					else
    					    y(index_of_objectives(j),M+V+1+i)=(next_obj-previous_obj)/(f_max-f_min);
    					end
    				end
    		end
    		distance=[];
    		distance(:1)=zeros(length(F(front).f),1);
    		for i=1:M
    			distance(:,1)=distance(:,1)+y(:,M+V+1+i);
    		end
    		y(:M+V+2)=distance;
    		y=y(:,1:M+V+2);
    		z(previous_index:current_index,:)=y;
    	end
    	f=z();%%%得到的是已经包含等级和拥挤度的种群矩阵,并且已经按等级排序
    	
    	
    	
    	
    %锦标赛选择代码
    function f=tournament_selection(chromosome,pool_size,tour_size)
        [pop,variables]=size(chromosome);%%获得种群的个体数量和决策变量数量
        rank=variables-1;%%个体向量中排序值所在位置
        distance=variables;%%个体向量中拥挤度所在位置
        %%锦标赛选择法,每次随机选择两个个体,优先选择排序等级高的个体,如果排序等级一样,优选拥挤度大的个体
        for i=1:pool_size  
    	    for j=1:tour_size
    		    candidate(j)=round(pop*rand(1));%随机选择参赛个体
    			if(candidate(j)==0)
    			    candidate(j)=1;
    			end
    			if(j>1)
    			    while ~isempty(find(candidate(1:j-1)==candidate(j)))%%防止两个参赛个体是同一个
    				    candidate(j)=round(pop*rand(1));
    					if(candidate(j)==0
    					    candidate(j)=1;
    					end
    				end
    			end
    		end
    		for j=1:tour_size %%记录每个参赛者的排序等级、拥挤度
    		    c_obj_rank(j)=chromosome(candidate(j),rank);
    			c_obj_distance(j)=chromosome(candidate(j),distance);
    		end
    		min_candidate=find(c_obj_rank==min(c_obj_rank));%%选择排序等级较小的参赛者,find返回该参赛者的索引
    		if(length(min_candidate)~=1)%%如果两个参赛者的排序等级相等,则继续标胶拥挤度,优选选择拥挤度答的个体
    		    max_candidate=find(c_obj_distance(min_candidate)==max(c_obj_distance(min_candidate)));
    			if(length(max_candidate)~=1
    			    max_candidate=max_candidate(1);
    			end
    			f(i,:)=chromosome(candidate(min_candidate(max_candidate)),:);
    		else
    	        f(i,:)=chromosome(candidate(min_candidate(1)),:);
    		end
    	end
    end
    
    
    %交叉变异操作
    function f=genetic_operator(parent_chromosome,M,V,mu,mum,l_limit,u_limit)
        [N,m]=size(parent_chromosome);%%N是交配池中的个体数量
    	clear m
    	p=1;
    	was_crossover=0;%%是否交叉标识位
    	was_mutation=0;%%是否变异标志位
    	for i=1:N  %%虽然循环N次,但每次循环都会有概率产生2个或者1个子代,所以最终产生的子代个体数量大约是2N个
    	    if(rand(1)<0.9)%%交叉概率0.9
    		    child_1=[];
    			child_2=[];
    			parent_1=round(N*rand(1));
    			if(parent_1<1)
    				parent_1=1;
    			end
    			parent_2=round(N*rand(1));
    			if(parent_2<1)
    			    parent_2=1;
    			end
    			while isequal(parent_chromosome(parent_1,:),parent_chromosome(parent_2,:))
    			    parent_2=round(N*rand(1));
    				if(parent_2<1)
    				    parent_2=1;
    				end
    			end
    			parent_1=parent_chromosome(parent_1,:);
    			parent_2=parent_chromosome(parent_2,:);
    			for j=1:V
    			    u(j)=rand(1);
    				if(u(j)<=0.5)
    				    bq(j)=(2*u(j))^(1/(mu+1));
    				else 
    				    bq(j)=(1/(2*(1-u(j))))^(1/(mu+1));
    				end
    				child_1(j)=0.5*(((1+bq(j))*parent_1(j))+(1-bq(j))*parent_2(j));
    				child_2(j)=0.5*(((1-bq(j))*parent_1(j))+(1+bq(j))*parent_2(j));
    				if(child_1>u_limit(j))
    				    child_1(j)=u_limit(j);
    				elseif(child_1(j)<l_limit(j))
    				    child_1(j)=l_limit(j);
    				end
    				if(child_2>u_limit(j))
    				    child_2(j)=u_limit(j);
    				elseif(child_2(j)<l_limit(j))
    				    child_2(j)=l_limit(j);
    				end
    			end
    			child_1(:,V+1:M+V)=evaluate_objective(child_1,M,V);
    			child_2(:,V+1:M+V)=evaluate_objective(child_2,M,V);
    			was_mutation=0;
    			was_crossover=1;
    		else
    			parent_3=round(N*rand(1));
    			if(parent_3<1)
    				parent_3=1;
    			end
    			child_3=parent_chromosome(parent_3,:);
    			for j=1:V
    			    r(j)=rand(1);
    				if(r(j)<0.5)
    					delta(j)=(2*r(j))^(1/(mun+1)-1;
    				else
    					delta(j)=1-(2*(1-r(j)))^(1/(mun+1));
    				end
    				child_3(j)=child_3(j)+delta(j);
    				if(child_3(j)>u_limit(j))
    					child_3(j)=u_limit(j);
    				elseif(child_3(j)<l_limit(j))
    					child_3(j)=l_limit(j);
    			    end
    			end
    			child_3(:,V+1:M+V)=evaluate_objective(child_3,M,V);
    			was_mutation=1;
                was_crossover=0;
    			if(was_crossover==1)
    			    child(p,:)=child_1;
    				child(p+1,:)=child_2;
    				was_cossover=0;
    				p=p+2;
    			elseif(was_mutation==1)
    			    child(p,:)=child_3(1,1:M+V);
    				was_mutation=0;
    				p=p+1;
    			end
    		end
    	end
    	f=child;
    
    	
    	
    	
    %生成新的种群(精英策略)
    function f=replace_chromosome(intermediate_chromosome,M,V,pop)%%精英选择策略
        [N,m]=size(intermediate_chromosome);
    	[temp,index]=sort(intermediate_chromosome(:,M+V+1));
    	clear temp m
    	for i=1:N
    	    sorted_chromosome(i,:)=intermediate_chromosome(index(i),:);
    	end
    	max_rank=max(intermediate_chromosome(:,M+V+1));
    	previous_index=0;
    	for i=1:max_rank
    	    current_index=max(find(sorted_chromosome(:,M+V+1)==i));
    		if(current_index>pop)
    		    remaining=pop-previous_index;
    			temp_pop=sorted_chromosome(previous_index+1:current_index,:);
    			[temp_sort,temp_sort_index]=sort(temp_pop(:,M+V+2),'descend');
    			for j=1:remaining
    			    f(previous_index+j,:)=temp_pop(temp_sort_index(j),:);
    			end
    			return 
    		elseif(current_index<pop)
    		    f(previous_index+1:current_index,:)=sorted_chromosome(previous_index+1:current_index,:);
    		end
    		previous_index=current_index;
    	end
    end
    
    
    
    
    %测试函数
    function f=evaluate_objective(x,M,V)%%计算每个个体的M个目标函数值
        f=[];
    	f(1)=x(1);
    	g=1;
    	sum=0;
    	for j=2:V
    	    sum=sum+x(i);
    	end
    	sum=9*(sum/(V-1));
    	g=g+sum;
    	f(2)=g*(1-sqrt(x(1)/g));
    end
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    展开全文
  • 如果需要严格的非支配排序,则可以通过将epsilons任意设置为较小来近似(在某种程度上,这里涉及浮点除。)默认情况下,1e-9的epsilon分辨率将有效地导致严格的非支配排序。 。 排序之前的数据。 目标f1和f2都应...
  • Jan 和 Deb 扩展了众所周知的 NSGA-II 来处理多目标优化问题,使用参考点方法,具有非支配排序机制。 新开发的算法简称为:NSGA-III。 主要参考文件可在此处获得: http : //doi.org/10.1109/TEVC.2013.2281535 。 ...
  • (matlab代码)带约束条件的非支配排序遗传算法NSGA-II,解决了一个多目标优化问题 (matlab代码)带约束条件的非支配排序遗传算法NSGA-II,解决了一个多目标优化问题 (matlab代码)带约束条件的非支配排序遗传算法...
  • 非支配排序遗传算法matlab代码NSGA-III:非支配排序遗传算法,第三版— MATLAB实现 这是MATLAB中NSGA-III(主导排序遗传算法,第三版)的实现。 有关更多信息,请访问以下URL: 引用这项工作 您可以按如下所示引用...
  • 本论文介绍了新颖的NSGA-III算法,并将其应用于高维的目标优化中,取得良好结果。
  • 多目标优化系列: MOP_1. 多目标优化的相关基本概念 MOP_2. 非支配排序遗传算法 —(NSGA、...1995年,Srinivas和Deb提出了非支配排序遗传算法(Non-dominatedSorting Genetic Algorithms,NSGA)。这是一种基于P...
  • 第三代非支配遗传算法是针对高维多目标优化计算代价大,难以挑选Pareto解的情况而开发的,基本流程与NSGA-II相似,但选择个体的方法加入了基于参考点的方法,能够有效降低计算代价。NSGA-III 首先定义一组参考点。...
  • 精英非支配排序算法与改进粒子群算法相结合的储能优化配置.pdf
  • 完整代码已上传我的资源:【优化算法】改进的量子遗传算法(IQGA)【含Matlab源码 1615期】 获取代码方式2: 通过订阅紫极神光博客付费专栏,凭支付凭证,私信博主,可获得此代码。 备注: 订阅紫极神光博客付费专栏...
  • 一种用于进化多目标优化的新型非支配排序算法
  • 资源名:基于非支配排序遗传算法改编实用型matlab算法程序源码_收敛速度快而且能够避免收敛在局部最优_非支配排序遗传算法_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百...
  • 非支配排序遗传算法NSGA-II学习笔记

    千次阅读 2022-03-29 22:34:59
    一、多目标优化问题的解 在单目标优化问题中,...注:劣解也称为有效解、非支配解、Pareto最优解或Pareto解。 二、Pareto解集 学习NSGA-II,首先要明白什么是Pareto解集。举个例子,想象一下我们想要设计一款电动
  • 针对快速非支配排序遗传算法(NSGA-Ⅱ)的精英保留策略会使大量冗余的高排序级别个体同时作为精英保留到下一代,极易发生早熟收敛现象问题,提出了改进的快速非支配排序遗传算法(I-NSGA-Ⅱ),并将其应用于交通信号...

空空如也

空空如也

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

非支配排序算法