快速掌握差分进化算法

快来打我* 2023-02-20 13:39 51阅读 0赞

**系列链接**

**        [遗传算法讲解及实例][Link 1]**

**        [差分进化算法讲解及实例][Link 2]**

**        [模拟退火算法讲解及实例][Link 3]**

# 定义 #

差分进化算法属于进化算法的一种，如果读者已经了解了[遗传算法][Link 1]，那么该算法理解起来将会相当轻松，差分进化算法中也包含三个操作：变异、交叉、选择，类似DNA或者遗传物质的进化，体现在算法里就是给一些解，我可以将解变异（解的某一部分进行改变）、交叉（几个解之间进行交换）、选择（是否在下一次迭代中保留当前解）。

# 算法思路 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70][]

## 初始化 ##

一般是在规定区间内随机初始化，求f(x)在区间\[a,b\]上边的最大值，那么初始值就选\[a,b\]的均匀分布即可

## 变异操作 ##

差分就是体现在这一步中，取当前解中的任意不同三个x1,x2,x3，使新一个解为x0 = x1 + F \* (x1 - x2)，其中F为变异因子

## 交叉操作 ##

将解中的某一部分进行交换，这里需要指定一个交叉因子

## 边界处理 ##

变异和交叉之后，解可能脱离了要求区间，因此可以选择按照区间端点值代替，也可以均匀选择区间内一个值代替

## 选择操作 ##

使用评价函数来评价解的好坏，例如求函数最小值，那么将解带入函数，值越小说明该解质量越高，越容易被选择

# 例题 #

**求f(x，y)=3cos(xy)+x+y的最小值，其中x∈\[-4,4\]，y∈\[-4,4\]，很明显函数有多个局部最优，下边我们先画出图来：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 1][]

先放出求解结果，当x = -3.9478，y = -4 时取得最小值-10.9374，迭代过程如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 2][]

# 代码 #

代码参考 “智能优化算法及其MATLAB实例”，做出了部分修改

## 脚本1 —— 画图 ##

%%%%%%%%%f(x，y)=3cos(xy)+x+y%%%%%%%%%%
    clear all;              %清除所有变量
    close all;              %清图
    clc;                    %清屏
    x=-4:0.02:4;
    y=-4:0.02:4;
    N=size(x,2);
    for i=1:N
        for j=1:N
             z(i,j)=3*cos(x(i)*y(j))+x(i)+y(j);
        end
    end
    mesh(x,y,z)
    xlabel('x')
    ylabel('y')

## 脚本2 —— 适应度函数 ##

%%%%%%%%%%%%%%%%%%%%%%%适应度函数%%%%%%%%%%%%%%%%%%%%%%%%%
    function value=func2(x)
    value=3*cos(x(1)*x(2))+x(1)+x(2);

## 脚本3 —— 差分进化算法 ##

%%%%%%%%%%%%%%%%%差分进化算法求函数极值%%%%%%%%%%%%%%%%%
    %%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%
    clear all;                            %清除所有变量
    close all;                            %清图
    clc;                                  %清屏
    NP=20;                                %个体数目
    D=2;                                  %变量的维数
    G=100;                                %最大进化代数
    F=0.5;                                %变异算子
    CR=0.1;                               %交叉算子
    Xs=4;                                 %上限
    Xx=-4;                                %下限
    %%%%%%%%%%%%%%%%%%%%%%%%%赋初值%%%%%%%%%%%%%%%%%%%%%%%%
    x=zeros(D,NP);                        %初始种群
    v=zeros(D,NP);                        %变异种群
    u=zeros(D,NP);                        %选择种群
    x=rand(D,NP)*(Xs-Xx)+Xx;              %赋初值
    %%%%%%%%%%%%%%%%%%%%计算目标函数%%%%%%%%%%%%%%%%%%%%%%%
    for m=1:NP
        Ob(m)=func2(x(:,m));
    end
    trace(1)=min(Ob);
    %%%%%%%%%%%%%%%%%%%%%%%差分进化循环%%%%%%%%%%%%%%%%%%%%%
    for gen=1:G
        %%%%%%%%%%%%%%%%%%%%%%变异操作%%%%%%%%%%%%%%%%%%%%%%
        %%%%%%%%%%%%%%%%%%r1,r2,r3和m互不相同%%%%%%%%%%%%%%%
        for m=1:NP
            r1=randi([1,NP],1,1);
            while (r1==m)
                r1=randi([1,NP],1,1);
            end
            r2=randi([1,NP],1,1);
            while (r2==m)|(r2==r1)
                r2=randi([1,NP],1,1);
            end
            r3=randi([1,NP],1,1);
            while (r3==m)|(r3==r1)|(r3==r2)
                r3=randi([1,NP],1,1);
            end
            v(:,m)=x(:,r1)+F*(x(:,r2)-x(:,r3));
        end
        %%%%%%%%%%%%%%%%%%%%%%交叉操作%%%%%%%%%%%%%%%%%%%%%%%
        r=randi([1,D],1,1);
        for n=1:D
            cr=rand(1);
            if (cr<=CR)|(n==r)
                u(n,:)=v(n,:);
            else
                u(n,:)=x(n,:);
            end
        end
        %%%%%%%%%%%%%%%%%%%边界条件的处理%%%%%%%%%%%%%%%%%%%%
        %%%%%%%%%%%%%%%%%%%%边界吸收%%%%%%%%%%%%%%%%%%%%%%%%%
        for n=1:D
            for m=1:NP
                if u(n,m)<Xx
                    u(n,m)=Xx;
                end
                if u(n,m)>Xs
                    u(n,m)=Xs;
                end
            end
        end
        %%%%%%%%%%%%%%%%%%%%%%选择操作%%%%%%%%%%%%%%%%%%%%%%%
        for m=1:NP
            Ob1(m)=func2(u(:,m));
        end
        for m=1:NP
            if Ob1(m)<Ob(m)
                x(:,m)=u(:,m);
            end
        end
        for m=1:NP
            Ob(m)=func2(x(:,m));
        end
        trace(gen+1)=min(Ob);
    end
    [SortOb,Index]=sort(Ob);
    x=x(:,Index);
    X=x(:,1);                              %最优变量
    Y=min(Ob);                             %最优值
    %%%%%%%%%%%%%%%%%%%%%%%%%画图%%%%%%%%%%%%%%%%%%%%%%%%%%
    figure
    plot(trace);
    xlabel('迭代次数')
    ylabel('目标函数值')
    title('DE目标函数曲线')

[Link 1]: https://blog.csdn.net/qq_41685265/article/details/106973406
[Link 2]: https://blog.csdn.net/qq_41685265/article/details/106983213
[Link 3]: https://yuqi-cheng.blog.csdn.net/article/details/107041801
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200627152701310.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200627153958508.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200627154123570.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1,size_16,color_FFFFFF,t_70