8.14 理论基础

由于演化算法的启发性，往往缺乏理论的支持。演化算法在机器学习中的成功应用也多依赖于实验验证。然而机器学习领域对理论基础非常重视，演化学习理论基础的薄弱已成为其进一步发展的关键瓶颈。近年来，研究者们开始在演化学习的理论分析上取得进展。

文献 [33] 将集成剪枝形式化成一个二目标优化问题：
其中 s ∈ {0,1} n 表示了所有基学习器的一个子集，每一位对应了一个特定的学习器，取值为 1 则该学习器被选择，取值为 0 则反之。第 1 个目标 f(s) 表示了当前学习器子集的泛化性能，常用验证集上的错误率来衡量；第 2 个目标 ||s|| 则是 s 中 1 的数目，即当前学习器子集的大小。引入局部搜索算子的一种简单多目标演化算法 PEP 被提出用于求解该二目标优化问题，在找到的 Pareto 最优解集中，拥有最小 f(s) 值的解被输出作为最终解。理论分析得出：相比以往基于单目标优化和基于排序的两大类集成剪枝方法，PEP 方法的优化性能更优，找到的学习器子集不仅可以获得更小的测试错误率，而且包含的学习器数目更少。

机器学习中的优化问题通常带有约束条件。通过将约束的违反程度视为另一个最小化目标，多目标演化算法可以去优化原始问题的二目标形式，即优化原始目标函数和最小化约束违反程度。在包括最小生成树[34] 、最小割问题 [35] 、最小代价覆盖 [36]等若干组合优化问题上的理论分析，已经显示出演化算法求解带约束优化问题的优势。受此启发，演化算法被成功应用于求解子集选择问题，其性能在理论上有严格保证[37-38] 。

子集选择（subset selection）问题旨在从给定的 n 个变量中选择一个大小不超过 k 的变量子集使某个给定的目标最优化，其形式化为
子集选择问题出现在各种各样的应用中，比如属性选择、稀疏学习、压缩感知等。文献 [37] 将其转化为一个显示的二目标优化问题：
进而提出一种简单多目标演化算法 POSS 去求解该问题，最后在找到的一组 Pareto 最优解中，将满足子集大小约束的最优解输出作为原始约束优化问题的解。在子集选择问题的代表实例稀疏回归上的理论分析和实验验证，均显示出 POSS 方法的优越性能。文献 [38] 进一步提出了 POSS 方法的并行化版本，其在保证解的质量不变的前提下，在运行时间上几乎获得了关于处理器数目的线性加速比。