当前位置:文档之家› 差分进化算法介绍

差分进化算法介绍

1.差分进化算法背景
差分进化(Differential Evolution,DE)是启发式优化算法的一种,它是基于群体差异的启发式随机搜索算法,该算法是Raincr Stom和Kenneth Price为求解切比雪夫多项式而提出的。

差分进化算法具有原理简单、受控参数少、鲁棒性强等特点。

近年来,DE在约束优化计算、聚类优化计算、非线性优化控制、神经网络优化、滤波器设计、阵列天线方向图综合及其它方面得到了广泛的应用。

差分算法的研究一直相当活跃,基于优胜劣汰自然选择的思想和简单的差分操作使差分算法在一定程度上具有自组织、自适应、自学习等特征。

它的全局寻优能力和易于实施使其在诸多应用中取得成功。

2.差分进化算法简介
差分进化算法采用实数编码方式,其算法原理同遗传算法相似刚,主要包括变异、交叉和选择三个基本进化步骤。

DE算法中的选择策略通常为锦标赛选择,而交叉操作方式与遗传算法也大体相同,但在变异操作方面使用了差分策略,即:利用种群中个体间的差分向量对个体进行扰动,实现个体的变异。

与进化策略(Es)采用Gauss或Cauchy分布作为扰动向量的概率密度函数不同,DE使用的差分策略可根据种群内个体的分布自动调节差分向量(扰动向量)的大小,自适应好;DE 的变异方式,有效地利用了群体分布特性,提高了算法的搜索能力,避免了遗传算法中变异方式的不足。

3.差分进化算法适用情况
差分进化算法是一种随机的并行直接搜索算法,最初的设想是用于解决切比雪夫多项式问题,后来发现差分进化算法也是解决复杂优化问题的有效技术。

它可以对非线性不可微连续空间的函数进行最小化。

目前,差分进化算法的应用和研究主要集中于连续、单目标、无约束的确定性优化问题,但是,差分进化算法在多目标、有约束、离散和噪声等复杂环境下的优化也得到了一些进展。

4.基本DE算法
差分进化算法把种群中两个成员之间的加权差向量加到第三个成员上以产生新的参数向量,这一操作称为“变异”。

然后,变异向量的参数与另外事先确
定的目标向量按一定规则混合产生试验向量,称为“交叉”。

如果实验向量代价函数比目标向量代价函数低,则实验向量则在下代中替代目标向量。

这一操作称为“选择”,种群中所有与成员必须作为目标向量按这样操作一次,以在下代中出现相同个竞争者。

进化过程中对每一代都评价最佳参数向量,以记录最小化过程,以这种方式利用随机偏差扰动产生新个体可以获得有较好收敛性的结果。

4.1初始化
DE 用NP 个维度为D 的实数值参数向量为每代的种群,每个个体表示为:(1,2,,)i NP = (1)
其中,i 为个体在种群中的序列;G 为进化代数;NP 为种群规模,在最小化过程中NP 保持不变。

种群首先要被初始化已建立优化搜索的初始点。

可以从给定边界约束内的值中随机选择以寻找初始种群。

在差分算法中,一般假设所有随机初始化种群都符
合均匀概率分布。

假设参数变量界限为L
U j j j x x x ≤≤,有:﹤
,0[0,1](+,(1,2,,;1,2,,)U L L ji j j j x rand x x x i NP j D =-==) (2)
其中:rand[0,1]—在[0,1]之间产生的均匀随机数。

如果能够得到问题的初步解,初始种群可通过对初步解加入正态分布随机偏差产生,以提高重建效果。

4.2变异
对于目标向量,,1,2,,,i G x i NP =基本差分进化算法的变异向量如下产生; ()
123,,,,i G r G r G r G v x F x x =+- (3)
其中,123,,r r r 是随机选择的序号,互不相同,并且目标向量序号I 也不相同。

故,NP 必须满足大于等于4。

变异算法[0,2]F ∈是一个实常数缩放因子,以控制偏差变量的放大作用。

4.3交叉
为增加干扰参数向量的多样性,引入交叉操作。

则试验向量变为:
(),11,12,1,,1,,i G i G i G Di G u u u u ++++= (4)
,1,1,1,,
,(())();ji G ji G ji G else v if randb j CR orj rnbr i u x +++≤=⎧⎪=⎨⎪⎩ (1,2,,,1,2,,)i NP j D == (5)
其中,()randb j 产生[0,1]之间随机发生器第个估计值;()1,2,
,rnbr i D ∈百事随机选择的序列,用来确保,1i G u +至少从,1i G v +获得一个残数据,CR 为交叉算
子,取值范围是[0,1]
4.4选择 差分算法按贪婪准则将试验向量,1i G u +与种群中的目标向量,i G x 进行比较,以决定试验向量是否能够成为下代成员。

若目标函数是最小化,则具有较小目标函数值的向量将进入下代种群。

下代中所有个体都将比当前种群的对应个体更佳或者至少一样好。

在差分进化选择程序中实验向量职能与一个个体进行对比,而非与所有个体进行比较。

4.5边界条件的处理
处理有边界的问题时,要确保产生新个体的参数值位于问题的可行域中。

确保这一结果的简单方法是将不符合要求的新个体用在可行域中随机产生的向
量替代。

即,若,1ji G u +<,1L
U j ji G j x x +>或u ,则:
,1[0,1](),
(1,2,,;1,2,,)U
L L ji G j j j u rand x x x i NP j D +=-+== (6)
另一方法是根据(6)产生新的实验向量,然后进行交叉操作,直至产生新个体满足边界约束,但是这样的做法效率较低。

5.差分算法流程
(1)确定差分控制参数和所要采用的具体策略,差分控制参数包括:种群数量、交叉算子、变异算子、最大进化代数、终止条件等等;
(2)随机产生初始化种群
(3)对初始种群进行评价,即,计算初始种群中函数值
(4)判断终止条件是否到达或者进化代数是否达到最大,以决定是否终止进化。

(5)进行变异和交叉操作,处理边界条件,得临时种群
(6)对临时种群进行评价,计算临时种群中各个体的目标函数值
(7)进行选择操作,得到新种群
(8)进化代数K=K+1,转步骤(4)。

相关主题