下载掌阅APP，畅读海量书库
立即打开
1.算法基本思想
差分进化（Differential Evolution，DE）算法由Storn和Price在1995年以技术报告的形式提出，用于连续空间中的非线性、不可微、多峰的函数的全局优化。
差分进化算法具有良好的自组织性，参数量少且易于选择，借用Bunday等人在1987年提出的Nelder-Mead局部优化算法中的思想，仅利用种群中的两个随机向量的差分信息即可对现存的向量进行扰动搜索，而不需要像进化策略一样通过预先确定的概率分布函数来确定向量的扰动。
差分进化算法与遗传算法相似，维护一个用于优化的种群，以及选择、交叉、变异算子，但差分进化算法相对于遗传算法而言，更易于并行，且收敛性更好。由于差分进化算法的向量种群的随机扰动搜索能在每个个体上独立进行，因此它具有良好的可并行性，适用于大规模、评估耗时长的高维度问题。差分进化算法相比遗传算法的遗传算子而言更具有确定性，因此在多次独立重复实验中收敛速度更快且更具鲁棒性。
2.算法流程
考虑一个维度为 D 的最小化目标函数值的问题，差分进化算法的流程图和伪代码如图1-11所示。
图1-11 差分进化算法的流程图和伪代码
从流程图中可见，差分进化算法执行遗传算子的先后顺序是变异、交叉、选择，与遗传算法的先后顺序（即选择、交叉、变异）相反，且差分进化算法的进化算子相比遗传算法而言更具有确定性，下面逐一进行介绍。
1）变异算子 ：如图1-12所示，差分进化算法通过两个种群向量的加权差分向量与第三个向量之间的和来产生新的向量，而不像遗传算法依靠随机产生新的基因。记第 G 次迭代中，规模为NP的种群中向量为 x { i ， G } ， i =1，2，3，…，NP，则变异后的向量根据式（1-2）产生
其中，
，三者都不等于
i
且互不相同，因此种群规模NP需大于等于4以达到这种操作的条件。
F
是[0，2]之间的实数，用于控制差分向量（
x
r
2，
G
-x
r
3，
G
）之间的权重。
图1-12 差分进化算法中的变异算子
2）交叉算子 ：如图1-13所示，交叉后的试验向量为 u i ， G +1 =（ u 1 i ， G +1 ， u 2 i ， G +1 ，…， u Di ， G +1 ），其中
图1-13 差分进化算法中的交叉算子
式（1-3）中randb（ j ）是第 j 个[0，1]之间的随机数，CR是[0，1]之间的交叉率，由用户决定，rnbr（ i ）是随机选中的{1，2，…， D }中的一个下标，以确保试验向量 u i ， G +1 从变异后的向量 v i ， G +1 中至少获得一个参数。
3）选择算子 ：为了决定试验向量 u i ， G +1 是否进入 G +1代的种群，采用贪心准则来决定，如式（1-4）所示：
其中，eval（ u i ， G +1 ）是评估试验向量 u i ， G +1 的适应值，cost[ i ]则是原种群中向量 x i ， G 的适应值，即如果 u i ， G +1 优于原种群中的向量 x i ， G ，则在新种群中用前者取代后者，否则新种群中的向量沿用原种群中的向量 x i ， G 。
综合上述流程来看，基本的差分进化算法需要用户预先确定的参数只有3个，即种群规模NP、差分向量权重因子 F 和交叉率CR，数量少，且算法对参数鲁棒，因而易于控制。Storn在文献[39]中指出控制参数的经验准则包括以下几项。
●常见的交叉率CR需要低于一定的数值，例如0.3，而如果无法收敛，则可以采用[0.8，1]之间的数值。
●通常NP=10* D 是较好的选择。
●权重因子常在[0.5，1]之间挑选。种群规模NP越大，权重因子 F 就应当被设置得越小。
差分进化算法的变体常用DE/ x/y/z 表示，例如图1-11中的基本的差分进化算法为DE/rand/1/bin，其中：
● x 表示当前用于变异的向量的类型，例如rand表示种群中随机抽取的向量，而best表示从当前种群中选取的最低成本的向量。
● y 表示选用的差分向量的数量。
● z 表示交叉算子的方案，例如bin表示二项交叉（binomial crossover），即由上述二项式独立实验进行的交叉。