多目标优化算法（一）NSGA-Ⅱ（NSGA2）[通俗易懂]

全栈程序员站长

发布于 2022-07-21 14:19:44

6.3K0

发布于 2022-07-21 14:19:44

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

多目标优化算法（一）NSGA-Ⅱ(NSGA2)

注：没有想到这篇博客竟然有很多人查看，这是我去年写的算法，里面难免会有一些错误，大家可以看看评论区，这里的matlab代码写的不太好，是以C语言思维写的，基本上没有并行，初学者建议可以看看platEMO上的源代码，提前培养好写代码的习惯！

0. 前言

这个算法是本人接触科研学习实现的第一个算法，因此想在这里和大家分享一下心得。

1. 算法简介

NSGA-Ⅱ算法，即带有精英保留策略的快速非支配多目标优化算法，是一种基于Pareto最优解的多目标优化算法。

1.1 Pareto支配关系以及Pareto等级

Pareto支配关系：对于最小化多目标优化问题，对于n个目标分量 f i ( x ) , i = 1… n f_i(x), i=1…n fi(x),i=1...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 \forall i \in {1,2,…,n} ∀i∈1,2,...,n，都有 f i ( X a ) ≤ f i ( X b ) f_i(X_a) \leq f_i(X_b) fi(Xa)≤fi(Xb)成立。 2. ∃ i ∈ 1 , 2 , . . . , n \exists i \in {1,2,…,n} ∃i∈1,2,...,n，使得 f i ( X a ) < f i ( X b ) f_i(X_a) <f_i(X_b) fi(Xa)<fi(Xb)成立。如果对于一个决策变量，不存在其他决策变量能够支配他，那么就称该决策变量为非支配解。 Pareto等级：在一组解中，非支配解Pareto等级定义为1，将非支配解从解的集合中删除，剩下解的Pareto等级定义为2，依次类推，可以得到该解集合中所有解的Pareto等级。示意图如图1所示。

1.2 快速非支配排序

假设种群大小为P，该算法需要计算每个个体p的被支配个数 n p n_p np和该个体支配的解的集合 S p S_p Sp这两个参数。遍历整个种群，该参数的计算复杂度为 O ( m N 2 ) O(mN^2) O(mN2)。该算法的伪代码如下： 1.计算出种群中每个个体的两个参数 n p n_p np和 S p S_p Sp。 2.将种群中参数 n p = 0 n_p=0 np=0的个体放入集合 F 1 F_1 F1中。 3.for 个体 i ∈ F 1 i \in F_1 i∈F1: for 个体 l ∈ S i l \in S_i l∈Si： n l = n l − 1 n_l=n_l-1 nl=nl−1；(该步骤即消除Pareto等级1对其余个体的支配，相当于将Pareto等级1的个体从集合中删除) if n l = 0 n_l=0 nl=0：将个体l加入集合 F 2 F_2 F2中。 end end end 4.上面得到Pareto等级2的个体的集合 F 2 F_2 F2，对集合 F 2 F_2 F2中的个体继续重复步骤3，依次类推直到种群等级被全部划分。 matlab 代码如下：

function [F,chromo] = non_domination_sort( pop,chromo,f_num,x_num )
%non_domination_sort 初始种群的非支配排序和计算拥挤度
%初始化pareto等级为1
pareto_rank=1;
F(pareto_rank).ss=[];%pareto等级为pareto_rank的集合
p=[];%每个个体p的集合
for i=1:pop
    %%%计算出种群中每个个体p的被支配个数n和该个体支配的解的集合s
    p(i).n=0;%被支配个体数目n
    p(i).s=[];%支配解的集合s
    for j=1:pop
        less=0;%y'的目标函数值小于个体的目标函数值数目
        equal=0;%y'的目标函数值等于个体的目标函数值数目
        greater=0;%y'的目标函数值大于个体的目标函数值数目
        for k=1:f_num
            if(chromo(i,x_num+k)<chromo(j,x_num+k))
                less=less+1;
            elseif(chromo(i,x_num+k)==chromo(j,x_num+k))
                equal=equal+1;
            else
                greater=greater+1;
            end
        end
        if(less==0 && equal~=f_num)%if(less==0 && greater~=0)
            p(i).n=p(i).n+1;%被支配个体数目n+1
        elseif(greater==0 && equal~=f_num)%elseif(greater==0 && less~=0)
            p(i).s=[p(i).s j];
        end
    end
    %%%将种群中参数为n的个体放入集合F(1)中
    if(p(i).n==0)
        chromo(i,f_num+x_num+1)=1;%储存个体的等级信息
        F(pareto_rank).ss=[F(pareto_rank).ss i];
    end
end
%%%求pareto等级为pareto_rank+1的个体
while ~isempty(F(pareto_rank).ss)
    temp=[];
    for i=1:length(F(pareto_rank).ss)
        if ~isempty(p(F(pareto_rank).ss(i)).s)
            for j=1:length(p(F(pareto_rank).ss(i)).s)
                p(p(F(pareto_rank).ss(i)).s(j)).n=p(p(F(pareto_rank).ss(i)).s(j)).n - 1;%nl=nl-1
                if p(p(F(pareto_rank).ss(i)).s(j)).n==0
                    chromo(p(F(pareto_rank).ss(i)).s(j),f_num+x_num+1)=pareto_rank+1;%储存个体的等级信息
                    temp=[temp p(F(pareto_rank).ss(i)).s(j)];
                end
            end
        end
    end
    pareto_rank=pareto_rank+1;
    F(pareto_rank).ss=temp;
end

1.3 拥挤度

为了使得到的解在目标空间中更加均匀，这里引入了拥挤度 n d n_d nd，其算法如下：

令参数 n d = 0 ， n ∈ 1 … N n_d=0，n∈1…N nd=0，n∈1…N。
for 每个目标函数 f m f_m fm ： ① 根据该目标函数对该等级的个体进行排序，记 f m m a x f_m^{max} fmmax为个体目标函数值 f m f_m fm的最大值， f m m i n f_m^{min} fmmin为个体目标函数值 f m f_m fm的最小值； ② 对于排序后两个边界的拥挤度 1 d 1_d 1d和 N d N_d Nd置为∞； ③ 计算 n d = n d + ( f m ( i + 1 ) − f m ( i − 1 ) ) / ( f m m a x − f m m i n ) n_d=n_d+(f_m (i+1)-f_m (i-1))/(f_m^{max}-f_m^{min}) nd=nd+(fm(i+1)−fm(i−1))/(fmmax−fmmin),其中 f m ( i + 1 ) f_m (i+1) fm(i+1)是该个体排序后后一位的目标函数值。

end

从二目标优化问题来看，就像是该个体在目标空间所能生成的最大的矩形（该矩形不能触碰目标空间其他的点）的边长之和。拥挤度示意图如图2所示。

matlab代码如下：

function chromo = crowding_distance_sort( F,chromo,f_num,x_num )
%计算拥挤度
%%%按照pareto等级对种群中的个体进行排序
[~,index]=sort(chromo(:,f_num+x_num+1));
[~,mm1]=size(chromo);
temp=zeros(length(index),mm1);
for i=1:length(index)%=pop
    temp(i,:)=chromo(index(i),:);%按照pareto等级排序后种群
end

%%%对于每个等级的个体开始计算拥挤度
current_index = 0;
for pareto_rank=1:(length(F)-1)%计算F的循环时多了一次空，所以减掉
    %%拥挤度初始化为0
    nd=[];
    nd(:,1)=zeros(length(F(pareto_rank).ss),1);
    %y=[];%储存当前处理的等级的个体
    [~,mm2]=size(temp);
    y=zeros(length(F(pareto_rank).ss),mm2);%储存当前处理的等级的个体
    previous_index=current_index + 1;
    for i=1:length(F(pareto_rank).ss)
        y(i,:)=temp(current_index + i,:);
    end
    current_index=current_index + i;
    %%对于每一个目标函数fm
    for i=1:f_num
        %%根据该目标函数值对该等级的个体进行排序
        [~,index_objective]=sort(y(:,x_num+i));
        %objective_sort=[];%通过目标函数排序后的个体
        [~,mm3]=size(y);
        objective_sort=zeros(length(index_objective),mm3);%通过目标函数排序后的个体
        for j=1:length(index_objective)
            objective_sort(j,:)=y(index_objective(j),:);
        end
        %%记fmax为最大值，fmin为最小值
        fmin=objective_sort(1,x_num+i);
        fmax=objective_sort(length(index_objective),x_num+i);
        %%对排序后的两个边界拥挤度设为1d和nd设为无穷
        y(index_objective(1),f_num+x_num+1+i)=Inf;
        y(index_objective(length(index_objective)),f_num+x_num+1+i)=Inf;
        %%计算nd=nd+(fm(i+1)-fm(i-1))/(fmax-fmin)
        for j=2:(length(index_objective)-1)
            pre_f=objective_sort(j-1,x_num+i);
            next_f=objective_sort(j+1,x_num+i);
            if (fmax-fmin==0)
                y(index_objective(j),f_num+x_num+1+i)=Inf;
            else
                y(index_objective(j),f_num+x_num+1+i)=(next_f-pre_f)/(fmax-fmin);
            end
        end
    end
    %多个目标函数拥挤度求和
    for i=1:f_num
        nd(:,1)=nd(:,1)+y(:,f_num+x_num+1+i);
    end
    %第2列保存拥挤度，其他的覆盖掉
    y(:,f_num+x_num+2)=nd;
    y=y(:,1:(f_num+x_num+2));
    temp_two(previous_index:current_index,:) = y;
end
chromo=temp_two;
end

1.4 精英保留策略

1.首先将父代种群 C i C_i Ci和子代种群 D i D_i Di合成种群 R i R_i Ri。 2.根据以下规则从种群 R i R_i Ri生成新的父代种群 C i + 1 C_{i+1} Ci+1： ①根据Pareto等级从低到高的顺序，将整层种群放入父代种群 C i + 1 C_{i+1} Ci+1，直到某一层该层个体不能全部放入父代种群 C i + 1 C_{i+1} Ci+1； ②将该层个体根据拥挤度从大到小排列，依次放入父代种群 C i + 1 C_{i+1} Ci+1中，直到父代种群 C i + 1 C_{i+1} Ci+1填满。 matlab代码如下：

function chromo = elitism( pop,combine_chromo2,f_num,x_num )
%精英保留策略
[pop2,temp]=size(combine_chromo2);
chromo_rank=zeros(pop2,temp);
chromo=zeros(pop,(f_num+x_num+2));
%根据pareto等级从高到低进行排序
[~,index_rank]=sort(combine_chromo2(:,f_num+x_num+1));
for i=1:pop2
    chromo_rank(i,:)=combine_chromo2(index_rank(i),:);
end
%求出最高的pareto等级
max_rank=max(combine_chromo2(:,f_num+x_num+1));
%根据排序后的顺序，将等级相同的种群整个放入父代种群中，直到某一层不能全部放下为止
prev_index=0;
for i=1:max_rank
    %寻找当前等级i个体里的最大索引
    current_index=max(find(chromo_rank(:,(f_num+x_num+1))==i));
    %不能放下为止
    if(current_index>pop)
        %剩余群体数
        remain_pop=pop-prev_index;
        %等级为i的个体
        temp=chromo_rank(((prev_index+1):current_index),:);
        %根据拥挤度从大到小排序
        [~,index_crowd]=sort(temp(:,(f_num+x_num+2)),'descend');
        %填满父代
        for j=1:remain_pop
            chromo(prev_index+j,:)=temp(index_crowd(j),:);
        end
        return;
    elseif(current_index<pop)
        % 将所有等级为i的个体直接放入父代种群
        chromo(((prev_index+1):current_index),:)=chromo_rank(((prev_index+1):current_index),:);
    else
        % 将所有等级为i的个体直接放入父代种群
        chromo(((prev_index+1):current_index),:)=chromo_rank(((prev_index+1):current_index),:);
        return;
    end
    prev_index = current_index;
end
end

1.5 实数编码的交叉操作（SBX）

模拟二进制交叉： x 1 j ( t ) = 0.5 × [ ( 1 + γ j ) x 1 j ( t ) + ( 1 − γ j ) x 2 j ( t ) ] x _{1j}(t)=0.5×[(1+γ_j ) x_{1j}(t)+(1-γ_j ) x_{2j} (t)] x1j(t)=0.5×[(1+γj)x1j(t)+(1−γj)x2j(t)] x 2 j ( t ) = 0.5 × [ ( 1 − γ j ) x 1 j ( t ) + ( 1 + γ j ) x 2 j ( t ) ] x _{2j} (t)=0.5×[(1-γ_j ) x_{1j}(t)+(1+γ_j ) x_{2j}(t)] x2j(t)=0.5×[(1−γj)x1j(t)+(1+γj)x2j(t)] 其中 γ j = { ( 2 u j ) 1 / ( η + 1 ) u j < 0.5 ( 1 / ( 2 ( 1 − u j ) ) 1 / ( η + 1 ) e l s e γ_j=\left\{\begin{matrix}(2u_j)^{1/(η+1)}\;\;\;\;\;\;\;\;\;\;\;\;u_j<0.5 \\ (1/(2(1-u_j))^{1/(η+1)}\;\;\;\;else \end{matrix}\right. γj={ (2uj)1/(η+1)uj<0.5(1/(2(1−uj))1/(η+1)else

1.6 多项式变异（polynomial mutation）

多项式变异： x 1 j ( t ) = x 1 j ( t ) + ∆ j x _{1j} (t)=x_{1j} (t)+∆_j x1j(t)=x1j(t)+∆j 其中 ∆ j = { ( 2 u j ) 1 / ( η + 1 ) − 1 u j < 0.5 ( 1 − ( 2 ( 1 − u j ) ) 1 / ( η + 1 ) e l s e ∆_j=\left\{\begin{matrix}(2u_j)^{1/(η+1)}-1\;\;\;\;\;\;\;\;\;\;\;\;u_j<0.5 \\ (1-(2(1-u_j))^{1/(η+1)}\;\;\;\;else \end{matrix}\right. ∆j={ (2uj)1/(η+1)−1uj<0.5(1−(2(1−uj))1/(η+1)else 并且0≤ u j u_j uj≤1。 matlab代码如下：

function chromo_offspring = cross_mutation( chromo_parent,f_num,x_num,x_min,x_max,pc,pm,yita1,yita2,fun )
%模拟二进制交叉与多项式变异
[pop,~]=size(chromo_parent);
suoyin=1;
for i=1:pop
   %%%模拟二进制交叉
   %初始化子代种群
   %随机选取两个父代个体
   parent_1=round(pop*rand(1));
   if (parent_1<1)
       parent_1=1;
   end
   parent_2=round(pop*rand(1));
   if (parent_2<1)
       parent_2=1;
   end
   %确定两个父代个体不是同一个
   while isequal(chromo_parent(parent_1,:),chromo_parent(parent_2,:))
       parent_2=round(pop*rand(1));
       if(parent_2<1)
           parent_2=1;
       end
   end
   chromo_parent_1=chromo_parent(parent_1,:);
   chromo_parent_2=chromo_parent(parent_2,:);
   off_1=chromo_parent_1;
   off_2=chromo_parent_1;
   if(rand(1)<pc)
       %进行模拟二进制交叉
       u1=zeros(1,x_num);
       gama=zeros(1,x_num);
       for j=1:x_num
           u1(j)=rand(1);
           if u1(j)<0.5
               gama(j)=(2*u1(j))^(1/(yita1+1));
           else
               gama(j)=(1/(2*(1-u1(j))))^(1/(yita1+1));
           end
           off_1(j)=0.5*((1+gama(j))*chromo_parent_1(j)+(1-gama(j))*chromo_parent_2(j));
           off_2(j)=0.5*((1-gama(j))*chromo_parent_1(j)+(1+gama(j))*chromo_parent_2(j));
           %使子代在定义域内
           if(off_1(j)>x_max(j))
               off_1(j)=x_max(j);
           elseif(off_1(j)<x_min(j))
               off_1(j)=x_min(j);
           end
           if(off_2(j)>x_max(j))
               off_2(j)=x_max(j);
           elseif(off_2(j)<x_min(j))
               off_2(j)=x_min(j);
           end
       end
       %计算子代个体的目标函数值
       off_1(1,(x_num+1):(x_num+f_num))=object_fun(off_1,f_num,x_num,fun);
       off_2(1,(x_num+1):(x_num+f_num))=object_fun(off_2,f_num,x_num,fun);
   end
   %%%多项式变异
   if(rand(1)<pm)
       u2=zeros(1,x_num);
       delta=zeros(1,x_num);
       for j=1:x_num
           u2(j)=rand(1);
           if(u2(j)<0.5)
               delta(j)=(2*u2(j))^(1/(yita2+1))-1;
           else
               delta(j)=1-(2*(1-u2(j)))^(1/(yita2+1));
           end
           off_1(j)=off_1(j)+delta(j);
           %使子代在定义域内
           if(off_1(j)>x_max(j))
               off_1(j)=x_max(j);
           elseif(off_1(j)<x_min(j))
               off_1(j)=x_min(j);
           end
       end
       %计算子代个体的目标函数值
       off_1(1,(x_num+1):(x_num+f_num))=object_fun(off_1,f_num,x_num,fun);
   end
   if(rand(1)<pm)
       u2=zeros(1,x_num);
       delta=zeros(1,x_num);
       for j=1:x_num
           u2(j)=rand(1);
           if(u2(j)<0.5)
               delta(j)=(2*u2(j))^(1/(yita2+1))-1;
           else
               delta(j)=1-(2*(1-u2(j)))^(1/(yita2+1));
           end
           off_2(j)=off_2(j)+delta(j);
           %使子代在定义域内
           if(off_2(j)>x_max(j))
               off_2(j)=x_max(j);
           elseif(off_2(j)<x_min(j))
               off_2(j)=x_min(j);
           end
       end
       %计算子代个体的目标函数值
       off_2(1,(x_num+1):(x_num+f_num))=object_fun(off_2,f_num,x_num,fun);
   end
   off(suoyin,:)=off_1;
   off(suoyin+1,:)=off_2;
   suoyin=suoyin+2;
end
chromo_offspring=off;
end

1.7 竞标赛选择（tournament selection）

锦标赛法是选择操作的一种常用方法，二进制竞标赛用的最多。假设种群规模为N，该法的步骤为： 1.从这N个个体中随机选择k（k<n）个个体，k的取值小，效率就高（节省运行时间），但不宜太小，一般取为n/2（取整）。（二进制即取2） 2.根据每个个体的适应度值，选择其中适应度值最好的个体进入下一代种群。 3.重复1-2步，至得到新的N个个体。二进制选择的matlab代码如下：

function chromo_parent = tournament_selection( chromo )
%二进制竞标赛
[pop, suoyin] = size(chromo);
touranment=2;
a=round(pop/2);
chromo_candidate=zeros(touranment,1);
chromo_rank=zeros(touranment,1);
chromo_distance=zeros(touranment,1);
chromo_parent=zeros(a,suoyin);
% 获取等级的索引
rank = suoyin - 1;
% 获得拥挤度的索引
distance = suoyin;
for i=1:a
  for j=1:touranment
      chromo_candidate(j)=round(pop*rand(1));%随机产生候选者
      if(chromo_candidate(j)==0)%索引从1开始
          chromo_candidate(j)=1;
      end
      if(j>1)
          while (~isempty(find(chromo_candidate(1:j-1)==chromo_candidate(j))))
              chromo_candidate(j)=round(pop*rand(1));
              if(chromo_candidate(j)==0)%索引从1开始
                  chromo_candidate(j)=1;
              end
          end
      end
  end
  for j=1:touranment
      chromo_rank(j)=chromo(chromo_candidate(j),rank);
      chromo_distance(j)=chromo(chromo_candidate(j),distance);
  end
  %取出低等级的个体索引
  minchromo_candidate=find(chromo_rank==min(chromo_rank));
  %多个索引按拥挤度排序
  if (length(minchromo_candidate)~=1)
      maxchromo_candidate=find(chromo_distance(minchromo_candidate)==max(chromo_distance(minchromo_candidate)));
      if(length(maxchromo_candidate)~=1)
          maxchromo_candidate = maxchromo_candidate(1);
      end
      chromo_parent(i,:)=chromo(chromo_candidate(minchromo_candidate(maxchromo_candidate)),:);
  else
      chromo_parent(i,:)=chromo(chromo_candidate(minchromo_candidate(1)),:);
  end
end
end

2. 算法实现框图

NSGA-Ⅱ算法的基本思想为：首先，随机产生规模为N的初始种群，非支配排序后通过遗传算法的选择、交叉、变异三个基本操作得到第一代子代种群；其次，从第二代开始，将父代种群与子代种群合并，进行快速非支配排序，同时对每个非支配层中的个体进行拥挤度计算，根据非支配关系以及个体的拥挤度选取合适的个体组成新的父代种群；最后，通过遗传算法的基本操作产生新的子代种群：依此类推，直到满足程序结束的条件。该算法的流程图如图3所示。

初始化matlab代码如下：

function chromo = initialize( pop,f_num,x_num,x_min,x_max,fun )
%   种群初始化
for i=1:pop
   for j=1:x_num
       chromo(i,j)=x_min(j)+(x_max(j)-x_min(j))*rand(1);
   end
   chromo(i,x_num+1:x_num+f_num) = object_fun(chromo(i,:),f_num,x_num,fun);
end

主程序matlab代码如下：

%---------------------------------------------------------------------
%程序功能：实现nsga2算法，测试函数为ZDT1,ZDT2,ZDT3,ZDT4,ZDT6,DTLZ1,DTLZ2
%说明：遗传算子为二进制竞赛选择，模拟二进制交叉和多项式变异
%      需要设置的参数：pop,gen,pc,pm,yita1,yita2
%作者：(晓风)
%最初建立时间：2018.9.3
%最近修改时间：2018.9.20
%----------------------------------------------------------
clear all
clc
tic;
%参数设置
fun='DTLZ1';
funfun;%函数选择
pop=300;%种群大小100
gen=250;%250进化代数
pc=1;%交叉概率
pm=1/x_num;%变异概率
% yita1=1;%模拟二进制交叉参数
% yita2=10;%多项式变异参数
yita1=2;%模拟二进制交叉参数10
yita2=5;%多项式变异参数50

%%初始化种群
chromo=initialize(pop,f_num,x_num,x_min,x_max,fun);
%%初始种群的非支配排序
[F1,chromo_non]=non_domination_sort(pop,chromo,f_num,x_num);%F为pareto等级为pareto_rank的集合，%p为每个个体p的集合(包括每个个体p的被支配个数n和该个体支配的解的集合s),chromo最后一列加入个体的等级
%%计算拥挤度进行排序
chromo=crowding_distance_sort(F1,chromo_non,f_num,x_num);
i=1;
%%循环开始
for i=1:gen
   %%二进制竞赛选择(k取了pop/2，所以选两次)
   chromo_parent_1 = tournament_selection(chromo);
   chromo_parent_2 = tournament_selection(chromo);
   chromo_parent=[chromo_parent_1;chromo_parent_2];
   %%模拟二进制交叉与多项式变异
   chromo_offspring=cross_mutation(chromo_parent,f_num,x_num,x_min,x_max,pc,pm,yita1,yita2,fun );
   %%精英保留策略
   %将父代和子代合并
   [pop_parent,~]=size(chromo);
   [pop_offspring,~]=size(chromo_offspring);
   combine_chromo(1:pop_parent,1:(f_num+x_num))=chromo(:,1:(f_num+x_num));
   combine_chromo((pop_parent+1):(pop_parent+pop_offspring),1:(f_num+x_num))=chromo_offspring(:,1:(f_num+x_num));
   %快速非支配排序
   [pop2,~]=size(combine_chromo);
   [F2,combine_chromo1]=non_domination_sort(pop2,combine_chromo,f_num,x_num);
   %计算拥挤度进行排序
   combine_chromo2=crowding_distance_sort(F2,combine_chromo1,f_num,x_num);
   %精英保留产生下一代种群
   chromo=elitism(pop,combine_chromo2,f_num,x_num);
   if mod(i,10) == 0
       fprintf('%d gen has completed!\n',i);
   end
end
toc;
aaa=toc;

hold on
if(f_num==2)
   plot(chromo(:,x_num+1),chromo(:,x_num+2),'r*');
end
if(f_num==3)
   plot3(chromo(:,x_num+1),chromo(:,x_num+2),chromo(:,x_num+2),'r*');
end
%%--------------------delta度量--------------------------------
% [~,index_f1]=sort(chromo(:,x_num+1));
% d=zeros(length(chromo)-1,1);
% for i=1:(length(chromo)-1)
%     d(i)=((chromo(index_f1(i),x_num+1)-chromo(index_f1(i+1),x_num+1))^2+(chromo(index_f1(i),x_num+2)-chromo(index_f1(i+1),x_num+2))^2)^0.5;
% end
% d_mean1=mean(d);
% d_mean=d_mean1*ones(length(chromo)-1,1);
% d_sum=sum(abs(d-d_mean));
% delta=(d(1)+d(length(chromo)-1)+d_sum)/(d(1)+d(length(chromo)-1)+(length(chromo)-1)*d_mean1);
% disp(delta);
%mean(a)
%(std(a))^2
%--------------------Coverage(C-metric)---------------------
A=PP;B=chromo(:,(x_num+1):(x_num+f_num));%%%%%%%%%%%%%%%%%%%
[temp_A,~]=size(A);
[temp_B,~]=size(B);
number=0;
for i=1:temp_B
   nn=0;
   for j=1:temp_A
       less=0;%当前个体的目标函数值小于多少个体的数目
       equal=0;%当前个体的目标函数值等于多少个体的数目
       for k=1:f_num
           if(B(i,k)<A(j,k))
               less=less+1;
           elseif(B(i,k)==A(j,k))
               equal=equal+1;
           end
       end
       if(less==0 && equal~=f_num)
           nn=nn+1;%被支配个体数目n+1
       end
   end
   if(nn~=0)
       number=number+1;
   end
end
C_AB=number/temp_B;
disp("C_AB:");
disp(C_AB);
%-----Distance from Representatives in the PF(D-metric)-----
A=chromo(:,(x_num+1):(x_num+f_num));P=PP;%%%%%%与论文公式保持相同，注意A和上述不一样
[temp_A,~]=size(A);
[temp_P,~]=size(P);
min_d=0;
for v=1:temp_P
   d_va=(A-repmat(P(v,:),temp_A,1)).^2;
   min_d=min_d+min(sqrt(sum(d_va,2)));
end
D_AP=(min_d/temp_P);
disp("D_AP:");
disp(D_AP);
filepath=pwd;          
cd('E:\GA\MOEA D\MOEAD_王超\nsga2对比算子修改\DTLZ1');
save C_AB4.txt C_AB -ASCII
save D_AP4.txt D_AP -ASCII
save solution4.txt chromo -ASCII
save toc4.txt aaa -ASCII
cd(filepath);

3. 实验结果

本文使用实数编码的模拟二进制交叉和多项式变异，交叉概率 p c = 0.9 p_c=0.9 pc=0.9，变异概率 p m = 1 / n p_m=1/n pm=1/n， η c = 20 η_c=20 ηc=20， η m = 20 η_m=20 ηm=20。以下为选取的5个非凸非均匀的多目标函数的运行结果如图4到图8所示。函数范围的matlab代码如下：

%测试函数
%--------------------ZDT1--------------------
if strcmp(fun,'ZDT1')
  f_num=2;%目标函数个数
  x_num=30;%决策变量个数
  x_min=zeros(1,x_num);%决策变量的最小值
  x_max=ones(1,x_num);%决策变量的最大值
  load('ZDT1.txt');%导入正确的前端解
  plot(ZDT1(:,1),ZDT1(:,2),'g*');
  PP=ZDT1;
end
%--------------------ZDT2--------------------
if strcmp(fun,'ZDT2')
  f_num=2;%目标函数个数
  x_num=30;%决策变量个数
  x_min=zeros(1,x_num);%决策变量的最小值
  x_max=ones(1,x_num);%决策变量的最大值
  load('ZDT2.txt');%导入正确的前端解
  plot(ZDT2(:,1),ZDT2(:,2),'g*');
  PP=ZDT2;
end
%--------------------ZDT3--------------------
if strcmp(fun,'ZDT3')
  f_num=2;%目标函数个数
  x_num=30;%决策变量个数
  x_min=zeros(1,x_num);%决策变量的最小值
  x_max=ones(1,x_num);%决策变量的最大值
  load('ZDT3.txt');%导入正确的前端解
  plot(ZDT3(:,1),ZDT3(:,2),'g*');
  PP=ZDT3;
end
%--------------------ZDT4--------------------
if strcmp(fun,'ZDT4')
  f_num=2;%目标函数个数
  x_num=10;%决策变量个数
  x_min=[0,-5,-5,-5,-5,-5,-5,-5,-5,-5];%决策变量的最小值
  x_max=[1,5,5,5,5,5,5,5,5,5];%决策变量的最大值
  load('ZDT4.txt');%导入正确的前端解
  plot(ZDT4(:,1),ZDT4(:,2),'g*');
  PP=ZDT4;
end
%--------------------ZDT6--------------------
if strcmp(fun,'ZDT6')
  f_num=2;%目标函数个数
  x_num=10;%决策变量个数
  x_min=zeros(1,x_num);%决策变量的最小值
  x_max=ones(1,x_num);%决策变量的最大值
  load('ZDT6.txt');%导入正确的前端解
  plot(ZDT6(:,1),ZDT6(:,2),'g*');
  PP=ZDT6;
end
%--------------------------------------------
%--------------------DTLZ1--------------------
if strcmp(fun,'DTLZ1')
  f_num=3;%目标函数个数
  x_num=10;%决策变量个数
  x_min=zeros(1,x_num);%决策变量的最小值
  x_max=ones(1,x_num);%决策变量的最大值
  load('DTLZ1.txt');%导入正确的前端解
%     plot3(DTLZ1(:,1),DTLZ1(:,2),DTLZ1(:,3),'g*');
  PP=DTLZ1;
end
%--------------------------------------------
%--------------------DTLZ2--------------------
if strcmp(fun,'DTLZ2')
  f_num=3;%目标函数个数
  x_num=10;%决策变量个数
  x_min=zeros(1,x_num);%决策变量的最小值
  x_max=ones(1,x_num);%决策变量的最大值
  load('DTLZ2.txt');%导入正确的前端解
%     plot3(DTLZ2(:,1),DTLZ2(:,2),DTLZ2(:,3),'g*');
  PP=DTLZ2;
end
%--------------------------------------------

函数的matlab代码如下：

function f = object_fun( x,f_num,x_num,fun )
% --------------------ZDT1--------------------
if strcmp(fun,'ZDT1')
  f=[];
  f(1)=x(1);
  sum=0;
  for i=2:x_num
      sum = sum+x(i);
  end
  g=1+9*(sum/(x_num-1));
  f(2)=g*(1-(f(1)/g)^0.5);
end
% --------------------ZDT2--------------------
if strcmp(fun,'ZDT2')
  f=[];
  f(1)=x(1);
  sum=0;
  for i=2:x_num
      sum = sum+x(i);
  end
  g=1+9*(sum/(x_num-1));
  f(2)=g*(1-(f(1)/g)^2);
end
% --------------------ZDT3--------------------
if strcmp(fun,'ZDT3')
  f=[];
  f(1)=x(1);
  sum=0;
  for i=2:x_num
      sum = sum+x(i);
  end
  g=1+9*(sum/(x_num-1));
  f(2)=g*(1-(f(1)/g)^0.5-(f(1)/g)*sin(10*pi*f(1)));
end
% --------------------ZDT4--------------------
if strcmp(fun,'ZDT4')
  f=[];
  f(1)=x(1);
  sum=0;
  for i=2:x_num
      sum = sum+(x(i)^2-10*cos(4*pi*x(i)));
  end
  g=1+9*10+sum;
  f(2)=g*(1-(f(1)/g)^0.5);
end
% --------------------ZDT6--------------------
if strcmp(fun,'ZDT6')
  f=[];
  f(1)=1-(exp(-4*x(1)))*((sin(6*pi*x(1)))^6);
  sum=0;
  for i=2:x_num
      sum = sum+x(i);
  end
  g=1+9*((sum/(x_num-1))^0.25);
  f(2)=g*(1-(f(1)/g)^2);
end
% --------------------------------------------
% --------------------DTLZ1--------------------
if strcmp(fun,'DTLZ1')
  f=[];
  sum=0;
  for i=3:x_num
      sum = sum+((x(i)-0.5)^2-cos(20*pi*(x(i)-0.5)));
  end
  g=100*(x_num-2)+100*sum;
  f(1)=(1+g)*x(1)*x(2);
  f(2)=(1+g)*x(1)*(1-x(2));
  f(3)=(1+g)*(1-x(1));
end
% --------------------------------------------
% --------------------DTLZ2--------------------
if strcmp(fun,'DTLZ2')
  f=[];
  sum=0;
  for i=3:x_num
      sum = sum+(x(i))^2;
  end
  g=sum;
  f(1)=(1+g)*cos(x(1)*pi*0.5)*cos(x(2)*pi*0.5);
  f(2)=(1+g)*cos(x(1)*pi*0.5)*sin(x(2)*pi*0.5);
  f(3)=(1+g)*sin(x(1)*pi*0.5);
end
% --------------------------------------------
end

3.1 ZDT1

f 1 = x 1 f_1=x_1 f1=x1 g = 1 + 9 ( ( ∑ i = 2 n x i ) / ( n − 1 ) ) g=1+9((∑_{i=2}^nx_i )/(n-1)) g=1+9((i=2∑nxi)/(n−1)) f 2 = g ( 1 − ( f 1 / g ) 0.5 ) . n = 30 , x i ∈ [ 0 , 1 ] f_2=g(1-(f_1/g)^{0.5} ).n=30,x_i∈[0,1] f2=g(1−(f1/g)0.5).n=30,xi∈[0,1] 选取种群大小为500，迭代次数500次，pc=0.9,pm=1/30,ηc=20,ηm=20,得到结果如图4(上)所示。选取种群大小为100，迭代次数2000次，pc=0.9,pm=1/30,ηc=20,ηm=20,得到结果如图4(下)所示。

图4 ZDT1 pareto最优解对比图（绿色为理论值，红色为实验值）

3.2 ZDT2

f 1 = x 1 f_1=x_1 f1=x1 g = 1 + 9 ( ( ∑ i = 2 n x i ) / ( n − 1 ) ) g=1+9((∑_{i=2}^n x_i )/(n-1)) g=1+9((i=2∑nxi)/(n−1)) f 2 = g ( 1 − ( f 1 / g ) 2 ) . n = 30 , x i ∈ [ 0 , 1 ] f_2=g(1-(f_1/g)^2 ).n=30,x_i∈[0,1] f2=g(1−(f1/g)2).n=30,xi∈[0,1] 选取种群大小为500，迭代次数500次，pc=0.9,pm=1/30,ηc=20,ηm=20,得到结果如图5（上）所示。选取种群大小为100，迭代次数2000次，pc=0.9,pm=1/30,ηc=20,ηm=20,得到结果如图5（下）所示。

图5 ZDT2 pareto最优解对比图（绿色为理论值，红色为实验值）

3.3 ZDT3

f 1 = x 1 f_1=x_1 f1=x1 g = 1 + 9 ( ( ∑ i = 2 n x i ) / ( n − 1 ) ) g=1+9((∑_{i=2}^nx_i )/(n-1)) g=1+9((i=2∑nxi)/(n−1)) f 2 = g ( 1 − ( f 1 / g ) 0.5 − ( f 1 / g ) s i n ⁡ ( 10 π f 1 ) ) . n = 30 , x i ∈ [ 0 , 1 ] f_2=g(1-(f_1/g)^{0.5}-(f_1/g)sin⁡(10πf_1)).n=30,x_i∈[0,1] f2=g(1−(f1/g)0.5−(f1/g)sin⁡(10πf1)).n=30,xi∈[0,1] 选取种群大小为136，迭代次数500次，pc=0.9,pm=1/30,ηc=20,ηm=20,得到结果如图6示。选取种群大小为136，迭代次数2000次，pc=0.9,pm=1/30,ηc=20,ηm=20,得到结果如图6示。

图6 ZDT3 pareto最优解对比图（绿色为理论值，红色为实验值）

3.4 ZDT4

f 1 = x 1 f_1=x_1 f1=x1 g = 1 + 9 ∗ 10 + ∑ i = 2 n ( ( x i ) 2 − 10 c o s ⁡ ( 4 π x i ) ) g=1+9*10+∑_{i=2}^n( (x_i )^2-10cos⁡(4πx_i)) g=1+9∗10+i=2∑n((xi)2−10cos⁡(4πxi)) f 2 = g ( 1 − ( f 1 / g ) 0.5 ) . n = 10 , x 1 ∈ [ 0 , 1 ] ; x ( 2 … 6 ) ∈ [ − 5 , 5 ] f_2=g(1-(f_1/g)^{0.5} ).n=10,x_1∈[0,1];x_(2…6)∈[-5,5] f2=g(1−(f1/g)0.5).n=10,x1∈[0,1];x(2…6)∈[−5,5] 选取种群大小为100，迭代次数500次，pc=0.9,pm=0.1,ηc=20,ηm=10,得到结果如图7（上）所示。选取种群大小为100，迭代次数2000次，pc=0.9,pm=0.1,ηc=20,ηm=10,得到结果如图7（下）所示。

图7 ZDT4 pareto最优解对比图（绿色为理论值，红色为实验值）

3.5 ZDT6

f 1 = 1 − e − 4 x 1 s i n 6 ( 6 π x 1 ) f_1=1-e^{-4x_1} sin^6 (6πx_1) f1=1−e−4x1sin6(6πx1) g = 1 + 9 ( ( ∑ i = 2 n x i ) / ( n − 1 ) ) 0.25 g=1+9((∑_{i=2}^nx_i )/(n-1))^{0.25} g=1+9((i=2∑nxi)/(n−1))0.25 f 2 = g ( 1 − ( f 1 / g ) 2 ) . n = 10 , x i ∈ [ 0 , 1 ] f_2=g(1-(f_1/g)^2 ).n=10,x_i∈[0,1] f2=g(1−(f1/g)2).n=10,xi∈[0,1] 选取种群大小为100，迭代次数500次，pc=0.9,pm=0.1,ηc=20,ηm=20,得到结果如图8（上）所示。选取种群大小为100，迭代次数2000次，pc=0.9,pm=0.1,ηc=20,ηm=20,得到结果如图8（下）所示。

图8 ZDT6 pareto最优解对比图（绿色为理论值，红色为实验值）从结果中可以看出，除ZDT4以外，找到的解几乎全部是pareto前端上的点，并且解在目标空间上分布十分均匀，该算法对于非凸非均匀的多目标函数最优解的寻找还是十分有效的。由于ZDT4具有许多局部pareto最优前沿，为了摆脱这些局部前沿，需要对决策向量进行大的改变，因此选取ηm=10，但仍离真正的pareto前沿还有很大的差距。

3.6 对比

表1 γ的均值和方差（500代）

项目	ZDT1	ZDT2	ZDT3	ZDT4	ZDT6
均值	0.0532	0.0972	0.1712	20.2304	0.3284
方差	0.0021	0.0051	0.0048	0.6310	0.0109

表2 Δ的均值和方差（500代）

项目	ZDT1	ZDT2	ZDT3	ZDT4	ZDT6
均值	0.4575	0.4615	0.6640	0.5203	0.9538
方差	0.0021	0.0015	0.0030	0.0013	0.0055

表3 γ的均值和方差（2000代）

项目	ZDT1	ZDT2	ZDT3	ZDT4	ZDT6
均值	0.0011	0.0027	0.0225	12.0341	0.2092
方差	0.0002	0.0002	0.0005	0.3320	0.0021

表4 Δ的均值和方差（2000代）

项目	ZDT1	ZDT2	ZDT3	ZDT4	ZDT6
均值	0.4478	0.4337	0.6586	0.5168	0.4529
方差	0.0001	0.0003	0.0006	0.0018	0.0001

根据上述实验数据，进行五组实验，计算distance metric γ，diversity metric Δ的均值和方差，迭代500次后得到结果如表格1-2所示。迭代2000次后得到的结果如表格3-4所示。表1显示了NSGA-Ⅱ（实数编码500代）在5个问题上运行获得的distance metric γ的均值和方差，实验结果表明，除了ZDT4和ZDT6以外的问题均取得了良好的收敛效果，除ZDT4以外，其他问题5次运行结果的差异也都很小。表2显示了NSGA-Ⅱ（实数编码500代）在5个问题上运行获得的diversity metric Δ的均值和方差，实验结果表明，NSGA-Ⅱ在上述问题上均具有较强的传播多样性，并且5次运行结果的差异都很小。像500代的时候一样保留所有其他参数，但将代数增加至2000代，得到表3的distance metric γ的均值和方差以及表4的diversity metric Δ的均值和方差。将表3表4与表1表2对比可知，5个问题的distance metric γ随着代数的增加都有改善，其中ZDT3和ZDT4的改善尤为显著，除此之外，因为在500代时问题的结果已经有了良好的多样性分布了，所以代数的增加并没有对diversity metric Δ产生巨大的影响。 [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.

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/124609.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年4月3，如有侵权请联系 cloudcommunity@tencent.com 删除

机器学习