💻 computer science

Smooth multi-function evolutionary algorithm

本文提出了一种用于符号回归的新型进化算法，该算法利用一种包含函数对之间平滑、单变量参数化平移的通用函数模板，以减少函数集并确保导数连续性，并在标准基准测试上证明了其有效性。

原作者： Peter Michalicek, Tomas Brandejsky

发布于 2026-08-24

📖 1 分钟阅读☕ 轻松阅读

原作者： Peter Michalicek, Tomas Brandejsky

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在计算机科学领域，存在着一个被称为“符号回归”（symbolic regression）的持久挑战。想象一位科学家收集了大量的观测数据——也许是风速、花粉计数或教职员工薪资——并且想要找到一个单一的数学句子来解释这些数字之间的关系。其目标是发现那个隐藏的规则，即那个能将输入数据转化为正确输出的方程。为了实现这一目标，计算机通常使用一种受自然选择启发的算法，通过生成成千上万个随机的数学句子，测试它们对数据的拟合程度，然后将表现最好的句子进行混合与变异，从而创造出更优的版本。然而，这个过程往往显得笨拙。计算机将这些句子的构建模块（如加法、减法或乘法）视为僵化且独立的工具。在不同工具之间进行切换，就像是在可能性的景观中进行一次突然的跳跃，使得计算机难以找到通往完美答案的平滑路径。这有点像是在攀登一座山脉，地形突然从缓坡变成了垂直峭壁；登山者难以找到正确的方向。

来自捷克帕尔杜比采大学的研究员彼得·米哈利切克（Peter Michalicek）和托马斯·布兰德斯基（Tomas Brandejsky）提出了一种新方法，旨在抚平这种崎岖的景观。他们开发了一个系统，让计算机不再需要像对待截然不同的选项那样，在不同的数学工具之间进行抉择。相反，他们创建了一个单一且灵活的工具，该工具可以在不同运算之间平滑地变形。在他们的新方法中，计算机使用一个特殊的控制变量——一个可以旋转的单调旋钮，用以逐渐改变函数的行为。如果旋钮设定在某个位置，该工具表现为加法；如果转到另一个位置，它表现为乘法；而在中间位置，它则执行两者的融合。这使得计算机能够连续地在不同的数学行为之间滑动，而不是进行突兀、剧烈的跳跃。通过这种方式，研究人员将寻找复杂树状结构的困难任务，转化为了一个更简单的任务：即对一组数值进行调优，从而使进化过程更加高效，并降低了陷入死胡同的可能性。

研究人员通过构建一个名为“平滑多函数进化算法”的系统来测试这一想法。他们并没有让计算机随机组装由不同数学运算构成的树，而是强制要求计算机使用一棵完美的、对称的树，其中每一个内部节点都是这个相同的、形状可变的工具。在学习过程中，唯一发生变化的是树中每个节点的控制旋钮值，以及树底部的特定数字或变量。这种设计显著简化了问题。由于树的结构是固定的，且操作之间的转换是平滑的，计算机可以使用标准的优化技术来寻找最佳设置，而不是依赖于此类问题通常所需的那些更混乱且不可预测的方法。研究人员发现，这种方法允许他们使用单个控制变量来表示任何数量基函数的复杂关系，从而降低了搜索空间的复杂度。

为了验证这种方法是否奏效，团队将他们的算法应用于各种用于测试符号回归的标准数据集，包括风向模式、花粉计数和大学教职员工薪资的数据。他们将结果与几种著名的其他方法进行了对比，包括使用传统遗传编程的系统，以及那些将进化与其它优化技术相结合的系统。结果显示，虽然由于在标准计算机处理器上运行时间较长，但该方法在寻找精确模型方面非常有效。在某些情况下，特别是当给予足够的时间进行多代测试时，他们的算法所找到的解与现有成熟方法一样好，甚至更好。例如，在一个涉及教职员工薪资的数据集上，他们的方法达到了与顶尖表现者相媲美的高精度水平。在另一个关于风向数据的集上，他们产生的结果也与现有的最佳工具相当。

其中一个最重要的发现与模型的泛化能力有关。在机器学习中，过度拟合（overfitting）是一个常见问题，即模型对训练数据记忆过于完美，以至于无法对新信息做出准确预测。研究人员通过比较训练数据上的误差率与测试数据上的误差率来衡量这一点。他们的平滑多函数方法在从训练转向测试时，误差率增加得非常小，这表明其创建的模型是稳定且鲁棒的。这说明在数学运算之间的平滑转换有助于算法找到捕捉数据真实底层模式的解，而不是仅仅拟合噪声。研究人员指出，他们目前的实现方式在编写方式上并未进行充分的速度优化，这限制了他们在固定时间内能进行的测试次数。他们建议，如果能通过使用专门的计算机硬件来重写代码以提高运行速度，性能可能会得到进一步提升。

研究结论指出，通过用平滑且连续的转换取代传统进化算法中僵化的、基于跳跃的转换，可以使寻找数学模型的搜索过程变得更加高效且可靠。研究人员证明，一个单一的控制变量可以有效地管理多个不同数学函数之间的转换，在不牺牲准确性的前提下降低了问题的复杂度。虽然该方法并非解决所有问题的灵丹妙药，但它为寻找数据中的隐藏规则提供了一种极具前景的替代方案。这项工作表明，我们如何表示模型的构建模块，与其使用的搜索算法同样重要。通过抚平景观，研究人员为计算机提供了一条更清晰的路径，有望在从环境科学到经济学的广泛领域中实现更准确、更可靠的模型。该研究的代码和结果已公开，供他人检查和借鉴，以邀请对这种更平滑的数学解进化方式进行进一步探索。

技术摘要：平滑多函数进化算法

问题陈述
在应用于符号回归（SR）的遗传编程算法（GPA）中，搜索空间由代数关系组成。标准的进化算子（变异和交叉）通常会在替换函数或改变树结构时，在适应度景观中诱发非线性的“跳跃式变化”。这种不连续性使得预测结果、选择候选解或评估特定变异的影响变得困难，从而损害了算法效率。此外，现有的创建“通用”或“平滑”函数的方法通常需要多个控制变量来在基函数之间进行转换（例如，每对函数或三元组使用一个变量），这导致了高维控制空间，增加了优化的复杂性。本文旨在解决一种能够减少控制空间维度，同时保持多个基函数之间平滑过渡的表示方法。

方法论
作者提出了一种“平滑多函数”（SM）表示法，该方法通过一个单一控制变量（ $\gamma$ ）来控制 GPA 中的函数集，无论涉及多少个基函数（ $n$ ），该变量均保持一致。

平滑多函数定义：
- 作者没有为每一对函数设置单独的控制变量，而是为单个控制变量 $\gamma$ 定义了一个循环域。
- $\gamma$ 的定义域被划分为 $n$ 个区域，每个区域对应于相邻函数对之间的转换（例如， $f_1 \to f_2$ ， $f_2 \to f_3$ ，...， $f_n \to f_1$ ）。
- 转换过程利用模糊逻辑概念（模糊化和去模糊化）进行建模。控制变量 $\gamma$ 决定了相邻函数的权重，并进行线性插值。
- 为了确保数学上的平滑性（特别是确保左导数和右导数相等的 $C^1$ 连续性），作者使用傅里叶级数近似取代了标准的三角形隶属度函数（由于其在峰值处具有不连续的导数）。这使得多函数在所有点上都是可微的，从而促进了更平滑的优化。
进化策略：
- 解的结构被表示为一个固定深度的完美二叉树。
- 至关重要的是，所有的内部节点（除叶节点外）都使用同一种类型的单一平滑多函数。
- 由于结构是固定的且节点是统一的，进化过程不需要进化树的拓扑结构。相反，它优化一个包含以下内容的扁平向量：
  - 每个多函数节点的控制变量值（ $\gamma$ ）。
  - 终端节点（常数或变量索引）。
- 这把问题从结构搜索（典型的 GP）转变为参数优化问题。
- 作者采用了带有精英选择的进化策略（ES）。交叉算子通过从父代值定义的区间（通过扩展率进行扩展）中采样来生成新的参数值，而不是简单地交换遗传物质。变异是可选的，并应用于向量值。
实验设置：
- 该算法在 SRBench 套件的基准测试上进行了测试。
- 评估了不同的变体：带有变异的 SM（SM3, SM4）、不带变异的 SM（SM3-NM, SM4-NM）以及不同的树深度。
- 与成熟的 SR 方法进行了对比：AFP、Bingo、EPLEX、PySR 和 TIR。

核心贡献

降维： 本文引入了一种方法，仅使用一个控制变量即可控制 $n$ 个基函数之间的平滑转换，与需要 $n-1$ 个或更多变量的现有方法相比，显著降低了适应度景观的维度。
通过傅里叶近似实现平滑性： 作者提供了一种特定的多函数实现方式，通过使用傅里叶级数近似三角形隶属度函数，确保了多函数具有 $C^1$ 连续性（平滑导数），解决了标准模糊转换中的不连续问题。
结构简化： 通过将树结构固定为具有统一多函数的完美二叉树，作者将进化的重心完全转移到了参数优化上。这消除了复杂的基于树的交叉需求，并允许通过将个体表示为扁平向量来实现高效的 GPU 计算。

结果

性能与运行时间的权衡： 在固定的运行时间预算下，所提出的 SM 算法每代的运行速度通常比竞争对手慢（由于未优化的 Python 实现），并且在较大数据集（如 564 fried）上表现出混合结果。然而，当按固定的迭代次数（10,000 次）进行评估时，SM 算法具有竞争力。具体而言，在 10,000 代后，SM3 在 230 machine cpu 数据集上实现了最低的测试均方误差（MSE）。
泛化能力： 一个重要的发现是其泛化能力。在所有评估的方法中，SM3 变体实现了最低的测试 MSE 与训练 MSE 之比（1.138）。这表明平滑多函数表示生成的模型具有较低的过拟合倾向和良好的对未知数据的迁移能力。
变异的影响： 变异算子的影响并不一致；在某些数据集中，无变异版本（如 SM4-NM）优于带有变异的版本，而在其他数据集中情况则相反。

意义与主张
本文声称，该方法通过以下方式为符号回归提供了标准遗传编程的一种便捷替代方案：

降低复杂度： 用在连续空间（ $R^n$ ）中优化参数向量，取代了树的结构进化。
支持硬件加速： 基于向量的表示消除了在 CPU 和 GPU 之间传输树结构的开销，使其非常适合 GPGPU 实现。
提高稳定性： 适应度景观的平滑性和固定的结构似乎减轻了过拟合问题，使得模型具有良好的泛化能力，即使在某些大型数据集上的原始预测精度尚未超越 PySR 等最先进的方法。

作者指出，目前存在的性能限制主要归因于未优化的 Python 实现，并建议代码优化、并行化或 GPU 加速可以显著提高在固定运行时间约束下的结果。

技术摘要：平滑多函数进化算法

类似论文