摘 要

演化学习目前理论基础仍较为薄弱，难以受到机器学习社区的广泛认同。本文介绍了近期针对在机器学习中，具有广泛应用的子集选择问题提出的一系列性能具有理论保障的演化学习算法。

关 键 字

机器学习；演化计算；演化学习；子集选择

0 引言

“机器学习”是人工智能的一个核心领域，旨在从数据中学得具有泛化能力的模型，以改善系统自身的性能。机器学习算法被认为可由模型表示、模型评估和模型优化三个部件构成，如图1所示。为解决复杂学习任务，需要使用非线性模型表示和（或）非凸模型评估函数，导致学习问题常常归结为复杂优化问题，其目标函数往往具有不可导、不连续、存在大量局部极值和不唯一等性质。这些性质可使传统优化算法（例如梯度下降）失效，而其他强大的优化算法（例如演化算法）可能会大有用武之地。

图 1 典型机器学习过程的三个构成部件

“演化算法”是受自然演化启发的一大类随机优化算法，通过考虑“变异繁殖”和“择优选择” 这两个关键因素来模拟自然演化过程。尽管演化算法有很多不同的实现，例如遗传算法、遗传编程和演化策略等，但典型的演化算法都能抽象为如图2所示的四个步骤。

（1）生成一个包含若干初始解的集合，称为种群；

（2）基于当前种群，通过变异和交叉等算子产生一些子代解；

（3）从当前种群和产生的子代解中去除一些 相对差的解，形成新的种群；

（4）返回第二步并重复运行，直至满足某个停止条件。

图 2 演化算法的一般结构

从上述过程中可以看到，演化算法在求解优化问题时，只需能对解的优劣进行评估，而无需问题结构信息。特别地，演化算法在缺乏目标函数的梯度信息，甚至缺乏目标函数的显示表达式时都能使用，只需能通过实验或模拟评估解的相对优劣即可。因此，演化算法被视为一种通用优化算法，甚至能以“黑箱”的方式求解优化问题。另外，演化算法基于种群搜索（即在优化过程中维持一个解集）的特质正好和多目标优化寻找一个最优解集的要求相配；也就是说，演化算法运行一次就可找到多个帕累托最优解，故演化算法 也适于求解多目标优化问题。

由于强大的优化能力，演化算法已被用来求解机器学习中的复杂优化问题。我们在《演化学习研究进展》中，从学习任务的类型（特征学习、监督学习、非监督学习和强化学习）出发，介绍 了“演化学习”的代表性应用。特别地，演化算法近年来被成功地用于优化深度神经网络，包括网络结构搜索和网络压缩等，演化得到的网络模型在性能上可超越专家设计的模型。然而，演化学习的这些应用往往缺乏理论分析，使其目前仍难以受到机器学习社区的广泛认同。研究者们为此进行了许多尝试，近期终于针对在机器学习中 具有广泛应用的“子集选择”问题，成功设计出了一系列性能具有理论保障的演化学习算法，这些算法可获得目前已知的最佳“多项式时间近似保证”。本文将对此进行简要介绍。

1 子集选择

如定义1所述，子集选择旨在从全集中选择一个规模有限的子集以最大化某个给定的目标函数。

选自《中国人工智能学会通讯》

2020年 第10卷 第5期 机器学习及其应用专题