8.18 单目标优化中的机器学习

●　 分布估计算法

分布估计算法（EDA，estimation of distributionalgorithms）是一种典型的使用了机器学习技术的EA [3] 。其最大特点是不采用一般意义上的重组算子，而是显式地对一个概率分布进行采样获得新的候选解，同时在演化的过程中不断更新概率模型。EDA的性能很大程度上取决于如何构建概率模型，这是一个典型的机器学习问题。但另一方面，EDA 的目标是解决优化问题，由于在演化过程中需要反复构建概率模型，引入复杂的机器学习技术尽管可能得到更精确的概率模型，同时也会带来十分昂贵的额外计算开销，反而不一定能提升算法性能（如单位时间内的求解质量）。因此，尽管研究者从 EDA的提出之日起就考虑了使用概率图模型，早期的EDA 仍大多使用简单的概率分布模型（如高斯分布）。这些模型具有单峰的特点，在应对多峰优化问题时往往性能不佳。因此也有一些研究已尝试利用聚类技术将 EDA 的种群分为多个子种群，并基于每个子种群分别建模，在多峰问题上取得了较好的效果[4-5] 。

●　 参数选择／调优／自适应

严格地说，EA 并非一个具体的算法，而是一个问题求解的一般性框架。该框架内的任何部件，例如候选解的表示、交叉、变异算子、选择机制（不失一般性，下文统称这些部件为参数）都可以根据不同的问题自定义配置。一方面，这保证了 EA 的普适性；但另一方面，由于参数与算法性能之间的关联是非线性的，参数可灵活配置往往给 EA 的实用带来了困难[6] 。利用机器学习自动配置参数的主要思路是通过机器学习方法显式地构建一个模型来刻画参数空间与问题空间的映射关系[5] 。在具体实践中，这样一个模型可以通过多种方式发挥作用，例如利用监督学习的方法构建“经验难度模型”(empiricalhardness model) [7] ，预测不同算法在典型 NP 难问题上的性能，从而实现算法参数的自动离线选择或优化；或是将参数的在线自适应视为一个强化学习问题加以解决[8] 。

●　 复杂问题自动约简

“固定算法改问题”的思路同样可以借助机器学习的手段加以实现。具体地说，这类研究可视为利用机器学习技术发现待求解问题的某种近似形式，令 EA 求解近似问题而非原问题，从而在保证求解质量的同时提升算法效率。其中，最有代表性的一类工作是基于代理模型的 EA (SAEA,surrogate-assisted EA) [9] 。 与 EDA 类 似，SAEA同样在演化的过程中显式地维护、更新一个或多个模型。但不同于 EDA，这些模型主要被用于适应度评估而非生成新解，因此 SAEA 一般选用支持向量机、神经网络等分类或回归模型，而非概率模型。由于 SAEA 的主要目的是减少演化过程中调用原始问题目标函数的次数，因此主要适用于原始目标函数计算代价较高的问题。需要说明的是，SAEA 也并非要求模型的精度越高越好。首先，精确的模型往往具有较高的复杂度，从而可能带来显著的额外开销，因此 SAEA 需要结合具体问题在模型精度和计算开销之间进行折衷。其次，即使代理模型与原始问题差别很大，只要两者对应相同的最优解，引入代理模型甚至有可能直接降低问题的难度（如图2 所示） [10] 。
问题自动分解是机器学习在问题约简方面的另一类例子，其目的在于将大规模问题的自变量分为若干组，对每组变量分别构建规模较小的子问题，从而达到对大规模问题分而治之的效果。自变量分组是一个非典型的聚类问题，其特殊之处在于自变量之间的相关性（“距离”）不是已知的，而只能通过某种学习机制完成[11] 。同时，一些聚类方法也已被用于对变量分组[12] 。

除以上的例子外，机器学习还能从许多其他角度为演化计算提供新思路、新工具。例如，由于演化计算的理论基础还不完善，计算实验是评价算法性能不可或缺的手段。为了保证实验评估的全面、准确，应尽可能覆盖不同难度的测试样例。给定一个待测的 EA 及问题类，机器学习方法可用于发现对该算法最难的问题实例[13] 。又如，机器学习也可被用于分析不同问题实例间的相关性，以便为 EA获得高质量的初始解[14] 。这些方面的研究目前还处于探索阶段，有广阔的发展空间。