在 Python 中从零开始实现进化策略

进化策略是一种随机全局优化算法。

它是一种进化算法,与其他算法(如遗传算法)相关,但它是专门为连续函数优化而设计的。

在本教程中,您将学习如何实现进化策略优化算法。

完成本教程后,您将了解:

  • 进化策略是一种随机全局优化算法,其灵感来自于自然选择的生物进化理论。
  • 进化策略有标准术语,并且算法有两种常见版本,分别称为 (mu, lambda)-ES 和 (mu + lambda)-ES。
  • 如何实现进化策略算法并将其应用于连续目标函数。

开始您的项目,阅读我的新书《机器学习优化》,其中包含分步教程和所有示例的Python源代码文件。

让我们开始吧。

Evolution Strategies From Scratch in Python

在 Python 中从零开始实现进化策略
照片由 Alexis A. Bermúdez 拍摄,保留部分权利。

教程概述

本教程分为三个部分;它们是:

  1. 进化策略
  2. 开发 (mu, lambda)-ES
  3. 开发 (mu + lambda)-ES

进化策略

进化策略,有时也称为进化策略(单数)或 ES,是一种随机全局优化算法。

该技术于 20 世纪 60 年代开发,供工程师手动实现,用于风洞中的最小阻力设计。

进化策略 (ES) 系列算法由 Ingo Rechenberg 和 Hans-Paul Schwefel 于 20 世纪 60 年代中期在柏林工业大学开发。

— 第 31 页,元启发式算法要点,2011 年。

进化策略是一种进化算法,其灵感来自自然选择的生物进化理论。与其他进化算法不同,它不使用任何形式的交叉;相反,候选解的修改仅限于变异算子。通过这种方式,进化策略可以被认为是并行随机爬山的一种类型。

该算法涉及一个候选解的种群,最初是随机生成的。算法的每次迭代首先评估解的种群,然后删除除了一部分最优解之外的所有解,这称为截断选择。剩余的解(父代)中的每一个都用作生成若干新候选解(变异)的基础,这些新候选解会替换父代或与父代竞争种群中的位置,以便在算法的下一次迭代(代)中进行考虑。

此过程有多种变体,并且有标准术语来总结算法。种群大小称为lambda,每次迭代选择的父代数量称为mu

每个父代创建的子代数量计算为 (lambda / mu),应选择参数使除法无余数。

  • mu:每次迭代选择的父代数量。
  • lambda:种群大小。
  • lambda / mu:每个选定父代生成的子代数量。

使用括号表示法描述算法配置,例如(mu, lambda)-ES。例如,如果mu=5lambda=20,则将其总结为(5, 20)-ESmulambda参数之间的逗号 (,) 表示子代在算法的每次迭代中直接替换父代。

  • (mu, lambda)-ES:一种进化策略版本,其中子代替换父代。

mulambda参数的加号 (+) 分隔表示子代和父代将共同定义下一迭代的种群。

  • (mu + lambda)-ES:一种进化策略版本,其中子代和父代被添加到种群中。

随机爬山算法可以实现为进化策略,并且表示法为(1 + 1)-ES

这是模拟或规范的 ES 算法,文献中有许多扩展和变体。

现在我们熟悉了进化策略,就可以探索如何实现该算法了。

想要开始学习优化算法吗?

立即参加我为期7天的免费电子邮件速成课程(附示例代码)。

点击注册,同时获得该课程的免费PDF电子书版本。

开发 (mu, lambda)-ES

在本节中,我们将开发一个(mu, lambda)-ES,即一种子代替换父代的算法版本。

首先,让我们定义一个具有挑战性的优化问题作为实现算法的基础。

Ackley 函数是多模态目标函数的一个示例,它具有单个全局最优解和多个局部最优解,局部搜索可能会陷入其中。

因此,需要一种全局优化技术。它是一个二维目标函数,在 [0,0] 处有全局最优解,其值为 0.0。

下面的例子实现了 Ackley 函数并创建了一个三维曲面图,显示了全局最优解和多个局部最优解。

运行该示例会创建 Ackley 函数的曲面图,显示大量的局部最优解。

3D Surface Plot of the Ackley Multimodal Function

Ackley 多峰函数的三维曲面图

我们将生成随机候选解以及现有候选解的修改版本。所有候选解都必须在搜索问题的边界内,这一点很重要。

为了实现这一点,我们将开发一个函数来检查候选解是否在搜索边界内,如果不在,则将其丢弃并生成另一个解。

下面的 `in_bounds()` 函数将接收一个候选解(点)和搜索空间边界的定义(bounds),如果解在搜索边界内,则返回 True,否则返回 False。

然后,我们可以在生成“lam”(例如,lambda)个随机候选解的初始种群时使用此函数。

例如

接下来,我们可以迭代固定次数的算法。每次迭代首先评估种群中的每个候选解。

我们将计算得分并将它们存储在一个单独的并行列表中。

接下来,我们需要选择得分最高的“mu”个父代,在本例中是得分最低的,因为我们在最小化目标函数。

我们将分两步进行。首先,我们将根据得分按升序对候选解进行排名,以便得分最低的解排名为 0,下一个排名为 1,依此类推。我们可以通过双重调用 argsort 函数 来实现此目的。

然后,我们将使用排名并选择排名低于“mu”值的父代。这意味着如果 `mu` 设置为 5 以选择 5 个父代,则只选择排名在 0 到 4 之间的父代。

然后,我们可以为每个选定的父代创建子代。

首先,我们必须计算每个父代要创建的子代总数。

然后,我们可以遍历每个父代并创建它们的修改版本。

我们将使用一种类似于随机爬山的技术来创建子代。具体来说,每个变量将使用以当前值为均值、标准差提供为“步长”超参数的高斯分布进行采样。

我们还可以检查每个选定的父代是否优于迄今为止看到的最佳解,以便我们可以在搜索结束时返回最佳解。

创建的子代可以添加到列表中,并在算法迭代结束时用子代列表替换种群。

我们可以将所有这些整合到一个名为 `es_comma()` 的函数中,该函数执行进化策略算法的逗号版本。

该函数采用目标函数的名称、搜索空间的边界、迭代次数、步长以及 mu 和 lambda 超参数,并返回搜索过程中找到的最佳解及其评估值。

接下来,我们可以将此算法应用于我们的 Ackley 目标函数。

我们将运行算法 5,000 次迭代,并在搜索空间中使用 0.15 的步长。我们将使用 100 的种群大小(lambda),选择 20 个父代(mu)。这些超参数是在经过一些试错后选择的。

在搜索结束时,我们将报告搜索过程中找到的最佳候选解。

将所有内容整合在一起,下面列出了将逗号版本的进化策略算法应用于 Ackley 目标函数的完整示例。

运行示例会在每次找到更好的解时报告候选解和得分,然后在搜索结束时报告找到的最佳解。

注意:由于算法或评估过程的随机性,或数值精度的差异,您的结果可能会有所不同。请考虑运行示例几次并比较平均结果。

在这种情况下,我们可以看到在搜索过程中性能提高了约 22 次,并且最佳解决方案接近最优值。

毫无疑问,该解决方案可以作为局部搜索算法的起点,以进行进一步的改进,这是在使用 ES 等全局优化算法时的常见做法。

现在我们已经熟悉了如何实现进化策略的逗号版本,让我们看看如何实现加号版本。

开发 (mu + lambda)-ES

进化策略算法的加号版本与逗号版本非常相似。

主要区别在于,最后,子代和父代共同构成种群,而不是仅仅子代。这使得父代能够与子代竞争下一迭代的选择。

这可能导致搜索算法的行为更加贪婪,并可能过早收敛到局部最优值(次优解)。这样做的好处是算法能够利用找到的优秀候选解,并专注于该区域的候选解,从而可能找到进一步的改进。

我们可以通过修改函数以在创建子代时添加父代来实现该算法的加号版本。

更新后的函数版本增加了此功能,并有一个新名称 *es_plus()*,如下所示。

我们可以将此版本的算法应用于 Ackley 目标函数,其超参数与上一节中使用的相同。

完整的示例如下所示。

运行示例会在每次找到更好的解时报告候选解和得分,然后在搜索结束时报告找到的最佳解。

注意:由于算法或评估过程的随机性,或数值精度的差异,您的结果可能会有所不同。请考虑运行示例几次并比较平均结果。

在这种情况下,我们可以看到在搜索过程中性能提高了约 24 次。我们还可以看到,与逗号版本在此目标函数上找到的 0.001147 相比,找到了一个更好的最终解决方案,评估值为 0.000532。

进一步阅读

如果您想深入了解,本节提供了更多关于该主题的资源。

论文

书籍

文章

总结

在本教程中,您了解了如何实现进化策略优化算法。

具体来说,你学到了:

  • 进化策略是一种随机全局优化算法,其灵感来自于自然选择的生物进化理论。
  • 进化策略有标准术语,并且算法有两种常见版本,分别称为 (mu, lambda)-ES 和 (mu + lambda)-ES。
  • 如何实现进化策略算法并将其应用于连续目标函数。

你有什么问题吗?
在下面的评论中提出你的问题,我会尽力回答。

掌握现代优化算法!

Optimization for Maching Learning

加深您对优化的理解

...只需几行python代码

在我的新电子书中探索如何实现
机器学习优化

它提供**自学教程**,并附有关于以下内容的**完整工作代码**:
梯度下降遗传算法爬山法曲线拟合RMSPropAdam,以及更多...

将现代优化算法应用于
您的机器学习项目


查看内容

从零开始用 Python 实现进化策略 的 6 条回复

  1. Roya 2021 年 11 月 26 日下午 4:35 #

    你好,
    非常感谢这堂全面的讲座。您能否解释一下如何将其用于 LSTM 算法以找到超参数的最佳值?
    您有 Python 代码吗?

    • Adrian Tam
      Adrian Tam 2021 年 11 月 29 日上午 8:34 #

      为什么您会使用 LSTM 来查找超参数?

  2. Roya 2021 年 11 月 29 日上午 11:26 #

    我想在 LSTM 算法中使用进化策略,并进行循环以选择 LSTM 参数的最佳值,例如 dropout 率、学习率等。

    • Adrian Tam
      Adrian Tam 2021 年 12 月 2 日上午 12:24 #

      这是一个关于 ES 如何应用的很好的例子。

  3. Stevie 2022 年 2 月 8 日下午 5:34 #

    感谢您的教程。您能否确认是否存在包含父代重组(交叉)的 ES 版本?

    我可以看到 (mu + lambda)-ES 执行了 24 次改进,而另一个版本只执行了 22 次。

    为什么 (mu + lambda)-ES 没有停止在
    2804, 最佳: f([3.86555110e-04 6.42776651e-05]) = 0.00111

    因为这比在逗号版本中
    3725, 最佳: f([ 0.00032757 -0.00023643]) = 0.00115
    更好。

    您能解释一下吗?
    谢谢你

发表回复

Machine Learning Mastery 是 Guiding Tech Media 的一部分,Guiding Tech Media 是一家领先的数字媒体出版商,专注于帮助人们了解技术。访问我们的公司网站以了解更多关于我们的使命和团队的信息。