精华内容
下载资源
问答
  • 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源码集锦-多目标快速非支配排序遗传算法优化代码
  • 多路径遗传算法的matlab代码,求解准确,实用,作图美观,具有详细的注释。
  • 代码 多目标快速非支配排序遗传算法优化代码代码 多目标快速非支配排序遗传算法优化代码代码 多目标快速非支配排序遗传算法优化代码代码 多目标快速非支配排序遗传算法优化代码代码 多目标快速非支配排序遗传算法...
  • #资源达人分享计划#
  • 针对快速非支配排序遗传算法(NSGA-Ⅱ)的精英保留策略会使大量冗余的高排序级别个体同时作为精英保留到下一代,极易发生早熟收敛现象问题,提出了改进的快速非支配排序遗传算法(I-NSGA-Ⅱ),并将其应用于交通信号...
  • 多目标问题的非支配排序 通过和 pareto.py在纯Python中实现了epsilon pareto.py的排序。 它将一个或多个解决方案文件分类为帕累托有效(或“无名”)集合。 解决方案可以包含目标以外的其他列,这些列将不加分类地...
  • 多目标规划的概念是 1961年由美国数学家查尔斯和库柏首先提出的。多目标最优化思想,最早是在1896年由法国经济学家V.帕雷托提出来的。他从政治经济学的角度考虑把本质上是不可比较的许多目标化成单个目标的最优化...
  • 代码 多目标快速非支配排序遗传算法优化代码.rar
  • 多目标快速非支配排序遗传算法优化matlab代码.zip
  • 快速非支配排序多目标遗传算法纯正源代码,绝对正确!
  • 多目标优化之核心知识点(快速非支配排序、拥挤距离、精英选择策略)详解(python实现)


    一、多目标优化算法简介

         什么是多目标优化算法,见链接:
    十分钟了解完多目标优化算法

    1.基本知识

    支配:假设小明9岁,50斤,小红8岁,45斤,小明无论是岁数还是体重都比小红大,所以小明支配小红。

    互不支配:假设小明7岁,50斤,小红8岁,45斤,小明岁数比小红小,但体重比小红大,所以小明和小红互不支配。

    帕累托集:在这个集合中,任意两个解互不支配。 如果有2个目标函数,帕累托集应该分布成一条曲线;如果有3个目标函数,帕累托集应该分布成一个超平面。 常规的2个目标函数,解法是目标加权得到是一个点,一个解;帕累托集,目标函数之间没有加权关系,所以得到是一条曲线。

    非支配排序:将一组解分成n个集合:rank1,rank2…rankn,每个集合中所有的解都互不支配,但ranki中的任意解支配rankj中的任意解(i<j).

    二、NSGA2算法

    1.基本原理

         多目标遗传算法是用来分析和解决多目标优化问题的一种进化算法,其核心就是协调各个目标函数之间的关系,找出使得各个目标函数都尽可能达到比较大的(或者比较小的)函数值的最优解集。在众多目标优化的遗传算法中,NSGA2算法是影响最大和应用范围最广的一种多目标遗传算法。在其出现后,由于它简单有效以及比较明显的优越性,使得该算法已经成为多目标优化问题中的基本算法之一。

         介绍NSGA2,首先来介绍以下NSGA算法。

         NSGA通过基于非支配排序的方法保留了种群中的优良个体,并且利用适应度共享函数保持了群体的多样性,取得了非常良好的效果。但实际工程领域中发现NSGA算法存在明显不足,这主要体现在如下3个方面:

    • (1)非支配排序的高计算复杂性。非支配排序算法一般要进行mN^3次搜索(m是目标函数的数目,体重和年龄可以被视为两个目标函数,N是一组解的大小),搜索的次数随着目标函数数量和种群大小的增加而增多。
    • (2)缺少精英策略。研究结果表明,引用精英策略可以加快遗传算法的执行,并且还助于防止优秀的个体丢失。
    • (3)需要指定共享参数share,在NSGA算法中保持种群和解的多样性方法都是依赖于共享的概念,共享的主要问题之一就是需要人为指定一个共享参数share。

         为了克服非支配排序遗传算法(NSGA)的上述不足,印度科学家Deb于2002年在NSGA算法的基础上进行了改进,提出了带精英策略的非支配排序遗传算法(Elitist Non-Dominated Sorting Genetic Algorithm,NSGA-II),NSGA-II 算法针对NSGA的缺陷通过以下三个方面进行了改进[16]:

    • 提出了快速非支配的排序算法,降低了计算非支配序的复杂度,使得优化算法的复杂度由原来的 降为 ( 为目标函数的个数, 为种群的大小)。
    • 引入了精英策略,扩大了采样空间。将父代种群与其产生的子代种群组合在一起,共同通过竞争来产生下一代种群,这有利于是父代中的优良个体得以保持,保证那些优良的个体在进化过程中不被丢弃,从而提高优化结果的准确度。并且通过对种群所有个体分层存放,使得最佳个体不会丢失,能够迅速提高种群水平。
    • 引入拥挤度和拥挤度比较算子,这不但克服了NSGA算法中需要人为指定共享参数 的缺陷,而且将拥挤度作为种群中个体之间的比较准则,使得准Pareto域中的种群个体能均匀扩展到整个Pareto域,从而保证了种群的多样性。

    2.快速非支配排序

         解的支配关系与Pareto最优解



         快速非支配排序步骤:
    快速非支配排序就是将解集分解为不同次序的Pareto前沿的过程。
    它可以描述为:

    • 1.为每个解p分配两个关键量:支配p的解个数n_p以及被p支配的解集S_p;
    • 2.设置i=1,将n_p=0的个体归入F_i;
    • 3.对于F_i中的个体,遍历每个解p的S_p,将其中每个解的n_p减1;
    • 4.i+=1,将n_p=0的解归入F_i;
    • 5.重复3、4,直到解集中所有个体都被归入某一个F_i。

    2.1快速非支配排序 python实现

    #!/usr/bin/env python3
    # -*- coding: utf-8 -*-
    # @Author: yudengwu(余登武)
    # @Date  : 2021/10/26
    #@email:1344732766@qq.com
    #============导入相关包========
    import numpy as np
    import matplotlib.pyplot as plt
    import matplotlib as mpl
    import matplotlib; matplotlib.use('TkAgg')
    mpl.rcParams['font.sans-serif'] = ['SimHei']  # 指定默认字体
    mpl.rcParams['axes.unicode_minus'] = False  # 解决保存图像是负号'-'显示为方块的问题
    
    #==========定义两个目标函数=============
    # 定义函数1
    def function1(x):
        value = -(x+2) ** 2+2*x
        return value
    # 定义函数2
    def function2(x):
        value = -(x - 2) ** 2
        return value
    
    #=========定义群体,并绘制初始解的分布图=====
    pop_size = 10
    max_gen = 100
    # 迭代次数
    #Initialization
    min_x=-10
    max_x=10
    np.random.seed(10)#固定随机数种子,使每次生成的初始解集一样
    solution=np.random.uniform(min_x,max_x,pop_size) #生成的初始解集
    
    
    #函数1 对应的初始目标函数值
    values1=map(function1,solution) #python中的map用法,可以对遍历一个列表如solution,然后将列表元素传入到函数function1。得到解。得到的格式为对象
    values1=[i for i in values1] #因为上一步得到是对象格式,需要转换成列表格式
    
    #函数2 对应的初始目标函数值
    values2=map(function2,solution) #python中的map用法,可以对遍历一个列表如solution,然后将列表元素传入到函数function2。得到解。得到的格式为对象
    values2=[i for i in values2] #因为上一步得到是对象格式,需要转换成列表格式
    
    plt.scatter(values1,values2, s=20, marker='o')
    for i in range(pop_size):
        plt.annotate(i, xy=(values1[i], values2[i]), xytext=(values1[i] - 0.05, values2[i] - 0.05),fontsize=18)
    plt.xlabel('function1')
    plt.ylabel('function2')
    plt.title('解的分布示意图')
    plt.show()
    
    #=================快速非支配排序==============
    '''
    
    1.n[p]=0 s[p]=[] 
    2.对所有个体进行非支配判断,若p支配q,则将q加入到S[p]中,并将q的层级提升一级。
      若q支配p,n[p]+1.
    3.找出种群中np=0的个体,即最优解,并找到最优解的支配解集合。存放到front[0]中
    4 i==0
    5.判断front是否为空,若不为空,将front中所有的个体sp中对应的被支配个体数减去1,(存放np==0的解序号进front[i+1]);i=i+1,跳到2;
      若为空,则表明得到了所有非支配集合,程序结束
    '''
    
    values=[values1,values2] #解集【目标函数1解集,目标函数2解集...】
    def fast_non_dominated_sort(values):
        """
        优化问题一般是求最小值
        :param values: 解集【目标函数1解集,目标函数2解集...】
        :return:返回解的各层分布集合序号。类似[[1], [9], [0, 8], [7, 6], [3, 5], [2, 4]] 其中[1]表示Pareto 最优解对应的序号
        """
        values11=values[0]#函数1解集
        S = [[] for i in range(0, len(values11))]#存放 每个个体支配解的集合。
        front = [[]] #存放群体的级别集合,一个级别对应一个[]
        n = [0 for i in range(0, len(values11))]#每个个体被支配解的个数 。即针对每个解,存放有多少好于这个解的个数
        rank = [np.inf for i in range(0, len(values11))]#存放每个个体的级别
    
    
    
        for p in range(0, len(values11)):#遍历每一个个体
            # ====得到各个个体 的被支配解个数 和支配解集合====
            S[p] = [] #该个体支配解的集合 。即存放差于该解的解
            n[p] = 0  #该个体被支配的解的个数初始化为0  即找到有多少好于该解的 解的个数
            for q in range(0, len(values11)):#遍历每一个个体
                less = 0 #的目标函数值小于p个体的目标函数值数目
                equal = 0 #的目标函数值等于p个体的目标函数值数目
                greater = 0 #的目标函数值大于p个体的目标函数值数目
                for k in range(len(values)):  # 遍历每一个目标函数
                    if values[k][p] > values[k][q]:  # 目标函数k时,q个体值 小于p个体
                        less = less + 1  # q比p 好
                    if values[k][p] == values[k][q]:  # 目标函数k时,p个体值 等于于q个体
                        equal = equal + 1
                    if values[k][p] < values[k][q]:  # 目标函数k时,q个体值 大于p个体
                        greater = greater + 1  # q比p 差
    
                if (less + equal == len(values)) and (equal != len(values)):
                    n[p] = n[p] + 1  # q比p,  比p好的个体个数加1
    
                elif (greater + equal == len(values)) and (equal != len(values)):
                    S[p].append(q)  # q比p差,存放比p差的个体解序号
    
            #=====找出Pareto 最优解,即n[p]===0 的 个体p序号。=====
            if n[p]==0:
                rank[p] = 0 #序号为p的个体,等级为0即最优
                if p not in front[0]:
                    # 如果p不在第0层中
                    # 将其追加到第0层中
                    front[0].append(p) #存放Pareto 最优解序号
    
        # =======划分各层解========
    
        """
        #示例,假设解的分布情况如下,由上面程序得到 front[0] 存放的是序号1
        个体序号    被支配个数   支配解序号   front
        1          0            2,3,4,5    0
        2,         1,          3,4,5
        3,        1,           4,5
        4,        3,           5
        5          4,           0
    
        #首先 遍历序号1的支配解,将对应支配解[2,3,4,5] ,的被支配个数-1(1-1,1-1,3-1,4-1)
        得到
        表
        个体序号    被支配个数   支配解序号   front
        1          0            2,3,4,5    0
        2,         0,          3,4,5
        3,        0,           4,5
        4,        2,           5
        5          2,           0
    
        #再令 被支配个数==0 的序号 对应的front 等级+1
        得到新表...
        """
        i = 0
        while (front[i] != []):  # 如果分层集合为不为空
            Q = []
            for p in front[i]:  # 遍历当前分层集合的各个个体p
                for q in S[p]:  # 遍历p 个体 的每个支配解q
                    n[q] = n[q] - 1  # 则将fk中所有给对应的个体np-1
                    if (n[q] == 0):
                        # 如果nq==0
                        rank[q] = i + 1
                        if q not in Q:
                            Q.append(q)  # 存放front=i+1 的个体序号
    
            i = i + 1  # front 等级+1
            front.append(Q)
    
        del front[len(front) - 1]  # 删除循环退出 时 i+1产生的[]
    
        return front #返回各层 的解序号集合 # 类似[[1], [9], [0, 8], [7, 6], [3, 5], [2, 4]]
    
    front=fast_non_dominated_sort(values)
    
    
    #=================打印结果=======================
    #遍历各层
    for i in range(len(front)):
        print('第%d层,解的序号为%s'%(i,front[i]))
        jie=[]
        for j in front[i]:#遍历第i层各个解
            jie.append(solution[j])
        print('第%d层,解为%s'%(i,jie))
    
    
    结果如图,发现成功找到最优解

    3.拥挤距离

          拥挤距离的定义
          在NSGA-II中,为了衡量在同一个前沿中各个解质量的优劣,作者为每个解分配了一个拥挤距离,其背后的思想是让求得的Pareto最优解在objective space中尽量分散,也就有更大可能让解在Pareto最优前沿上均匀分布。

          拥挤距离主要是维持种群中个体的多样性。具体而言,一般来说 是指种群按照支配关系进行非支配排后单个Rank层中个体的密集程度。常用于支配关系的多目标算法中,例如NSGA-1I.

    主要步骤如下:

    • 取单个前沿中个体按照一个目标上的值从小到大排序
    • 将最大目标值作为max,最小目标值保留作为min。并且这两个极值点的拥挤距离都被设置为inf即无穷大。因此注意,一个层中可能有多个具有inf的点,即如果层中有多个点在至少一个目标上相等,并且最大或最小,那么这些点的拥挤距离都是无穷大! !因为目标上呈现垂直的关系也是属于非支配的关系! !如果出现这种情况,说明你算法的多样性很烂! ~或者在某些算法早期可能出现这种情况
    • 在这个目标上计算每个个体最相邻个体之间的距离,即i-1和i+1的目标值的差。 并使用max和min对次值进行归一化。
    • 遍历目标,将目标上已经归一化的拥挤距离相加。
    • 进入下一层front前沿
    • 拥挤距离越大越好,最后按照拥挤距离重新排序各层,进而排序种群。

    3.1 拥挤距离python 实现

    #!/usr/bin/env python3
    # -*- coding: utf-8 -*-
    # @Author: yudengwu(余登武)
    # @Date  : 2021/10/27
    #@email:1344732766@qq.com
    #============导入相关包========
    import numpy as np
    import matplotlib.pyplot as plt
    import matplotlib as mpl
    import matplotlib; matplotlib.use('TkAgg')
    mpl.rcParams['font.sans-serif'] = ['SimHei']  # 指定默认字体
    mpl.rcParams['axes.unicode_minus'] = False  # 解决保存图像是负号'-'显示为方块的问题
    
    #==========定义两个目标函数=============
    # 定义函数1
    def function1(x):
        y = (x - 1) ** 2
        return y
    # 定义函数2
    def function2(x):
        y = np.cos(x)
        return y
    
    #=========定义群体,并绘制初始解的分布图=====
    pop_size = 50
    max_gen = 100
    # 迭代次数
    #Initialization
    min_x=-10
    max_x=10
    np.random.seed(10)#固定随机数种子,使每次生成的初始解集一样
    solution=np.random.uniform(min_x,max_x,pop_size) #生成的初始解集
    
    
    #函数1 对应的初始目标函数值
    values1=map(function1,solution) #python中的map用法,可以对遍历一个列表如solution,然后将列表元素传入到函数function1。得到解。得到的格式为对象
    values1=[i for i in values1] #因为上一步得到是对象格式,需要转换成列表格式
    
    #函数2 对应的初始目标函数值
    values2=map(function2,solution) #python中的map用法,可以对遍历一个列表如solution,然后将列表元素传入到函数function2。得到解。得到的格式为对象
    values2=[i for i in values2] #因为上一步得到是对象格式,需要转换成列表格式
    
    plt.scatter(values1,values2, s=20, marker='o')
    for i in range(pop_size):
        plt.annotate(i, xy=(values1[i], values2[i]), xytext=(values1[i] - 0.05, values2[i] - 0.05),fontsize=18)
    plt.xlabel('function1')
    plt.ylabel('function2')
    plt.title('解的分布示意图')
    plt.show()
    
    
    #=================快速非支配排序==============
    values=[values1,values2] #解集【目标函数1解集,目标函数2解集...】
    def fast_non_dominated_sort(values):
        """
        优化问题一般是求最小值
        :param values: 解集【目标函数1解集,目标函数2解集...】
        :return:返回解的各层分布集合序号。类似[[1], [9], [0, 8], [7, 6], [3, 5], [2, 4]] 其中[1]表示Pareto 最优解对应的序号
        """
        values11=values[0]#函数1解集
        S = [[] for i in range(0, len(values11))]#存放 每个个体支配解的集合。
        front = [[]] #存放群体的级别集合,一个级别对应一个[]
        n = [0 for i in range(0, len(values11))]#每个个体被支配解的个数 。即针对每个解,存放有多少好于这个解的个数
        rank = [np.inf for i in range(0, len(values11))]#存放每个个体的级别
    
        for p in range(0, len(values11)):#遍历每一个个体
            # ====得到各个个体 的被支配解个数 和支配解集合====
            S[p] = [] #该个体支配解的集合 。即存放差于该解的解
            n[p] = 0  #该个体被支配的解的个数初始化为0  即找到有多少好于该解的 解的个数
            for q in range(0, len(values11)):#遍历每一个个体
                less = 0 #的目标函数值小于p个体的目标函数值数目
                equal = 0 #的目标函数值等于p个体的目标函数值数目
                greater = 0 #的目标函数值大于p个体的目标函数值数目
                for k in range(len(values)):  # 遍历每一个目标函数
                    if values[k][p] > values[k][q]:  # 目标函数k时,q个体值 小于p个体
                        less = less + 1  # q比p 好
                    if values[k][p] == values[k][q]:  # 目标函数k时,p个体值 等于于q个体
                        equal = equal + 1
                    if values[k][p] < values[k][q]:  # 目标函数k时,q个体值 大于p个体
                        greater = greater + 1  # q比p 差
    
                if (less + equal == len(values)) and (equal != len(values)):
                    n[p] = n[p] + 1  # q比p,  比p好的个体个数加1
    
                elif (greater + equal == len(values)) and (equal != len(values)):
                    S[p].append(q)  # q比p差,存放比p差的个体解序号
    
            #=====找出Pareto 最优解,即n[p]===0 的 个体p序号。=====
            if n[p]==0:
                rank[p] = 0 #序号为p的个体,等级为0即最优
                if p not in front[0]:
                    # 如果p不在第0层中
                    # 将其追加到第0层中
                    front[0].append(p) #存放Pareto 最优解序号
    
        # =======划分各层解========
    
        i = 0
        while (front[i] != []):  # 如果分层集合为不为空
            Q = []
            for p in front[i]:  # 遍历当前分层集合的各个个体p
                for q in S[p]:  # 遍历p 个体 的每个支配解q
                    n[q] = n[q] - 1  # 则将fk中所有给对应的个体np-1
                    if (n[q] == 0):
                        # 如果nq==0
                        rank[q] = i + 1
                        if q not in Q:
                            Q.append(q)  # 存放front=i+1 的个体序号
    
            i = i + 1  # front 等级+1
            front.append(Q)
    
        del front[len(front) - 1]  # 删除循环退出 时 i+1产生的[]
    
        return front #返回各层 的解序号集合 # 类似[[1], [9], [0, 8], [7, 6], [3, 5], [2, 4]]
    
    front=fast_non_dominated_sort(values)
    
    
    #=============拥挤距离================
    def crowding_distance(values,front):
        """
        :param values: 群体[目标函数值1,目标函数值2,...]
        :param front: 群体解的等级,类似[[1], [9], [0, 8], [7, 6], [3, 5], [2, 4]]
        :return: front 对应的 拥挤距离
        """
        distance = np.zeros(shape=(pop_size, ))  # 拥挤距离初始化为0
        for rank in front:  # 遍历每一层Pareto 解 rank为当前等级
            for i in range(len(values)):  # 遍历每一层函数值(先遍历群体函数值1,再遍历群体函数值2...)
                valuesi = [values[i][A] for A in rank]  # 取出rank等级 对应的  目标函数值i 集合
                rank_valuesi = zip(rank, valuesi)  # 将rank,群体函数值i集合在一起
                sort_rank_valuesi = sorted(rank_valuesi, key=lambda x: (x[1],x[0]))  # 先按函数值大小排序,再按序号大小排序
    
                sort_ranki = [j[0] for j in sort_rank_valuesi]  # 排序后当前等级rank
                sort_valuesi = [j[1] for j in sort_rank_valuesi]  # 排序后当前等级对应的 群体函数值i
                #print(sort_ranki[0],sort_ranki[-1])
                distance[sort_ranki[0]] = np.inf  # rank 等级 中 的最优解 距离为inf
                distance[sort_ranki[-1]] = np.inf  # rank 等级 中 的最差解 距离为inf
    
                #计算rank等级中,除去最优解、最差解外。其余解的拥挤距离
                for j in range(1, len(rank) - 2):
                    distance[sort_ranki[j]] = distance[sort_ranki[j]] + (sort_valuesi[j + 1] - sort_valuesi[j - 1]) / (
                                max(sort_valuesi) - min(sort_valuesi))  # 计算距离
    
    
        # 按照格式存放distances
        distanceA = [[] for i in range(len(front))]  #
        for j in range(len(front)):  # 遍历每一层Pareto 解 rank为当前等级
            for i in range(len(front[j])):  # 遍历给rank 等级中每个解的序号
                distanceA[j].append(distance[front[j][i]])
    
        return distanceA
    
    
    distanceA=crowding_distance(values,front)
    
    #打印拥挤距离结果
    
    
    for i in range(len(front)):
        print('当前等级 解的序号为:',front[i])
        print('当前等级 解的拥挤距离为:',distanceA[i])
    
    
    

    4.精英选择策略

          多目标优化过程中,得到父辈和子代解后,我们需要选择优秀的群体进行下一代。
          这里采用精英选择策略

    4.1 精英选择策略python 实现

    #这里的front,distance,solution 数据格式同前文
    
     def elitism(self,front, distance, solution):
            """
            精英选择策略
            :param front: 父代与子代 组合构成的解的等级
            :param distance:  父代与子代 组合构成的解 拥挤距离
            :param solution:  父代与子代 组合构成的解
            :return:  返回群体解。群体数量=(父代+子代)//2
            """
            X1index = []  # 存储群体编号
            pop_size = len(solution) // 2  # 保留的群体个数 即(父辈+子辈)//2
    
            for i in range(len(front)):  # 遍历各层
                rank_distancei = zip(front[i], distance[i])  # 当前等级 与当前拥挤距离的集合
                sort_rank_distancei = sorted(rank_distancei, key=lambda x: (x[1], x[0]),
                                             reverse=True)  # 先按拥挤距离大小排序,再按序号大小排序,逆序
                sort_ranki = [j[0] for j in sort_rank_distancei]  # 排序后当前等级rank
                sort_distancei = [j[1] for j in sort_rank_distancei]  # 排序后当前等级对应的 拥挤距离i
    
                if (pop_size - len(X1index)) >=len(sort_ranki):  # 如果X1index还有空间可以存放当前等级i 全部解
                    X1index.extend([A for A in sort_ranki])
    
                #print('已存放len(X1index)', len(X1index))
                #print('当前等级长度', len(sort_ranki))
                #print('需要存放的总长度,popsize)
                #num = pop_size-len(X1index)# X1index 还能存放的个数
                elif len(sort_ranki) > (pop_size-len(X1index)):  # 如果X1空间不可以存放当前等级i 全部解
                    num = pop_size - len(X1index) 
                    X1index.extend([A for A in sort_ranki[0:num]])
            X1 = [solution[i] for i in X1index]
    
            return X1
    
    

    总结

          本文通定义两个目标函数,然后生成初始解。利用初始解,解释了核心知识点:快速非支配排序、拥挤距离、精英选择策略。本文的文字部分有借鉴他人博客。代码为自己纯手打。下一步,将快速非支配排序、拥挤距离、精英选择策略写进遗传算法,解决常规约束、带复杂约束问题(可能需要修改下快速非支配排序代码,因为复杂约束不仅仅考虑适应度,还有惩罚项在里面)构成多目标优化问题代码模板。
    多目标遗传优化算法nsga2[python源码实现]
    多目标遗传优化算法nsga2求解复杂约束问题【python源码实现】

    经实验:快速非支配排序、拥挤距离、精英选择策略 无法应用于粒子群算法。因为无法定义pbest,gbest。
    在这里插入图片描述
    作者:电气-余登武。原创不易,禁止抄袭。

    展开全文
  • 多目标炼钢—连铸生产调度的改进带精英策略的快速非支配排序遗传算法.pdf
  • 非支配快速排序算法详解 对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源码
  • NSGA-II非支配排序算法

    2015-07-09 15:33:14
    NSGA-II,多目标优化代码,含有ZDT、DTLZ、WFG测试问题,能直接运行。
  • 非支配排序遗传算法NSGA-II学习笔记

    千次阅读 2022-03-29 22:34:59
    一、多目标优化问题的解 在单目标优化问题中,...注:劣解也称为有效解、非支配解、Pareto最优解或Pareto解。 二、Pareto解集 学习NSGA-II,首先要明白什么是Pareto解集。举个例子,想象一下我们想要设计一款电动

    一、多目标优化问题的解

    在单目标优化问题中,通常最优解只有一个,而且能用比较简单和常用的数学方法求出其最优解。然而在多目标优化问题中,各个目标之间相互制约,可能使得一个目标性能的改善是以其他目标性能为代价,不可能存在一个使所有目标性能都达到最优的解,所以对于多目标优化问题,其解通常是一个非劣解的集合——Pareto解集

    注:非劣解也称为有效解、非支配解、Pareto最优解或Pareto解。

    二、Pareto解集

    学习NSGA-II,首先要明白什么是Pareto解集。举个例子,想象一下我们想要设计一款电动汽车,它有两个主要目标:

    • 一个很短的百公里加速时间。
    • 最大可能的行驶里程。

    汽车公司已经制造了汽车的一些部件,我们作为设计团队,可以改变三个参数:

    • 车轮尺寸。
    • 电机功率。
    • 电池容量。

    很明显,这个问题并不是只有一个完美的解决方案,以扩大汽车的续航能力而言,需要更大的电池,这就增加了额外的重量,因此,百公里加速时间就增加了。

    假设,下图表示不同汽车可能输出的结果:
    在这里插入图片描述
    每一个点代表一辆带有上述设计参数的参数化汽车,有车轮尺寸、电机功率、电池容量。

    所以对于这辆车,第一个点的行驶里程约为600公里,百公里加速需要2.5秒。

    而第二个点,有更大的行驶里程,约为650公里,但百公里加速时间也更长,约为4.7秒。
    在这里插入图片描述
    我们的目标是针对定义的目标参数优化系统,在这个系统中,指行驶里程和加速时间,所以,我们希望最小化加速时间,并最大化汽车的行驶里程。

    首先,先理解支配的概念,数学解释如下:

    对于最小化多目标问题,n个目标分量 f i ( x ) , i = 1 , 2... n {f_i}\left( x \right),i = 1,2...n fi(x),i=1,2...n,任意给定两个决策变量 X a {X_a} Xa X b {X_b} Xb,如果有以下两个条件同时成立,则称 X a {X_a} Xa支配 X b {X_b} Xb

    1. 任意 i ∈ 1 , 2... n i \in 1,2...n i1,2...n,都有 f i ( X a ) ≤ f i ( X b ) {f_i}\left( {{X_a}} \right) \le {f_i}\left( {{X_b}} \right) fi(Xa)fi(Xb)成立。
    2. 存在 i ∈ 1 , 2... n i \in 1,2...n i1,2...n,使得 f i ( X a ) < f i ( X b ) {f_i}\left( {{X_a}} \right) < {f_i}\left( {{X_b}} \right) fi(Xa)<fi(Xb)成立。

    如果对于一个决策变量,不存在其他决策变量能够支配它,那么就称该决策变量为非支配解。

    通俗点讲,假设存在两个目标函数,解A的两个目标值均优于解B,则称解A支配解B。

    如图所示,红线相连的点共同组成Pareto前沿,或者说Pareto最优解集,这些解没有被其他解所支配,可以认为这些解就是这个汽车的最优解。
    在这里插入图片描述
    在存在多个Pareto最优解的情况下,如果没有关于问题的更多的信息,那么很难选择哪个解更可取,因此所有的Pareto最优解都可以被认为是同等重要的。由此可知,对于多目标优化问题,最重要的任务是找到尽可能多的关于该优化问题的Pareto最优解。因而,在多目标优化中主要完成以下两个任务:

    • 找到一组尽可能接近Pareto最优域的解。
    • 找到一组尽可能不同的解。

    第一个要求算法要保证可靠的收敛性,第二个要求算法保证充足的多样性。即要求能够得到尽可能均匀分布的pareto最优解集,然后根据不同的设计要求和意愿,从中选择最满意的设计结果。

    三、介绍

    NSGA-II是带精英策略的非支配排序的遗传算法,属于遗传算法的一种改进算法,所以,最好先弄懂遗传算法是什么,不然理解NSGA-II会比较吃力。

    NSGA-II是NSGA算法的改进,主要改进了以下三个问题:

    1. 提出了快速非支配排序算法,一方面降低了计算的复杂度,另一方面它将父代种群跟子代种群进行合并,使得下一代的种群从双倍的空间中进行选取,从而保留了最为优秀的所有个体;
    2. 引进精英策略,保证某些优良的种群个体在进化过程中不会被丢弃,从而提高了优化结果的精度;
    3. 采用拥挤度和拥挤度比较算子,不但克服了NSGA中需要人为指定共享参数的缺陷,而且将其作为种群中个体间的比较标准,使得准Pareto域中的个体能均匀地扩展到整个Pareto域,保证了种群的多样性。

    论文:《A fast and elitist multiobjective genetic algorithm: NSGA-II》

    四、关键步骤

    1、快速非支配排序

    多目标优化问题的设计关键在于求取Pareto最优解集。NSGA-II算法中的快速非支配排序是依据个体的非劣解水平对种群分层,其作用是指引搜索向Pareto最优解集方向进行。

    在NSGA-II算法中,对于每个解,需要计算两个实体:

    1. 支配计数 N p {N_p} Np。即支配该解的所有解的数量。
    2. 支配解集合 S p {S_p} Sp。即该解支配的解的集合。

    显然,第一层非支配前沿中的所有解的支配计数 N p {N_p} Np都为零。对于每一个 N p = 0 {N_p} = 0 Np=0的解,访问该解集合中的每个成员解,并将成员解的支配计数减一。如果任何成员的支配计数 N p {N_p} Np变为零,将其放在一个单独的列表中。这些单独列表中的成员解属于第二层非支配前沿。重复该过程并确定第三层、第四层非支配前沿,直到所有前沿都确定下来。

    对于第二层或者更高层的非支配前沿的每一个解 p p p,其支配计数 N p {N_p} Np在减为0之前,最大值可以为 N − 1 N - 1 N1。对于这样的解,会被分配到一个无支配的集合并且不会再被访问到,可以理解为这个解没有支配其他解,属于“最底层”。因为最多有 N − 1 N - 1 N1个这样的解,总的时间复杂度为,因此, O ( M N 2 ) O\left( {M{N^2}} \right) O(MN2)整个过程的时间复杂度是有限的。注意,虽然时间复杂度降到了 O ( M N 2 ) O\left( {M{N^2}} \right) O(MN2),但空间复杂度提升到了 O ( N 2 ) O\left( {{N^2}} \right) O(N2)

    例如
    在这里插入图片描述

    如图所示,假设工资Salary和身高Height越大越好,那么,很显然,

    A A A的支配计数 N A = 0 {N_A} = 0 NA=0,支配解集合 S A = { C , D } {S_A} = \{ C,D\} SA={C,D}

    B B B的支配计数 N B = 0 {N_B} = 0 NB=0,支配解集合 S B = { C , D } {S_B} = \{ C,D\} SB={C,D}

    C C C的支配计数 N C = 2 {N_C} = 2 NC=2,支配解集合 S C = { D } {S_C} = \{ D\} SC={D}

    D D D的支配计数 N D = 3 {N_D} = 3 ND=3,支配解集合 S D = { } {S_D} = \{ \} SD={}

    根据排序过程, A A A B B B会被分配在第一层非支配前沿, C C C是第二层非支配前沿,而 D D D是第三层非支配前沿,属于“最底层”。

    排序过程伪代码

    //快速非支配排序伪代码
    for each p in P{
    	Sp = {}
    	np = 0
        for each q in P{
            if (p < q){			//如果p支配q	
                Sp = Sp U {q}	//将q添加到p的支配解集合中
            }else if (q < p){	//否则如果q支配p
                np = np + 1		//p的支配计数加一
            }
        }//for
    	if np == 0{				//p属于第一层非支配前沿
            P_rank = 1
            F1 = F1 U {p}
        }//if
    }//for
    
    i=1							//初始化前沿计数器
    while (Fi != {}){
        Q = {}					//用来存储下一个前沿的成员
        for each p in Fi{
            for each q in Sp{
                nq = nq - 1
                if (nq == 0){	//q属于下一层前沿
                    q_rank = i+1
                    Q = Q U {q}
                }
            }
        }
        i++
        Fi = Q
    }
    

    2、个体拥挤距离

    NSGA算法使用了共享函数方法,通过适当设置相关参数,该方法可以维持种群的多样性。这个参数与选择计算两个个体之间的接近度的距离指标有关。但存在两个难题:

    1. 共享函数法在保持解分布方面的性能在很大程度上取决于所选的值。
    2. 由于每个解决方案必须与群体中的所有其他解决方案进行比较,共享函数方法的整体复杂性是 O ( N 2 ) O\left( {{N^2}} \right) O(N2)

    而NSGA-II将共享函数方法替换为拥挤比较方法,在一定程度上消除了上述两个困难。新方法不需要任何用户定义的参数来维持群体成员之间的多样性。此外,该方法具有更好的计算复杂度。为了描述这种方法,NSGA-II定义了拥挤度,然后给出了拥挤比较算子。

    2.1、拥挤距离

    为了估计个体中某个特定解周围的解密度,我们计算该点两侧沿每个目标的两个点的平均距离。这个数量作为使用最近邻点作为顶点形成的长方体周长的估计值,称为拥挤距离。

    拥挤距离计算需要根据每个目标函数值按数值大小对种群中个体进行排序。对于每个目标函数,边界解(具有最小和最大函数值的解)被分配一个无限距离值。所有其他中间解都指定了一个距离值,该距离值等于两个相邻解的函数值的绝对归一化差。这种计算在其他目标函数中继续进行,总的拥挤距离为对应于每个目标的拥挤距离的之和。

    具体算法如下:

    • 初始时,令 i d i s t a n c e = 0 {i_{distance}} = 0 idistance=0 n ∈ { 1 , 2.... , N } n \in \{ 1,2....,N\} n{1,2....,N}

    • for 每个目标函数 f m {f_m} fm

      • 根据该目标函数对该等级的个体进行排序,记 f m max ⁡ f_m^{\max } fmmax为个体目标函数值的最大值, f m min ⁡ f_m^{\min } fmmin为个体目标函数值的最小值;
      • 设置排序后两个边界的拥挤距离 1 d i s t a n c e = ∞ {1_{distance}} = \infty 1distance= N d i s t a n c e = ∞ {N_{distance}} = \infty Ndistance=
      • 计算 i d i s t a n c e = i d i s t a n c e + ∣ f m ( i + 1 ) − f m ( i − 1 ) ∣ f m max ⁡ − f m min ⁡ {i_{distance}} = {i_{distance}} + \frac{{\left| {{f_m}\left( {i + 1} \right) - {f_m}\left( {i - 1} \right)} \right|}}{{f_m^{\max } - f_m^{\min }}} idistance=idistance+fmmaxfmminfm(i+1)fm(i1) f m ( i ) {f_m}\left( i \right) fm(i)表示第 i i i个体第 m m m个目标函数值。(这一步是将每个目标函数下的拥挤距离相加)

    对于二目标优化问题,这个拥挤距离就类似于是该个体在目标空间能生成的最大矩形的两个边长之和,如下图所示、

    2.2、拥挤比较算子

    拥挤比较算子引导算法的选择过程向均匀分布的帕累托最优前沿前进。根据之前的计算,种群中的每个个体都会有两个属性:

    1. 非支配排序决定的非支配序 i r a n k {i_{rank}} irank ,即第 r a n k rank rank层非支配前沿。
    2. 拥挤距离 i d i s t a n c e {i_{distance}} idistance

    根据这两个属性定义出拥挤比较算子,将“ ≺ \prec ”定义为:

    i ≺ j , i f i r a n k < j r a n k O R ( i r a n k = = j r a n k A N D i d i s tan ⁡ c e > j d i s tan ⁡ c e ) i \prec j,\quad if \quad {i_{rank}} < {j_{rank}} \quad OR\quad ({i_{rank}} = = {j_{rank}}\quad AND\quad {i_{dis\tan ce}} > {j_{dis\tan ce}}) ij,ifirank<jrankOR(irank==jrankANDidistance>jdistance)

    注: ≺ \prec 可以理解为优于, i ≺ j i \prec j ij表示 i i i优于 j j j

    3、精英策略选择

    精英策略即保留父代中的优良个体直接进入子代,以防止获得的Pareto最优解丢失。精英策略选择算子首先先将父代 C i {C_i} Ci和子代 D i {D_i} Di合并为种群 R i {R_i} Ri(显然, R i {R_i} Ri的种群大小是 2 N 2N 2N),然后对 R i {R_i} Ri进行非支配排序,再进行优选,以组成新父代种群 C i + 1 {C_{i + 1}} Ci+1

    具体算法如下:

    1. 根据Pareto等级从低到高的顺序(即先第一层,然后第二层…),将整层种群放入新的种群 C i + 1 {C_{i + 1}} Ci+1,直到某一层出现该层个体不能全部放入种群 C i + 1 {C_{i + 1}} Ci+1的情况;
    2. 将该层个体根据拥挤距离从大到小排列,依次放入种群 C i + 1 {C_{i + 1}} Ci+1中,直到种群 C i + 1 {C_{i + 1}} Ci+1中填满 N N N个个体。

    如下图所示。

    五、参考

    1. Deb K , Pratap A , Agarwal S , et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
    2. NSGA-II解决多目标优化问题
    3. 多目标优化算法(一)NSGA-Ⅱ(NSGA2)
    展开全文
  • 多目标优化系列: MOP_1. 多目标优化的相关基本概念 MOP_2. 非支配排序遗传算法 —(NSGA、...1995年,Srinivas和Deb提出了非支配排序遗传算法(Non-dominatedSorting Genetic Algorithms,NSGA)。这是一种基于P...
  • 多目标优化中的非支配排序算法

    千次阅读 2021-11-14 10:11:04
    多目标优化中的非支配排序算法 以NSGA-II为例 多目标优化指的是针对多个目标函数,去寻找一组最优解,形式如下: 其中*fi(x)*是各单一的目标函数 但是多目标优化问题通常面临多个目标函数无法同时达到最优,为了解决...
  • 摘要:多目标优化问题一直是科学和工程研究领域的难题和热点问题...本文研究的非支配排序遗传算法(Non-dominated Sorting Genetic Algorithm,NSGA)及其改进算法NSGA-Ⅱ就是其中发展较快,优化效果较好的一种方法.本文...
  • 基于NSGA-II的卫星星座设计,含全套代码
  • nsga2非支配排序遗传算法,c++源码实现
  • 经典非支配排序详解(原理+举例说明),后续进行代码实现。
  • 快速非支配排序

    千次阅读 2015-03-12 20:41:00
    该算法需要计算种群P中每个个体i的两个参数ni(种群中支配个体i的个体数目)和si(种群中被个体i支配的个体集合)。 1、找出种群中所有ni=0的个体,保存在集合F1中(也就是第一层)。 2、对F1中的每个个体i,其所...
  • 多目标优化NSGA-II(非支配排序常见于遗传算法)[1] 多目标遗传优化算法NSGAII求解微电网调度(Python&Matlab) 2案例 本次我们以ZDT1函数为例. 3C语言代码实现 //======头文件======= #...
  • 一、获取代码方式 获取代码方式1: 完整代码已上传我的资源:【优化算法】非支配排序遗传算法(NSGA)【含Matlab源码 176期】 获取代码方式2: 通过订阅紫极神光博客付费专栏,凭支付凭证,私信博主,可获得此代码。...
  • 非支配排序算法NSGA-Ⅱ(Matlab)

    千次阅读 2020-04-28 20:18:17
    end end %快速非支配排序和拥挤度计算代码 %%对初始种群开始排序 快速非支配排序 %%使用非支配排序对种群进行排序,该函数返回每个个体对应的排序值和拥挤距离,是一个两列矩阵 %%并将排序值和拥挤距离添加到染色体...
  • 基于非支配排序遗传算法处理多目标优化的matlab例程,可以自行修改
  • 3非支配排序常见于遗传算法 3.1 解决的问题及三大特点 3.2数学模型 3.3 Pareto 最优解 1 兴趣引入 (1)在生活中,你想买一辆车,又想汽车的性能好,外观不错,价格还比较低,对于这同时满足这三个条件,我们...

空空如也

空空如也

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

快速非支配排序

友情链接: password.rar