一、获取代码方式

获取代码方式1：
完整代码已上传我的资源：【优化算法】非支配排序遗传算法（NSGA）【含Matlab源码 176期】

获取代码方式2：
通过订阅紫极神光博客付费专栏，凭支付凭证，私信博主，可获得此代码。

备注：
订阅紫极神光博客付费专栏，可免费获得1份代码（有效期为订阅日起，三天内有效）；

二、遗传算法简介

非支配排序遗传算法NSGA(Non-dominated So rng Genetic Algor thms) 是由Srinivas和Deb于1995年提出的”。这是一种基于Pareto最优概念的遗传算法， 它是众多的多目标优化遗传算法中体现God beg思想最直接的方法。该算法就是在基本遗传算法的基础上，对选择再生方法进行改进：将每个个体按照它们的支配与非支配关系进行分层，再做选择操作，从而使得该算法在多目标优化方面得到非常满意的结果。Z it z ler与Thiele等191曾对NSGA、NPG A、VEGA， 与Haj ela和Lin的加权向量算法以及纯随机搜索算法，作了系统的定量实验比较。通过采用多背包问题扩展形式的九种不同规模设置作为数值型多目标测试问题，经过全面的比较分析， 得到比较结果：NSGA的性能最优， 其次是VEGA， 而NPG A与Haj ela和Lin的加权向量算法的全部实验结果不分上下例。虽然这种比较结果不能无限制
的外推， 但是它在一定程度上说明了NSGA具有一定的优越性。因此， 对该算法进行理论研究和应用研究具有十分重要的意义。

虽然NSGA与其它多目标优化遗传算法比较具有一定的优越性：优化目标个数任选，非劣最优解分布均匀，并允许存在多个不同的等价解。但它仍存在一些问题(例：a)计算复杂度较高，当种群较大时，计算相当耗时；b)没有精英策略，精英策略可以加速算法的执行速度，而且也能在一定程度上确保已经找到的满意解不被丢失； c) 需要指定共享半径o， hare·

三、部分源代码

function NSGAII()
clc;
% format compact;
tic;
% hold on

%--初始化 参数设定
generations=100;        %迭代次数
popnum=100;             %种群大小（偶数）
poplength=30;           %个体长度
minvalue=repmat(zeros(1,poplength),popnum,1);   %个体最小值---B = repmat(A, m, n) %将矩阵A复制m*n块，即B由m*n块A平铺而成
maxvalue=repmat(ones(1,poplength),popnum,1);    %个体最大值
population=rand(popnum,poplength).*(maxvalue-minvalue)+minvalue;    %产生新的初始种群

    %--开始迭代进化
    for gene=1:generations      %开始迭代

        %--交叉
        newpopulation=zeros(popnum,poplength);  %子代种群
        for i=1:popnum/2                        %交叉产生子代
            k=randperm(popnum);                 %从种群中随机选择出两个父母，不采用二进制联赛方法
            beta=(-1).^round(rand(1,poplength)).*abs(randn(1,poplength))*1.481;     %采用正态分布交叉产生两个子代
            newpopulation(i*2-1,:)=(population(k(1),:)+population(k(2),:))/2+beta.*(population(k(1),:)-population(k(2),:))./2;  %产生第一个子代
            newpopulation(i*2,:)=(population(k(1),:)+population(k(2),:))/2-beta.*(population(k(1),:)-population(k(2),:))./2;    %产生第二个子代
        end
        %--变异
       
        newpopulation(temp)=newpopulation(temp)+(maxvalue(temp)-minvalue(temp)).*((2.*miu(temp)+(1-2.*miu(temp)).*(1-(newpopulation(temp)-minvalue(temp))./(maxvalue(temp)-minvalue(temp))).^21).^(1/21)-1);        %变异情况一
        newpopulation(temp)=newpopulation(temp)+(maxvalue(temp)-minvalue(temp)).*(1-(2.*(1-miu(temp))+2.*(miu(temp)-0.5).*(1-(maxvalue(temp)-newpopulation(temp))./(maxvalue(temp)-minvalue(temp))).^21).^(1/21));  %变异情况二

        %--越界处理/种群合并
        newpopulation(newpopulation>maxvalue)=maxvalue(newpopulation>maxvalue); %子代越上界处理
        newpopulation(newpopulation<minvalue)=minvalue(newpopulation<minvalue); %子代越下界处理
      

        %--计算目标函数值
        functionvalue=zeros(size(newpopulation,1),2);   %合并后种群的各目标函数值，这里问题是ZDT1
        functionvalue(:,1)=newpopulation(:,1);   %计算第一维目标函数值
        g=1+9*sum(newpopulation(:,2:poplength),2)./(poplength-1);
        functionvalue(:,2)=g.*(1-(newpopulation(:,1)./g).^0.5); %计算第二维目标函数值

        %--非支配排序
        fnum=0;     %当前分配的前沿面编号
        cz=false(1,size(functionvalue,1));      %记录个体是否已被分配编号
        frontvalue=zeros(size(cz));             %每个个体的前沿面编号
        [functionvalue_sorted,newsite]=sortrows(functionvalue); %对种群按第一维目标值大小进行排序 则第一行个体p即为种群中支配个体p的数量为零的个体，Np=0
        while ~all(cz)      %开始迭代判断每个个体的前沿面，采用改进的deductive sort
            fnum=fnum+1;
            d=cz;
            
                if ~d(i)
                    for j=i+1:size(functionvalue,1) %判断i对应的所有集合里面的支配和非支配的解，被i支配则为1，不被i支配则为0
                        if ~d(j)
                            k=1;
                            for m=2:size(functionvalue,2) %判断是否支配，找到个体p不支配的个体，标记为k=0
                                if functionvalue_sorted(i,m)>functionvalue_sorted(j,m) %判断i,j是否支配，如果成立i,j互不支配
                                    k=0; %i,j互不支配
                                    break;
                                end
                            end
                            if k
                                d(j)=true;  %那么p所支配的个体k=1并记录在d里，则后面该个体已被支配就不能在这一层里进行判断
                            end
                        end
                    end
                    frontvalue(newsite(i))=fnum; %实际位置的非支配层赋值
                    cz(i)=true;
                end
            end
        end

        %--计算拥挤距离/选择出下一代个体
       
        popu=find(frontvalue==fnum+1);   %popu记录第fnum+1个面上的个体编号
        distancevalue=zeros(size(popu));    %popu各个体的拥挤距离
        fmax=max(functionvalue(popu,:),[],1);   %popu每维上的最大值
        fmin=min(functionvalue(popu,:),[],1);   %popu每维上的最小值
        for i=1:size(functionvalue,2)   %分目标计算每个目标上popu各个体的拥挤距离
            [~,newsite]=sortrows(functionvalue(popu,i)); %popu里对第一维排序之后的位置
            distancevalue(newsite(1))=inf;
            distancevalue(newsite(end))=inf;
            for j=2:length(popu)-1
                distancevalue(newsite(j))=distancevalue(newsite(j))+(functionvalue(popu(newsite(j+1)),i)-functionvalue(popu(newsite(j-1)),i))/(fmax(i)-fmin(i)); %
            end
        end
        popu=-sortrows(-[distancevalue;popu]')';    %按拥挤距离降序排序第fnum+1个面上的个体
        population(newnum+1:popnum,:)=newpopulation(popu(2,1:popnum-newnum),:); %将第fnum+1个面上拥挤距离较大的前popnum-newnum个个体复制入下一代
    end

%--程序输出
fprintf('已完成，耗时%4s秒\n',num2str(toc));    %程序最终耗时
output=sortrows(functionvalue(frontvalue==1,:));    %最终结果：种群中非支配解的函数值
plot(output(:,1),output(:,2),'*b');             %作图
axis([0,1,0,1]);
xlabel('F_1');
ylabel('F_2');
title('ZDT1');

四、运行结果

五、matlab版本及参考文献

1 matlab版本
2014a

2 参考文献
[1]包子阳 ,余继周,杨杉.智能优化算法及其MATLAB实例（第2版）[J].电子工业出版社
[2]高媛.非支配排序遗传算法（NSGA）的研究与应用[D].浙江大学

• 【多目标优化】1. 多目标优化的相关基本概念
• 【多目标优化】2. 非支配排序遗传算法 —（NSGA、NSGA-II)
• 【多目标优化】3. 基于分解的多目标进化算法 —（MOEAD)

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

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

(1) 基本原理

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

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

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

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

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

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

(2) 算法流程

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

(3) 算法缺陷

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

a) 计算复杂度较高，为(m为目标函数个数，N为种群大小)，所以当种群较大时，计算相当耗时。

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

c) 需要指定共享半径。

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

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

a) 提出了快速非支配排序法，降低了算法的计算复杂度。由原来的降到，其中，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 作上述分级操作并赋予相应的非支配序，直到所有的个体都被分级。其计算复杂度为，m为目标函数个数，N为种群大小。（按照1）、2）的方法完成所有分级）

确定拥挤度：

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

如图所示：

拥挤度比较算子: 

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

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

(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),))，取前个个体，使 P(t+1) 个体数量达到N。然后通过遗传算子(选择、交叉、变异)产生新的子代种群 Q(t+1)。

算法的整体复杂性为，由算法的非支配排序部分决定。

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

NSGA-Ⅱ的matlab程序下载：

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

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

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

参考文献：

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

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