精华内容
下载资源
问答
  • 多目标优化算法(一)NSGA-Ⅱ(NSGA2)

    万次阅读 多人点赞 2018-09-28 20:39:42
    NSGA-Ⅱ算法,即带有精英保留策略的快速非支配多目标优化算法,是一种基于Pareto最解的多目标优化算法。 1.1 Pareto支配关系以及Pareto等级 Pareto支配关系:对于最小化目标优化问题,对于n个目标分量 fi(x),i=1...

    多目标优化算法(一)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} i1,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} i1,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 iF1:
            for 个体 l ∈ S i l \in S_i lSi
                    n l = n l − 1 n_l=n_l-1 nl=nl1;(该步骤即消除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,其算法如下:

    1. 令参数 n d = 0 , n ∈ 1 … N n_d=0,n∈1…N nd=0n1N
    2. 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(i1))/(fmmaxfmmin),其中 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(1uj))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(1uj))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所示。
     NSGA-Ⅱ算法流程图
    初始化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=2nxi)/(n1))
    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=2nxi)/(n1))
    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=2nxi)/(n1))
    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+910+i=2n((xi)210cos(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(26)[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=1e4x1sin6(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=2nxi)/(n1))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代)

    项目ZDT1ZDT2ZDT3ZDT4ZDT6
    均值0.05320.09720.171220.23040.3284
    方差0.00210.00510.00480.63100.0109

    表2 Δ的均值和方差(500代)

    项目ZDT1ZDT2ZDT3ZDT4ZDT6
    均值0.45750.46150.66400.52030.9538
    方差0.00210.00150.00300.00130.0055

    表3 γ的均值和方差(2000代)

    项目ZDT1ZDT2ZDT3ZDT4ZDT6
    均值0.00110.00270.022512.03410.2092
    方差0.00020.00020.00050.33200.0021

    表4 Δ的均值和方差(2000代)

    项目ZDT1ZDT2ZDT3ZDT4ZDT6
    均值0.44780.43370.65860.51680.4529
    方差0.00010.00030.00060.00180.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.

    展开全文
  • 精华多目标优化算法

    2018-11-04 13:06:35
    介绍了多目标优化问题的...并且介绍了解决多目标优化的几种典型算法,讨论并对比了算法存在的优缺点,认为要进一步研究求解多目标优化问题的更高效算法,若能结合各种算法优点,处理目标问题的效果将越来越好。
  • 然后针对该问题,按照选择机制的不同详细介绍基于Pareto支配、基于分解策略和基于性能评价指标的典型高维多目标优化算法,并分析各自的优缺点;接着立足于一种全新的性能评价指标-----R2指标,给出R2指标的具体定义,介绍...
  • 多目标优化算法:基于分解的目标进化算法 MOEA/D 相关概念 MOP-目标优化 目标优化问题(MOP): maxF(x)=(f1(x),,,fm(x))T max F(x) = (f_1(x),,,f_m(x))^T maxF(x)=(f1​(x),,,fm​(x))T subject&amp;amp;...

    多目标优化算法:基于分解的多目标进化算法 MOEA/D

    相关概念

    1. MOP-多目标优化
      多目标优化问题(MOP):
      m a x F ( x ) = ( f 1 ( x ) , , , f m ( x ) ) T max F(x) = (f_1(x),,,f_m(x))^T maxF(x)=(f1(x),,,fm(x))T
      s u b j e c t   t o   x ∈ Ω subject\ to\ x \in \varOmega subject to xΩ
      Ω \varOmega Ω是决策空间, F : Ω → R m F: \varOmega \to R^m F:ΩRm包含m个实数值目标函数, R m R^m Rm被称为目标空间,{ F ( x ) ∣ x ∈ Ω F(x)|x \in \varOmega F(x)xΩ}为可得到目标集合
      if x ∈ R n x \in R_n xRn,所有的连续目标和 Ω \varOmega Ω被描述为
      Ω = { x ∈ R n ∣ h j ( x ) ≤ 0 , j = 1 , . . . , m } \varOmega =\{x \in R^n|h_j(x) \le 0,j=1,...,m\} Ω={xRnhj(x)0,j=1,...,m}

    MOEA/D的特点

    1. 将多目标问题分解成一定数量N的子问题,再同时进行优化每个子问题,简单但是有效
    2. 由于MOEA/D算法利用相邻子问题的解同时优化多个子问题而不是优化整体,MOEA/D对保持多样性和降低适应度分配的难度都有很好的表现
    3. 当MOEA/D算法当遇到种群数量较小时,也可以产生分步均匀的解。
    4. T为最接近的相邻子问题的数量,当T太小时,搜索域太小;当T太大时,产生的解质量会下降。
    5. 相比于NSGA-II和MOGLS,MOEA/D有较好的计算复杂度,MOGLS和MOEA/D在解决0-1背包问题时,使用相同的分解方法,MOEA/D的解更优。在有个3目标连续测试中,使用一个先进分解方法的MOEA/D算法的表现比NSGA-II优秀许多。

    MOEA/D的分解策略

    1. 权重求和法(Weighted Sum Approach)
      使 λ = ( λ 1 , . . . . . . , λ m ) T \lambda = (\lambda_1,......,\lambda_m)^T λ=(λ1,......,λm)T为一个权重向量,对所有的 i = 1 , . . . , m i=1,...,m i=1,...,m λ i ≥ 0 \lambda_i \geq 0 λi0 ∑ i = 1 m = 1 \sum_{i=1}^m=1 i=1m=1.对于优化问题:
      m a x   g w s ( x ∣ λ ) = ∑ i = 1 m λ i f i ( x ) max \ g^{ws}(x|\lambda) = \sum_{i=1}^m \lambda_if_i(x) max gws(xλ)=i=1mλifi(x)
      s u b j e c t   t o   x ∈ Ω subject \ to \ x \in \varOmega subject to xΩ
      x x x是需要被优化的变量时, λ \lambda λ在目标函数中是一个系数向量。在上面标量化的问题中,我们可以使用不同权重的 λ \lambda λ以生成一组不同的Pareto最优向量。不是每个Pareto最优向量可以通过这种方法获得非凹PFs.。

    2. 切比雪夫法(Tchebycheff Approach)

      标量优化问题如下:
      m i n   g t e ( x ∣ λ , z ∗ ) =   max ⁡ 1 ≤ i ≤ m   { λ i ∣ f i ( x ) − z i ∗ ∣ } min \ g^{te}(x|\lambda,z^*) = {\ \max_{1 \leq i \leq m}}\ \{\lambda_i|f_i(x)-z_i^*|\} min gte(xλ,z)= 1immax {λifi(x)zi}
      s u b j e c t   t o   x ∈ Ω subject \ to\ x \in \varOmega subject to xΩ
      其中 z ∗ = ( z 1 ∗ , . . . , z m ∗ ) T z^* = (z_1^*,...,z_m^*)^T z=(z1,...,zm)T是参照点,对于每个 i = 1 , , , m i=1,,,m i=1,,,m z i ∗ = m a x { f i ( x ) ∣ x ∈ Ω } 3 z_i^*=max\{f_i(x)|x \in \varOmega\}^3 zi=max{fi(x)xΩ}3。一个能够获得不同Pareto最优解的方式是交换权重向量。一个缺点是,对于连续的MOP,使用这种方法的聚合函数不平滑。然而这种方法仍然可以使用在我们提出的EA框架中,因为我们不需要计算该聚合函数的倒数。

    3. 边界交叉法(Boundary Intersection)

    在这里插入图片描述
    m i n   g b i ( x ∣ λ , z ∗ ) = d min \ g^{bi}(x|\lambda,z^*) = d min gbi(xλ,z)=d
    s u b j e c t   t o   z ∗ − F ( x ) = d λ ,   x ∈ Ω subject\ to\ z^*-F(x) = d\lambda, \ x \in \varOmega subject to zF(x)=dλ, xΩ
    λ \lambda λ z ∗ z^* z分别是权重向量和参考点时,上图中约束 z ∗ − F ( x ) = d λ z^*-F(x)=d\lambda zF(x)=dλ保证 F ( x ) F(x) F(x)这个点总是在方向为 λ \lambda λ且穿过 z ∗ z^* z的直线L上。优化的目标是尽可能高的将F(x)推至可达到目标集合的边界上。

    上述方法其中有个最大的缺点是处理相等约束。我们可以使用罚函数来解决约束问题,具体如下:

    在这里插入图片描述
    m i n   g b i p ( x ∣ λ , z ∗ ) = d 1 + θ d 2 min \ g^{bip}(x|\lambda,z^*)=d_1+\theta d_2 min gbip(xλ,z)=d1+θd2
    s u b j e c t   t o   x ∈ Ω subject \ to\ x \in \varOmega subject to xΩ
    where
    d 1 = ∥ ( z ∗ − F ( x ) ) T λ ∥ ∥ λ ∥ d_1 = \frac {\lVert (z^* - F(x))^T \lambda \rVert} {\lVert \lambda \rVert} d1=λ(zF(x))Tλ
    a n d   d 2 = ∥ F ( x ) − ( z ∗ − d 1 λ ) ∥ and \ d_2 = \lVert F(x) - (z^* - d_1\lambda) \rVert and d2=F(x)(zd1λ)
    θ &gt; 0 \theta &gt; 0 θ>0是一个预设的惩罚参数。 y y y是F(x)在直线L上的投影, d 1 d_1 d1 z ∗ z^* z和y的距离, d 2 d_2 d2是F(x)和L的距离。当 θ \theta θ去适当的值时,两种边界交叉法的结果会非常接近。

    MOEA/D的算法步骤(Tchebycheff Approach)

    λ j = ( λ 1 j , . . . , λ m j ) T \lambda^j = (\lambda_1^j,...,\lambda_m^j)^T λj=(λ1j,...,λmj)T为一组均匀分布的权重向量, z ∗ z^* z为参考点,第j个问题的目标函数为:
    g t e ( x ∣ λ j , z ∗ ) = max ⁡ 1 ≤ i ≤ m { λ i j ∣ f i ( x ) − z i ∗ ∣ } g^te(x|\lambda^j,z^*)= \max_{1 \leq i \leq m}\{\lambda_i^j | f_i(x) - z_i^*|\} gte(xλj,z)=1immax{λijfi(x)zi}
    MOEA/D可以在一次运行中,同时优化所有这N个子问题目标函数。
    在MOEA/D中,权重向量的邻居中取几个最接近的权重向量,每一代的种群由每个子问题的最优解组成。只有相邻子问题可以进行优化当前的解。

    YES
    NO
    开始
    初始化种群
    为每个子问题分配权重向量
    运用遗传算子使相邻问题的最优解产生当前问题的解
    根据聚合函数更新父代种群
    满足终止条件
    结束

    每一代(t),MOEA/D(Techebycheff)包括:

    • x 1 , . . . , x N ∈ Ω x^1,...,x^N \in \varOmega x1,...,xNΩ由N个点组织成的种群, x i x^i xi是第i个问题的当前解
    • F V i , . . . , F V N FV^i,...,FV^N FVi,...,FVN, F V i = F ( x i ) FV^i = F(x^i) FVi=F(xi)
    • z = ( z 1 , . . . , z m ) T ​ z = (z_1 , ... ,z_m)^T​ z=(z1,...,zm)T, z i z_i zi是目标 f i f_i fi中已发现最好的值。
    • EP用来存储咋搜索过程中的非支配解

    Input:

    • MOP(1);
    • 算法停止条件
    • N:分解成的子问题的个数
    • N个分布均匀的权重向量
    • T:每个权重向量相邻的权重向量的个数
      Output:EP

    Step 1) 初始化:
    Step 1.1) Set EP = ∅ \empty

    Step 1.2) 计算任意两个权重向量的欧氏距离,找出每个权重向量最近邻的T个权重向量,对每一个 i = 1 , . . . , N i = 1,...,N i=1,...,N,设$B(i) = {i_1,…,i_T}, 其 中 其中 \lambda{i1},…,\lambda{iT} 是 最 接 近 是最接近 \lambda^i$的N个权重向量。

    Step 1.3) 随机或者使用特定方法生成一个初始化种群 x 1 , . . . , x N x^1,...,x^N x1,...,xN。设 F V i = F ( x i ) FV^i = F(x^i) FVi=F(xi)

    Step 1.4) 根据特定的问题初始化 z = ( z 1 , . . . , z m ) T z = (z_1,...,z_m)^T z=(z1,...,zm)T

    Step 2) 更新:
    ​ 循环对 i = 1 , . . . , N i=1,...,N i=1,...,N做以下操作
    Step 2.1)繁殖: B ( i ) B(i) B(i)中随机选择两个索引 k , l k,l k,l x k x^k xk x l x^l xl使用遗传算子生成新的解 y y y

    Step 2.2)改善: 根据特定问题,使用启发式方法改进 y y y生成 y ′ y&#x27; y

    Step 2.3)更新z: 对于每一个$j = 1 , …,m , 如 果 ,如果 z_j < f_i(y’) , 使 ,使 ,使z_j = f_j(y’)$。

    Step 2.4)更新邻域解: 对每个属于 B ( i ) B(i) B(i)的索引j,如果 g t e ( y ′ ∣ λ j , z ) ≤ g t e ( x j ∣ λ j , z ) g^{te}(y&#x27;|\lambda^j,z) \leq g^{te}(x^j|\lambda^j,z) gte(yλj,z)gte(xjλj,z),则令 x j = y ′ x^j = y&#x27; xj=y F V j = F ( y ′ ) FV^j = F(y&#x27;) FVj=F(y)

    Step 2.5)更新EP:
    ​ 1.删除EP中所有被 F ( y ′ ) F(y&#x27;) F(y)支配的向量。
    ​ 2.如果EP中没有向量支配 F ( y ′ ) F(y&#x27;) F(y),则将 F ( y ′ ) ​ F(y&#x27;)​ F(y)加入到EP中。

    Step 3)停止条件: 如果满足停止条件,停止并且输出EP,否则则跳转至Step 2

    MOEA/D与NSGA-II的对比

    1. 评价准则

    1.1 C-Metric
    ​ A和B是MOP问题的两个接近的PF集合
    C ( A , B ) = ∣ { u ∈ B ∣ ∃ v ∈ A : v d o m i n a t e s   u } ∣ ∣ B ∣ C(A,B) = \frac {\lvert \{u \in B | \exist v \in A: v dominates \ u \} \rvert} {\lvert B \rvert} C(A,B)=B{uBvA:vdominates u}
    C ( A , B ) C(A,B) C(A,B)不等于 1 − C ( B , A ) 1-C(B,A) 1C(B,A) C ( A , B ) = 1 C(A,B) = 1 C(A,B)=1表示B中所有的解都被A中的一些解支配。当 C ( A , B ) = 0 C(A,B)=0 C(A,B)=0表示B中没有解被A中支配。
    1.2 D-Metric
    ​ 令 P ∗ P^* P为沿着PF的一组分布均匀的点,令A为接近PF的集合, P ∗ P^* P和A的平均距离定义如下:
    D ( A , P ∗ ) = ∑ v ∈ P ∗ d ( v , A ) ∣ P ∗ ∣ D(A,P^*) = \frac {\displaystyle\sum_{v \in P^*}d(v,A)} {\lvert P^* \rvert} D(A,P)=PvPd(v,A)
    d ( v , A ) d(v,A) d(v,A) v v v和A中的点之间的最小欧氏距离。如果 ∣ P ∗ ∣ ​ \lvert P^* \rvert​ P足够大,说明集合很好的代表了PF, D ( A , P ∗ ) D(A,P^*) D(A,P)可以一定程度上评估A的多样性和收敛性。

    1. MOEA/D与NSGA-II的对比

    2.1 时间复杂度对比

    ​ 采用改良的MOEA/D进行实验,去掉了额外种群EP,因此去掉步骤2.5,去掉了启发式优化过程,因此删去了步骤2.2,所以时间复杂度主要在步骤2部分。步骤2.3进行了 O ( m ) O(m) O(m)次比较,步骤2.4部分的时间复杂度为 O ( m T ) O(mT) O(mT),由于分成了N个子问题,所以改良的MOEA/D的时间复杂度为 O ( m T N ) O(mTN) O(mTN)。而NSGA-II的时间复杂度为 O ( m N 2 ) O(mN^2) O(mN2)因为N为权重向量的个数,而T为一个权重向量相邻的权重向量的个数,所以 T &lt; N T &lt; N T<N,故而MOEA/D的时间复杂度比NSGA-II要小,但时间复杂度的优势不是非常明显
    2.2 空间复杂度对比

    ​ 改良后的MOEA/D没有EP,只有m个参照点z需要存储,但是与一代种群大小相比,所占空间非常小,我觉得两者是空间复杂度上没有特别大的差别。

    2.3 测试函数及实验结果
    根据论文中,针对2个目标问题将NSGA-II和MOEA/D的种群大小都100。针对3目标问题,种群数都设为300,都采用模拟二进制的交叉变异和多项式变异, p c = 1.0 , p m = 1 / n , T = 20 p_c=1.0,p_m=1/n,T=20 pc=1.0,pm=1/n,T=20

    • ZDT1

    f 1 ( X ) = x 1 f_1(X) = x_1 f1(X)=x1
    f 2 ( X ) = g ( X ) [ 1 − x 1 / g ( X ) ] f_2(X) = g(X)[1-\sqrt{x_1/g(X)}] f2(X)=g(X)[1x1/g(X) ]
    g ( X ) = 1 + 9 ( ∑ i = 2 n x i ) / ( n − 1 ) g(X) = 1+9(\sum_{i=2}^nx_i)/(n-1) g(X)=1+9(i=2nxi)/(n1)

    n = 30 , n=30, n=30,
    x 1 ∈ [ 0 , 1 ] , x i = 0 x_1\in[0,1],x_i = 0 x1[0,1],xi=0

                    NSGA-II                MOEA/D
    • ZDT2

    f 1 ( X ) = x 1 f_1(X) = x_1 f1(X)=x1
    f 2 ( X ) = g ( X ) [ 1 − ( x 1 / g ( X ) ) 2 ] f_2(X) = g(X)[1-(x_1/g(X))^2] f2(X)=g(X)[1(x1/g(X))2]
    g ( X ) = 1 + 9 ( ∑ i = 2 n x i ) / ( n − 1 ) g(X) = 1+9(\sum_{i=2}^nx_i)/(n-1) g(X)=1+9(i=2nxi)/(n1)

    n = 30 , n=30, n=30,
    x 1 ∈ [ 0 , 1 ] , x i = 0 x_1\in[0,1],x_i = 0 x1[0,1],xi=0

                    NSGA-II                MOEA/D
    • ZDT3

    f 1 ( X ) = x 1 f_1(X) = x_1 f1(X)=x1
    f 2 ( X ) = g ( X ) [ 1 − x 1 / g ( X ) − x 1 g ( X ) sin ⁡ ( 10 π x 1 ) ] f_2(X) = g(X)[1-\sqrt{x_1/g(X)}-{\frac{x_1}{g(X)}}\sin(10\pi x_1)] f2(X)=g(X)[1x1/g(X) g(X)x1sin(10πx1)]
    g ( X ) = 1 + 9 ( ∑ i = 2 n x i ) / ( n − 1 ) g(X) = 1+9(\sum_{i=2}^nx_i)/(n-1) g(X)=1+9(i=2nxi)/(n1)

    n = 30 , n=30, n=30,
    x 1 ∈ [ 0 , 1 ] , x i = 0 x_1\in[0,1],x_i = 0 x1[0,1],xi=0

                    NSGA-II                MOEA/D
    • ZDT4

    f 1 ( X ) = x 1 f_1(X) = x_1 f1(X)=x1
    f 2 ( X ) = g ( X ) [ 1 − x 1 / g ( X ) ] f_2(X) = g(X)[1-\sqrt{x_1/g(X)}] f2(X)=g(X)[1x1/g(X) ]
    g ( X ) = 1 + 10 ( n − 1 ) + ∑ i = 2 n [ x i 2 − 10 cos ⁡ ( 4 π x i ) ] g(X) = 1+10(n-1)+\sum_{i=2}^n[x_i^2-10\cos(4\pi x_i)] g(X)=1+10(n1)+i=2n[xi210cos(4πxi)]

    n = 10 , n=10, n=10,
    x 1 ∈ [ 0 , 1 ] , x i = 0 x_1\in[0,1],x_i = 0 x1[0,1],xi=0

                    NSGA-II                MOEA/D
    • ZDT6

    f 1 ( X ) = 1 − e x p ( − 4 π x 1 ) sin ⁡ 6 ( 6 π x 1 ) f_1(X)= 1-exp(-4\pi x_1)\sin^6(6\pi x_1) f1(X)=1exp(4πx1)sin6(6πx1)
    f 2 ( X ) = g ( X ) [ 1 − ( f 1 ( X ) / g ( X ) ) 2 ] f_2(X)= g(X)[1-(f_1(X)/g(X))^2] f2(X)=g(X)[1(f1(X)/g(X))2]
    g ( X ) = 1 + 9 [ ( ∑ n i = 2 x i ) / ( n − 1 ) ] 0.25 g(X) = 1+9[(\sum_n^{i=2}x_i)/(n-1)]^{0.25} g(X)=1+9[(ni=2xi)/(n1)]0.25

    n = 10 , n=10, n=10,
    x 1 ∈ [ 0 , 1 ] , x i = 0 x_1\in[0,1],x_i = 0 x1[0,1],xi=0

                    NSGA-II                MOEA/D
    • DTLZ1
      f 1 ( X ) = ( 1 + g ( X ) ) x 1 x 2 f_1(X) = (1+g(X))x_1x_2 f1(X)=(1+g(X))x1x2
      f 2 ( X ) = ( 1 + g ( X ) ) x 1 ( 1 − x 2 ) f_2(X) = (1+g(X))x_1(1-x_2) f2(X)=(1+g(X))x1(1x2)
      f 3 ( X ) = ( 1 + g ( X ) ) ( 1 − x 1 ) f_3(X) = (1+g(X))(1-x_1) f3(X)=(1+g(X))(1x1)
      g ( X ) = 100 ( n − 2 ) + 100 ∑ i = 3 n { ( x i − 0.5 ) 2 − cos ⁡ [ 20 π ( x i − 0.5 ) ] } g(X) = 100(n-2)+100\sum_{i=3}^n\{(x_i-0.5)^2-\cos[20\pi(x_i-0.5)]\} g(X)=100(n2)+100i=3n{(xi0.5)2cos[20π(xi0.5)]}

    x = ( x 1 , . . . , x n ) T ∈ [ 0 , 1 ] n x = (x_1,...,x_n)^T \in [0,1]^n x=(x1,...,xn)T[0,1]n

                    NSGA-II                MOEA/D
    • DTLZ2
      f 1 ( X ) = ( 1 + g ( X ) ) cos ⁡ ( x 1 π 2 ) cos ⁡ ( x 2 π 2 ) f_1(X) = (1+g(X))\cos(\frac {x_1\pi} {2})\cos(\frac {x_2\pi} {2}) f1(X)=(1+g(X))cos(2x1π)cos(2x2π)
      f 2 ( X ) = ( 1 + g ( X ) ) cos ⁡ ( x 1 π 2 ) sin ⁡ ( x 2 π 2 ) f_2(X) = (1+g(X))\cos(\frac {x_1\pi} {2})\sin(\frac {x_2\pi} {2}) f2(X)=(1+g(X))cos(2x1π)sin(2x2π)
      f 3 ( X ) = ( 1 + g ( X ) ) sin ⁡ ( x 1 π 2 ) f_3(X) = (1+g(X))\sin(\frac {x_1\pi} {2}) f3(X)=(1+g(X))sin(2x1π)
      g ( X ) = ∑ i = 3 n x i 2 g(X)=\sum_{i=3}^nx_i^2 g(X)=i=3nxi2
      x = ( x 1 , . . . , x 2 ) T ∈ [ 0 , 1 ] 2 ∗ [ − 1 , 1 ] n − 2 x = (x_1,...,x_2)^T \in [0,1]^2*[-1,1]^{n-2} x=(x1,...,x2)T[0,1]2[1,1]n2
                    NSGA-II                MOEA/D

    Δ \Delta Δ的Mean

    ProblemZDT1ZDT2ZDT3ZDT4ZDT6DTLZ1DTLZ2
    NSGA-II0.6420.7060.4251.000.6100.9450.0323
    MOEA/D1.001.000.9311.000.0410.8300.0281

    γ \gamma γ的Mean

    ProblemZDT1ZDT2ZDT3ZDT4ZDT6DTLZ1DTLZ2
    NSGA-II0.005740.06620.0061429.2990.0039772.5580.07819
    MOEA/D0.01770.40170.013515.6720.0063544.7260.4634

    可以从图的对比和表中 Δ \Delta Δ γ \gamma γ两个参数的对比看出,在两目标问题上,两者算法相差不多,甚至在ZDT1、ZDT2、ZDT3等问题上NSGA-II更优一些,但是在ZDT6上MOEA/D表现的更好,MOEA/D的主要优势在算法的计算速度上,在面对三目标问题时,MOEA/D比NSGA-II要优秀很多。

    展开全文
  • 基于NSGA-II的多目标优化算法及论文,算法代码可运行,论文已在cscwd2018会议中发表
  • 经典的多目标优化算法,用matlab编的
  • 进化算法在解决目标优化问题中有其特有的优势.首先对目标优化问题进行了描述;然后结合研究现状讨论了目前几种主要的基于...最后给出了目标进化优化算法的一些应用, 以及进化多目标优化算法的未来发展方向.</p>
  • 多目标优化-NSGAII算法

    千次阅读 2020-07-04 22:42:26
    NSGA-II学习笔记 ...从学长那里得知,NSGA-II和MOEAD是多目标优化算法的经典算法,不了解这两个讲点算法,相当于白学了多目标优化算法,很算法也是基于NSGA-II和MOEAD来进行改进和拓展,从而衍生出一系列算法

    NSGA-II学习笔记

    阅读文献:A Fast and Elitist Multiobjective Genetic Algorithm:
    NSGA-II
    有兴趣的话可以阅读中文翻译版本:https://wenku.baidu.com/view/61daf00d0508763230121235.html

    简介

    从学长那里得知,NSGA-II和MOEAD是多目标优化算法的经典算法,不了解这两个讲点算法,相当于白学了多目标优化算法,很多算法也是基于NSGA-II和MOEAD来进行改进和拓展,从而衍生出一系列算法。
    下面我先介绍一下NSGA-II
    NSGA-II 是由Deb跟他的学生在2000年提出了NSGA的改进版本。NSGA2采用快速非支配排序以及拥挤距离的策略,时间复杂度在O(MN2)。由于其速度及效果上的优势,许多年来NSGA2都被作为对比算法。

    下面来说一下,NSGA-II相比于NSGA有以下三点改进:

    1.提出快速非支配排序算法,是计算复杂度由计算复杂度O(MN^3 )降低为O(MN^2 )

    2.引入精英策略,扩大采样空间。将父代种群与其产生的子代种群组合,共同竞争产生下一代种群,有利于保持父代中的优良个体进入下一代,保证某些优良的种群个体在进化过程中不会被丢弃,从而提高了优化结果的精度。并通过对种群中所有个体的分层存放,使得最佳个体不会丢失,有效提高种群水平。

    3.采用拥挤度和拥挤度比较算子,不但克服了NSGA中需要人为指定共享参数的缺陷,而且将其作为种群中个体间的比较标准,使得准Pareto域中的个体能均匀地扩展到整个Pareto域,保证了种群的多样性。

    具体

    1.大体算法流程

    	确定种群大小 n,交叉概率 t,迭代次数 g
    
    ​	随机产生 n 个个体,它们整体视为种群 P
    
    ​	for i = 1 to g
    
     		  P’ = ∅ 
    
      		 for j = 1 to n
    
    ​            产生一个 [0,1] 的随机数 a
    
    ​      	 if (a<t)
    
    ​         	从 P 中随机选出两个个体作为父母,交叉产生一个新的个体并放入 P’ 中
    
    ​     	  else
    
    ​         	从 P 中随机选出一个个体,变异产生一个新的个体并放入 P’ 中
    
    ​       	end
    
       end
    
       利用非支配排序和拥挤距离,从 P∪P’ 中选出 n 个个体, 代替 P
    
    end
    输出最终种群 P 中的**非支配个体**
    
    

    在这里插入图片描述

    2.快速非支配排序

    传统的NSGA排序方法:计算复杂度O(MN3) ,M为目标个数,N为种群大小。计算第一帕累托前沿时,每个解都要与其他N-1个解比较M次,即比较次数为M*(N-1)*N,则计算的复杂度为O(MN2),
    如果按照最坏的打算来看的话,即每个解占一个前沿,每个前沿中只有一个解的时候,则计算的复杂度是O(MN3)。
    在经过改进的NSGA-II的快速非支配算法中,计算的复杂度为O(MN2).
    在上篇博客已经写到支配和非支配之间的关系以及表示形式,不熟悉的可以看上一篇博客。
    在这里插入图片描述

    符号含义:
    •种群:P(大写)
    •个体:p,q
    •NP:支配个体p的个体数量
    •SP:被个体p支配的个体集合
    在这里插入图片描述
    根据上图我们可以分析到对于每个种群P而言,p是属于P中的,SP所支配的集合不为空,NP一开始为0,如果p支配于q,那么个体q将并入Sp集合中,如果p被q支配,那么NP自动加一,如果NP为0,那么将是帕累托第一前沿,将p并入F1(第一帕累托前沿)。接着,访问帕累托最优解中S的集合中的解,对每个个体p被访问后,则所支配的个体q,Nq减一,Qrank=i+1。其中若有解对应n值为0,则保存至下一前沿面Frank+1 ,重复上一步骤,直到所有解都划分到对应的前沿面中。在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    同理可得出以下的4.5.6.7.8.9各个点支配情况
    在这里插入图片描述
    我们可以看出1,2,3号点并没有被支配,所以为第一帕累托前沿Np为0,同理可得,4号点被1,2号支配,Np为2,以此类推,N5=3,N6=2,N7=5,N8=6,N9=5。通过下面这张图,通过这张可以非常直观的看到NP和SP的具体情况。
    在这里插入图片描述
    对于4号点,当1号点进行确定后,则1号多支配的4,5,7,8,9的NP-1
    在这里插入图片描述
    以此类推,则可以看到下图,以及Frank的情况
    在这里插入图片描述

    3.拥挤比较算子

    拥挤度

    目的 同一层非支配个体集合中,为了保证解的个体能均匀分配在Pareto前沿,就需要使同一层中的非支配个体具有多样性,否则,个体都在某一处“扎堆”。NSGA—II采用了拥挤度策略,即计算同一非支配层级中某给定个体周围其他个体的密度。

    计算 每个个体的拥挤距离是通过计算与其相邻的两个个体在每个子目标函数上的距离差之和来求取
    在这里插入图片描述
    在这里插入图片描述
    就是在目标变量空间,两个个体在每个子目标函数上的距离差之和来求取拥挤距离。
    在这里插入图片描述
    经过快速非支配排序和拥挤度计算之后,种群中每个个体拥有两个属性:非支配等级ⅈrank和拥挤度id
    定义偏序<n如下:
    在这里插入图片描述

    4.精英策略

    在这里插入图片描述
    在父代种群p和t代产生的新种群Q中,通过非支配排序可以选择出帕累托最优解靠前的前沿面Z1,Z2,对于Z3来说,整体数量已经超过N,可以通过拥挤度比较算子来选择比较优越的个体,从而淘汰不够优越的个体,最终使得父代获得一个整体为N 的个体数量。

    总结

    这是我个人理解的NSGA-II算法大概思想,希望能够帮到大家,也是初学多目标优化算法,如果有一些不对的地方还请大佬们进行批评指正,同时也借鉴了https://blog.csdn.net/qq_35414569/article/details/79639848 这篇博客,使我受益匪浅。

    展开全文
  • 多目标优化算法(一):知识储备

    千次阅读 2021-01-30 19:08:33
    多目标优化算法(一):知识储备 算法小白第一次记笔记,多多指教! 注:我最近在研读向毅博士的毕业论文,以下知识点来自其博士论文,但是也有我自己的理解与总结。在此附上论文的百度学术链接:...

    算法小白第一次记笔记,多多指教!
    注:我最近在研读向毅博士的毕业论文,以下知识点来自其博士论文,但是也有我自己的理解与总结。在此附上论文的百度学术链接:https://xueshu.baidu.com/usercenter/paper/show?paperid=1g5806j0910a00p0rd3g0ax0r5437805&site=xueshu_se

    目录

    1. 智能优化算法的优势
    2. 优化问题的分类
    3. 高维多目标演化算法的分类(MaOEAs)
    4. 多目标优化问题基本定义
    5. 多目标测试问题集
    6. 多目标算法性能评价指标

    智能优化算法的优势

    与数学方法相比,演化算法和基于群集智能算法的优势为:

    1. 不要求当前问题具有较好的解析性质,如可导,连续等;
    2. 可处理大规模,甚至极为复杂的搜索空间;
    3. 基于种群(或群体)特性,使算法单次运行即可产生真实帕累托前沿近似解集。

    优化问题的分类

    在科学研究及工程实践中,人们往往会遇到各种优化问题。一般来说,这些优化问题被分为单目标优化问题和多目标优化问题。

    1. 单目标优化问题(Single-objective optimization problem,SOPs) :待优化的目标只有一个;一个问题对应一个最优解。
    2. 多目标优化问题(Multi-objective optimization problem,MOPs):至少存在两个目标,且各目标之间往往冲突,即一个目标的改善通常会导致至少一个其它目标的退化。当目标个数超过3,称为高维多目标优化问题(Many-objective optimization problem,MaOPs)

    高维多目标演化算法的分类(MaOEAs)

    1. 基于改进的Pareto支配算法:比较个体时考虑目标真实值;比较个体时考虑各目标比较的优劣数。缺点是涉及问题相关控制参数。
    2. 基于改进多样性维护方法的算法:代表性算法如GrEA(引入3个准则维护多样性),SDE(基于转换的密度评估策略)。缺点是过分强调多样性可能会对收敛性造成影响。
    3. 基于分解的算法::常采用一组权向量(或参考方向)和特定成就标量函数(ASF)将多目标问题转化为一系列标量子问题。缺点是需在高维目标空间生成一组分布均匀的权向量。代表性算法框架是MOEA/D。
    4. 基于性能指标的算法:常用的指标为HV,IGD,R2等。缺点是计算效率低下。
    5. 其它类别的高维多目标演化算法:基于新算法框架的算法,基于目标降维的算法,基于用户偏好的算法等。

    多目标优化问题基本定义

    1. Pareto最优:在比较解的优劣时,单目标优化直接根据适应度值大小比较不同解的优劣,但是多目标优化中目标值不只一个,根据某一个目标值决定优劣关系是不合理的,常用的比较方法是非支配排序法。

    2. Pareto支配:图中给出一个双目标最小化的例子,B和A比较时,B的两个目标值都比A好,因此B肯定比A好,则称B支配A;B和C比较时,B的第一个目标比C好,但是第二个目标比C差,此时无法判断B和C哪个更好,则称B和C是互不支配的关系。
      在这里插入图片描述

    3. Pareto前沿:在一个种群中,存在一个不被其他任何个体支配的解集,这个解集在目标空间的映射称为Pareto前沿(PF)。
      在这里插入图片描述

    4. Pareto解集:相应地,在决策空间称为帕累托解集(PS)。
      在这里插入图片描述

    多目标测试问题集

    为了验证进化多目标算法(EMO)的性能,学者们设计了众多测试问题。这些测试问题的设计主要参考以下性质:
    –决策变量和目标个数可调
    –PS形状多样
    –PF形状多样
    –真实PS和PF已知
    –等效最优解集个数可调
    –具有全局和局部最优解集

    常用的基准测试函数集

    1. DTLZ(7个问题)
      –所有问题均可分
      –可任意设定决策变量和优化目标的个数
      –DTLZ1的PF是一个超平面
      –DTLZ2是一个相对简单问题
      –DTLZ3非常适合检验算法收敛性
      –DTLZ4使得一般EMO算法难以获得分布广泛的最终解集
      –DTLZ5,6是退化的曲面,可检测算法在高维目标空间搜索低维PF的能力
      –DTLZ7可用于检测算法是否具备有效处理不连续PF的能力
      文献:Deb K, Thiele L, Laumanns M, et al. Scalable test problems for evolutionary multiobjective optimization. Springer, 2005.

    2. WFG(9个问题)
      –可任意设定决策变量和优化目标的个数
      –大多数问题不可分
      –引入更多问题特性:单峰/多峰,有偏/无偏,欺骗性/无欺骗性,凹状/凸状,退化/非退化等
      文献:Huband S, Hingston P, Barone L, et al. Areview of multiobjective test problems and a scalable test problem toolkit. IEEE Transactions on Evolutionary Computation, 2006, 10(5):477–506.

    3. DTLZ-1/WFG-1
      –在原始DTLZ和WFG测试问题各目标函数前乘以(-1)即可,其目的在于获得反转的PF
      –该测试问题的主要目的在于测试EMO算法处理凸状PF的能力
      文献:Ishibuchi H, Setoguchi Y, Masuda H, et al. Performance of Decomposition-Based
      Many-Objective Algorithms Strongly Depends on Pareto Front Shapes. IEEE Transactions on Evolutionary Computation, 2017, 21(2):169–190.

    4. MMF suite
      –不可任意设定决策变量和优化目标的个数
      –PF的几何形状为凸/凹/线性
      –PS的几何形状为曲线段
      –PS个数不可调
      –函数比较简单
      文献:J. J. Liang, W. Xu, C. Yue, K. Yu, H. Song, O. D. Crisalle, and B. Qu, “Multimodal Multiobjective Optimization with Diffierential Evolution,” Swarm and Evolutionary Computation, vol. 44, no. 2019, pp. 1028-1059, 2018.

    5. SYM-PART
      –不可任意设定决策变量和优化目标的个数
      –PF的几何形状为凸
      –PS的几何形状为直线段
      –PS个数不可调
      –函数比较简单
      文献:G. Rudolph, B. Naujoks, and M. Preuss, “Capabilities of EMOA to Detect and Preserve Equivalent Pareto Subsets,” International Conference on Evolutionary Multi-Criterion Optimization, pp. 36-50, 2007.

    6. Omini-test
      –可任意设定决策变量个数
      –不可任意设定优化目标个数
      –PF的几何形状为凸
      –PS的几何形状为直线段
      –PS个数可调
      –函数比较简单
      文献:K. Deb, and S. Tiwari, “Omni-Optimizer: A Procedure for Single and Multi-Objective Optimization,” International Conference on Evolutionary Multi-Criterion Optimization, pp. 47-61, 2005.

    多目标算法性能评价指标

    在多目标优化中,性能指标用于评估算法最终解集的质量。随着EMO研究领域的不断发展壮大,研究人员提出了众多性能指标。这些性能指标的设计主要被期望具有以下性质:
    –可量化
    –可解释性
    –实用性强
    –计算简单

    常用的性能指标

    1. IGDX
    2. IGDF
    3. HV/rHV
    4. PSP/rPSP
    5. Generalized SPREAD
    6. Peak Ratio(适用于单目标优化)
    7. Success Rate(适用于单目标优化)
    展开全文
  • 多目标优化算法】自适应粒子群算法APSO,2009

    千次阅读 热门讨论 2019-05-04 16:17:44
    自适应粒子群算法(APSO) 算法 PSO算法面临的两个最大的问题是收敛的速度和陷入局部最小值。针对此种情况,詹志辉教授基于标准的PSO提出了三个方式进行改进,分别是进化状态评估(ESE)、系统自适应参数(惯性权重...
  • 进化多目标优化算法学习综述

    千次阅读 2019-03-13 17:19:23
    最初,多目标优化问题→通过加权等方式转化为单目标问题→用数学规划求解。 这样每次只能得到一种权值下的最解。而且MOP的目标函数、约束函数可能是非线性、不可谓、不连续的,传统的数学规划效率低,并且它们...
  • 多目标优化-Pareto遗传算法

    千次阅读 多人点赞 2019-10-25 16:02:17
    这里写自定义目录标题多目标优化的应用背景遗传算法自适应遗传算法Pareto遗传算法Pareto遗传算法的求解 这里写自定义目录标题多目标优化的应用背景遗传算法自适应遗传算法Pareto遗传算法Pareto遗传算法的求解遗传...
  • 论文研读-基于变量分类的动态多目标优化算法

    千次阅读 热门讨论 2020-06-19 14:48:44
    论文研读-基于变量分类的动态多目标优化算法 A Dynamic Multiobjective Evolutionary Algorithm Based on Decision Variable Classification 觉得有用的话,欢迎一起讨论相互学习~ 此篇文章为 Liang Z , Wu T , Ma ...
  • 多目标优化问题的算法及其求解

    万次阅读 多人点赞 2018-09-06 17:32:58
    多目标优化问题的算法及其求解 一、多目标优化问题 ...将这两者结合起来,能够利用遗传算法的全局搜索能力,避免传统的多目标优化方法在寻过程中陷入局部最解,可以使解个体保持多样性。...
  • 多目标优化算法(二)MOEAD及MOEAD与NSGA-Ⅱ的对比

    万次阅读 多人点赞 2018-10-09 21:17:27
    前言 这个算法是本人接触科研学习实现的第二个算法,除了单纯实现此算法外,还与NSGA-Ⅱ进行了对比,复现了李青富老师的论文,一下是具体的内容,结尾附上MATLAB代码供读者参考。 ...
  • 将粒子群算法与局部优化方法相结合,提出了一种混合粒子群多目标优化算法(HMOPSO)。该算法针对粒子群局部优化性能较差的缺点,引入目标线搜索与粒子群算法相结合的策略,以增强粒子群算法的局部搜索能力。HMOPSO...
  • 以不同性能指标的最优组合作为总体目标,采用逐步回归分析和复形调法,建立混凝土配合比的非线性多目标优化模型。通过变量的高阶化以及目标和约束系统的柔性化,以克服线性规划中变量取值范围狭小、目标和约束函数...
  • 多目标遗传算法优化

    万次阅读 热门讨论 2017-03-31 20:29:37
    %% 遗传算法求解多目标优化案例 %% 将原目标函数改写为f1=(x^2+y^2)/4;f2=x(1-y)+10; % 运用线性叠加法,F=a*f1(x)+b*f2(x) ,a+b=1 % 总目标函数改写为 f=0.6*(x^2+y^2)/4+0.4*(x*(1-y)+10); popse=100; % ...
  • 为提高目标粒子群优化(MOPSO)算法处理多目标优化问题的性能,降低计算复杂度,改善算法的收敛性,提出了一种改进的目标粒子群优化算法。通过运用比例分布及跳数改进机制策略的方法,使该算法不仅继承了MOPSO...
  • 目标&多目标 灰狼算法算法讲解

    千次阅读 2019-10-05 11:38:03
    1. 灰狼算法思想 2. 单目标灰狼算法 3. 多目标灰狼算法
  • In the Multi-Objective Grey Wolf Optimizer (MOGWO), a fixed-sized external archive is integrated to the GWO for saving and retrieving the Pareto optimal solutions. This archive has been employed to ...
  • 多目标优化NSGA算法

    2012-07-19 15:04:05
    该NSGA源代码由Srinivas, N.和Deb, K用c语言编写,可直接运行
  • 粒子群优化算法因形式简洁、收敛快速和参数调节机制灵活等优点,同时一次运行可得到个解,且能逼 近非凸或不连续的 Pareto 最优前端,
  • MOPSO 多目标粒子群优化算法

    千次阅读 多人点赞 2016-03-06 14:22:00
    有代表性的多目标优化算法主要有NSGA、NSGA-II、SPEA、SPEA2、PAES和PESA等。粒子群优化(PSO)算法是一种模拟社会行为的、基于群体智能的进化技术,以其独特的搜索机理、出色的收敛性能、方便的计算机实现,在工程...
  • 关于多目标遗传算法的实现 有详细的介绍与实现方案
  • 为了解决多目标灰狼优化算法(MOGWO)易陷入局部最优,稳定性差等缺点,基于对算法寻优时灰狼个体运动情况的分析,提出了两条改进策略:一是通过引入“观察”策略赋予灰狼个体自主探索的能力,以提高算法的优化效率...
  • 针对在传统飞行控制系统控制器参数整定问题中单目标优化不能同时满足个控制指标要求的缺点,提出了一种基于改进的NSGA-II算法目标进化算法。在改进的NSGA-II算法中,提出了改进的精英保留策略增强算法收敛性;...
  • 优化算法】简述灰狼优化算法(GWO)原理

    万次阅读 多人点赞 2019-03-25 21:10:34
    系列优化算法简述: OP_1. 简述遗传算法(GA)原理 OP_2 简述灰狼优化算法(GWO)原理 前言: 灰狼优化算法(Grey Wolf Optimizer,GWO)由澳大利亚格里菲斯大学学者 Mirjalili 等人于2014年提出来的一种群智能...
  • 为降低微电网运行成本和污染排放,建立微电网多目标优化运行模型,并提出一种新型的α约束支配排序混合进化算法求解模型,该算法通过采用α约束支配排序机制,将所有约束条件统一处理为α约束水平度,并将其作为进化...
  • 多目标进化算法nsga2

    2020-04-22 10:18:43
    NSGA-Ⅱ是最流行的目标遗传算法之一,它降低了非劣排序遗传算法的复杂性,具有运行速度快,解集的收敛性好的优点,成为其他多目标优化算法性能的基准。NSGA-Ⅱ就是在第一代非支配排序遗传算法的基础上改进而来,其...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 101,890
精华内容 40,756
关键字:

多目标优化算法的优点