多目标优化算法 订阅
《多目标智能优化算法及其应用》系统地介绍了多目标智能优化算法理论与应用,力图全面地介绍多目标智能优化算法的最新研究进展。全书共分为8章,主要内容包括:多目标进化算法、多目标粒子群算法、其他多目标智能优化算法、人工神经网络优化、交通与物流系统优化、多目标生产调度和电力系统优化及其他。 [1] 展开全文
《多目标智能优化算法及其应用》系统地介绍了多目标智能优化算法理论与应用,力图全面地介绍多目标智能优化算法的最新研究进展。全书共分为8章,主要内容包括:多目标进化算法、多目标粒子群算法、其他多目标智能优化算法、人工神经网络优化、交通与物流系统优化、多目标生产调度和电力系统优化及其他。 [1]
信息
作    者
雷德明严新平
定    价
75.00
装    帧
平装
丛书名
智能科学技术著作丛书
书    名
多目标智能优化算法及其应用
出版时间
2009年
开    本
16
出版社
科学出版社
ISBN
9787030236944
页    数
389 页
多目标智能优化算法及其应用简介
《多目标智能优化算法及其应用》可作为计算机、自动控制、人工智能、管理科学和工业工程等专业的研究 生及高年级本科生教材,也可作为从事计算智能、生产调度等研究人员和工程技术人员的参考书。
收起全文
精华内容
下载资源
问答
  • 多目标优化算法(一)NSGA-Ⅱ(NSGA2)

    万次阅读 多人点赞 2018-09-28 20:39:42
    多目标优化算法(一)NSGA-Ⅱ 0.前言 这个算法是本人接触科研学习实现的第一个算法,因此想在这里和大家分享一下心得。 1. 算法简介 NSGA-Ⅱ算法,即带有精英保留策略的快速非支配多目标优化算法,是一种基于Pareto...

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

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

    0. 前言

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

    1. 算法简介

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

    1.1 Pareto支配关系以及Pareto等级

    Pareto支配关系:对于最小化多目标优化问题,对于n个目标分量 fi(x),i=1...nf_i(x), i=1...n,任意给定两个决策变量XaX_aXbX_b,如果有以下两个条件成立,则称XaX_a支配XbX_b
    1.对于i1,2,...,n\forall i \in {1,2,...,n},都有fi(Xa)fi(Xb)f_i(X_a) \leq f_i(X_b)成立。
    2.i1,2,...,n\exists i \in {1,2,...,n},使得fi(Xa)<fi(Xb)f_i(X_a) <f_i(X_b)成立。
    如果对于一个决策变量,不存在其他决策变量能够支配他,那么就称该决策变量为非支配解。
    Pareto等级:在一组解中,非支配解Pareto等级定义为1,将非支配解从解的集合中删除,剩下解的Pareto等级定义为2,依次类推,可以得到该解集合中所有解的Pareto等级。示意图如图1所示。
    在这里插入图片描述

    1.2 快速非支配排序

    假设种群大小为P,该算法需要计算每个个体p的被支配个数npn_p和该个体支配的解的集合SpS_p这两个参数。遍历整个种群,该参数的计算复杂度为O(mN2)O(mN^2)。该算法的伪代码如下:
    1.计算出种群中每个个体的两个参数npn_pSpS_p
    2.将种群中参数np=0n_p=0的个体放入集合F1F_1中。
    3.for 个体iF1i \in F_1:
            for 个体lSil \in S_i
                   nl=nl1n_l=n_l-1;(该步骤即消除Pareto等级1对其余个体的支配,相当于将Pareto等级1的个体从集合中删除)
                    if nl=0n_l=0
                           将个体l加入集合F2F_2中。
                    end
            end
    end
    4.上面得到Pareto等级2的个体的集合F2F_2,对集合F2F_2中的个体继续重复步骤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 拥挤度

    为了使得到的解在目标空间中更加均匀,这里引入了拥挤度ndn_d,其算法如下:

    1. 令参数nd=0n1Nn_d=0,n∈1…N
    2. for 每个目标函数fmf_m
              ① 根据该目标函数对该等级的个体进行排序,记fmmaxf_m^{max}为个体目标函数值fmf_m的最大值,fmminf_m^{min}为个体目标函数值fmf_m的最小值;
              ② 对于排序后两个边界的拥挤度1d1_dNdN_d置为∞;
              ③ 计算nd=nd+(fm(i+1)fm(i1))/(fmmaxfmmin)n_d=n_d+(f_m (i+1)-f_m (i-1))/(f_m^{max}-f_m^{min}),其中fm(i+1)f_m (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.首先将父代种群CiC_i和子代种群DiD_i合成种群RiR_i
    2.根据以下规则从种群RiR_i生成新的父代种群Ci+1C_{i+1}
          ①根据Pareto等级从低到高的顺序,将整层种群放入父代种群Ci+1C_{i+1},直到某一层该层个体不能全部放入父代种群Ci+1C_{i+1}
          ②将该层个体根据拥挤度从大到小排列,依次放入父代种群Ci+1C_{i+1}中,直到父代种群Ci+1C_{i+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)

    模拟二进制交叉:
    x1j(t)=0.5×[(1+γj)x1j(t)+(1γj)x2j(t)]x _{1j}(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)]x _{2j} (t)=0.5×[(1-γ_j ) x_{1j}(t)+(1+γ_j ) x_{2j}(t)]
    其中
    γj={(2uj)1/(η+1)                        uj<0.5(1/(2(1uj))1/(η+1)        elseγ_j=\left\{\begin{matrix}(2u_j)^{1/(η+1)}\;\;\;\;\;\;\;\;\;\;\;\;u_j<0.5 \\ (1/(2(1-u_j))^{1/(η+1)}\;\;\;\;else \end{matrix}\right.

    1.6 多项式变异(polynomial mutation)

    多项式变异:
    x1j(t)=x1j(t)+jx _{1j} (t)=x_{1j} (t)+∆_j
    其中
    j={(2uj)1/(η+1)1                        uj<0.5(1(2(1uj))1/(η+1)        else∆_j=\left\{\begin{matrix}(2u_j)^{1/(η+1)}-1\;\;\;\;\;\;\;\;\;\;\;\;u_j<0.5 \\ (1-(2(1-u_j))^{1/(η+1)}\;\;\;\;else \end{matrix}\right.
    并且0≤uju_j≤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. 实验结果

    本文使用实数编码的模拟二进制交叉和多项式变异,交叉概率pc=0.9p_c=0.9,变异概率pm=1/np_m=1/nηc=20η_c=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

    f1=x1f_1=x_1
    g=1+9((i=2nxi)/(n1))g=1+9((∑_{i=2}^nx_i )/(n-1))
    f2=g(1(f1/g)0.5).n=30,xi[0,1]f_2=g(1-(f_1/g)^{0.5} ).n=30,x_i∈[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

    f1=x1f_1=x_1
    g=1+9((i=2nxi)/(n1))g=1+9((∑_{i=2}^n x_i )/(n-1))
    f2=g(1(f1/g)2).n=30,xi[0,1]f_2=g(1-(f_1/g)^2 ).n=30,x_i∈[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

    f1=x1f_1=x_1
    g=1+9((i=2nxi)/(n1))g=1+9((∑_{i=2}^nx_i )/(n-1))
    f2=g(1(f1/g)0.5(f1/g)sin(10πf1)).n=30,xi[0,1]f_2=g(1-(f_1/g)^{0.5}-(f_1/g)sin⁡(10πf_1)).n=30,x_i∈[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

    f1=x1f_1=x_1
    g=1+910+i=2n((xi)210cos(4πxi))g=1+9*10+∑_{i=2}^n( (x_i )^2-10cos⁡(4πx_i))
    f2=g(1(f1/g)0.5).n=10,x1[0,1];x(26)[5,5]f_2=g(1-(f_1/g)^{0.5} ).n=10,x_1∈[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

    f1=1e4x1sin6(6πx1)f_1=1-e^{-4x_1} sin^6 (6πx_1)
    g=1+9((i=2nxi)/(n1))0.25g=1+9((∑_{i=2}^nx_i )/(n-1))^{0.25}
    f2=g(1(f1/g)2).n=10,xi[0,1]f_2=g(1-(f_1/g)^2 ).n=10,x_i∈[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.

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

    2012-03-05 13:45:07
    当前多目标优化的研究趋势,一方面,粒子群优化、人工免疫系统、分布估计算法等越来越多的进化范例被引入多目标优化领域,一些新颖的受自然系统启发的多目标优化算法相继提出;另一方面,为了更有效的求解高维多 目标优化...
  • MOALO优化算法——多目标蚁狮优化算法:一种求解工程问题的多目标优化算法
  • 多目标优化算法——多目标粒子群算法实战分享

    万次阅读 多人点赞 2019-03-09 12:34:24
    运筹学优化领域,多目标优化算法,多目标自适应粒子群优化算法;并简要介绍了开源多目标优化算法框架jMetal。 基本的粒子群优化算法可参照博主的一篇文章粒子群算法实战分享-附原版动画PPT(技术分享也可以文艺范...

    版权声明:本文为博主原创文章,未经博主允许不得转载。

    运筹学优化领域,多目标优化算法,多目标自适应粒子群优化算法;并简要介绍了开源多目标优化算法框架jMetal。
    基本的粒子群优化算法可参照博主的一篇文章粒子群算法实战分享-附原版动画PPT(技术分享也可以文艺范?)

    PPT下载地址:《多目标粒子群算法分享 - CSDN博主dkjkls》

    参考文献:
    杨俊杰. 基于MOPSO和集对分析决策方法的流域梯级联合优化调度[D]. 华中科技大学, 2007.

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述


    --------------------------文档信息--------------------------
    版权声明:本文为博主原创文章,未经博主允许不得转载
    署名(BY) :dkjkls(dkj卡洛斯)
    文章出处:http://blog.csdn.net/dkjkls

    展开全文
  • 基于参考点的非支配排序方法的进化多目标优化算法NSGA-III算法Deb K , Jain H . An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: ...

    基于参考点的非支配排序方法的进化多目标优化算法NSGA-III算法

    Deb K , Jain H . An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints[J]. Evolutionary Computation, IEEE Transactions on, 2014, 18(4):577-601.

    摘要

    已经使用进化优化方法开发了多目标优化算法,并展示了它们在涉及两个和三个目标的各种实际问题上的优势,现在越来越需要开发进化多目标优化(EMO)算法来处理多目标(具有四个或更多目标)优化问题。作者提出基于参考点的多目标NSGA-II,称之为NSGA-III,强调非主导但接近一组提供的参考点的总体成员。提出的NSGA-III适用于许多具有2到15个目标的多目标测试问题,并与最近提出的一些EMO算法(MOEA / D)的两个版本进行了比较。虽然两种MOEA / D方法在不同类别的问题上均能很好地发挥作用,但发现我们提出的的NSGA-III在本研究中考虑的所有问题上都能产生令人满意的结果。

    核心

    基于多目标算法NSGA-II的基础上,提出了中参考点的方法,强调种群成员是非支配的并且与所提供的参考点距离很近。主要用于在处理超目标优化问题中解决非约束条件和约束条件下。

    动机

    首先,非支配解的比例在随机选择目标向量集中与目标的数量呈指数相关(非支配解的比例随目标数量的增加而成指数增长),因为非支配解占据了种群中大部分位置,任何精英保护的EMO都很难容纳下足够数量的种群中的新解,这大大减慢了搜索过程。其次,实现多样性保存(类似于拥挤度距离和聚类)将是一项计算耗时非常大的操作。最后,超维前沿可视化是一个很困难的任务,因此导致了后续决策任务和算法性能评估的困难。总结来说,性能指标(如超维度度量或其他度量)要么在计算上太昂贵,要么没有意义。

    大多数多目标进化算法在求解目标维数较低的问题时较为有效,当目标数目大于等于3的时候,也就是面对高维目标优化问题,很多方法由于维数增多选择压力下降,效果变得不理想。NSGA-III的框架基本和NSGA-II相同,同样利用快速非支配排序将种群个体分类进入不同的非支配前沿,不同的是:对于在临界层中的环境选择,NSGA-II的方法是利用拥挤比较操作来选择从而保持多样性,NSGA-III最大的变化就是利用良好分布的参考点来保持种群的多样性。在选择过程中,将拥挤度距离改为参考点法(因为我们要解决的是超目标优化问题,NSGA-II中的拥挤度距离法在平衡算法的多样性和收敛性表现得并不好),限制于解决各种无约束问题,如归一化、缩放、凸、凹、收敛于PF面的一段。

    1.参考点的产生

    参考点既可以以结构化的方法预定义也可以由使用者提前提供。论文中使用的是Das and Dennis提出的边界交叉构造权重的方法,将参考点放在一个标准化的超平面上。

    在目标空间中,一个维度为(M-1)标准单纯形(如3目标的话,那么该单纯形就是个平面),它对所有的目标轴都有相同的倾斜度。如果考虑沿着每个目标方向分为p份,参考点H的总数就可以计算出来。比如在一个三目标(M=3)的问题中,参考点在一个顶点为(1,0,0),(0,1,0)和(0,0,1)的三角形上产生。如果每个目标轴分为4部分(p=4),那么参考点的个数H=15。

    a268db74b6344e098ca06ba1202f1c4b.png

    计算公式如下:

    其中M为目标数目,p为每个方向上分割的份数。

    4c1ac63841a21959faff0a58736343e1.png

    但是,该方法有一个严重的缺点,就是分割份数p的大小的会影响中间点产生的情况,而如果想产生中间点,在目标维度较大的情况下,参考点数量则会急剧增加,因此为了避免这种情况,论文提出采用两层参考点产生方法,增加了内层,这样既能保证中间点的产生也不会使得参考点数目过多。

    解释NSGA-III中定义参考点和NSGA-II中使用拥挤距离的区别,随机生成N个个体的初始种群,N为种群大小。P{t}为第t代时的种群,Q{t}为P{t}经过交叉、变异(参考遗传算法)后生成的种群,R{t}为两种群之和。显然,R{t}和Q{t}的大小都为N,R{t}的大小为2N,此时将R{t}中非支配排序的解放入S{t}中,若S_{t}的大小刚好为N,则相安无事。若小于N,那么继续寻找下一个非支配层,直到首次大于N。

    参考点法:假设F{l}为S{t}中首次大于N层的最后一个非支配层,其中{F{1},F{2},…,F{n-1}}为前面的非支配层,参考点法的目的就是为了找出F{l}中的N-S{t}个最优个体,并入到S{t+1}中。

    6967b3b2334611bdfaf57b2089b0187a.png

    2. 标准化目标空间

    也就是种群成员的自适应标准化,在这个过程中较难理解的是极值点是如何得到的,下面简述大体步骤,重点分析极值点的产生。

    d244b703a38e47251be4aab61e6b4381.png

    162e80573e88be6497fe2e0a7c794b31.png

    2e6785860aa5f0bc59931f48fd05e778.png

    以最小化为例,首先得到种群St中的所有个体在每一维目标上的最小值,构成当前种群的理想点,然后将所有个体的目标值,以及理想点以此理想点为参考作转换操作,这时理想点变为原点,个体的目标值为转换后的临时标准化目标值。然后计算每一维目标轴上的极值点,这M个极值点组成了M-1维的线性超平面,这时可以计算出各个目标方向上的截距。然后利用截距和临时的标准化目标值计算真正的标准化目标值:

    08631e9f105d926c1f28b4c6d64c74cd.png

    其中ai为各维目标方向上的截距。针对三个目标问题,显示了计算截距然后从极点形成超平面的过程。

    下面详叙极值点的产生方法:

    计算每维目标方向(目标函数)上的极值点,就是在该维上目标值很大,在其他维度上很小的点所对应的个体所对应的目标值。

    010ac14060733c64f7fa5f50e997c768.png

    论文中利用将权重向量w作为坐标轴方向的achievement scalarizing function得到极值点:为了计算第i维目标轴上的极值点,需要固定一个目标方向,则该方向向量wi=1,其他方向的权重设为10e-6无限接近0,则权重向量w = (1,10e-6,…)固定了,然后将下面的ASF函数作为目标函数进行最小化求解,得到的就是该目标方向上的极值点,ASF函数:

    举个3目标的例子,解释该过程:我们初始化种群后,会得到很多个体,他们的目标值可能是(1,0.4,0.5),(2,4,0.8),(0.3,0.6,5)等等,如果有一些点如果在某个目标上的值很大,在另外两个目标上的值很小,则这类点更靠近该目标轴,它们就是所谓的极值点,目标就是找到在一个方向上值很大,另外两个目标值很小的点,但是我们可能得到很多这样的点,这样就需要选择其中最小的作为极值点,所以是一个最小化问题。三个目标的问题话可以找到三个这样的极值点。在ASF方程中,固定第一个坐标轴,权重向量w =(1,10e-6, 10e-6),那么(1,0.4,0.5)/w,这个时候最大的肯定是0.5这个方向,得到值0.5 x 10e-6。另外两个点同样计算得到:(2,4,0.8)在ASF后变为0.8 x 10e-6,(0.3,0.6,5)在ASF后变为0.6 x 10e-6,然后选取这三个值中最小的对应的点作为极值点,可知:0.5 x 10e-6是最小的,对应(1,0.4,0.5)是最合适的极值点。我理解的是:因为我们得到的极值点是想更靠近该目标方向的坐标轴。

    3、关联操作

    adee8b8f588b9d30b84c3a7a0f655179.png

    参考点设置完成后,要进行关联操作,我们要让种群中的个体分别关联到相应的参考点。为了这个目的,我们定义一个参考线,它是原点与参考点在目标空间的连线。有了参考线后,我们计算种群St的每个个体到参考线的垂直距离。然后个体与和它最近的参考线关联起来。

    4.环境选择操作

    这是从临界层FL中选择k个个体加入到下一父代Pt+1的操作。在上面的关联操作后,可能会出现以下情况:

    1.参考点关联一个或多个个体;

    2.没有一个个体与之关联。

    NSGA-III记录了参考点在集合Pt+1=St/FL中所关联的个体数目,将这个小生境计数记为ρj,它是第j个参考点关联的个体数目。个体保留操作:首先我们选择ρj最小的参考点,如果有多个这样的点,那么随机选择一个即可。如果ρj=0,就表示集合Pt+1=St/FL中没有与之关联的点。

    那么在FL中会出现以下两种情况:

    (1)在FL中存在一个或多个个体与之关联,则将离它最近的个体与之关联,并将该个体加入到Pt+1中;

    (2)在FL中不存在个体与他关联,那么在余下的操作中就不考虑该参考点。如果ρj≥1,表示Pt+1=St/FL中已经有一个个体与该参考点关联,如果FL中有个体与之关联,随机选择一个,将该个体加入到Pt+1中。重复以上操作指导Pt+1的大小等于N。

    总结

    在看NSGA-III的论文时,感觉归一化(Adaptive Normalization of Population Members)这一部分比较难理解,特别是里面提到的ASF函数。我觉得可以一边看论文,一边看NSGA-III的代码实现,加深理解。

    大多数多目标进化算法在求解目标维数较低的问题时较为有效,当目标数目大于等于3的时候,也就是面对高维目标优化问题,很多方法由于维数增多选择压力下降,效果变得不理想。NSGA-III的框架基本和NSGA-II相同,同样利用快速非支配排序将种群个体分类进入不同的非支配前沿,不同的是:对于在临界层中的环境选择,NSGA-II的方法是利用拥挤比较操作来选择从而保持多样性,NSGA-III最大的变化就是利用良好分布的参考点来保持种群的多样性。

    展开全文
  • matab代码基于遗传算法的多目标优化算法
  • 通过混合多目标优化算法优化本体映射结果
  • 提出趋磁性细菌多目标优化算法(MTBMO). 该算法以趋磁性细菌优化算法(MBOA) 中磁小体(MTSs) 的生成机制为基础, 设计适用于多目标优化的新型MTSs 磁矩调节机制, 确保群体的收敛性; 同时采用基于混沌变异的替换方法取代...
  • 基于邻域竞赛的多目标优化算法
  • 首先针对常规多目标优化算法求解高维多目标优化时面临的选择压力衰减问题进行论述;然后针对该问题,按照选择机制的不同详细介绍基于Pareto支配、基于分解策略和基于性能评价指标的典型高维多目标优化算法,并分析各自...
  • 大多数工程和科学问题都是多目标优化问题,从本专业的角度来说,例如建筑运行节能与室内光热舒适的权衡、能源系统的经济效益与碳排放的权衡等。存在如此多个彼此冲突的目标,如何获取这些问题的最优解,一直都是学术...

    大多数工程和科学问题都是多目标优化问题,从本专业的角度来说,例如建筑运行节能与室内光热舒适的权衡、能源系统的经济效益与碳排放的权衡等。

    存在如此多个彼此冲突的目标,如何获取这些问题的最优解,一直都是学术界和工程界关注的焦点问题。与单目标优化问题不同,多目标优化的本质在于,大多数情况下,某目标的改善可能引起其他目标性能的降低,同时使多个目标均达到最优是不可能的,只能在各目标之间进行协调权衡和折中处理,使所有目标函数尽可能达到最优,而且问题的最优解由数量众多,甚至无穷大的Pareto最优解组成。

    智能优化算法是一类通过模拟某一自然现象或过程而建立起来的优化方法,和传统的数学规划法相比,智能优化算法更适合求解多目标优化问题。首先,大多数智能优化算法能同时处理一组解,算法每运行一次,能获得多个有效解。其次,智能优化算法对Pareto最优前端的形状和连续性不敏感,能很好地逼近非凸或不连续的最优前端。这类算法包括进化算法、粒子群算法、禁忌搜索、分散搜索、模拟退火、人工免疫系统和蚁群算法等。

    1.进化算法

    进化算法来源于对生物进化过程的模拟,它将问题的求解表示成染色体的适者生存过程,通过染色体的一代代进化,最终收敛到最适应环境的个体(即问题的最优解或满意解),该类算法主要包括遗传算法(GA)、进化策略(ES)和进化规划(EP)等。

    2.粒子群算法

    粒子群算法来源于对鸟群优美而不可预测的飞行动作的模拟,粒子的飞行速度动态地随粒子自身和同伴的历史飞行行为改变而改变。是在对动物集群活动行为观察基础上,利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程,从而获取最优解。

    3.禁忌搜索

    禁忌搜索是一种全局逐步优化算法,它模拟人类的智力过程,通过引入一种灵活的存储结构和相应的禁忌规则来避免迂回搜索,并通过藐视原则来赦免一些被禁忌的优良状态,进而保证多样化的有效搜索以最终实现全局优化。

    4.分散搜索

    分散搜索主要组成部分包括五个方法:多样化产生方法、改进方法、参考集更新方法、子集产生方法和组合方法等。分散搜索十分灵活,它的每个组成部分都能采取不同的方式实现。

    5.模拟退火

    模拟退火是基于Mente Carlo迭代求解策略的随机寻优算法,其出发点是固体物质的退火过程与一般组合优化问题的相似性,从某一初温开始,随着温度的降低,结合概率突跳特性在解空间中搜索最优解,即在局部解时能概率性地跳出并最终趋于全局最优。

    6.人工免疫系统

    人工免疫系统是一种模仿生物免疫系统功能的智能系统,免疫系统是—种复杂的分布式信息处理学习系统,这种系统具有免疫保护、免疫记忆、免疫学习功能以及较强的自适应性、多样性、学习、识别和记忆等特点。抗原、抗体、抗原和抗体之间的亲和度分别对应于优化问题的目标函数和各种约束条件、优化解、解与目标函数的匹配程度。

    7.蚁群算法

    蚁群算法是受自然界中蚂蚁搜索食物行为的启发而提出的一种随机优化算法,单个蚂蚁是脆弱的,而蚁群的群居生活却能完成许多单个个体无法承担的工作,蚂蚁间借助于信息素这种化学物质进行信息的交流和传递,并表现出正反馈现象:某段路径上经过的蚂蚁越多,该路径被重复选择的概率就越高。正反馈机制和通信机制是蚁群算法的两个重要基础。

    智能优化算法作为一类启发式搜索算法,已被成功应用于多目标优化领域,同时,多目标智能优化算法在电力系统、制造系统和控制系统等方面的应用研究也取得了很大的进展。

    1fcd1ce2c8b0ec697ac260a01a5234d9.png

    展开全文
  • 点击上方“蓝字”关注我们了解更多精彩多目标优化算法 — 相关定义1.相关知识科学研究和工程实践中的许多优化问题都含有多个相互矛盾的优化目标,这类问题被称为多目标优化问题(multi-objective optimization ...
  • 基于多目标优化算法的多无人机协同航迹规划
  • 基于生态策略的动态多目标优化算法
  • 欢迎关注智能优化与学习实验室在很多实际问题中,例如科学、工程设计等领域...平衡收敛性、多样性和合法性是解决约束多目标优化问题的核心挑战,下面介绍两个基于多种群协同演化的约束多目标优化算法框架。为了保持...
  • 一种新颖的基于两归档匹配的多目标和多目标优化算法
  • 元启发式多目标优化的评判指标的matlab代码,包括spread\IGD\GD\RNI从多样性、收敛性等角度评价多目标优化算法
  • 针对基于软件定义网络(SDN)的复杂结构中不同资源效用目标共存、资源选择策略相互影响的问题,提出了一种基于 SDN 的网络资源选择多目标优化算法。该算法综合考虑资源供给方和客户方对资源效用的不同优化目标,构建...
  • 研究多目标优化问题,针对提高算法的快速性,提出一种混合变异克隆选择多目标优化算法。进化在三个抗体群中进行,不同的抗体群采用不同的变异算子,并通过外部记忆抗体群的更新,来保留进化的最优抗体,避免算法进化后期...
  • 基于支配和分解的进化多目标优化算法
  • 多目标优化算法NSGAⅢMATLAB代码及注释
  • 基于离散菌落趋化性的多目标优化算法
  • MATLAB源码集锦-普通多目标优化算法代码

空空如也

空空如也

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

多目标优化算法