精华内容
下载资源
问答
  • 多目标优化

    万次阅读 多人点赞 2018-09-14 11:40:57
    最优化问题的分类 1)无约束和有约束条件;...使多个目标在给定区域同时尽可能最佳,多目标优化的解通常是一组均衡解(即一组由众多 Pareto最优解组成的最优解集合 ,集合中的各个元素称为 Pareto最优解或非劣最...

    最优化问题的分类
    1)无约束和有约束条件;
    2)确定性和随机性最优问题(变量是否确定);
    3)线性优化与非线性优化(目标函数和约束条件是否线性);
    4)静态规划和动态规划(解是否随时间变化)。


    1. 什么是多目标优化?

    使多个目标在给定区域同时尽可能最佳,多目标优化的解通常是一组均衡解(即一组由众多 Pareto最优解组成的最优解集合 ,集合中的各个元素称为 Pareto最优解或非劣最优解)。

    非劣解——多目标优化问题并不存在一个最优解,所有可能的解都称为非劣解,也称为Pareto解。
    Pareto最优解——无法在改进任何目标函数的同时不削弱至少一个其他目标函数。这种解称作非支配解或Pareto最优解。

    • 多目标优化问题的描述

    这里写图片描述

    • Pareto支配关系:

    这里写图片描述


    2. 如何实现多目标优化?有哪些方法?

    多目标优化问题不存在唯一的全局最优解 ,过多的非劣解是无法直接应用的 ,所以在求解时就是要寻找一个最终解

    (1)求最终解主要有三类方法:

    一是求非劣解的生成法,即先求出大量的非劣解,构成非劣解的一个子集,然后按照决策者的意图找出最终解;(生成法主要有加权法﹑约束法﹑加权法和约束法结合的混合法以及多目标遗传算法

    二为交互法,不先求出很多的非劣解,而是通过分析者与决策者对话的方式,逐步求出最终解;

    三是事先要求决策者提供目标之间的相对重要程度,算法以此为依据,将多目标问题转化为单目标问题进行求解

    (2)多目标优化算法归结起来有传统优化算法和智能优化算法两大类。

    传统优化算法包括加权法、约束法和线性规划法等,实质上就是将多目标函数转化为单目标函数,通过采用单目标优化的方法达到对多目标函数的求解。

    线性加权求和法——对多目标优化问题中的N个目标按其重要程度赋以适当的权系数,其乘积和作新的目标函数,再求最优解。

    智能优化算法包括进化算法(Evolutionary Algorithm, 简称EA)、粒子群算法(Particle Swarm Optimization, PSO)等。

    两者的区别——传统优化技术一般每次能得到Pareo解集中的一个,而用智能算法来求解,可以得到更多的Pareto解,这些解构成了一个最优解集,称为Pareto最优解(任一个目标函数值的提高都必须以牺牲其他目标函数值为代价的解集)。


    3. 多目标进化算法 (MOEA )

    ①MOEA通过对种群 X ( t)执行选择、交叉和变异等操作产生下一代种群 X ( t + 1) ;
    ②在每一代进化过程中 ,首先将种群 X ( t)中的所有非劣解个体都复制到外部集 A ( t)中;
    ③然后运用小生境截断算子剔除A ( t)中的劣解和一些距离较近的非劣解个体 ,以得到个体分布更为均匀的下一代外部集 A ( t + 1) ;
    ④并且按照概率 pe从 A ( t + 1)中选择一定数量的优秀个体进入下代种群;
    ⑤在进化结束时 ,将外部集中的非劣解个体作为最优解输出。

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


    这里写图片描述

    小生境技术——将每一代个体划分为若干类,每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个群,再在种群中,以及不同种群中之间,杂交,变异产生新一代个体群。同时采用预选择机制和排挤机制或分享机制完成任务。
    基于共享机制的小生境实现方法——通过反映个体之间的相似程度的共享函数来调节群体中各个个体的适应度,从而在这以后的群体进化过程中,算法能够依据这个调整后的新适应度来进行选择运算,以维持群体的多样性,创造出小生境的进化环境。
    共享函数——表示群体中两个个体之间密切关系程度的一个函数

    共享度是某个个体在群体中共享程度的一中度量,它定义为该个体与群体内其它各个个体之间的共享函数值之和,用S 表示:
    S = (i=1,… ,M)
    在计算出了群体中各个个体的共享度之后,依据下式来调整各个个体的适应度
    F(X) =F(X) / S (i=1,… ,M)

    小生境算法的描述如下:
    (1)设置进化代数计数器;随机生成M个初始群体P(t),并求出各个个体的适应度F (i=1,2,M)。
    (2)依据各个个体的适应度对其进行降序排列,记忆前N个个体(N小于M)。
    (3)选择算法。对群体P(t)进行比例选择运算,得到P (t)。
    (4)交叉选择。对选择的个体集合P (t) 作单点交叉运算,得到P (t)。
    (5)变异运算。对P (t)作均匀变异运算,得到P (t)。
    (6)小生境淘汰运算。将第(5)步得到的M个个体和第(2)步所记忆的N个个体合并在一起,得到一个含有M+N 个个体的新群体;对着M+N个个体,按照下式得到两个个体x 和x 之间的海明距离:|| x - x ||= d,当|| x - x ||小于L时,比较个体x 和个体x 的适应度大小,并对其中适应度较低的个体处以罚函数: Fmin(x,x )=Penalty。
    (7)依据这M+N个个体的新适应度对各个个体进行降序排列,记忆前N个个体。
    (8)终止条件判断。若不满足终止条件,则:更新进化代数记忆器t = t+1, 并将第(7)步排列中的前M个个体作为新的下一代群体P(t),然后转到第(3)步:若满足终止条件,则:输出计算结果,算法结束。

    NSGA使用了非支配分层方法和适应度共享策略。非支配分层方法可以使好的个体有更大的机会遗传到下一代;适应度共享策略则使得准Pareto面上的个体均匀分布,保持了群体多样性,克服了超级个体的过度繁殖,防止了早熟收敛。

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

    3.2 NSGAII(带精英策略的非支配排序的遗传算法)


    这里写图片描述

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

    非支配排序算法
    考虑一个目标函数个数为K(K>1)、规模大小为N的种群,通过非支配排序算法可以对该种群进行分层,具体的步骤如下:
    这里写图片描述

    通过上述步骤得到的非支配个体集是种群的第一级非支配层;

    然后,忽略这些标记的非支配个体,再遵循步骤(1)一(4),就会得到第二级非支配层;

    依此类推,直到整个种群被分类。

    快速非支配排序算法:
    这里写图片描述

    拥挤度——指种群中给定个体的周围个体的密度,直观上可表示为个体。

    拥挤度比较算子:
    这里写图片描述

    3.3 多目标粒子群算法( PSO )


    设想这么一个场景:一群鸟进行觅食,而远处有一片玉米地,所有的鸟都不知道玉米地到底在哪里,但是它们知道自己当前的位置距离玉米地有多远。那么找到玉米地的最佳策略,也是最简单有效的策略就是是搜寻目前距离玉米地最近的鸟群的周围区域。

    基本粒子群算法:
    粒子群由 n个粒子组成 ,每个粒子的位置 xi 代表优化问题在 D维搜索空间中潜在的解;
    粒子在搜索空间中以一定的速度飞行 , 这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整下一步飞行方向和距离;
    所有的粒子都有一个被目标函数决定的适应值(可以将其理解为距离“玉米地”的距离) , 并且知道自己到目前为止发现的最好位置 (个体极值 pi )和当前的位置 ( xi ) 。

    粒子群算法的数学描述 :
    每个粒子 i包含为一个 D维的位置向量 xi = ( xi1, xi2, …, xiD )和速度向量 vi = ( vi1, vi2,…, viD ) ,粒子 i搜索解空间时 ,保存其搜索到的最优经历位置pi = ( pi1, pi2, …, piD ) 。在每次迭代开始时 ,粒子根据自身惯性和经验及群体最优经历位置 pg = ( pg1, pg2, …, pgD )来调整自己的速度向量以调整自身位置。

    粒子群算法基本思想:
    (1)初始化种群后 ,种群的大小记为 N。基于适应度支配的思想 ,将种群划分成两个子群 ,一个称为非支配子集 A,另一个称为支配子集 B ,两个子集的基数分别为 n1、n2 。
    (2)外部精英集用来存放每代产生的非劣解子集 A,每次迭代过程只对 B 中的粒子进行速度和位置的更新 ;
    (3)并对更新后的 B 中的粒子基于适应度支配思想与 A中的粒子进行比较 ,若 xi ∈B , ϖ xj ∈A,使得 xi 支配 xj,则删除 xj,使 xi 加入 A 更新外部精英集 ;且精英集的规模要利用一些技术维持在一个上限范围内 ,如密度评估技术、分散度技术等。
    (4)最后 ,算法终止的准则可以是最大迭代次数 Tmax、计算精度ε或最优解的最大凝滞步数 Δt等。


    展开全文
  • 多目标优化算法(一)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.

    展开全文
  • 多目标优化的微分进化算法-多目标优化的微分进化算法.rar 多目标优化的微分进化算法
  • 多目标优化问题的算法及其求解

    万次阅读 多人点赞 2018-09-06 17:32:58
    多目标优化问题的算法及其求解 一、多目标优化问题   多目标优化是在现实各个领域中都普遍存在的问题,每个目标不可能都同时达到最优,必须各有权重。但是,究竟要怎样分配这样的权重,这已经成为人们...

    多目标优化问题的算法及其求解

    一、多目标优化问题

      多目标优化是在现实各个领域中都普遍存在的问题,每个目标不可能都同时达到最优,必须各有权重。但是,究竟要怎样分配这样的权重,这已经成为人们研究的热点问题。同时,根据生物进化论发展起来的遗传算法,也得到了人们的关注。将这两者结合起来,能够利用遗传算法的全局搜索能力,避免传统的多目标优化方法在寻优过程中陷入局部最优解,可以使解个体保持多样性。所以,基于遗传算法的多目标寻优策略已经被应用于各个领域中。

    二、多目标优化的数学描述

      一般来讲,多目标优化问题是由多个目标函数与有关的一些等式以及不等式约束组成,从数学角度可以做如下描述:minf1(x1,x2,...,xn)min\qquad f_1(x_1,x_2,...,x_n)...............\qquad...\quad...\quad... minfr(x1,x2,...,xn)min\qquad f_r(x_1,x_2,...,x_n) maxfr+1(x1,x2,...,xn)\quad max\qquad f_{r+1}(x_1,x_2,...,x_n) ...............\qquad...\quad...\quad... maxfm(x1,x2,...,xn)\quad max\qquad f_m(x_1,x_2,...,x_n) s.t.gi(x)0,i=1,2,...,ps.t.\qquad g_i(x)\ge0,i=1,2,...,p hj(x)0,j=1,2,...,q\quad \quad \qquad h_j(x)\ge0,j=1,2,...,q (1)
      式中,函数fi(x),{i=1,2,3,...,m}f_i(x),\{i={1,2,3,...,m}\}称为目标函数;gi(x)g_i(x)hi(x)h_i(x)称为约束函数;x={x1,x2,...,xn}Tx=\{x_1,x_2,...,x_n\}^Tnn维的设计变量。X={xxRn,gi(x)0,hj(x)=0,i=1,2,...,p,j=1,2,...,q}X=\{x|x\in R^n,g_i(x)\ge0,h_j(x)=0,i=1,2,...,p,j=1,2,...,q\}称为上述公式的可行域
      在这个多目标优化问题中有m(m2)m(m\ge2)个目标函数(rr个极小化目标函数,(mr)(m-r)个极大化目标函数)和(p+q),p,q0(p+q),p,q\ge0个约束函数(其中有pp个不等式约束和qq个等式约束)。
      如果上述多目标优化问题公式(1)的目标函数全部是极小化目标函数,约束函数全都是不等式约束,则可以得到一个标准多目标优化模型minF(X)=[f1(x),f2(x),...,fm(x)]Tmin\qquad F(X)=[f_1(x),f_2(x),...,f_m(x)]^T s.t.gi(x)0,i=1,2,...,ps.t.\qquad g_i(x)\le0,i=1,2,...,p(2)
      设计变量x={x1,x2,...,xn}Tx=\{x_1,x_2,...,x_n\}^T是一组确定的向量,对应nn维欧氏设计变量空间RnR^n上的一点,而相应的目标函数f(x)f(x)则对应一个mm维的欧氏目标函数RmR^m空间的一点。也就是说,目标函数f(x)f(x)对应的是由n维设计变量空间到m维目标函数空间的一个映射:f:RnRmf:\qquad R^n\to R^m
      由此可知,设计变量、目标函数以及约束函数是构成多目标优化问题的三要素。
      设计变量x1,x2,...,xnx_1,x_2,...,x_n是在实际工程设计中可以人为指定控制的,并且能对工程系统的属性、性能产生影响的一组向量,不同取值的设计变量便意味着对应不同的工程系统设计方案,一组设计变量通常可以用向量x={x1,x2,...,xn}Tx=\{x_1,x_2,...,x_n\}^T表示,并把它称之为优化问题的一个
      目标函数可以看作是评价设计系统性能指标的数学表达式,在实际工程设计中,设计者(决策者)希望能同时使这些性能指标达到最优化。所有的目标函数f1(x),f2(x),...,fm(x)f_1(x),f_2(x),...,f_m(x)构成了多目标优化问题(2)的目标函数向量F(X)F(X)
      约束条件给出了设计变量需要满足的限制条件,用含有等式和不等式的约束函数来表示。满足所有约束函数(约束条件)的一组设计变量可以称之为一个***可行解***,优化问题中所有的可行解构成了整个优化问题的可行域。

    三、多目标优化的目标占优和Pareto占优

      在多目标优化算法的搜索中,普遍使用了占优(dominate)的概念。在这里将给出占优的概念以及相关术语的定义。

    定义1:帕累托占优(Pareto Dominate)和帕累托最优解(Pareto Optimal)

      考察两个决策向量a,bXa,b\in Xaa帕累托占优(Pareto Dominate)bb,记为a&gt;ba&gt;b,当且仅当:{i{1,2,...,n}fi(a)fi(b)}{j{1,2,...,n}fj(a)&lt;fj(b)}\{\forall i\in \{1,2,...,n \}f_i(a)\le f_i(b)\} \land\{\exists j\in \{1,2,...,n \}f_j(a)&lt;f_j(b)\}
      如果在整个参数空间内不存在任何决策向量帕累托占优某个决策向量,则称该决策向量既是帕累托最优解。所有帕累托最优解组成了帕累托最优解集合(Pareto Optimal Set)。

    定义2:绝对最优解、非劣解、帕累托前沿(Pareto Front)

       设S为多目标优化的可行域,f(x)f(x)为多目标优化的向量目标函数。
       若f(X)f(X)XSf(X^*)\le f(X)\qquad \forall X\in S,则ff^*称是多目标优化的***绝对最优解***。
      若f(X)f(X)XSf(X)\le f(X^-)\qquad \forall X\in S,则称XX^-是多目标优化问题的***非劣解***,即***Pareto最优解***。非劣解也成为有效解(Efficient Solution)、非支配解(Non-dominated Solution)、Pareto最优解(Pareto Optimal Solution)或Pareto解。
      多目标优化问题的非劣解一般不止一个,由所有非劣解构成的集合称为***非劣解集(Non-inferior Set)***。所有非劣解对应的目标函数构成了多目标优化问题的***非劣最优目标域***,也成为***Pareto前缘(Pareto Front)***,再不引起混淆的情况下也可以称为非劣解集。

    四、多目标优化问题的解

      在单目标优化问题中,通常最优解只有一个,而且能用比较简单和常用的数学方法求出其最优解。然而在多目标优化问题中,各个目标之间相互制约,可能使得一个目标性能的改善往往是以损失其它目标性能为代价,不可能存在一个使所有目标性能都达到最优的解,所以对于多目标优化问题,其解通常是一个非劣解的集合——Pareto解集。
      在存在多个Pareto最优解的情况下,如果没有关于问题的更多的信息,那么很难选择哪个解更可取,因此所有的Pareto最优解都可以被认为是同等重要的。由此可知,对于多目标优化问题,最重要的任务是找到尽可能多的关于该优化问题的Pareto最优解。因而,在多目标优化中主要完成以下两个任务:

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

      第一个任务是在任何优化工作中都必须的做到的,收敛不到接近真正Pareto最优解集的解是不可取的,只有当一组解收敛到接近真正Pareto最优解,才能确保该组解近似最优的这一特性。
      除了要求优化问题的解要收敛到近似Pareto最优域,求得的解也必须均匀稀疏地分布在Pareto最优域上。一组在多个目标之间好的协议解是建立在一组多样解的基础之上。因为在多目标进化算法中,决策者一般需要处理两个空间——决策变量空间和目标空间,所以解(个体)之间的多样性可以分别在这两个空间定义。例如,若两个个体在决策变量空间中的欧拉距离大,那么就说这两个解在决策变量空间中互异;同理,若两个个体在目标空间中的欧拉距离大,则说它们在目标空间中互异。尽管对于大多数问题而言,在一个空间中的多样性通常意味着在另一个空间中的多样性,但是此结论并不是对所有的问题都是成立的。对于这样复杂的非线性优化问题,要找到在要求的空间中有好的多样性的一组解也是一项非常重要的任务。

    五、求解帕累托前沿解的方法

      目前求解帕累托前沿解的主要算法有基于数学的规划方法和基于遗传算法的两类方法。本文重点介绍目前使用较普遍的NSGA-II算法。
      多目标遗传算法是用来分析和解决多目标优化问题的一种进化算法,其核心就是协调各个目标函数之间的关系,找出使得各个目标函数都尽可能达到比较大的(或比较小的)函数值的最优解集。在众多多目标优化的遗传算法中,NSGA-II算法(带精英策略的非支配排序遗传算法(Elitist Non-Dominated Sorting Genetic Algorithm,NSGA-II),NSGA-II )是影响最大和应用范围最广的一种多目标遗传算法。在其出现以后,由于它简单有效以及比较明显的优越性,使得该算法已经成为多目标优化问题中的基本算法之一。该算法主要优点(改善内容)如下三点:

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

    六、在供应链优化过程中的应用案例

      供应链系统优化问题的本质是:
    1)供应链可以理解为一个多实体集成的系统或网络,它同步一系列相互关联的实体业务流程;
    2)协同优化问题不是最大限度地提高单一实体的盈利能力,而是促进各种合作伙伴(包括供应商,制造商,零售商,分销商和第三方物流供应商)共同盈利能力;
    3)只有当所有实体都希望优化整个供应链的性能和盈利能力(协同优化),并且不将其个体偏好(个体优化)置于系统的优先级之外时,才能实现协同优化;
    4)供应链协同优化必须找到一种尽可能兼顾满足个体偏好,同时最大规模实现全局最优帕累托解的解决方案。
      假设如下供应链模型:
    这里写图片描述
    驱动数据集
    (i, j): Component-Supplier 组件 - 供应商
    (i, j, k): Component-Supplier-Plant 组件 - 供应商 - 工厂
    (k, l): Plant-Customer Zone 工厂 - 客户区
    数据集如下
    这里写图片描述
    约束函数设计如下
    这里写图片描述
    目标函数设计如下
    这里写图片描述
    模拟数据集如下
    这里写图片描述
    运行结果
    这里写图片描述
    这里写图片描述

    展开全文
  • 单目标优化、多目标优化

    千次阅读 2020-03-10 18:24:12
    多目标优化问题的各个子目标之间是矛盾的 ,一个子目标的改善有可能会引起另一个或者另几个子目标的性能降低 , 也就是要同时使多个子目标一起达到最优值是不可能的 , 而只能在它们中间进行协调和折中处理 , 使各个子...

    1、优化问题三要素:

    决策变量、目标函数、约束

    2、单、多目标优化的关系:

    多目标优化问题的各个子目标之间是矛盾的 ,一个子目标的改善有可能会引起另一个或者另几个子目标的性能降低 , 也就是要同时使多个子目标一起达到最优值是不可能的 , 而只能在它们中间进行协调和折中处理 , 使各个子目标都尽可能地达到最优化。其与单目标优化问题的本质区别在于 ,它的解并非唯一 ,而是存在一组由众多 Pareto最优解组成的最优解集合 ,集合中的各个元素称为 Pareto最优解或非劣最优解。

    3、不同算法在多目标优化中的应用 :

    多目标优化问题不存在唯一的全局最优解 ,过多的非劣解是无法直接应用的 ,所以在求解时就是要寻找一个最终解。求最终解主要有三类方法 : 
    a)生成法 ,即先求出大量的非劣解 ,构成非劣解的一个子集 ,然后按照决策者的意图找出最终解 ; 
    b)为交互法 ,不先求出很多的非劣解 ,而是通过分析者与决策者对话的方式逐步求出最终解 ; 
    c)是事先要求决策者提供目标之间的相对重要程度 即权重,算法以此为依据 ,将多目标问题转换为单目标问题进行求解。而这些主要是通过算法来实现的 ,一直以来很多专家学者采用不同算法解决多目标优化问题 ,如多目标进化算法、多目标粒子群算法和蚁群算法、模拟退火算法及人工免疫系统等。

    4、优化问题分类:

    • 数量:

    单目标优化问题;多目标优化有多个评测函数的存在,而且使用不同的评测函数的解,也是不同的。也即是说:多目标优化问题中,同时存在多个最大化或是最小化的目标函数,并且,这些目标函数并不是相互独立的,也不是相互和谐融洽的,他们之间会存在或多或少的冲突,使得不能同时满足所有的目标函数。

    • 变量性质:

    数值优化问题:决策变量的取值往往是连续的,通常是一段连续定义域上的连续函数的函数求得最值的问题

    组合优化问题决策变量是离散的。 组合优化问题是对离散变量按照一定评价标准的排序,筛选或分类。

    组合问题首先有解的集合,但是怎样优化是重点。

    • 是否有约束:

    有约束问题:既可以是等式约束也可以是不等式约束。寻找这一组参数值的关键可是:满足约束条件和目标值要达到最优。

    无约束优化问题:初始点选择好之后,就可以按照各种不同的无约束最优化求解算法,求解最小值点了。主要的连个概念:步长和方向。https://blog.csdn.net/nocml/article/details/8287466

    • 目标函数:

    线性规划:线性规划问题是要最小化或最大化一个受限于一组有限的线性约束的线性函数。https://blog.csdn.net/fjssharpsword/article/details/53195556

    非线性优化:如果目标函数或者约束条件中至少有一个是非线性函数时,最优化问题叫做非线性规划问题

    https://blog.csdn.net/qjzcy/article/details/51727741

    二次规划:二次规划问题是目标函数是二次的,约束条件是线性的

    https://blog.csdn.net/fangqingan_java/article/details/49720497
     

    展开全文
  • 多目标优化moda

    2018-01-17 14:05:20
    多目标优化算法MODA。多应用在工程技术领域解决多目标优化问题
  • 大多数工程和科学问题都是多目标优化问题,从本专业的角度来说,例如建筑运行节能与室内光热舒适的权衡、能源系统的经济效益与碳排放的权衡等。存在如此多个彼此冲突的目标,如何获取这些问题的最优解,一直都是学术...
  • 多目标优化,遗传算法,适合于研究多目标优化的朋友。 多目标优化是在现实各个领域中都普遍存在的问题,每个目标不可能都同时达到最优,必须各有权重。但是,究竟要怎样分配这样的权重,这已经成为人们研究的热点...
  • MOALO优化算法——多目标蚁狮优化算法:一种求解工程问题的多目标优化算法
  • 解决多目标优化问题的超多目标进化算法
  • 资源整理不易,欢迎下载交流学习! NSGA2优化算法Matlab求解多目标优化问题,遗传算法优化+帕累托排序,有效地解决了多目标优化问题,算例可行有效。
  • 多峰多目标优化:初步研究
  • 精华多目标优化算法

    2018-11-04 13:06:35
    介绍了多目标优化问题的含义以及给出了多目标优化问题的数学描述。并且介绍了解决多目标优化的几种典型算法,讨论并对比了算法存在的优缺点,认为要进一步研究求解多目标优化问题的更多高效算法,若能结合各种算法的...
  • 多目标优化ABC

    2018-04-14 13:13:11
    MOABC,人工蜂群算法多目标优化matlab代码,注释多,容易读。
  • 多目标优化详解【转载】

    万次阅读 多人点赞 2017-09-02 11:05:47
    多目标优化问题详解 生活中 ,许多问题都是由相互冲突和影响的多个目标组成。人们会经常遇到使多个目标在给定区域同时尽可能最佳的优化问题 ,也就是多目标优化问题。优化问题存在的优化目标超过一个并需要同时处理 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,018
精华内容 4,407
关键字:

多目标优化