差分进化算法是一种十分强大的黑盒子优化算法(也称无导数优化算法)黑盒优化是关于寻找一个函数的最小值 ,我们不知道他的解析形式,因此无法计算导数来最小化它,下图显示了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()
我们的目标是将一条曲线(由多项式定义)拟合到我们之前生成的点集。这条曲线应该接近生成这些点的原始 。
我们需要一个多项式有足够的次数来生成曲线。为了这个目的,一个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()
本文主要介绍了一种简单的进化差分算法,并且展示了该算法的实现方法和效果,后续将继续介绍该算法具体的实现细节和参数调节方式,并且说明如何利用该算法寻找最小二乘法最优分段点,敬请期待!
评论(0)
您还未登录,请登录后发表或查看评论