差分进化算法是一种十分强大的黑盒子优化算法(也称无导数优化算法)黑盒优化是关于寻找一个函数的最小值 [公式] ,我们不知道他的解析形式,因此无法计算导数来最小化它,下图显示了DE算法如何在连续的步骤中逼近一个函数的最小值:

黑盒函数的优化在现实世界问题中非常常见,有些需要要优化的函数非常复杂(并且可能需要使用模拟器或外部软件进行计算)。对于这类问题,DE可以做出非常漂亮的结果,这就是为什么它在解决许多不同领域的问题时很受欢迎,包括天文学、化学、生物学等等。例如,欧洲航天局(欧空局)利用DE设计最佳轨道,以便尽可能少地使用燃料到达行星的轨道。听起来很棒的对吗?最重要的是,该算法非常容易理解和实现。

在讨论更多技术细节之前,让我们先动手。DE吸引我的地方不仅在于它的强大功能,还在于它的简单性,因为它只需几行代码就可以实现。下面是de的一种简单实现形式:

import numpy as np

def de(fobj, bounds, mut=0.8, crossp=0.7, popsize=20, its=1000):
    dimensions = len(bounds)
    pop = np.random.rand(popsize, dimensions)
    min_b, max_b = np.asarray(bounds).T
    diff = np.fabs(min_b - max_b)
    pop_denorm = min_b + pop * diff
    fitness = np.asarray([fobj(ind) for ind in pop_denorm])
    best_idx = np.argmin(fitness)
    best = pop_denorm[best_idx]
    for i in range(its):
        for j in range(popsize):
            idxs = [idx for idx in range(popsize) if idx != j]
            a, b, c = pop[np.random.choice(idxs, 3, replace = False)]
            mutant = np.clip(a + mut * (b - c), 0, 1)
            cross_points = np.random.rand(dimensions) < crossp
            if not np.any(cross_points):
                cross_points[np.random.randint(0, dimensions)] = True
            trial = np.where(cross_points, mutant, pop[j])
            trial_denorm = min_b + trial * diff
            f = fobj(trial_denorm)
            if f < fitness[j]:
                fitness[j] = f
                pop[j] = trial
                if f < fitness[best_idx]:
                    best_idx = j
                    best = trial_denorm
        yield best, fitness[best_idx]

在上文中,我们说到做车道线拟合时,有时候单一曲线并不能良好的表达一条曲线,所以本文将用该算法解决此问题。

现在让我们用另一个具体的例子来看看这个算法。给定一组点(x, y),曲线拟合问题的目标是找到更好地拟合给定点的多项式,例如通过最小化每个点与曲线之间的距离和,说白了就是让拟合出来的曲线更贴近实际采样点。为此,我们将使用函数 [公式] 生成一组观测值(x, y),并添加少量高斯噪声:

>>> x = np.linspace(0, 10, 500)
>>> y = np.cos(x) + np.random.normal(0, 0.2, 500)
>>> plt.scatter(x, y)
>>> plt.plot(x, np.cos(x), label='cos(x)')
>>> plt.legend()

图为使用函数y=cos(x)生成的带有高斯噪声的2D点(x, y)数据集

我们的目标是将一条曲线(由多项式定义)拟合到我们之前生成的点集。这条曲线应该接近生成这些点的原始 [公式] 

我们需要一个多项式有足够的次数来生成曲线。为了这个目的,一个5次的多项式应该足够了(你可以尝试更多/更少的次数,看看会发生什么):

[公式]

这个多项式有6个参数 [公式] 。这些参数的不同值会产生不同的曲线。让我们实现它:

def fmodel(x, w):
    return w[0] + w[1]*x + w[2] * x**2 + w[3] * x**3 + w[4] * x**4 + w[5] * x**5

利用这个表达式,参数不同,我们可以生成无限条可能的曲线。例如:

>>> plt.plot(x, fmodel(x, [1.0, -0.01, 0.01, -0.1, 0.1, -0.01]))


在这无穷多的曲线中,我们想要一条更接近原始函数 [公式] 的曲线。为此,我们需要一个函数来衡量多项式的好坏。例如,我们可以使用均方根误差(RMSE)函数:

def rmse(w):
    y_pred = fmodel(x, w)
    return np.sqrt(sum((y - y_pred)**2) / len(y))

现在我们对问题有了清晰的描述:我们需要找到5次多项式的参数 [公式] ,使rmse函数最小化。让我们用DE进化一个由20个随机多项式组成的种群,用于2000次迭代:

>>> result = list(de(rmse, [(-5, 5)] * 6, its=2000))
>>> result

(array([ 0.99677643,  0.47572443, -1.39088333,  0.50950016, -0.06498931,
         0.00273167]), 0.214860061914732)

我们得到了一个均方根为~0.215的解。我们可以画出这个多项式来看看我们的近似有多好:

>>> plt.scatter(x, y)
>>> plt.plot(x, np.cos(x), label='cos(x)')
>>> plt.plot(x, fmodel(x, [0.99677643, 0.47572443, -1.39088333, 
>>>                        0.50950016, -0.06498931, 0.00273167]), label='result')
>>> plt.legend()



本文主要介绍了一种简单的进化差分算法,并且展示了该算法的实现方法和效果,后续将继续介绍该算法具体的实现细节和参数调节方式,并且说明如何利用该算法寻找最小二乘法最优分段点,敬请期待!