仿生智能算法系列之八---差分进化算法
差分进化算法（Differential Evolution 简称DE）是Rainer Storn 和Kenneth Price在1996 年提出，最初试图使用向量差进行向量种群的混洗，以此来解决切比雪夫多项式适应性问题。DE 通过种群内个体间的合作与竞争来实现对优化问题的求解，其本质上是一种基于实数编码的具有保优思想的进化算法。该算法实现技术简单，在对各种测试问题的实验中表现优异，已经成为近年来进化算法研究中的热点之一。
和其它演化算法一样，DE是一种模拟生物进化的随机模型，通过反复迭代，使得那些适应环境的个体被保存了下来。但相比于进化算法，DE保留了基于种群的全局搜索策略，采用实数编码、基于差分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂性。同时，DE特有的记忆能力使其可以动态跟踪当前的搜索情况，以调整其搜索策略，具有较强的全局收敛能力和鲁棒性，且不需要借助问题的特征信息，适于求解一些利用常规的数学规划方法所无法求解的复杂环境中的优化问题。目前，DE已经在在约束优化计算、聚类优化计算、非线性优化控制、神经网络优化、滤波器设计、阵列天线方向图综合及其它方面得到广泛应用。
和其它进化算法相比, 差分进化算法具有以下优点:
（1）差分进化算法在求解非凸、多峰、非线性函数优化问题表现极强的稳健性。
（2）在同样的精度要求下, 差分进化算法收敛的速度快。
（3）差分进化算法尤其擅长求解多变量的函数优化问题。
（4）操作简单, 易编程实现。
同时差分进化算法也具有一定的缺点：
由于差分进化的关键步骤-变异操作是基于群体的差异向量信息来修正各个体的值, 随着进化代数的增加, 各个体之间的差异化信息在逐渐缩小, 以至于后期收敛速度变慢, 甚至有时会陷入局部最优点。
差分进化算法的一般步骤：
(1)初始化。
(2)变异。
(3)交叉。
(4)选择。
(5)边界条件的处理。
差分进化算法的流程图如下：
下面给出算法实例，通过对下述测试函数进行算法测试：
差分进化算法的matlab程序如下：
function DE(Gm,F0)
t0 = cputime;
%差分进化算法程序
%F0是变异率 %Gm 最大迭代次数
Gm = 10000;
F0 = 0.5;
Np = 100;
CR = 0.9; %交叉概率
G= 1; %初始化代数
D = 10; %所求问题的维数
Gmin = zeros(1,Gm); %各代的最优值
best_x = zeros(Gm,D); %各代的最优解
value = zeros(1,Np); %产生初始种群
%xmin = -10; xmax = 100;%带负数的下界
xmin = -5.12;
xmax = 5.12;
function y = f(v) %Rastrigr 函数
y = sum(v.^2 - 10.*cos(2.*pi.*v) + 10);
end
X0 = (xmax-xmin)*rand(Np,D) + xmin; %产生Np个D维向量
XG = X0;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
XG_next_1= zeros(Np,D); %初始化
XG_next_2 = zeros(Np,D);
XG_next = zeros(Np,D);
while G <= Gm
G
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for i = 1:Np %产生j,k,p三个不同的数
a = 1;
b = Np;
dx = randperm(b-a+1) + a- 1;
j = dx(1);
k = dx(2);
p = dx(3); %要保证与i不同
if j == i
j = dx(4);
else if k == i
k = dx(4);
else if p == i
p = dx(4);
end
end
end
%变异算子
suanzi = exp(1-Gm/(Gm + 1-G));
F = F0*2.^suanzi;
%变异的个体来自三个随机父代
son = XG(p,:) + F*(XG(j,:) - XG(k,:));
for j = 1: D
if son(1,j) >xmin & son(1,j) < xmax %防止变异超出边界
XG_next_1(i,j) = son(1,j);
else
XG_next_1(i,j) = (xmax - xmin)*rand(1) + xmin;
end
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for i = 1: Np
randx = randperm(D);% [1,2,3,...D]的随机序列
for j = 1: D
if rand > CR & randx(1) ~= j % CR = 0.9
XG_next_2(i,j) = XG(i,j);
else
XG_next_2(i,j) = XG_next_1(i,j);
end
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for i = 1:Np
if f(XG_next_2(i,:)) < f(XG(i,:))
XG_next(i,:) = XG_next_2(i,:);
else
XG_next(i,:) = XG(i,:);
end
end
%找出最小值
for i = 1:Np
value(i) = f(XG_next(i,:));
end
[value_min,pos_min] = min(value);
%第G代中的目标函数的最小值
Gmin(G) = value_min;
%保存最优的个体
best_x(G,:) = XG_next(pos_min,:);
XG = XG_next;
trace(G,1) = G;
trace(G,2) = value_min;
G = G + 1;
end
[value_min,pos_min] = min(Gmin);
best_value = value_min
best_vector = best_x(pos_min,:)
fprintf('DE所耗的时间为：%f \n',cputime - t0);
%画出代数跟最优函数值之间的关系图
plot(trace(:,1),trace(:,2));
end
感谢关注，欢迎感兴趣的一起交流讨论！