从Matlab实例学习差分进化算法

背景

接上一篇博客从Matlab实例学习遗传算法， 默认读者已有了遗传算法的基本概念。 本篇涉及的差分进化算法，本质上仍是一种遗传算法， 最大的不同点仍是对选择、交叉、变异这三个操作的新的定义。

算法流程

1. 初始化一个有$N_p$个个体的种群，每个个体可表示为 $X_i,i=1,\cdots ,N_p$
2. 变异操作： 生成$N_p$个新个体， 其中第$i$个个体的生成公式如下：
   $$V_i=X_{r_1}+F\times (X_{r_2}-X_{r_3})$$
   其中， $X_{r_1}，X_{r_2}，X_{r_3}$ 为3个随机个体， 满足$r_1\ne r_2\ne r_3\ne i$。 $F$是一个实常数，随着遗传代数的增加而改变。 可以看到， 第$i$个新个体来自于3个随机个体的基因重组，但却和第$i$个旧个体无关。
3. 交叉操作： 上一步变异操作中产生的个体并非我们真正想要的新个体。 相反，这只是在这一步交叉操作中使用到的中间变量。 取出 $X_i$和 $V_i$， 对于$X_i$的每一位基因，都以 $p=CR$ 的概率被换成$V_i$的对应位基因。 为确保$X_i$至少拿到了$V_i$的一位基因，还会规定对于第$j$位基因要以概率$1$换成$V_i$的第$j$位基因，其中$j$是等概率随机生成的。 因此这一步生成的新个体$U_i$可表示为：
   $$[U_i{]}_j=\{\begin{array}{l}[V_i{]}_j,rand()<CR或j=j_0\\ [X_i{]}_j,rand()\ge CR\end{array}$$
4. 选择： 最后在生成的$U_i$和上一代的$X_i$中，我们进行对位比较，得到下一代的种群个体${\hat{X}}_i$：
   $${\hat{X}}_i=argmax(f(U_i),f(X_i))$$
   也即，留下适应度更高的个体。
5. 循环以上操作，直到遗传到指定代数。 输出最优的个体结果。

附录

关于$F$

$F$代表变异算子，决定了变异量。 常用的自适应变异算子可以定义如下：
$$\lambda ={\mathrm{e}}^{1-\frac{G_{\mathrm{m}}}{G_{\mathrm{m}}+1-G}},F=F_0\times 2^{\lambda }$$

其中$G_m$代表当前代数。 也就是说，在初始代数较小时，$\lambda$较大也就对应了较大的$F$，鼓励大幅变异。 当代数较大时， $\lambda 趋于0$, F趋于$F_0$， 鼓励优良信息的保留。

对差分进化算法的思考

还是直接摘书中的原话吧：

差分进化算法是一种自组织最小化方法, 用户只需很少的输入。 它的关键思想与传统进化方法不同：传统方法是用预先确定的概率分 布函数决定向量扰动; 而差分进化算法的自组织程序利用种群中两个 随机选择的不同向量来干扰一个现有向量, 种群中的每一个向量都要 进行干扰。差分进化算法利用一个向量种群, 其中种群向量的随机扰 动可独立进行, 因此是并行的。如果新向量对应函数值的代价比它们 的前辈代价小, 它们将取代前辈向量。

同其他进化算法一样, 差分进化算法也是对候选解的种群进行操 作, 但其种群繁殖方案与其他进化算法不同: 它通过把种群中两个成 员之间的加权差向量加到第三个成员上来产生新的参数向量, 该操作 称为 “变异” ; 然后将变异向量的参数与另外预先确定的目标向量参 数按一定规则混合来产生试验向量, 该操作称为 “交叉” ; 最后, 若 试验向量的代价函数比目标向量的代价函数低, 试验向量就在下一代 中代替目标向量, 该操作称为 “选择”。种群中所有成员必须当作目 标向量进行一次这样的操作, 以便在下一代中出现相同个数竞争者。 在进化过程中对每一代的最佳参数向量都进行评价, 以记录最小化过 程。这样利用随机偏差扰动产生新个体的方式, 可以获得一个收玫性 非常好的结果, 引导搜索过程向全局最优解逼近 ${}^{[6-7]}$ 。

然而， 仍无法理解为何差分进化比传统进化更好背后的理论原因？

代码

%%%%%%%%%%%%%%%%%差分进化算法求函数极值%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%
clear all;                            %清除所有变量
close all;                            %清图
clc;                                  %清屏
NP=50;                                %个体数目
D=10;                                 %变量的维数
G=200;                                %最大进化代数
F0=0.4;                               %初始变异算子
CR=0.1;                               %交叉算子
Xs=20;                                %上限
Xx=-20;                               %下限
yz=10^-6;                             %阈值
%%%%%%%%%%%%%%%%%%%%%%%%%赋初值%%%%%%%%%%%%%%%%%%%%%%%%
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)=func1(x(:,m));
end
trace(1)=min(Ob);
%%%%%%%%%%%%%%%%%%%%%%%差分进化循环%%%%%%%%%%%%%%%%%%%%%
for gen=1:G
    %%%%%%%%%%%%%%%%%%%%%%变异操作%%%%%%%%%%%%%%%%%%%%%%
    %%%%%%%%%%%%%%%%%%%自适应变异算子%%%%%%%%%%%%%%%%%%%
    lamda=exp(1-G/(G+1-gen));
    F=F0*2^(lamda);
    %%%%%%%%%%%%%%%%%r1,r2,r3和m互不相同%%%%%%%%%%%%%%%%
    for m=1:NP
        r1=randi(NP);
        while (r1==m)
            r1=randi(NP);
        end
        r2=randi(NP);
        while (r2==m)||(r2==r1)
            r2=randi(NP);
        end
        r3=randi(NP);
        while (r3==m)||(r3==r1)||(r3==r2)
            r3=randi(NP);
        end
        v(:,m)=x(:,r1)+F*(x(:,r2)-x(:,r3));
    end
    %%%%%%%%%%%%%%%%%%%%%%交叉操作%%%%%%%%%%%%%%%%%%%%%%%
    r=randi(D);
    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)Xs)
                u(n,m)=rand*(Xs-Xx)+Xx;
            end
        end
    end
    %%%%%%%%%%%%%%%%%%%%%%选择操作%%%%%%%%%%%%%%%%%%%%%%%
    for m=1:NP
        Ob1(m)=func1(u(:,m));
    end
    for m=1:NP
        if Ob1(m)