差分进化算法原理及应用

七彩极 · 发表于 2022-5-8 15:24

一、差分进化（differential evolution）算法的起源

差分进化算法由1995，1997年Storn 与Price在文献（Differential evolution – A simple and efficient adaptive scheme for global optimization over continuous spaces；Differential evolution – A simple and efficient heuristic for global optimization over continuous spaces）所提出。
差分进化算法是一种收敛速度快、精度高的一种演化算法，简称DE。而差分进化算法实则源于遗传退火算法（Genetic Annealing Algorithm），在Kenneth Price应用遗传退火算法解决切比雪夫多项式系数的过程中发现虽然解决了该问题，但是收敛过程很慢且有效控制参数很难确定。至此，Ken改进了遗传退火算法，使用浮点数替换位串编码并用算术运算替换逻辑运算，在这过程中发现了差分变异操作。
此后，Rainer为了更好的适应并行计算机体系，提出了创建单独的父代种群和子代种群，这是不同于遗传退火算法的，并且在处理33维切比雪夫多项式系数问题时DE表现了比较好的效果。
至此，差分进化算法（DE）诞生。差分进化算法被称为一种非常高效的全局优化器，因此在同等条件下，差分进化算法的收敛速度、精度能够比遗传算法、粒子群算法好。
二、差分进化算法的原理

差分进化算法在解决优化问题的过程是相对来说比较好的演化算法，被后面研究者进行改进研究。差分进化算法的运行步骤分为：
步骤1：初始化参数；
步骤2：初始化种群；
步骤3：种群变异；
步骤4：种群交叉；
步骤5：最优种群选择；
（一）初始化参数

在差分进化算法中，有几个参数比较重要，突变参数F，交叉概率Cr，种群数Np，个体维度D；这里需要注意F，Cr的取值范围通常在（0，1），但是不意味不能取超过1，这是在大多数的情况都是取（0，1）。关于种群数和个体的关系通常是Np=5D~10D，种群数也是影响整体算法的因素之一。初始化种群之后，接下来进行初始化种群。
（二）初始种群

初始化种群X通常需要结合决策空间的上界和下届，分别为xmax,xmin，具体的计算如下：

这样以决策空间边界的初始种群被建立，用于后期的变异，交叉。其中xmax(j)，xmin(j)表示决策空间j的上界和下届。
（三）种群变异

经历了初始化种群之后，对其进行变异产生变异向量，为后期的产生子代种群建立基础。具体的变异操作如下：

其中g表示第g代的变异向量i个体，r1,r2,r3为常量指标。
（四）种群的交叉

种群的交叉是为了产生多样性的子代向量，增强种群的多样性，使结构更加复杂，促使种群的结构化差异。具体的计算公式如下：

进行种群的交叉之后，为了挑选出最优子代，接下来将进行选择操作。
（五）最优种群的选择

为使种群能从中挑选出最优子代，将执行贪婪选择操作。具体计算公式如下：

以上五个部分就是差分进化算法的核心，也是它的数学原理。可见，差分进化算法的原理比遗传算法、粒子群算法、蚁群算法的简单吧。那知道了原理该如何写程序进行验证其优越性呢？
下面将提供差分进化算法的伪代码参考：
//初始化...

do //生成一个实验种群
{
for(i=0;i<Np;i++)  //r1!=r2!=r3！=i
{
      do r1=floor(rand(0,1)*Np) ;while(r1==i);
      do r2=floor(rand(0,1)*Np) ;while(r1==r2 or r2==i);
      do r2=floor(rand(0,1)*Np) ;while(r3==r2 or r2==r1 or r2==i);
      jrand=floor(D*rand(0,1));

      for(j=0;j<D;j++)  //生成一个实验向量
      {
         if(rand(0,1)<=Cr or j=jrand)
         {
            u(i,j)=x(r1,j)+F*(x(r2,j)-x(r3,j));  //需要检验是否越界
         }
         else
         {
            u(i,j)=x(i,j);
         }
      }
}
}
//选择下一代
for(i=0;i<Np;i++)
{
if (f(u(i,:))<=f(x(i,:)))
{
      x(i,:)=u(i,:)
}else
{
x(i,:)=x(i,:)
}
}
}三、差分进化算法的几何分析

以上是从理论上的角度来分析我们的差分进化算法的运行结构，下面我们从几何分布上来讨论差分进化到底是怎样选择出最优子代的。
1.产生初始种群的空间几何分布如下：

可见此时的种群分布是杂乱无章的，完全离最优区域的领域很远。因此，需要对种群进行变异，以增加子代种群的多样性。
2. 变异过程的几何表示：

可见通过变异的操作，使着部分种群经过差分改变其运动方向。
3. 交叉操作的几何表示：

交叉操作，通过随机比较，产生子代U，以方便通过贪婪选择进行比较选择最优子代，达到最优化的目的。从上图可以看出子代的选择方式的几何分布特征，最终朝着最优区域前进。
4.选择操作

可以看出最终的子代都停留在3.85这个位置，说明此时的种群已经收敛到最优值上了。
四、差分进化的标准测试集

（一）单目标优化

单目标优化是众多研究者测试算法性能的重要测试集之一，通过标准测试集来检验当前的算法在收敛性和精度、稳定上的差异。
这里首先提供以下的标准测试集：
1. 23个单峰、多峰的单目标测试集
来源文献：Evolutionary Programming Made Faster
2.CEC 2005 Special Session on Real-Parameter Optimization
文献来源：Problem Defifinitions and Evaluation Criteria for the CEC 2005 Special Session on Real-Parameter Optimization
3. CEC&#39;2008 special session and competition on large scale global optimization
文献来源：Benchmark functions for the CEC&#39;2008 special session and competition on large scale global optimization
4. CEC&#39;2013 Special Session and Competition on Large-Scale Global Optimization
文献来源： Benchmark Functions for the CEC&#39;2013 Special Session and Competition on Large-Scale Global Optimization
5. CEC 2014 special session and competition on single objective real-parameter numerical optimization
文献来源： Problem defifinitions and evaluation criteria for the CEC 2014 special session
and competition on single objective real-parameter numerical optimization
（二）约束优化

约束优化问题也是测量算法的重要标准测试集，约束优化这里主要提供单目标下的约束优化。
1.CEC 2006 special session on constrained real-parameter
文献来源： Problem defifinitions and evaluation criteria for the CEC 2006 special session
on constrained real-parameter optimization
（三）多目标优化

1.ZDT,SCH,FON,POL,KUR
文献来源： A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II
2. DTLZ
文献来源：Scalable Multi-Objective Optimization Test Problems
3. MOP
文献来源： Decomposition of a Multiobjective Optimization Problem into a Number of Simple Multiobjective Subproblems
4. CF,UF
文献来源： Multiobjective optimization Test Instances for the CEC 2009 Special Session and
Competition
5. MMF
文献来源： Problem Defifinitions and Evaluation Criteria for the CEC 2019 Special Session
on Multimodal Multiobjective Optimization
以上是标准测试集，这里提供matlab下差分进化算法优化单目标，多目标、约束优化的代码来实际展示差分进化算法的优化效果。
（I）单目标优化代码

clc
clear
close all
% DE算法应用---多元函数-------单目标
%需求：DE算法求解多维函数--以超椭球题函数f(x)=sum(x(i).^2*2^(i-1)),i=1,2,...
%求解超椭球体函数的最优值---最大值/最小值
%matlab与java写的程序，所要的评价次数来说，matlab需要的更多
%时间：2020.12.18
%改进：主要从多种群框架---加上一些参数调整----利用其几何性质来做---改进在单目标上，进一步推广在多目标下

%function [optvalue]=DE_One_object(xmax,xmin,iter,Funindex)
D=100;%群体个数
Np=2;%所求的变量个数，这里相当于个体数
xmin=-5;
xmax =5;
K=1000;%iter; %迭代次数
F=0.5; %变异因子[0 2]
Cr=0.9;    %交叉因子[0.6 0.9]
type=1;%Funindex;
%第一步初始化种群
  x=xmin+(xmax-xmin)*rand(D,Np);
%for i=1:Np
best(1,:)=x(1,:);  %全局最优个体 ---之后不断更新--令其等于我们的初始值的第一个值
%end

  for i=2:D
   if(fun_DE1(x(i,:),type)<fun_DE1(best(1,:),type)) %编写函数有问题，下去思考
      best(1,:)=x(i,:);                   %选择最优个体
   end
   end
fi=fun_DE1(best,type); %保证个体全局最优

  %%进入循环直到满足精度要求或者迭代次数达到
  for n=1:K          %做迭代
   time(n)=n;
   %F=0.9-(n*(0.9-0.5)./K); %采用线性递减的方式做
   %第二步变异
   for i=1:D
         for j=1:Np %检查是否越界
      r1=1;r2=1;r3=1;%使得个体满足变异条件.此处与Java有点不一样，他是从1开始
      while(r1==r2||r1==r3||r2==r3||r1==i||r2==i||r3==i)
         r1=ceil(D*rand(1));       %保持其中的r1,r2,r3互异，这样做的目的是为了防止种群的单一性
         r2=ceil(D*rand(1));
         r3=ceil(D*rand(1));
         end
      v(i,j)=x(r1,j)+F*(x(r2,j)-x(r3,j));

      %做一个防止越界
            if v(i,j)<xmin
               v(i,j)=xmin;
            elseif x(i,j) >xmax
               x(i,j)=xmax;
            end
         end

      %交叉
      for j=1:Np
      temper=rand;  %随机产生一个数，用于进行多点交叉
      if(temper<Cr)
         u(i,j)=v(i,j);
      else
         u(i,j)=x(i,j);
      end
      end

      %选择
      if(fun_DE1(u(i,:),type)<fun_DE1(x(i,:),type))
         x(i,:)=u(i,:);
      end
      if(fun_DE1(x(i,:),type)<fi)
         %fi=fun_DE1(x(i,:));
         best=x(i,:);

      end
         Best_f(n)=fun_DE1(best,type);
   end
  end
  %optvalue=Best_f;
  %fprintf(&#39;最优解结果为%f,%f,%f,%f,%f,%f,%f,%f,%f,%f&#39;,best);
  disp([&#39;最小函数值为:&#39;, num2str(Best_f(n))]);

  plot(time,Best_f(time),&#39;b-&#39;,&#39;LineWidth&#39;,2);

function [ y ] = fun_DE1(x,type)
%TESTFUNCTION 此处显示有关此函数的摘要
% 此处显示详细说明
if type==1
%       y=sum(x.^2);
   %y=1-sin(10*pi*x)/x;
   % len=length(x);
   %  y=0;
   %  for i=1:len
   %  y=y+(x(:,i).^2)*2.^(i-1);
   % end
   y=4*x(1)-2.1*x(1).^4+x(1).^6/3+x(1)*x(2)-4*x(2).^2+4*x(2).^4;
   end
end(II)多目标代码

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%DE解决多目标优化问题-----传统的差分进化算法
%时间：2021.10.27
%开发者：gouhuipeng
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clc
clear
close all
Np=100;  %种群数
D=30;    %个体数（问题的维度）
F=0.5; %突变因子（变异因子）
Cr=0.3;  %交叉因子
%xmax(1)=1; %问题上界
%xmin(1)=0; %问题下届
for i=1:D
xmin(:,i)=0;
xmax(:,i)=1;
end
type=5; %测试问题的类型
K=500; %迭代次数

for j=1:D
x(:,j)=xmin(:,j)+(xmax(:,j)-xmin(:,j))*rand(Np,1);  %产生初始值------第一代----对于这里的初始值可不可以进行给定一个最优初始值
end
best=x(1,:);  %全局最优个体 ---之后不断更新--令其等于我们的初始值的第一个值
%end
%plot(x(:,1),x(:,2),&#39;.&#39;);
  for i=2:Np
   if(muti_fun(x(i,:),type)<muti_fun(best(1,:),type)) %编写函数有问题，下去思考
      best=x(i,:);                   %选择最优个体
   end
   end
muti_y=muti_fun(best,type); %保证个体全局最优

%%进入循环直到满足精度要求或者迭代次数达到
  for n=1:K          %做迭代
   time(n)=n;
   %F=0.9-(n*(0.9-0.5)./K); %采用线性递减的方式做
   %第二步变异
   for i=1:Np
         for j=1:D %检查是否越界
      r1=1;r2=1;r3=1;%使得个体满足变异条件.此处与Java有点不一样，他是从1开始
      while(r1==r2||r1==r3||r2==r3||r1==i||r2==i||r3==i)
         r1=ceil(Np*rand(1));       %保持其中的r1,r2,r3互异，这样做的目的是为了防止种群的单一性
         r2=ceil(Np*rand(1));
         r3=ceil(Np*rand(1));
         end
      v(i,j)=x(r1,j)+F*(x(r2,j)-x(r3,j));

      %做一个防止越界
            if v(i,j)<xmin(:,j)
               v(i,j)=xmin(:,j);
            elseif x(i,j) >xmax(:,j)
               x(i,j)=xmax(:,j);
            end
         end

      %交叉
      for j=1:D
      temper=rand;  %随机产生一个数，用于进行多点交叉
      if(temper<Cr)
         u(i,j)=v(i,j);
      else
         u(i,j)=x(i,j);
      end
      end
      mutifun_Uresult(i,:)=muti_fun(u(i,:),type);
      mutifun_Xresult(i,:)=muti_fun(x(i,:),type);
      %选择----------修改选择方法
   % if(muti_fun(u(i,:),type)<=muti_fun(x(i,:),type))
   %    x(i,:)=u(i,:);
   % end
   % plot(i,x,&#39;bo&#39;);
      if  mutifun_Uresult(i,:)<= mutifun_Xresult(i,:)
         x(i,:)=u(i,:);

      end
      fun_muti_x(i,:)=muti_fun(x(i,:),type);
      % plot( fun_muti_x(i,1), fun_muti_x(i,2),&#39;b--&#39;);
      if fun_muti_x(i,:)< muti_y
         %fi=fun_DE1(x(i,:));
         best=x(i,:);

      end
         Best_f(n,:)=muti_fun(best,type);
   end
  end
  %ZDT1理论前沿面
  x1=0:0.01:1;
  f2=1-sqrt(x1);
  plot(x1,f2,&#39;k-&#39;);title(&#39;ZDT1&#39;)
  %ZDT2理论前沿面
% x1=0:0.01:1;
% f2=1-x1.^2;
% plot(x1,f2,&#39;k-&#39;);
%ZDT3理论前沿面
%ZDT4理论前沿面
   %ZDT6理论前沿面
  hold on
  plot( fun_muti_x(:,1), fun_muti_x(:,2),&#39;k+&#39;);
  xlabel(&#39;f-1&#39;);ylabel(&#39;f-2&#39;);zlabel(&#39;f-3&#39;);
% legend(&#39;optimal PF&#39;,&#39;DE&#39;)
  %optvalue=Best_f;
  %fprintf(&#39;最优解结果为%f,%f,%f,%f,%f,%f,%f,%f,%f,%f&#39;,best);
  disp([&#39;最小函数值为:&#39;, num2str(Best_f(n,:))]);
五、差分进化算法的应用领域

1. 差分进化算法优化Si-H族

2. 差分进化算法在非成像光学设计中的应用

3. 工业压缩机供应系统的优化

4. 基于差分进化算法的多传感器融合的极小化表示

5. 测定地震震源：差分进化算法的挑战

6. 并行差分进化在3-D医学图像配准上的应用

原文链接：差分进化算法原理及优化应用_秋刀鱼程序编程的博客-CSDN博客
欢迎关注知乎，留言咨询！

		自动登录	找回密码
密码			立即注册

差分进化算法原理及应用

本帖子中包含更多资源