浅析智能优化算法—进化策略 (上)

时间：2024-06-04

? 在学习最优模型参数时，梯度下降并不是唯一的选择，在不知道目标函数的精确解析或不能直接计算梯度的情况下，一种无梯度随机优化算法—进化策略 $\ ext{(Evolution Strategies, ES)}$ 将能发挥不可替代的作用。

? 本系列文章分上下两篇，从经典二元和多元进化策略，到设计巧妙的协方差自适应调整的进化策略 $\ ext{CMA-ES}$ ，分别从算法介绍、理解和应用等方面进行整理和讨论。

? 进化策略是一种黑箱优化算法 $\ ext{(Black box optimization)}$ ，诞生于进化算法 $\ ext{(Evolutionary algorithm, EA)}$ 家族。进化算法是一种基于种群划分的优化算法，其灵感源于自然选择。自然选择认为具有有利于生存特性的个体可以世代生存，并将好的特性传给下一代。由于不需要使用梯度更新、利用函数的内部知识，所以进化策略适用于无梯度优化、黑盒优化和连续变量的函数优化问题等场景。

? 同神经网络梯度下降算法一样，进化策略也是最优化算法的一种，但不同的是，进化策略是一种不需要建立中间复杂函数关系的黑盒算法，通过干预来影响结果，逐步选取最优点迭代，只需定义 $\ ext{reward}$ 就可直接对目标进行参数优化。针对中等规模的参数寻优，进化策略能表现出很好的效果。对于一个优化问题，如果不能够直接对 $\ ext{x}$ 和 $\ ext{y}$ 定义其之间的联系，或者说他们联系很多且不好确定时，则可直接选用进化策略。

图1. 黑箱模型 $f: \\mathcal{X}\\subseteq \\mathbb{R}^n \\rightarrow \\mathbb{R}, \\quad \\boldsymbol{x}\\mapsto f(\\boldsymbol{x})$

? 进化策略的主要思路是通过反复迭代调整一个正态分布进行搜索，主要有以下三步：采样产生新解、计算目标函数值和更新分布参数。在算法每次进化中，一次完整的迭代称为一代 $\ ext{(generation)}$ 、一个候选解称为一个个体、计算目标函数值的过程称为评估、每次迭代产生的新的候选解称为子代 $\ ext{(offspring)}$ 、通过选择得到的用于产生子代的解称为父代 $\ ext{(parent)}$ ，其中每次迭代的正态分布一般写成：

$\\boldsymbol{x}_i \\sim m+\\sigma \\mathcal{N}_i(\\mathbf{0}, \\mathbf{C}) \\quad \ ext{ for }i=1, \\ldots, \\lambda \\\\$

其中三个参数所起的作用为：

$m_t$ ：均值，决定分布的中心位置，在算法中决定搜索区域；
$\\sigma_t$ ：步长参数，决定分布的整体方差，在算法中决定搜索范围的大小和强度；
$C_t$ ：协方差矩阵，决定分布的形状，在算法中决定变量之间的依赖关系，以及搜索方向之间的相对尺度。

? 进化策略设计的核心是对上面三个参数进行调整，尤其是步长参数和协方差矩阵的调整，以达到尽可能好的搜索效果，而且这些参数对算法收敛速率有非常重要的影响。一般地， $\ ext{ES}$ 参数调整的基本思路是，调整参数使沿好的搜索方向进行搜索的概率增大。

图2. 正态分布采样和 2-D 标准正态分布 $^{[1]}$

? 根据产生解和选择解的方式不同，进化策略可以分为如下几种类型 $^{[2]}$ ：

? $(1+1)\ ext{-ES}$ 是进化策略的一种形式，每次迭代只产生一个新解，通过与父代进行比较，较好的一个成为下一次迭代的父代，其他的则直接舍去，并相应的调整分布参数，该算法也是众多形式中比较方便有效的一种，算法流程描述如下：

选择一个初始解 $\\mathrm{x}$ ；
通过初始解 $\\mathrm{X}$ 和变异强度 $\\delta$ ，产生新解 $y=x+N(0, \\delta)$ ；
比较 $\\mathrm{f}(\\mathrm{x})$ 和 $\\mathrm{f}(\\mathrm{y})$ ，如果变异成功 $f(y)>f(x)$ ，则 $\\mathrm{y}$ 替换 $\\mathrm{x}$ ；
重复执行2、3步，直到满足条件跳出。

? 二元 $\ ext{ES}$ 的变异强度是由一个为 $\\delta$ 的正态分布 $N(0, \\delta)$ 产生所决定的，这里理解 $\\delta$ 为变异强度，通过控制分布、选取扰动影响进化强度；通过对比扰动带来的 $\ ext{reward}$ 选择成功变异的扰动，进而控制进化方向，因此能否找到最优解很大程度上取决于 $\\delta$ 。

? 这里补充下 $\ ext{Rechenberg}$ 提出的著名" $1/5\ ext{ success rule}$ "，根据历史成功变异能力不断的调控 $\\delta$ 。成功的变异与所有变异的比率应该是 $\ ext{1/5}$ ，若比率大于 $\ ext{1/5}$ ，则应增加变异强度进一步搜寻最优解，否则就降低变异强度。计算公式如下， $\ ext{ Schwefel }$ 提出将因子 $c_d=0.817$ 用于 $\\sigma$ 更新规则：
$\\delta^{g+1}=\\left\\{\\begin{array}{l}\\delta^g\\left(1 / c_d\\right) ,\ ext{ if }(p s>1 / 5) \\\\ \\delta^g c_d, \ ext{ if }(p s)<1 / 5 \\\\ \\delta^g ,\ ext{ else }\\end{array}\\right. \\\\$

? 利用最优变异强度和" $1/5\ ext{ success rule}$ "，可使得 $\ ext{ES}$ 优于简单的蒙特卡洛方法，且在多元 $\ ext{ES}$ 中引入种群方法可以使 $\ ext{ES}$ 更进一步。在 $\ ext{ES}$ 中引入多个个体的方法可形成两种进化策略 $^{[7]}$ ： $(\\mu+\\lambda)-ES$ 和 $(\\mu, \\lambda)-ES$ 。

图3. $(\\mu+\\lambda)\ ext{ -ES}$ 和 $(\\mu, \\lambda)\ ext{ -ES}$ 原理 $^{[2]}$

? $(\\mu+\\lambda)\ ext{ -ES}$ 是一种"加法策略“，其中 $\\mu (>1)$ 个父代通过仅使用变异来创建 $\\lambda$ 个子代。由于在选择操作中同时使用了父代和子代，因此是一个 $(\\mu+\\lambda)\ ext{ -ES}$ 精英算法。但在某些优化场景中，尽管保留精英是必要的，但并不能控制精英主义的程度，容易导致算法收敛于局部最优，减少继续对末知空间的探索。为了避免出现这个问题，提出了一种新的 $(\\mu, \\lambda)\ ext{ -ES}$ 。

? $(\\mu, \\lambda)\ ext{ -ES}$ 的思路是每次迭代产生 $\\lambda$ 个新解，其中较好的 $\\mu$ 个成为下一次迭代的父代，其他的直接舍去，并相应的调整分布参数。这种方法中所有解都只存活一代，避免长时间陷入某个范围，且每次只保留产生的最好解，该方法常用于理论分析。

? 二维 $\ ext{Rastrigin}$ 函数常被用于测试连续黑盒优化算法，如下为该函数值分布图和自上而下的二维图，图中较浅的区域代表的较高值，如图可知该函数存在许多局部最优值，因此优化算法的任务就是找到一组模型参数 $(x,y)$ ，使 $\\mathbf{F}(x,y)$ 尽可能地接近全局最大值。

图5. 二维 $\ ext{Rastrigin}$ 函数示意图 $^{[3]}$

? 下面分别展示了经典 $\ ext{ES}$ 和简单遗传算法 $\ ext{(Genetic Algorithm，GA)}$ 在 $\ ext{Rastrigin}$ 函数上的探索效果，可以看到经典 $\ ext{ES}$ 除了最佳解之外，会丢掉所有其他解，这是一种“贪婪”的做法，一般只适用于简单问题，对于更复杂的问题，容易陷入局部最优解。遗传算法 $\ ext{GA}$ 则是通过跟踪一组多样化的候选解来帮助多样性，以繁衍下一代，然而在实践中，大多数精英存活种群中的解决方案会随着时间的推移，同样会收敛到一个局部最优。

图6. $\ ext{GA}$ 和 $\ ext{ES}$ 在二维 $\ ext{Rastrigin}$ 函数上的探索效果对比 $^{[3]}$

? 简单 $\ ext{ES}$ 和 $\ ext{GA}$ 的缺点是其标准差噪声参数都是固定的，有时我们希望探索更多有用的可行解范围，需要增加搜索空间的标准差，或者在接近一个良好解时，只想微调一下解决方案时，能够自动调整搜索空间大小和移动方向，因此出现了协方差自适应调整的进化策略 $\ ext{(Covariance Matrix Adaptation Evolution Strategy，CMA-ES)}$ 。

? 相比于上面几种简单的集中式方法，从名字就能看出，该算法能够进行自适应的进行参数调整，最终使得产生好解的概率逐渐增大。更多关于 $\ ext{CMA-ES}$ 的基本原理、算法步骤及其在无人机和集群参数优化中的应用，将在下文进一步探讨。

[1]. Hansen, Nikolaus. "The CMA evolution strategy: A tutorial." arXiv preprint arXiv:1604.00772 (2016).

[2]. 公众号：进化策略算法（CMA-ES）理解

[3]. A Visual Guide to Evolution Strategies

[4]. The CMA Evolution Strategy

[5]. Hansen, Nikolaus, and Andreas Ostermeier. "Completely derandomized self-adaptation in evolution strategies." Evolutionary computation 9.2 (2001): 159-195.

[6]. 知乎：进化策略-简介1

[7]. CSDN：进化计算-进化策略（Evolutionary Strategies,ES）前世今生与代码共享

封面：智能优化算法：分类、特点和未来