精华内容
下载资源
问答
  • 本资源包含灰狼优化算法(GWO)代码以及粒子群算法(PSO),主函数为使用灰狼优化和粒子群优化对不同函数进行寻优并将两种算法的比较结果绘图显示
  • 各种智能优化算法比较与实现(matlab版)

    万次阅读 多人点赞 2020-05-05 10:13:46
    各种智能优化算法比较与实现(matlab版) 一、 方法介绍 1免疫算法(Immune Algorithm,IA) 1.1算法基本思想 免疫算法是受生物免疫系统的启发而推出的一种新型的智能搜索算法。它是一种确定性和随机性选择相结合并...

    各种智能优化算法比较与实现(matlab版)

    一、 方法介绍

    1免疫算法(Immune Algorithm,IA)

    1.1算法基本思想

    免疫算法是受生物免疫系统的启发而推出的一种新型的智能搜索算法。它是一种确定性和随机性选择相结合并具有“勘探”与“开采”能力的启发式随机搜索算法。免疫算法将优化问题中待优化的问题对应免疫应答中的抗原,可行解对应抗体(B细胞),可行解质量对应免疫细胞与抗原的亲和度。如此则可以将优化问题的寻优过程与生物免疫系统识别抗原并实现抗体进化的过程对应起来,将生物免疫应答中的进化过程抽象成数学上的进化寻优过程,形成一种智能优化算法。它具有一般免疫系统的特征,采用群体搜索策略,通过迭代计算,最终以较大的概率得到问题的最优解。相对于其他算法,免疫算法利用自身产生多样性和维持机制的特点,保证了种群的多样性,克服了一般寻优过程(特别是多峰值的寻优过程)的不可避免的“早熟”问题,可以求得全局最优解。免疫算法具有自适应性、随机性、并行性、全局收敛性、种群多样性等优点。
    1.2 算法操作步骤
    (1)首先进行抗原识别,即理解待优化的问题,对问题进行可行性分析,提取先验知识,构造出合适的亲和度函数,并制定各种约束条件。
    (2)然后初始化抗体群,通过编码把问题的可行解表示成解空间中的抗体,在解的空间内随机产生一个初始种群。
    (3)对种群中的每一个可行解进行亲和度评价。(记忆单元的更新:将与抗原亲和性高的抗体加入到记忆单元,并用新加入的抗体取代与其亲和性最高的原有抗体(抗体和抗体的亲和性计算))
    (4)判断是否满足算法终止条件;如果满足条件则终止算法寻优过程,输出计算结果;否则继续寻优运算。
    (5)计算抗体浓度和激励度。(促进和抑制抗体的产生:计算每个抗体的期望值,抑制期望值低于阈值的抗体;可以知道与抗原间具有的亲和力越高,该抗体的克隆数目越高,其变异率也越低)
    (6)进行免疫处理,包括免疫选择、克隆、变异和克隆抑制。
    免疫选择:根据种群中抗体的亲和度和浓度计算结果选择优质抗体,使其活化;
    克隆:对活化的抗体进行克隆复制,得到若干副本;
    变异:对克隆得到的副本进行变异操作,使其发生亲和度突变;
    克隆抑制:对变异结果进行再选择,抑制亲和度低的抗体,保留亲和度高的变异结果。
    (7)种群刷新,以随机生成的新抗体替代种群中激励度较低的抗体,形成新一代抗体,转步骤(3)。
    免疫算法运算流程图
    在这里插免疫算法入图片描述
    1.3 代码实现

    %%%%%%%%%%%%%%%%%免疫算法求函数极值%%%%%%%%%%%%%%%%%%%%
    %%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%
    clear all;                                %清除所有变量
    close all;                                %清图
    clc;                                      %清屏
    D=10;                                     %免疫个体维数
    NP=100;                                   %免疫个体数目
    Xs=20;                                    %取值上限
    Xx=-20;                                   %取值下限
    G=500;                                    %最大免疫代数
    pm=0.7;                                   %变异概率
    alfa=1;                                   %激励度系数
    belta=1;                                  %激励度系数   
    detas=0.2;                                %相似度阈值
    gen=0;                                    %免疫代数
    Ncl=10;                                   %克隆个数
    deta0=1*Xs;                               %邻域范围初值
    %%%%%%%%%%%%%%%%%%%%%%%初始种群%%%%%%%%%%%%%%%%%%%%%%%%
    f=rand(D,NP)*(Xs-Xx)+Xx;
    for np=1:NP
        MSLL(np)=func1(f(:,np));
    end
    %%%%%%%%%%%%%%%%%计算个体浓度和激励度%%%%%%%%%%%%%%%%%%%
    for np=1:NP
        for j=1:NP     
            nd(j)=sum(sqrt((f(:,np)-f(:,j)).^2));
            if nd(j)<detas
                nd(j)=1;
            else
                nd(j)=0;
            end
        end
        ND(np)=sum(nd)/NP;
    end
    MSLL =  alfa*MSLL- belta*ND;
    %%%%%%%%%%%%%%%%%%%激励度按升序排列%%%%%%%%%%%%%%%%%%%%%%
    [SortMSLL,Index]=sort(MSLL);
    Sortf=f(:,Index);
    %%%%%%%%%%%%%%%%%%%%%%%%免疫循环%%%%%%%%%%%%%%%%%%%%%%%%
    while gen<G
        for i=1:NP/2
            %%%%%%%%选激励度前NP/2个体进行免疫操作%%%%%%%%%%%
            a=Sortf(:,i);
            Na=repmat(a,1,Ncl);
            deta=deta0/(gen+0.0001);
            for j=1:Ncl
                for ii=1:D
                    %%%%%%%%%%%%%%%%%变异%%%%%%%%%%%%%%%%%%%
                    if rand<pm
                        Na(ii,j)=Na(ii,j)+(rand-0.5)*deta;
                    end
                    %%%%%%%%%%%%%%边界条件处理%%%%%%%%%%%%%%%
                    if (Na(ii,j)>Xs)  |  (Na(ii,j)<Xx)
                        Na(ii,j)=rand * (Xs-Xx)+Xx;
                    end
                end
            end
            Na(:,1)=Sortf(:,i);               %保留克隆源个体
            %%%%%%%%%%克隆抑制,保留亲和度最高的个体%%%%%%%%%%
            for j=1:Ncl
                NaMSLL(j)=func1(Na(:,j));
            end
            [NaSortMSLL,Index]=sort(NaMSLL);
            aMSLL(i)=NaSortMSLL(1);
            NaSortf=Na(:,Index);
            af(:,i)=NaSortf(:,1);
        end 
        %%%%%%%%%%%%%%%%%%%%免疫种群激励度%%%%%%%%%%%%%%%%%%%
        for np=1:NP/2
            for j=1:NP/2
                nda(j)=sum(sqrt((af(:,np)-af(:,j)).^2));         
                if nda(j)<detas
                    nda(j)=1;
                else
                    nda(j)=0;
                end
            end
            aND(np)=sum(nda)/NP/2;
        end
        aMSLL =  alfa*aMSLL-  belta*aND;
        %%%%%%%%%%%%%%%%%%%%%%%种群刷新%%%%%%%%%%%%%%%%%%%%%%%
        bf=rand(D,NP/2)*(Xs-Xx)+Xx;
        for np=1:NP/2
            bMSLL(np)=func1(bf(:,np));
        end
        %%%%%%%%%%%%%%%%%%%新生成种群激励度%%%%%%%%%%%%%%%%%%%%
        for np=1:NP/2
            for j=1:NP/2
                ndc(j)=sum(sqrt((bf(:,np)-bf(:,j)).^2));
                if ndc(j)<detas
                    ndc(j)=1;
                else
                    ndc(j)=0;
                end
            end
            bND(np)=sum(ndc)/NP/2;
        end
        bMSLL =  alfa*bMSLL-  belta*bND;
        %%%%%%%%%%%%%%免疫种群与新生种群合并%%%%%%%%%%%%%%%%%%%
        f1=[af,bf];
        MSLL1=[aMSLL,bMSLL];
        [SortMSLL,Index]=sort(MSLL1);
        Sortf=f1(:,Index);
        gen=gen+1;
        trace(gen)=func1(Sortf(:,1));
    end
    %%%%%%%%%%%%%%%%%%%%%%%输出优化结果%%%%%%%%%%%%%%%%%%%%%%%%
    Bestf=Sortf(:,1);                 %最优变量
    trace(end);                       %最优值
    figure,plot(trace)
    xlabel('迭代次数')
    ylabel('目标函数值')
    title('亲和度进化曲线')
    
    %%%%%%%%%%%%%%%%%%%%%%%%%亲和度函数%%%%%%%%%%%%%%%%%%%%%%
    function result=func1(x)
    summ=sum(x.^2);
    result=summ;
    
    

    结果为
    在这里插入图片描述

    2蚁群优化算法(Ant Colony Optimization,ACO)

    2.1算法基本思想
    蚁群算法是一种源于大自然生物世界的新的仿生进化算法,通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式搜索算法。蚂蚁在运动过程中,能够在它所经过的路径上留下信息素进行信息传递,而且蚂蚁在运动过程中能够感知这种物质,并以此来指导自己的运动方向。初始阶段,环境中没有信息素的遗留,蚂蚁寻找事物完全是随机选择路径,随后寻找该事物源的过程中就会受到先前蚂蚁所残留的信息素的影响,其表现为蚂蚁在选择路径时趋向于选择信息素浓度高的路径。同时,信息素是一种挥发性化学物,会随着时间的推移而慢慢地消逝。如果每只蚂蚁在单位距离留下的信息素相同,那对于较短路径上残留的信息素就相对较高,这被后来的蚂蚁选择的概率就将大,从而导致这条短路径上走的蚂蚁就越多。而经过的蚂蚁越多,该路径上残留的信息素就将更多,这样使得整个蚂蚁的集体行为构成了信息素的正反馈过程,最终整个蚁群会找出最优路径。
    2.2 基本蚁群算法操作步骤
    (1)初始化参数:开始时每条边的信息素量都相等
    (2)将各蚂蚁放置各顶点,禁忌表为对应的顶点。
    (3)蚂蚁个体根据状态转移概率计算转移概率选择下一个顶点,更新禁忌表,再计算概率,再选择顶点,再更新禁忌表,直至遍历所有顶点1次。
    (4)计算该只蚂蚁留在各边的信息素量,该蚂蚁死去。
    (5)重复(3)~(4),直至所有蚂蚁都周游完毕。
    (6)计算各边的信息素增量和信息素量。
    (7)记录本次迭代的路径,更新当前的最优路径,清空禁忌表。
    (8)判断是否达到预定的迭代步数,或者是否出现停滞现象。若是,算法结束,输出当前最优路径;否则,转(2),进行下一次迭代。

    2.3 代码实现
    这里用蚁群算法解决旅行商问题

    %%%%%%%%%%%%%%%%%%%%蚁群算法解决TSP问题%%%%%%%%%%%%%%%%%%%%%%%%%%
    %%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    clear all;                %清除所有变量
    close all;                %清图
    clc;                      %清屏
    m=50;                     %蚂蚁个数
    Alpha=1;                  %信息素重要程度参数              
    Beta=5;                   %启发式因子重要程度参数
    Rho=0.1;                  %信息素蒸发系数
    G_max=200;                %最大迭代次数
    Q=100;                    %信息素增加强度系数
    C=[6734	1453
    2233	10
    5530	1424
    401	841
    3082	1644
    7608	4458
    7573	3716
    7265	1268
    6898	1885
    1112	2049
    5468	2606
    5989	2873
    4706	2674
    4612	2035
    6347	2683
    6107	669
    7611	5184
    7462	3590
    7732	4723
    5900	3561
    4483	3369
    6101	1110
    5199	2182
    1633	2809
    4307	2322
    675	1006
    7555	4819
    7541	3981
    3177	756
    7352	4506
    7545	2801
    3245	3305
    6426	3173
    4608	1198
    23	2216
    7248	3779
    7762	4595
    7392	2244
    3484	2829
    6271	2135
    4985	140
    1916	1569
    7280	4899
    7509	3239
    10	2676
    6807	2993
    5185	3258
    3023	1942];                %31个省会城市坐标
    %%%%%%%%%%%%%%%%%%%%%%%%第一步:变量初始化%%%%%%%%%%%%%%%%%%%%%%%%
    n=size(C,1);              %n表示问题的规模(城市个数)
    D=zeros(n,n);             %D表示两个城市距离间隔矩阵
    for i=1:n
        for j=1:n
            if i~=j
                D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
            else
                D(i,j)=eps;
            end
            D(j,i)=D(i,j);
        end
    end
    Eta=1./D;                    %Eta为启发因子,这里设为距离的倒数
    Tau=ones(n,n);               %Tau为信息素矩阵
    Tabu=zeros(m,n);             %存储并记录路径的生成
    NC=1;                        %迭代计数器
    R_best=zeros(G_max,n);       %各代最佳路线
    L_best=inf.*ones(G_max,1);   %各代最佳路线的长度
    figure(1);%优化解
    while NC<=G_max            
        %%%%%%%%%%%%%%%%%%第二步:将m只蚂蚁放到n个城市上%%%%%%%%%%%%%%%%
        Randpos=[];
        for i=1:(ceil(m/n))
            Randpos=[Randpos,randperm(n)];
        end
        Tabu(:,1)=(Randpos(1,1:m))'; 
        %%%%%第三步:m只蚂蚁按概率函数选择下一座城市,完成各自的周游%%%%%%
        for j=2:n
            for i=1:m
                visited=Tabu(i,1:(j-1));  %已访问的城市
                J=zeros(1,(n-j+1));       %待访问的城市
                P=J;                      %待访问城市的选择概率分布
                Jc=1;
                for k=1:n
                    if length(find(visited==k))==0
                        J(Jc)=k;
                        Jc=Jc+1;
                    end
                end
                %%%%%%%%%%%%%%%%%%计算待选城市的概率分布%%%%%%%%%%%%%%%%
                for k=1:length(J)
                    P(k)=(Tau(visited(end),J(k))^Alpha)...
                        *(Eta(visited(end),J(k))^Beta);
                end
                P=P/(sum(P));
                %%%%%%%%%%%%%%%%按概率原则选取下一个城市%%%%%%%%%%%%%%%%
                Pcum=cumsum(P);
                Select=find(Pcum>=rand);
                to_visit=J(Select(1));
                Tabu(i,j)=to_visit;
            end
        end
        if NC>=2
            Tabu(1,:)=R_best(NC-1,:);
        end
        %%%%%%%%%%%%%%%%%%%第四步:记录本次迭代最佳路线%%%%%%%%%%%%%%%%%%
        L=zeros(m,1);
        for i=1:m
            R=Tabu(i,:);
            for j=1:(n-1)
                L(i)=L(i)+D(R(j),R(j+1));
            end
            L(i)=L(i)+D(R(1),R(n));
        end
        L_best(NC)=min(L);
        pos=find(L==L_best(NC));
        R_best(NC,:)=Tabu(pos(1),:);
        %%%%%%%%%%%%%%%%%%%%%%%%%第五步:更新信息素%%%%%%%%%%%%%%%%%%%%%%
        Delta_Tau=zeros(n,n);
        for i=1:m
            for j=1:(n-1)
                Delta_Tau(Tabu(i,j),Tabu(i,j+1))=...
                    Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
            end
            Delta_Tau(Tabu(i,n),Tabu(i,1))=...
                Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
        end
        Tau=(1-Rho).*Tau+Delta_Tau;
        %%%%%%%%%%%%%%%%%%%%%%%第六步:禁忌表清零%%%%%%%%%%%%%%%%%%%%%%
        Tabu=zeros(m,n);
        %%%%%%%%%%%%%%%%%%%%%%%%%历代最优路线%%%%%%%%%%%%%%%%%%%%%%%%%%
        for i=1:n-1
            plot([ C(R_best(NC,i),1), C(R_best(NC,i+1),1)],...
                [C(R_best(NC,i),2), C(R_best(NC,i+1),2)],'bo-');
            hold on;
        end
        plot([C(R_best(NC,n),1), C(R_best(NC,1),1)],...
            [C(R_best(NC,n),2), C(R_best(NC,1),2)],'ro-');  
        title(['优化最短距离:',num2str(L_best(NC))]);
        hold off;
        pause(0.005);
        NC=NC+1;    
    end
    %%%%%%%%%%%%%%%%%%%%%%%%%%第七步:输出结果%%%%%%%%%%%%%%%%%%%%%%%%%%
    Pos=find(L_best==min(L_best));
    Shortest_Route=R_best(Pos(1),:);            %最佳路线
    Shortest_Length=L_best(Pos(1));             %最佳路线长度
    figure(2),
    plot(L_best)
    xlabel('迭代次数')
    ylabel('目标函数值')
    title('适应度进化曲线')
    

    结果显示
    在这里插入图片描述

    在这里插入图片描述

    3粒子群算法(Particle Swarm Optimization,PSO)

    3.1算法基本思想
    粒子群算法(Particle Swarm Optimization,PSO)最早是由Eberhart和Kennedy于1995年提出,它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景:一群鸟在区域中随机搜寻食物,在这个区域里只有一块食物,所有的鸟知道自己当前位置离食物多远,那么搜索的最简单有效的策略就是搜索目前离食物最近的鸟的周围区域。粒子群算法利用这种模型得到启示并应用于解决优化问题。在粒子群算法中,-用一种粒子来模拟上述的鸟类个体,每个粒子可视为N维搜索空间中的一个搜索个体,粒子的当前位置即为对应优化问题的一个候选解,粒子的飞行过程即为该个体的搜索过程.粒子的飞行速度可根据粒子历史最优位置和种群历史最优位置进行动态调整.粒子仅具有两个属性:速度和位置,速度代表移动的快慢,位置代表移动的方向。每个粒子单独搜寻的最优解叫做个体极值,粒子群中最优的个体极值作为当前全局最优解。不断迭代,更新速度和位置。最终得到满足终止条件的最优解。
    3.2算法基本操作步骤
    (1)初始化粒子群,包括群体规模N,每个粒子的位置xi和速度vi。
    (2)计算每个粒子的适应度fit[i]。
    (3)对每个粒子,用它的适应度值fit[i]和个体极值pbest(i)比较。如果fit[i]小于pbest(i),则用fit[i]替换掉pbest(i)。
    (4)对每个粒子,用它的适应度值fit[i]和全局极值gbest(i)比较。如果fit[i]小于gbest(i),则用fit[i]替换掉gbest(i)。
    (5)迭代更新粒子的位置xi和速度vi。
    (6)进行边界条件处理
    (7)判断算法终止条件是否满足:若是,则结束算法并输出优化结果;否则返回(2)
    粒子群算法运算流程图
    在这里插入图片描述

    3.3 代码实现

    %%%%%%%%%%%%%%%%%粒子群算法求函数极值%%%%%%%%%%%%%%%%%%%%%%%%%%
    %%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    clear all;              %清除所有变量
    close all;              %清图
    clc;                    %清屏
    N=100;                  %群体粒子个数
    D=10;                   %粒子维数
    T=200;                  %最大迭代次数
    c1=1.5;                 %学习因子1
    c2=1.5;                 %学习因子2
    w=0.8;                  %惯性权重
    Xmax=20;                %位置最大值
    Xmin=-20;               %位置最小值
    Vmax=10;                %速度最大值
    Vmin=-10;               %速度最小值
    %%%%%%%%%%%%%%%%初始化种群个体(限定位置和速度)%%%%%%%%%%%%%%%%
    x=rand(N,D) * (Xmax-Xmin)+Xmin;
    v=rand(N,D) * (Vmax-Vmin)+Vmin;
    %%%%%%%%%%%%%%%%%%初始化个体最优位置和最优值%%%%%%%%%%%%%%%%%%%
    p=x;
    pbest=ones(N,1);
    for i=1:N
        pbest(i)=func1(x(i,:));
    end
    %%%%%%%%%%%%%%%%%%%初始化全局最优位置和最优值%%%%%%%%%%%%%%%%%%
    g=ones(1,D);
    gbest=inf;
    for i=1:N
        if(pbest(i)<gbest)
            g=p(i,:);
            gbest=pbest(i);
        end
    end
    gb=ones(1,T);
    %%%%%%%%%%%按照公式依次迭代直到满足精度或者迭代次数%%%%%%%%%%%%%
    for i=1:T
        for j=1:N
            %%%%%%%%%%%%%%更新个体最优位置和最优值%%%%%%%%%%%%%%%%%
            if (func1(x(j,:))<pbest(j))
                p(j,:)=x(j,:);
                pbest(j)=func1(x(j,:));
            end
            %%%%%%%%%%%%%%%%更新全局最优位置和最优值%%%%%%%%%%%%%%%
            if(pbest(j)<gbest)
                g=p(j,:);
                gbest=pbest(j);
            end
            %%%%%%%%%%%%%%%%%跟新位置和速度值%%%%%%%%%%%%%%%%%%%%%
            v(j,:)=w*v(j,:)+c1*rand*(p(j,:)-x(j,:))...
                +c2*rand*(g-x(j,:));
            x(j,:)=x(j,:)+v(j,:);
            %%%%%%%%%%%%%%%%%%%%边界条件处理%%%%%%%%%%%%%%%%%%%%%%
            for ii=1:D
                if (v(j,ii)>Vmax)  |  (v(j,ii)< Vmin)
                    v(j,ii)=rand * (Vmax-Vmin)+Vmin;
                end
                if (x(j,ii)>Xmax)  |  (x(j,ii)< Xmin)
                    x(j,ii)=rand * (Xmax-Xmin)+Xmin;
                end
            end
        end
        %%%%%%%%%%%%%%%%%%%%记录历代全局最优值%%%%%%%%%%%%%%%%%%%%%
        gb(i)=gbest;
    end
    g;                         %最优个体         
    gb(end);                   %最优值
    figure
    plot(gb)
    xlabel('迭代次数');
    ylabel('适应度值');
    title('适应度进化曲线')
    
    
    
    %%%%%%%%%%%%%%%%%%%适应度函数%%%%%%%%%%%%%%%%%%%%
    function result=func1(x)
    summ=sum(x.^2);
    result=summ;
    
    

    二、基准测试函数

    本次实验选取下面的5个测试函数,分别用以上智能算法进行结果分析比较。首先使用蚁群算法、免疫算法和粒子群算法以第一个基准函数为例,画出适应度图像并据此分析每个函数的特点。本文用到的环境是Windows10系统,软件是MATLAB R2017a.
    (1)函数f1(x,y)=3cos(xy)+x+y2的最小值,其中x的取值范围为[-4,4],y的取值范围为[-4,-4]。这是一个有多个局部极值的函数,其函数图像如图所示:
    在这里插入图片描述
    (2)函数f2(x,y)=5sin(xy)+x2+y2的最小值,其中x的取值范围为[-4,4],y的取值范围为[-4,-4]。这是一个有多个局部极值的函数,其函数图像如图所示:
    在这里插入图片描述
    (3)函数f3(x,y)=6sin(4x)+9cos(5y)+y2的最小值,其中x的取值范围为[-4,4],y的取值范围为[-4,-4]。这是一个有多个局部极值的函数,其函数图像如图所示:
    在这里插入图片描述
    (4)函数f4(x,y)=3cos6y+x2+y2的最小值,其中x的取值范围为[-4,4],y的取值范围为[-4,-4]。其函数图像如图所示:
    在这里插入图片描述
    (5)函数f5(x,y)=sin(x2+y)+cos(5x)+x+y的最小值,其中x的取值范围为[-4,4],y的取值范围为[-4,-4]。这是一个有多个局部极值的函数,其函数图像如图所示:
    在这里插入图片描述

    2.1使用免疫算法求解函数极值

    仿真过程如下设置:
    第一步:初始化免疫个体维数为D=2,免疫种群个体数为NP=50,最大免疫代数为G=200,变异概率为Pm=0.7,激励度系数为alfa=2,belta=1,相似度阈值为detas=0.2,克隆个数为Nc1=5;
    第二步:随机产生初始种群,计算个体亲和度、抗体浓度和激励度,并按激励度排序。
    第三步:取激励度前NP/2个个体进行克隆、变异、克隆抑制的免疫操作;免疫后的种群进行激励度计算。
    第四步:随机生成NP/2个个体的新种群,并计算个体亲和度、抗体浓度和激励度;免疫种群和随机种群合并,并按激励度排序,进行免疫迭代。
    第五步:判断是否满足终止条件:若满足,则结束搜索过程,输出优化值;若不满足,则继续进行迭代优化。
    优化结束后,其适应度进化曲线如下图2.1所示。

    在这里插入图片描述

    图2.1免疫算法适应度
    分析:
    优化后的结果为:在免疫代数为200,即x=-4,y=0.7539时,函数取得最小值-6.4078.免疫算法不强调算法参数设置和初始解的质量,利用其启发式的智能搜索机制,即使起步于劣质解种群,最终也可以搜索到问题的全局最优解,对问题和初始解的依赖性不强,具有很强的适应性和鲁棒性。故在上图,种群20代以后基本处于最优解。

    2.2使用蚁群算法求解函数极值

    仿真过程如下设置:
    第一步:初始化蚂蚁个数m=20,最大迭代次数G=200,信息素蒸发系数Rh0=0.9,转移概率常数P0=0.2,局部搜索步长step=0.1
    第二步:随机产生蚂蚁初始位置,计算适应度函数值,设为初始信息素,计算状态转移概率。
    第三步:进行位置更新:当状态转移概率小于转移概率常数时,进行局部搜索;当状态转移概率大于转移概率常数时,进行全局搜索,产生新的蚂蚁位置,并用边界吸收方式进行 边界条件处理,将蚂蚁位置界定在取值范围内。
    第四步:计算新的蚂蚁位置的适应度值,判断蚂蚁是否移动,更新信息素。
    第五步:判断是否满足终止条件:若满足,则结束搜索过程,输出优化值;若不满足,则继续进行迭代优化。
    优化结束后,其适应度进化曲线如下图2.2所示。
    在图2.2 蚁群算法适应度这里插入图片描述
    图2.2 蚁群算法适应度
    分析:
    优化后的结果为:在200轮迭代,即x=-4,y=-0.7539时,函数取得最小值-6.4079.蚁群算法一般需要较长的搜索时间和容易出现停滞现象等不足,故在上图中,容易看到,在100代后,才基本找到最优解。

    2.3使用粒子群算法求解函数极值

    仿真过程如下设置:
    第一步:初始化群体例子个数为N=100,粒子维数为D=2,最大迭代次数为T=200,学习因子c1=c2=1.5,惯性权重最大值为Wmax=0.8,惯性权重最小值为Wmin=0.4,位置最大值为Xmax=4,位置最小值为Xmin=-4,速度最大值为Vmax=1,速度最小值为Vmin=-1.
    第二步:初始化种群粒子位置x和速度v,粒子个体最优位置p和最优值pbest,
    粒子群全局最优位置g和最优值gbest。
    第三步:计算动态惯性权重值w,更新位置x和速度值v,并进行边界条件处理,判断是否替换粒子个体最优位置p和最优值pbest,以及粒子群全局最优位置g和最优值gbest。
    第四步:判断是否满足终止条件:若满足,则结束搜索过程,输出优化值;若不满足,则继续进行迭代优化。
    优化结束后,其适应度进化曲线如下图2.3所示。
    在这里插入图片描述
    图2.3 粒子群适应度
    分析:
    优化后的结果为:在200轮迭代,即x=-4,y=-0.7588时,函数取得最小值-6.4072。粒子群算法本质是一种随机搜索算法,它是一种新型的智能优化技术。该算法能以较大概率收敛于全局最优解。如上图所示,算法在40次迭代,基本找到全局最优解。实践证明,粒子群算法适合在动态、多目标优化环境中寻优,与传统优化算法相比,具有较快的计算速度和更好地全局搜索能力。所以,与其他算法相比,粒子群算法是一种高效的并行搜索算法。

    2.4 蚁群算法和免疫算法比较

    蚁群算法和免疫算法分别在5个基准函数上进行实验,同时在每个基准函数实验20次,并求出20次实验蚁群算法和免疫算法求得全局最优解的平均迭代次数及其标准差。平均迭代次数来反映算法的性能,标准差来反映算法的稳定性。如下表2-1
    表2-1
    在这里插入图片描述

    分析:
    由表2-1所示,免疫算法在平均10次迭代,基本找到全局最优解,而蚁群算法最好的是在平均29次迭代,才基本找到全局最优解。从这个例子上看,免疫算法在效率上是蚁群算法的3倍左右。从标准差上看,免疫算法更稳定。免疫算法和蚁群算法这两种算法,对问题和初始解的依赖性不强,具有很强的适应性和鲁棒性。免疫算法不需要集中控制,可实现并行处理。而且免疫算法的优化进程是一种多进程的并行优化,在探求问题最优解的同时可以得到问题的多个次优解,即除找到问题的最佳方案外,还会得到若干个较好的备选方案,尤其适合于多模态的优化问题。蚁群算法的参数较少,设置简单,因而该算法易于应用到组合优化问题的求解。
    2.5 蚁群算法和粒子群算法比较
    蚁群算法和粒子群算法分别在5个基准函数上进行实验,同时在每个基准函数实验20次,并求出20次实验蚁群算法和免疫算法求得全局最优解的平均迭代次数及其标准差。平均迭代次数来反映算法的性能,标准差来反映算法的稳定性。如下表2-2
    表2-2
    在这里插入图片描述
    分析:
    由表2-2所示,蚁群算法最差结果在平均101次迭代,找到全局最优解,而粒子群算法最差结果在22次迭代左右,就找到了全局最优解。从这个例子上看,粒子群算法效率是蚁群算法的5倍左右。从标准差上来比较,粒子群算法算法更稳定。蚁群算法的参数较少,设置简单,因而该算法易于应用到组合优化问题的求解。粒子群算法是基于群智能理论的优化算法,通过群体中粒子间的合作与竞争产生的群体智能指导优化算法。与其他算法相比,粒子群算法是一种高效的并行搜索算法。实践证明,它适合在动态、多目标优化环境中寻优,与传统优化算法相比,具有较快的计算速度和更好地全局搜索能力。

    2.6 粒子群算法和免疫算法比较

    粒子群算法和免疫算法分别在5个基准函数上进行实验,同时在每个基准函数实验20次,并求出20次实验蚁群算法和免疫算法求得全局最优解的平均迭代次数及其标准差。平均迭代次数来反映算法的性能,标准差来反映算法的稳定性。如下表2-3
    在这里插入图片描述
    分析:
    由表2-3所示,免疫算法最好的结果是在平均8次迭代,基本找到全局最优解,粒子群算法则最好的结果是在平均6次迭代左右,更快地找到全局最优解。从这点看,粒子群算法略微快些,即使从最坏结果看,免疫算法最坏平均在14次,而粒子群算法,则是11次,这点看,依然是粒子群算法更好点。在从标准差方面看,免疫算法和粒子群算法算法稳定性一样。从这个例子上看,粒子群算法在效率上和免疫算法的几乎相同。整体上来看的话,与免疫算法相比,粒子群算法具有较快的计算速度和更好地全局搜索能力,是一种高效的并行搜索算法。

    2.7蚁群算法、免疫算法、粒子群算法比较

    蚁群算法、粒子群算法和免疫算法分别在5个基准函数上进行实验,同时在每个基准函数实验20次,并求出20次实验蚁群算法和免疫算法求得全局最优解的平均迭代次数及其标准差。平均迭代次数来反映算法的性能,标准差来反映算法的稳定性。如下表2-4
    在这里插入图片描述
    分析:
    由表2-4所示,免疫算法和粒子群算法平均在10次迭代左右,基本找到了全局最优解,蚁群算法则最好结果在平均29次迭代,才基本找到全局最优解,从这点看,免疫算法和粒子群算法在效率上是蚁群算法的3倍左右,而免疫算法和粒子群算法在效率上几乎持平。

    三 结论

    免疫算法和蚁群算法不强调算法参数设置和初始解的质量,利用其启发式的智能搜索机制,即使起步于劣质解种群,最终也可以搜索到问题的全局最优解,对问题和初始解的依赖性不强,具有很强的适应性和鲁棒性。免疫算法不需要集中控制,可实现并行处理。而且免疫算法的优化进程是一种多进程的并行优化,在探求问题最优解的同时可以得到问题的多个次优解,即除找到问题的最佳方案外,还会得到若干个较好的备选方案,尤其适合于多模态的优化问题。蚁群算法的参数较少,设置简单,因而该算法易于应用到组合优化问题的求解。粒子群算法是基于群智能理论的优化算法,通过群体中粒子间的合作与竞争产生的群体智能指导优化算法。与其他算法相比,粒子群算法是一种高效的并行搜索算法。实践证明,它适合在动态、多目标优化环境中寻优,与传统优化算法相比,具有较快的计算速度和更好地全局搜索能力。

    参考文献

    [1] 蔡自兴,王勇. 智能系统原理、算法与应用[M].北京:机械工业出版社,2014
    [2] 李爱国,覃征,鲍复民,等.粒子群优化算法[J].计算机工程与应用,2002
    [3] 包子阳,余继周,杨杉编著,智能优化算法及其MATLAB实例(第2版)[M].北京:电子工业出版社,2018.
    [4] 刘冰.人工免疫算法及其应用研究[D].重庆:重庆大学,2004.
    [5] 黄友锐.智能优化算法及其应用[M].北京:国防工业出版社,2008.
    [6] 高海昌,冯博琴.智能优化算法求解TSP问题[J].控制与决策,2006
    [7] 段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.
    [8]《群体智能优化算法》专题导语[J].郑州大学学报(工学版),2018.
    [9] 王凤娟,姜淑凤,单永瑞,张鹏飞,冉东.群智能优化算法的研究与分析[J].信息通信,2018.
    [10] 费腾, 张立毅.现代智能优化算法研究[J].信息技术, 2015.
    [11] 李智.智能优化算法研究及应用展望.武汉轻工大学学报, 2016.
    [12] 楚东来, 赵伟辰, 林春城.群智能算法的研究现状和发展趋势[J].信息通信, 2015,
    [13] https://blog.csdn.net/wangqiuyun/article/details/12838903
    [14] https://blog.csdn.net/taonull/article/details/45972393
    [15] https://blog.csdn.net/greedystar/article/details/80343841
    [16] https://blog.csdn.net/v_JULY_v/article/details/6132775

    展开全文
  • SGD ,Adam,momentum等优化算法比较

    千次阅读 2018-06-03 11:20:58
    深度学习优化算法经历了 SGD -&gt; SGDM -&gt; NAG -&gt;AdaGrad -&gt; AdaDelta -&gt; Adam -&gt; Nadam这样的发展历程。优化算法通用框架:首先定义:待优化参数:w ,目标函数: f(w),...

    深度学习优化算法经历了 SGD -> SGDM -> NAG ->AdaGrad -> AdaDelta -> Adam -> Nadam这样的发展历程

    优化算法通用框架

    首先定义:待优化参数:w ,目标函数: f(w),初始学习率 α。而后,开始进行迭代优化。在每个epoch t:1计算目标函数关于当前参数的梯度2根据历史梯度计算一阶动量和二阶动量3计算当前时刻的下降梯度4根据下降梯度进行更新各个优化算法在步骤3、4都是一致的,主要的差别就体现在1和2上优化算法分为固定学习率和自适应学习率。固定学习率优化策略有SGDSGDMNAG;自适应学习率优化策略有AdaGradAdaDe;taAdamNadam

    SGD算法没有动量的概念,它的,其中是梯度。SGD最大的缺点是下降速度慢,而且可能会在沟壑的两边持续震荡,停留在一个局部最优点对学习率要求严格。

    SGDM是后来为了抑制SGD震荡,在SGD的基础上引入了动量,也就是常说的“惯性”,t时刻的下降方向不仅仅有当前时刻的梯度方向所决定,还收累积的动量方向的影响。。它的优点是下降初期,梯度方向与动量方向一直,可以起到很好的加速作用;下降中后期,在局部最小值震荡,此时梯度趋近于0,累积的动量能是权重更新幅度加大,容易跳过局部最优值。

    NAG算法在梯度更新是做了一个矫正,避免了前进太快,同时提高灵敏度。

    SGDM的更新公式。可以看出累积的动量并没有改变t时刻的梯度。而NAG改进点就是让累积的动量影响当前动量,NAG步骤:1)不计算当前位置的梯度方向,而是计算如果按照累积动量走了一步,那个时候的下降方向:,然后用下一个点的梯度方向,与历史累积动量相结合,计算步骤 2 中当前时刻的累积动量:

     

    momentum首先计算一个梯度(短的蓝色向量),然后在加速更新梯度的方向进行一个大的跳跃(长的蓝色向量),nesterov项首先在之前加速的梯度方向进行一个大的跳跃(棕色向量),计算梯度然后进行校正(绿色梯向量)

     

    自适应学习率策略

    以上的算法都是在SGD的基础上几添加一阶动量,后来在一阶动量的基础上添加二阶动量便是我们说的自适应学习率优化算法。

    Adagrad  Adagrad其实是对学习率加了一个约束。首先去度量历史梯度的更新频率:,所以实际的学习率:是极小整数,防止分母为0。由公式看出,如果设置过大,会使敏感,对梯度调节过大;参数更新越频繁,二阶动量越大,学习率越小。但是二阶动量是单调递增的,会导致学习率最终递减为0,可能会使训练过程提前结束,即使后面还有数据也无法学习。适合处理稀疏梯度。

    Adadelta  由于AdaGrad单调递减的学习率变化过于激进,我们考虑一个改变二阶动量计算方法的策略:不累积全部历史梯度,而只关注过去一段时间窗口的下降梯度。这也就是AdaDelta名称中Delta的来历。,这样就避免了Adagrad中二阶动量持续累积,导致训练过程提前结束的问题。但是Adadelta是度量某一时间窗口内的二阶动量,在这一窗口内可能存在巨变的数据,是学习率上升,造成训练无法收敛。Adadelta容易在训练后期在局部最小值附近震荡。

    Adam  SGD-M在SGD基础上增加了一阶动量,AdaGrad和AdaDelta在SGD基础上增加了二阶动量。把一阶动量和二阶动量都用起来,就是Adam了——Adaptive + Momentum。它利用梯度的一阶动量和二阶动量动态调整每个参数的学习率。Adam的优点主要在于经过偏置校正后,每一次迭代学习率都有个确定范围,使得参数比较平稳。

    Nadam   Nesterov + Adam = Nadam步骤1如同Nesterov

    现在用的最多的算法是SGDAdam,两者各有好坏。SGD能够到达全局最优解,而且训练的最佳精度也要高于其他优化算法,但它对学习率的调节要求非常严格,而且容易停在鞍点;Adam是傻瓜式的优化算法,它很容易的跳过鞍点,而且不需要人为的干预学习率的调节,但是它很容易在局部最小值处震荡,存在在特殊的数据集下出现学习率突然上升,造成不收敛的情况,也就是说它有其他优化算法的所有优点和所有不足。

     

     

    算法

    优点

    缺点

    适用情况

    牛顿法

    收敛速度快

    靠近极小值时收敛速度减慢,求解Hessian矩阵的逆矩阵复杂,容易陷入鞍点

    不适用于高维数据

    拟牛顿法

    收敛速度快,不用计算二阶导数,低运算复杂度

    存储正定矩阵,内存消耗大

    不适用于高维数据

    批量梯度下降

    目标函数为凸函数时,可以找到全局最优值

    收敛速度慢,需要用到全部数据,内存消耗大

    不适用于大数据集,不能在线更新模型

    随机梯度下降

    避免冗余数据的干扰,收敛速度加快,能够在线学习

    更新值的方差较大,收敛过程会产生波动,可能落入极小值,选择合适的学习率比较困难

    适用于需要在线更新的模型,适用于大规模训练样本情况

    小批量梯度下降

    降低更新值的方差,收敛较为稳定

    选择合适的学习率比较困难

     

    Momentum

    能够在相关方向加速SGD,抑制振荡,从而加快收敛

    需要人工设定学习率

    适用于有可靠的初始化参数

    Nesterov

    梯度在大的跳跃后,进行计算对当前梯度进行校正

    需要人工设定学习率

     

    Adagrad

    不需要对每个学习率手工地调节

    仍依赖于人工设置一个全局学习率,学习率设置过大,对梯度的调节太大。中后期,梯度接近于0,使得训练提前结束

    需要快速收敛,训练复杂网络时;适合处理稀疏梯度

    Adadelta

    不需要预设一个默认学习率,训练初中期,加速效果不错,很快,可以避免参数更新时两边单位不统一的问题。

    训练后期,反复在局部最小值附近抖动

    需要快速收敛,训练复杂网络时

    RMSprop

    解决 Adagrad 激进的学习率缩减问题

    依然依赖于全局学习率

    需要快速收敛,训练复杂网络时;适合处理非平稳目标 - 对于RNN效果很好

    Adam

    对内存需求较小,为不同的参数计算不同的自适应学习率

     

    需要快速收敛,训练复杂网络时;善于处理稀疏梯度和处理非平稳目标的优点,也适用于大多非凸优化 - 适用于大数据集和高维空间

     

     

    展开全文
  • 卷积神经网络中的优化算法比较

    千次阅读 2016-10-30 01:30:31
    卷积神经网络一般力求能够做到 end to end ... 因此, CNN 中的各种优化算法还是在梯度下降算法上面做手脚, 这篇文章的主要目的是总结和比较深度学习中各种常用的优化算法. 这这篇文章中不会涉及到怎么求(偏)导数, 我们

    卷积神经网络一般力求能够做到 end to end 的训练, end to end 训练也是目前深度学习的主流. 训练中主要采用 Back Propagation 算法, 而 BP 算法是我们早就学过的梯度下降算法的一种实现. 因此, CNN 中的各种优化算法还是在梯度下降算法上面做手脚, 这篇文章的主要目的是总结和比较深度学习中各种常用的优化算法. 这这篇文章中不会涉及到怎么求(偏)导数, 我们假设已经得到了(偏)导数.

    Stochastic Gradient Descent

    基本的 SGD

    原始的 SGD 方法在机器学习中经常被称为 Vanilla update, 这和我们在高中学习过的梯度下降算法没有什么区别, 都是先求(偏)导数, 然后, 以一定的学习速率, 利用该(偏)导数去更新要优化的参数.

         
    # Vanilla update
    x += - learning_rate * dx

    Momentum Update

    Momentum update 是一种加快收敛速度的方法(注意, 这里说的不是计算速度). 这个方法来自于物理中的启发. loss function 看做是一座山, 对于参数的初始化看做是在这个山坡上面随机放一个小球. 这个小球的初始速度为 0, 其相对于地面(或者更严格的说是山谷, 也是Loss Function 优化过程中的局部最优点)的势能为  U=mgh U=mgh, 其中,  m m 是小球的质量,  g g 是重力加速度, h 是小球的位置相对于山谷最低点的高度. 因为  m m 和  g g 都是常数, 因此, 势能正比与高度  h h. 优化过程看以看做是模拟这个小球在山坡上的状态. 小球来自于地球引力的受力为  F=mg F=mg, 而这恰好是 Loss Function 的梯度. 另外一方面, 小球的整体受力为  F=ma,ag F=ma,a≠g, 因为其中还有摩擦力等其它因素.

         
    # Momentum update
    v = mu * v - learning_rate * dx # integrate velocity
    x += v # integrate position

    这里的变量 mu 就是我们在各种深度学习框架中/论文中见到的 momentum. 一般设置为 0.9, 0.99 等. 然而, 把 mu 理解为摩擦(或者加上其它的因素)更好. mu 的作用是在小球在山坡上滚动的过程中来降低小球的动能. 否则, 如果没有这个因素, 那么, 小球永远不会停下来, 优化过程也永远不会停止.

    Nesterov Momentum

    Nesterov Momentum 是最近比较流行的一种与传统的momentum update稍有不同的方法, Nesterov Momentum 在凸优化中有较强的理论保证收敛, 并且,在实践中, Nesterov Momentum也比单纯的 Momentum 的效果要好. 核心思想是: 注意到 momentum 方法, 如果只看 mu * v 项, 那么, 当前的 x 进过 momentum 的作用会变成 x+ mu*v. 因此, 可以把 x+ mu*v 这个位置看做是当前优化的一个”展望”位置, 所以, 可以在 x+ mu*v 求导, 而不是原始的 x


         
    x_ahead = x + mu * v
    # evaluate dx_ahead (the gradient at x_ahead instead of at x)
    v = mu * v - learning_rate * dx_ahead
    x += v

    自适应优化算法

    在优化的过程中, 如果学习率设置的过大, 那么, 小球就会在山谷之间跳来跳去, 无法到达最低点, 如果是非常缓慢地降低学习速率, 那么, 虽然小球跳来跳去的现象会有缓解, 但是, 效果不明显, 浪费了计算资源, 而如果快速降低学习速率, 那么, 小球可能会很快到达一个(不是那么好的)局部最优点, 而不能到达一个更好的局部最优点. 通常, 在实验中有下面三种方法:

    Step decay 每隔几个epoch减少一次learning rate, 一般是每运行5个epoch左右把learning rate减少一半, 或者是每隔20个epoch减少为原来的1/10. 然而,具体的learning rate 的调整方法还是要看网络的设计和模型. 另外, 还有一种方法是, 在训练的过程中观察training error和validation error, 当validation error不再减小的时候, 减小learning rate.

    Exponential decay 的数学描述是  α=α0ekt α=α0e−kt, 其中  α0,k α0,k 是超参数,  t t 是迭代次数.

    1/t decay 的数学描述是 α=α01+kt α=α01+kt 其中  (α0,k (α0,k) 是超参数,  t t 是迭代次数.

    PS: 我一般使用第一种方法.

    逐个调整参数

    上面讨论过的所有的方法都是所有的参数都使用相同的调整策略. 调整学习率的代价一般比较高, 因此, 有许多研究还是如何自动调学习率, 甚至是调整每一个需要优化的参数的学习率. 在这些方法中往往会引入更多的超参数, 但是, 这些方法对超参数的设置并不是那么敏感, 因此, 总会比上面讨论过的调整学习率的方法要好用.

    AdaGrad

    pass

         
    # Assume the gradient dx and parameter vector x
    cache += dx** 2
    x += - learning_rate * dx / (np.sqrt(cache) + eps)

    cache 的大小和gradient的大小相同, 记录的是每个参数的梯度的平方和. 之后,cache 用来以 element-wise 的方式 normalize 参数的更新. 从上面的代码中可以看出, 梯度较高的权重的有效 learning rate 会减小, 相应的梯度较低的权重的有效 learning rate 会增大. 这里, 让我感到不解的是, sqrt 操作非常重要,如果没有 sqrt 操作, 该算法的效果非常差. eps 用来避免出现除 0 错误的,一般设置为  104 10−4 到  108 10−8 之间. (这种方法,在 CNN 中训练中极为常见, 比如在 batch normalization 中也是通过这种方法避免出现除 0 的错误). Adagrad 的缺点是,在深度学习中, 这种方法导致学习率的调整太激进, 因此常常过早结束了学习过程.

    RMSProp

    RMSProp是一个非常高效的算法, 但是目前并没有发表. Hinton 老爷子果然任性. RMSProp 对 AdaGrad 稍作改进, 是的算法不再像 AdaGrad 那么激进 它使用的是 moving average of squared gradients, 有关 moving average 的相关解释可以参考 batch normalization 的实现说明.

         
    cache = decay_rate * cache + ( 1 - decay_rate) * dx** 2
    x += - learning_rate * dx / (np.sqrt(cache) + eps)

    decay_rate 是超参数, 一般可以设置为 0.9,0.99,0.999 0.9,0.99,0.999. 其中, x+= 操作和Adagrad完全相同, 但是, 变量cache是leaky的,所以, RMSProp 仍然根据每个权重的gradient来调整learning rate.

    Adam

    Adam 是最近提出的一种算法, 该算法和(下面将要介绍的)带有momentum的RMSprop比较类似, 过程类似于:

         
    m = beta1*m + ( 1-beta1)*dx
    v = beta2*v + ( 1-beta2)*(dx** 2)
    x += - learning_rate * m / (np.sqrt(v) + eps)

    该方法和 RMSProp 唯一的区别是 “smooth” 过程, 这里使用的是 m 来做 smooth 操作, 而不是使用原始的 gradient vector dx. 论文中推荐的超参数为 eps=1e-6, bata1=0.9, beta2=0.999, 在实践中, 推荐使用Adam方法. Adam 算法通常会比 RMSProp 算法效果好. 另外,也可以尝试 SGD+Nesterov Momentum. 完整的Adam算法中还包括 bias 的纠正机制, 这是因为,在刚开始的几个steps中,m 和 v 都要初始化, 并且在 warm up 之前他们都 biased at zero. 更多的细节可以参考论文原文.

    Reference

    cs231n

    展开全文
  • 优化算法】简述灰狼优化算法(GWO)原理

    万次阅读 多人点赞 2019-03-25 21:10:34
    系列优化算法简述: OP_1. 简述遗传算法(GA)原理 OP_2 简述灰狼优化算法(GWO)原理 前言: 灰狼优化算法(Grey Wolf Optimizer,GWO)由澳大利亚格里菲斯大学学者 Mirjalili 等人于2014年提出来的一种群智能...

    前言:

    灰狼优化算法(Grey Wolf Optimizer,GWO)由澳大利亚格里菲斯大学学者 Mirjalili 等人于2014年提出来的一种群智能优化算法。该算法受到了灰狼捕食猎物活动的启发而开发的一种优化搜索方法,它具有较强的收敛性能、参数少、易实现等特点。近年来受到了学者的广泛关注,它己被成功地应用到了车间调度、参数优化、图像分类等领域中。


    算法原理:

    灰狼隶属于群居生活的犬科动物,且处于食物链的顶层。灰狼严格遵守着一个社会支配等级关系。如图:

    社会等级第一层:狼群中的头狼记为 \alpha\alpha 狼主要负责对捕食、栖息、作息时间等活动作出决策。由于其它的狼需要服从\alpha 狼的命令,所以 \alpha 狼也被称为支配狼。另外, \alpha 狼不一定是狼群中最强的狼,但就管理能力方面来说, \alpha 狼一定是最好的。

    社会等级第二层\beta 狼,它服从于 \alpha 狼,并协助 \alpha 狼作出决策。在 \alpha 狼去世或衰老后,\beta 狼将成为 \alpha 狼的最候选者。虽然 \beta 狼服从 \alpha 狼,但 \beta 狼可支配其它社会层级上的狼。

    社会等级第三层\delta 狼,它服从 \alpha 、\beta 狼,同时支配剩余层级的狼。\delta 狼一般由幼狼、哨兵狼、狩猎狼、老年狼及护理狼组成。

    社会等级第四层\omega 狼,它通常需要服从其它社会层次上的狼。虽然看上去 \omega 狼在狼群中的作用不大,但是如果没有 \omega 狼的存在,狼群会出现内部问题如自相残杀。

    GWO 优化过程包含了灰狼的社会等级分层跟踪包围攻击猎物等步骤,其步骤具体情况如下所示。

    1)社会等级分层(Social Hierarchy)当设计 GWO 时,首先需构建灰狼社会等级层次模型。计算种群每个个体的适应度,将狼群中适应度最好的三匹灰狼依次标记为 \alpha\beta 、\delta ,而剩下的灰狼标记为 \omega。也就是说,灰狼群体中的社会等级从高往低排列依次为; \alpha\beta 、\delta  及 \omega。GWO 的优化过程主要由每代种群中的最好三个解(即  \alpha\beta 、\delta )来指导完成。

    2)包围猎物( Encircling Prey )灰狼捜索猎物时会逐渐地接近猎物并包围它,该行为的数学模型如下:

    式中:t 为当前迭代次数:。表示 hadamard 乘积操作;A 和 C 是协同系数向量;Xp 表示猎物的位置向量; X(t) 表示当前灰狼的位置向量;在整个迭代过程中 a 由2 线性降到 0; r1 和 r2 是 [0,1] 中的随机向量。

    3)狩猎( Hunring)

    灰狼具有识别潜在猎物(最优解)位置的能力,搜索过程主要靠 \alpha\beta 、\delta 灰狼的指引来完成。但是很多问题的解空间特征是未知的,灰狼是无法确定猎物(最优解)的精确位置。为了模拟灰狼(候选解)的搜索行为,假设 \alpha\beta 、\delta 具有较强识别潜在猎物位置的能力。因此,在每次迭代过程中,保留当前种群中的最好三只灰狼( \alpha\beta 、\delta ),然后根据它们的位置信息来更新其它搜索代理(包括 \omega)的位置。该行为的数学模型可表示如下:

    式中:X_{_{\alpha }}X_{_{\beta }}X_{_{\delta }} 分别表示当前种群中 \alpha\beta 、\delta 的位置向量;X表示灰狼的位置向量;D_{_{\alpha }}D_{_{\beta }}D_{_{\delta }}  分别表示当前候选灰狼与最优三条狼之间的距离;当|A|>1时,灰狼之间尽量分散在各区域并搜寻猎物。当|A|<1时,灰狼将集中捜索某个或某些区域的猎物。

    从图中可看出,候选解的位置最终落在被 \alpha\beta 、\delta 定义的随机圆位置内。总的来说, \alpha\beta 、\delta 需首先预测出猎物(潜
    在最优解)的大致位置,然后其它候选狼在当前最优兰只狼的指引下在猎物附近随机地更新它们的位置。

    4)攻击猎物(Attacking Prey)构建攻击猎物模型的过程中,根据2)中的公式,a值的减少会引起 A 的值也随之波动。换句话说,A 是一个在区间[-a,a](备注:原作者的第一篇论文里这里是[-2a,2a],后面论文里纠正为[-a,a])上的随机向量,其中a在迭代过程中呈线性下降。当 A 在[-1,1]区间上时,则捜索代理(Search Agent)的下一时刻位置可以在当前灰狼与猎物之间的任何位置上。

    5)寻找猎物(Search for Prey)灰狼主要依赖 \alpha\beta 、\delta 的信息来寻找猎物。它们开始分散地去搜索猎物位置信息,然后集中起来攻击猎物。对于分散模型的建立,通过|A|>1使其捜索代理远离猎物,这种搜索方式使 GWO 能进行全局搜索。GWO 算法中的另一个搜索系数是C。从2)中的公式可知,C向量是在区间范围[0,2]上的随机值构成的向量,此系数为猎物提供了随机权重,以便増加(|C|>1)或减少(|C|<1)。这有助于 GWO 在优化过程中展示出随机搜索行为,以避免算法陷入局部最优。值得注意的是,C并不是线性下降的,C在迭代过程中是随机值,该系数有利于算法跳出局部,特别是算法在迭代的后期显得尤为重要。


    参考文献:

    加工时间可控的多目标车间调度问题研究

    Grey Wolf Optimizer
     

     

    展开全文
  • 优化算法之粒子群算法(PSO)

    万次阅读 多人点赞 2018-08-03 10:26:45
      粒子群优化算法(PSO:Particle swarm optimization) 是一种进化计算技术(evolutionary computation)。源于对鸟群捕食的行为研究。粒子群优化算法的基本思想:是通过群体中个体之间的协作和信息共享来寻找最优...
  • 智能优化算法:麻雀搜索算法-附代码

    万次阅读 多人点赞 2020-09-27 16:34:00
    算法比较新颖,具有寻优能力强,收敛速度快的优点 1.算法原理 建立麻雀搜索算法的数学模型,主要规则如下所述: 发现者通常拥有较高的能源储备并且在整个种群中负责搜索到具有丰富食物的区域,为所有的加
  • 智能算法:鲸鱼优化算法-附代码 文章目录智能算法:鲸鱼优化算法-附代码1.算法原理1.1包围猎物1.2 狩猎行为1.3 搜索猎物1.4 算法流程2. 算法结果:参考文献: 摘要:鲸鱼优化算法 (whale optimization algorithm,WOA...
  • 智能优化算法:灰狼优化算法-附代码

    万次阅读 多人点赞 2020-07-31 16:31:41
    智能算法:灰狼优化算法-附代码 摘要:受 灰 狼 群 体 捕 食 行 为 的 启 发,Mirjalili等[1]于 2014年提出了一种新型群体智能优化算法:灰狼优化算法。GWO通过模拟灰狼群体捕食行为,基于狼群群体协作的机制来达到...
  • 传统优化算法VS智能优化算法

    千次阅读 2020-12-20 11:05:40
    而智能优化算法一般针对的是较为普适的问题描述,普遍比较缺乏结构信息。 传统优化算法不少都属于凸优化范畴,有唯一明确的全局最优点;而智能优化算法针对的绝大多数是多极值问题,如何防止陷入局部最优而尽可能...
  • 智能优化算法:蝴蝶优化算法-附代码

    千次阅读 热门讨论 2020-08-07 09:58:08
    智能优化算法:蝴蝶优化算法-附代码 文章目录智能优化算法:蝴蝶优化算法-附代码1.算法原理2.算法流程:3.算法结果4.参考文献:5.MATLAB代码 摘要:蝴蝶优化算法 (Butterfly optimization algorithm,BOA)是由 ...
  • 智能优化算法:蜻蜓优化算法-附代码 文章目录智能优化算法:蜻蜓优化算法-附代码1.算法原理1.1分离2.2 排队2.3 结盟2.4 寻找猎物2.5 躲避天敌2.算法流程3.算法结果4.参考文献5.MATALAB代码 摘要:蜻蜓优化算法( ...
  • 智能优化算法:鸽群优化算法-附代码 文章目录智能优化算法:鸽群优化算法-附代码1.算法原理1.1 指南针算子1.2 地标算子2.算法结果3.参考文献4.Matlab代码5....与其他算法比较有着计算相对简单,鲁棒性相对较强等明
  • 智能优化算法:狮群优化算法 - 附代码

    千次阅读 热门讨论 2021-01-30 10:49:53
    智能优化算法:狮群优化算法 文章目录智能优化算法:狮群优化算法1.狮群算法原理1.1参数定义1.2算法原理2.实验结果3.参考文献4.Matlab代码5.python代码 摘要:狮群优化算法(Loin Swarm Optimization, LSO),是于...
  • 优化算法——常见优化算法分类及总结

    万次阅读 多人点赞 2018-10-27 12:54:53
    之前做特征选择,实现过基于群智能算法进行最优化的搜索,看过一些群智能优化算法的论文,在此做一下总结。 最优化问题  在生活或者工作中存在各种各样的最优化问题,比如每个企业和个人都要考虑的一个问题“在...
  • 智能优化算法:旗鱼优化算法-附代码

    千次阅读 热门讨论 2020-10-24 11:30:56
    2019智能优化算法:旗鱼优化算法-附代码 文章目录2019智能优化算法:旗鱼优化算法-附代码1.算法原理1.2 旗鱼位置更新1.3 沙丁鱼的位置更新1.4 综合考虑旗鱼和沙丁鱼的位置2.算法结果3.参考文献4.Matlab代码 摘要:...
  • 智能优化算法:飞蛾扑火优化算法-附代码 文章目录智能优化算法:飞蛾扑火优化算法-附代码1.算法原理2.算法流程3.算法结果4.参考文献5.MATLAB代码 摘要:飞饿扑火优 化 算 法 ( Moth-flame optimization algorithm,...
  • 文章目录鲸鱼优化算法(Whale Optimization Algorithm,WOA)1.1 灵感1.2 数学建模和优化算法1.2.1 包围捕食(Encircling prey)1.2.2 气泡网攻击方式(Bubble-net attacking method)(利用阶段)1.2.3搜索猎物...
  • 智能优化算法:黏菌优化算法 文章目录智能优化算法:黏菌优化算法1.算法原理2.实验结果3.参考文献4.Matlab代码5.python代码 摘要:黏菌优化算法(Slime mould algorithm,SMA)由 Li等于 2020 年提出,其灵感来自于...
  • 粒子群优化算法(PSO)

    万次阅读 多人点赞 2018-06-04 20:07:09
    粒子群优化算法(Partical Swarm Optimization PSO),粒子群中的每一个粒子都代表一个问题的可能解,通过粒子个体的简单行为,群体内的信息交互实现问题求解的智能性。由于PSO操作简单、收敛速度快,...
  • 智能优化算法:海鸥优化算法-附代码

    千次阅读 2020-07-23 14:24:01
    2019智能算法:海鸥优化算法-附代码 摘要:本文简单介绍智能优化算法-海鸥优化算法 1.原理 海鸥是遍布全球的海鸟,海鸥种类繁多且大小和身长各不相同。 海鸥是杂食动物,吃昆虫、鱼、爬行动物、两栖动物和蚯蚓等。 ...
  • 智能优化算法:果蝇优化算法 文章目录智能优化算法:果蝇优化算法1.算法原理2.算法结果4.参考文献5.Matlab代码 摘要:Pan 于 2011 年受果蝇觅食行为启发,提出了果蝇优化算法 (FOA)。虽然其出现时间不长,但因其具有...
  • 智能优化算法:多元宇宙优化算法-附代码 文章目录智能优化算法:多元宇宙优化算法-附代码1.算法原理2.算法流程图3.算法结果4.参考文献5.MATLAB代码 摘要:多元宇宙优化算法(Multi-Verse Optimizer,MVO)是Seyedali...
  • 1. 常见的群体智能优化算法分类2. 粒子群优化算法思想3. 粒子群优化算法的基本框架4. 对粒子群优化算法中惯性权重的认识5. 粒子群优化算法举例——求解旅行商问题6. 参考文献  同进化算法(见博客《[Evolutionary ...
  • 智能优化算法

    万次阅读 多人点赞 2018-09-03 21:27:12
    智能优化算法 目录 智能优化算法 目录 遗传算法(Genetic Algorithm) 理论 特点 领域 算法流程 差分进化算法(Differential Evolution Algorithm) 理论 特点 领域 算法流程 免疫算法(Immune Algorithm,...
  • 智能优化算法:鸡群优化算法-附代码 文章目录智能优化算法:鸡群优化算法-附代码1.算法原理1.1 鸡群优化算法简介1.2 位置更新策略1.2.1公鸡的位置更新策略1.2.2 母鸡的位置更新策略2.2.3 小鸡的位置更新策略2.算法...
  • 智能优化算法:樽海鞘群优化算法-附代码 文章目录智能优化算法:樽海鞘群优化算法-附代码1.算法原理1.1种群初始化1.2 领导者位置更新1.3 追随者位置更新2.算法流程:3.算法结果4.参考文献5.MATLAB 代码 摘要:樽海鞘...
  • 2019智能优化算法:乌燕鸥优化算法 文章目录2019智能优化算法:乌燕鸥优化算法1.算法原理1.1 迁移行为(全局探索)1.2 攻击行为(局部探索)2.实验结果3.参考文献4.Matlab代码 摘要:乌燕鸥优化算法是由 G. Dhiman 和 A....
  • 智能优化算法:蝗虫优化算法-附代码

    千次阅读 热门讨论 2020-07-30 17:20:04
    智能算法:蝗虫优化算法-附代码 摘要:蝗虫算法( Grasshopper Optimization Algorithm,GOA ) 是 由 Saremi 等[1]于2017 年提出的一种元启发式仿生优化算法,具有较高的搜索效率和较快的收敛速度,且算法本身特殊的...
  • 智能优化算法:头脑风暴优化算法 文章目录智能优化算法:头脑风暴优化算法1.算法原理1.1 聚类1.2 变异2.算法流程3.算法结果4.参考文献5.MATLAB代码 摘要:头脑风暴优化算法(Brain Storming Optimization algorithm, ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 917,342
精华内容 366,936
关键字:

优化算法比较