极简遗传编程

# 极简遗传编程 来源：https://arxiv.org/html/2606.10237 \nameLeonardo Trujillo\addrleonardo\.trujillo@tectijuana\.edu\.mx \addrTecnológico Nacional de México/IT de Tijuana, Tijuana, BC, 墨西哥 \addrLASIGE, 信息学系, 理学院, 里斯本大学, 里斯本, 葡萄牙 ###### 摘要 遗传编程（GP）基于两个重要洞见。首先，任何学习任务从根本上都可以被表述为一个程序归纳问题，其目标是构建一个以语法树形式表达的符号层级模型。其次，将该任务表述为一个搜索问题，并利用进化过程来定位所需模型。自提出以来，GP 在广泛的任务和问题领域中取得了显著成果。本文通过修改 GP 的第二个核心洞见来提出另一种视角，将该问题转而表述为句法推导任务。具体而言，本文提出了极简遗传编程（MGP），这是一种与 GP 同样受生物学启发的算法，但并非受进化论启发，而是从人类语言的极简方案中汲取灵感。在极简方案中，句法被理解为连接另外两个心理系统问题的优化解。其核心计算过程是一个称为MERGEMERGE的二元集合形成算符，可通过简单的马尔可夫过程逐步构建复杂的句法结构。MGP 能够发现符号表达式的核心构建模块，并通过MERGEMERGE逐步组合它们。本系统在已知因易膨胀而难以用标准 GP 系统求解的符号回归任务上进行了基准测试。结果表明，若选择合适的原子句法对象词汇表，MGP 能够一致地在标准 GP 难以做到的一组符号回归任务上精确重构真实模型。极简方案所提供的洞见被证明与程序归纳问题相关，且基于 MGP 在本工作中展现的潜力，值得进一步探索。 关键词 > 极简方案、树恋性、MERGEMERGE、句法 ## 1引言 1992 年，John Koza 在其同名开创性著作中提出了遗传编程（GP），这是进化计算的核心范式之一（Koza,1992 (https://arxiv.org/html/2606.10237#bib.bib2)）。在更广泛的人工智能（AI）研究纲领背景中，Koza 在其提案中提出了两个关键洞见。要理解第一个洞见，重要的是指出：作为一个科学领域，AI 长期以来基于这样一个猜想，即“学习的每个方面或任何其他智能特征原则上都可以被如此精确地描述，以至于可以制造一台机器（程序）来模拟它”（McCarthy et al.,1955 (https://arxiv.org/html/2606.10237#bib.bib4)）。到了 Koza 著作发表时，大多数 AI 研究者已得出结论：大多数“智能特征”的精确描述极难系统性地推导出来，更不用说在“机器”中实现这些理论了（Mitchell,2019 (https://arxiv.org/html/2606.10237#bib.bib3)）。因此，许多人开始转向机器学习（ML）方法，其中智能行为的模型及其作为程序的实现并不是直接设计的。在 ML 中，这些模型是通过数据驱动的学习/搜索/优化过程生成的。Koza 的第一个关键洞见是：尽管大多数方法依赖于这种模型的间接表示，但直接探索计算机程序空间或许是明智的。他指出，“对于许多问题，解决方案最自然的表示是层级计算机程序”（第 63 页）（Koza,1992 (https://arxiv.org/html/2606.10237#bib.bib2)）；即许多学习任务可以被表述为程序归纳问题。Koza 原版的 GP 也被称为基于树的 GP，因为它将程序直接编码为层级语法树。

Koza 的第二个洞见涉及如何探索这个“层级程序”空间，以找到具有期望行为或性能的程序。这是 Koza 的第二个关键洞见：利用进化过程在该空间内进行搜索。使用进化论可以在多个方面得到论证。在该著作发表时，已有明确证据表明进化计算，特别是遗传算法，可用于实现强大的基于种群的全局搜索方法。这些技术在对梯度信息不可用的情况下尤为有用（Stork et al.,2020 (https://arxiv.org/html/2606.10237#bib.bib5); Sörensen et al.,2018 (https://arxiv.org/html/2606.10237#bib.bib6)）。此外，众所周知，进化能够在生物学中产生复杂的层级和模块化结构（Mengistu et al.,2016 (https://arxiv.org/html/2606.10237#bib.bib7)），而这些性质也是计算机程序所需要的。Koza 两个洞见之间的协同作用产生了一套令人印象深刻的搜索和学习方法，这些方法已经解决了来自不同领域的各种问题（Koza,2010 (https://arxiv.org/html/2606.10237#bib.bib1)）。

本文聚焦于 GP 的一个主要应用领域：符号回归（SR）（Kronberger et al.,2024 (https://arxiv.org/html/2606.10237#bib.bib8); La Cava et al.,2021 (https://arxiv.org/html/2606.10237#bib.bib47)），这也是 Koza 最初研究的最引人入胜的 GP 应用之一。其中，期望程序是一个最能拟合训练数据集的符号数学模型。当将 GP 与其他自动建模技术进行比较时，程序与模型以符号形式表达的事实可能是其最独特的特征。这些模型至少在潜力上是内在可解释的（Atzmueller et al.,2024 (https://arxiv.org/html/2606.10237#bib.bib9)），而大多数强大的黑箱 ML 模型则不然（Rudin,2019 (https://arxiv.org/html/2606.10237#bib.bib48)）。可解释性允许领域专家获得关于问题的宝贵见解，从而能够扩展和改进由 GP 搜索生成的解决方案（Romera-Paredes et al.,2024 (https://arxiv.org/html/2606.10237#bib.bib10)）。然而，尽管这一潜力是 GP 的内置特性，但当前大多数方法往往难以始终如一地实现它（Castelli,2023 (https://arxiv.org/html/2606.10237#bib.bib12)）。同样，尽管人们清楚进化常常导致模块化和层级结构，但这种模块化在 GP 中很难生成（Saini and Spector,2021 (https://arxiv.org/html/2606.10237#bib.bib13)）。本研究假设，这一未实现潜力的一个可能原因在于 GP 探索程序空间的方式。实现可解释性的主要障碍之一与膨胀有关，即模型大小不必要的增加且未带来性能提升（Silva et al.,2011 (https://arxiv.org/html/2606.10237#bib.bib15)）。然而，膨胀似乎是受适应度函数指导的人工进化过程的内置属性（Langdon and Poli,1998 (https://arxiv.org/html/2606.10237#bib.bib16)）。尽管几种启发式方法可以帮助减轻其影响（Juárez-Smith et al.,2019 (https://arxiv.org/html/2606.10237#bib.bib140)），但随着时间的推移，寻求改进适应度的搜索将倾向于更大的解。因此，本文提出了一种新的 SR 方法，该方法利用了 Koza 的第一个洞见，但改变了他第二个洞见中的提议。这并非全新，先前已有一些工作使用进化的替代方案，包括使用正则化回归（McConaghy,2011 (https://arxiv.org/html/2606.10237#bib.bib65)）或使用工业工程方法论（De Melo,2014 (https://arxiv.org/html/2606.10237#bib.bib96)）。然而，本工作与 Koza 的提议一样，从生物学中汲取灵感，但来自不同的分支。不同于进化论，本提案从认知科学中汲取灵感，并开发一个受生成语法极简方案启发的 SR 系统（Chomsky,1995 (https://arxiv.org/html/2606.10237#bib.bib17),2004 (https://arxiv.org/html/2606.10237#bib.bib29); Berwick and Chomsky,2016 (https://arxiv.org/html/2606.10237#bib.bib18); Komachi et al.,2019 (https://arxiv.org/html/2606.10237#bib.bib30); Pan et al.,2024 (https://arxiv.org/html/2606.10237#bib.bib26)）。该方法被称为极简遗传编程（MGP）（原因显而易见），并作为对 Koza 30 多年前提议的重新表述而提出。它不是将程序归纳任务表述为一个搜索问题，而是将其表述为一个句法推导任务。尽管此前已有工作将语法整合到 GP 系统中，但这些都是混合方法，使用受上下文无关语法约束的进化搜索（O’Neill and Ryan,2003 (https://arxiv.org/html/2606.10237#bib.bib35); McKay et al.,2010 (https://arxiv.org/html/2606.10237#bib.bib36)）。MGP 是独特的，它取代了进化理论中的元素来指导模型构建过程，代之以基于极简句法的公式化描述，这是人类语言能力的核心计算过程的描述（Chomsky,1995 (https://arxiv.org/html/2606.10237#bib.bib17)）。

在介绍 MGP 之前，需要提出几点评论以框定本研究工作。首先，与进化理论不同，极简方案是一个不太成熟的理论，它提供了一个概念框架来理解计算和算法层面上的人类语言能力，但距离解释实现层面还很远（Berwick and Chomsky,2016 (https://arxiv.org/html/2606.10237#bib.bib18)）。然而，极简方案确实旨在涵盖所有三个层次的解释力，即观察充分性、描述充分性和解释充分性，同时为探索达尔文问题111语言能力明显缺乏选择优势的问题。(Darwin,1871 (https://arxiv.org/html/2606.10237#bib.bib37); Berwick and Chomsky,2016 (https://arxiv.org/html/2606.10237#bib.bib18)) 的可能解决方案提供基础。其次，与 Koza 受进化论启发类似，我们受极简方案的启发也足够细致。MGP 与 GP 一样，并不是旨在模拟其所源自的生物过程，而是旨在应用潜在生物学理论中最相关的原则和核心要素，同时引入必要的简化和非生物学修改来解决当前问题。最后，有人可能会争辩说，另一个受生物启发的计算系统可能是本研究社区最不需要的东西（Aranha et al.,2021 (https://arxiv.org/html/2606.10237#bib.bib38)）。对不断扩大的受生物启发计算文献的批评大多是合理且必要的（Sörensen,2013 (https://arxiv.org/html/2606.10237#bib.bib39)）。然而，我们相信这些批评不适用于 MGP，因为它引入了一种具有生物学基础且算法上独特的方法来解决程序归纳问题。实际上，MGP 不是一种元启发式算法（在 (Stork et al.,2020 (https://arxiv.org/html/2606.10237#bib.bib5)) 中所描述的全局搜索算法的意义上），而是一个句法推导系统。然而，MGP 确实包含一些与元启发式搜索核心思想可比的元素，例如基于随机性的探索和基于性能的利用，同时也引入了相关技术的思想，如新颖性搜索（Stanley and Lehman,2015 (https://arxiv.org/html/2606.10237#bib.bib40)）和增量进化（Stanley and Miikkulainen,2002 (https://arxiv.org/html/2606.10237#bib.bib41)）。虽然本文主要旨在激励和概述一种基于极简方案的新颖程序归纳方法的主要元素，但 MGP 在标准 SR 任务上进行了基准测试，展示了重构精确真值数学表达式的能力。MGP 为程序归纳问题提供了一种替代视角，有可能解决传统 GP 当前面临的一些挑战。本着原始 AI 研究纲领的精神，MGP 从一种使得人类区别于生物界其他部分的核心认知能力理论中汲取灵感（Darwin,1871 (https://arxiv.org/html/2606.10237#bib.bib37); Berwick and Chomsky,2016 (https://arxiv.org/html/2606.10237#bib.bib18)），提供了对自动化构建符号模型意味着什么的独特重新构想。

本文其余部分组织如下。第2节 (https://arxiv.org/html/2606.10237#S2) 概述了 GP，讨论了树结构在 GP、进化和认知科学中的相关性。第3节 (https://arxiv.org/html/2606.10237#S3) 旨在对极简方案做一个简化的介绍。第5节 (https://arxiv.org/html/2606.10237#S5) 概述了我们使用极简句法推导 SR 模型的提议，第4节 (https://arxiv.org/html/2606.10237#S4) 介绍了所提出的推导系统，称为 MGP。实验和结果在第6节 (https://arxiv.org/html/2606.10237#S6) 中详细说明。最后，第7节 (https://arxiv.org/html/2606.10237#S7) 包含结束性讨论、结论和未来工作概述。

## 2 基于树的遗传编程

GP 与所有全局搜索技术共享基本算法结构（Stork et al.,2020 (https://arxiv.org/html/2606.10237#bib.bib5)）。这是一个迭代过程，从一组随机生成的候选解（种群）开始，根据目标（适应度）函数222 虽然适应度的概念是 GP 和进化计算特有的，但在本工作中，我们将它与基于目标或成本函数的性能互换使用。进行评估。然后选择一部分候选解（基于适应度）以生成一组新的候选解，其中一些被保留（再次基于适应度）以重复该过程，直到满足终止条件。为了生成新的解，进化算法主要采用一元或二元搜索算子，这些算子受生物变异和交叉启发。这些算子试图捕捉遗传的概念，使得当前解集中的有用特征在连续的迭代（世代）中传递下去，而新颖性则由这些算子中固有的随机性引入。此外，与其他进化方法相比，GP 有两个独特特征。首先，也是最重要的，候选解是离散的符号结构，实现了可计算的表达式、程序或模型。其次，候选解没有固定的大小或架构，这些方面的解与其行为一同进化。在 Koza 提出的基于树的 GP 中，候选解使用从有限原始元素集合构建的树结构进行编码，这些元素包括终端（输入变量、常量或 0 元函数）和函数（不同种类的算子，表示为 n 元函数），使得终端是叶子节点，函数是内部节点。变异和交叉是树上的结构操作，通常依赖于随机修改或交换子树或节点。

基本 GP 方法的许多元素已经以不同方式得到改进、扩展或增强，而其他元素则大多被遗忘。例如，在最初的 GP 公式中，Koza 提出了一个称为自动定义函数（ADF）的概念。