差分进化算法-优化多项式拟合

差分进化算法由Rainer Storn和Kenneth Price于1995年首次提出，主要用于求解连续变量的全局优化问题。它的基本流程和遗传算法非常相似，都包括变异、重组和选择操作，从随机产生的初始种群开始，以适应度值作为选择标准，保留优良个体，淘汰劣质个体，引导搜索过程向全局最优解逼近。二者的不同之处在于：差分进化算法采用实数矢量进行编码，并采用基于差分的简单变异操作和一对一的竞争生存策略，降低了复杂性。它首先从种群中随机选择两个个体，计算它们的矢量差，以此作为第三个个体的随机变化源，将其加权后按照一定的规则与第三个个体求和，从而产生变异个体。然后，变异个体与某个预先决定的目标（父代）个体进行参数混合重组，生成新的试验个体。最后，在试验个体与目标个体之间根据适应度值进行选择，将优秀的个体保存到下一代种群中去。基本流程如图5.9（a）所示。遗传算法根据适应度值，按照概率在父代中进行选择，然后交叉重组和变异。显然，差分进化算法的收敛效果更明显。

图5.9　差分进化算法流程图

差分进化算法可以分为两个部分。首先，初始化种群，通过在参数的限定范围内为每个参数生成均匀分布的随机值，构造NP个均匀分布的个体矢量，参数就相当于矢量的分量，它的个数就代表着个体矢量的维度。通常NP的大小取决于维度d，一般取NP=5d～10d。可以先尝试固定值。初始化完成后，就进入进化阶段。进化阶段的具体内容如图5.9（b）所示。

在进化阶段，将执行突变、重组和选择等操作。

在突变过程中需要为种群中的每个目标矢量产生一个突变矢量，G代表当前种群所处的世代。式（6.8）为突变矢量的基本产生方法：

其中，r1、r2、r3为从种群中随机选择的互不相同的3个个体，这3个个体和目标矢量也不同。如图5.9（b）中，为了对步骤1选择的目标矢量执行突变操作，随机选择了r1和r2两个个体的矢量求差，并乘以缩放因子F进行加权后再和r3个体的矢量相加，形成突变矢量。F称为差分权重或变异常数，它的大小可以控制差分矢量的影响程度，取值在［0，2］区间，通常在（0，1）区间取值更稳定，推荐取值范围为［0.4，0.95］。

交叉重组在突变矢量和目标矢量之间进行，由重组参数Cr∈［0，1］控制。该参数控制重组的速率或概率，通常取值范围为［0.1，0.8］，首选Cr=0.5。常用的重组方式有二项式（binomial）和指数式（exponential）两种。

在二项式方案中，对个体矢量的每个分量都按照概率来交叉，生成一个0到1之间均匀分布的随机数randj，以该随机数决定该分量是否交换，如公式（5.9）所示：

对每一个分量先抽一个签，如果大于Cr，那么就交换，否则不交换，换下一个分量抽签，……，从而得到重组后的矢量。

在指数方案中，选择突变矢量的一段进行交换，该段以具有随机长度为L的随机整数k开始，也就是交换的分量位置以及分量个数都是随机的，交换从k到k-L+1的所有分量。显然，k∈［0，d-1］，L∈［1，d］，d为矢量维度。

除了采用式（5.8）的模式产生突变矢量以外，还有其他一些模式：

rand表示随机选取，best表示选种群中最优的，1表示使用1个差分矢量。式（5.8）模式也称为rand/1模式。突变模式和重组模式结合就形成了差分进化算法的方案名称，比如：rand/1/bin就代表采用随机突变矢量、一个差分矢量、二项式方式重组方案，Best/1/exp表示采用最佳突变矢量、一个差分矢量、指数方式重组方案。

选择的方法同遗传算法一样，根据适应度值在目标矢量和试验矢量之间选择优秀的存活到下一代

下面用多项式曲线拟合（polynomial curve fitting）的例子来进行说明。多项式拟合是指给定一些点，找到能最好拟合这些点的多项式。拟合的评价可以通过拟合误差来进行，比如计算并以每个点和拟合曲线的距离的和作为拟合误差，然后以用差分进化算法最小化拟合误差的方式来找到最佳拟合多项式。

例5.3　在函数f（）x=cos（x）中添加一些高斯噪声，得到一组观测值（x，y），用该观测值作为样本，求拟合多项式。

解　首先可以在Python中绘制观测值的散点图，需要用到NumPy和Matplotlib包。

输出效果如图5.10所示。

为了拟合复杂的曲线，需要使用足够高次数的多项式，这里选择5次多项式f（w，x）=w0+w1x+w2x2+w3x3+w4x4+w5x5，它具有6个系数w=（w0，w1，w2，w3，w4，w5）。（可以试着将次数变多或变少看一下会发生什么。）

图5.10　被高斯噪声污染了的余弦信号

为了使用差分进化算法，种群的个体数至少为4个，假设种群数量为20个，每个矢量用和w对应的6个实数来表示。为了测量多项式拟合的程度怎样，需要计算均方根误差，可以用均方根误差作为适应度函数来判断个体的优劣，均方根误差越小说明拟合得越好。

接下来，要用差分进化算法找到多项式的一组系数w，使得均方根误差达到最小。

首先初始化，生成数量为popSize、维度为dimensions的随机初始种群。

(www.xing528.com)

然后执行图5.9（b）所示流程：

（1）选择目标个体。

（2）随机选择其他3个互不相同的群成员。

（3，4）求两个个体的差分矢量并乘以差分权重，然后与第3个个体的矢量相加。

（5）进行重组，得到试验矢量。

（6）选择适应度好的存活到下一代。

将此过程循环迭代2000次后，均方根误差小于0.22，此时的参数拟合曲线如图5.11所示。

图5.11　多项式拟合曲线

差分进化算法对于复杂函数的优化非常简单和有效，尤其是在一些其他方法不合适的情况下，比如梯度下降。实际应用时，还可以借助Python的库进一步简化差分进化算法的使用方法。

包含差分进化算法的Python库有许多，比如SciPy、Platypus、Pygmo、Yabox等。在scipy.optimize库中具有differential_evolution类。它用于为多变量目标函数寻找全局最小值，定义如下：

主要参数说明如下：

func为需要最小化的目标函数，形式必须为“f（x，*args）”，其中“x”是由一维数组表示的函数参数，“*args”是用元组表示的函数需要的一些固定参数。

bounds是函数参数的边界，可以用（min，max）对来表示函数func中“x”的每个参数的边界，bounds的长度需要和“x”的参数个数一致。

strategy是字符串，代表着差分进化算法的突变和重组的模式，默认值为“‘best1bin’”，其他的还有“‘rand1bin’”和“‘best2exp’”等。

maxiter是最大迭代次数。

popsize是种群大小参数，实际种群大小为“popsize*len（x）”。

tol为收敛时的相对容差设定。

atol为收敛时的绝对容差设定。

mutation是差分权重F，默认为0.5。

recombination为重组参数Cr，默认为0.7。

返回值为优化结果对象OptimizeResult，其中“x”属性是解矩阵，“fun”属性是目标函数的值。

对于例5.3，调用SciPy中的库实现代码如下：

运行结果如下：