arXiv:2501.17848cs.LG2025-01被引 14

用等式图避免重复搜索,让遗传编程更快找到简洁准确的公式。

Improving Genetic Programming for Symbolic Regression with Equality Graphs

  • 用等式图记录表达式及其等价形式,防止重复计算。
  • 在小规模表达式上性能媲美PySR和Operon,且不增加算力开销。
  • 适合追求简洁高效公式的科研与工程用户。

遗传编程(GP)在符号回归中常重复生成相同或等价的表达式,导致效率低下。等式图(e-graph)可紧凑存储表达式及其等价形式,实现高效查重。本文提出eggp方法,将所有访问过的表达式存入e-graph,筛选掉会生成已访问表达式的子树组合,从而减少冗余搜索。实验表明,在小规模表达式上,该方法使简单GP算法性能达到PySR和Operon水平,且计算成本未增加。特别地,eggp在SRBench基准及真实数据集上均能稳定生成简短且精确的模型。

原文摘要 · Abstract (English)

The search for symbolic regression models with genetic programming (GP) has a tendency of revisiting expressions in their original or equivalent forms. Repeatedly evaluating equivalent expressions is inefficient, as it does not immediately lead to better solutions. However, evolutionary algorithms require diversity and should allow the accumulation of inactive building blocks that can play an important role at a later point. The equality graph is a data structure capable of compactly storing expressions and their equivalent forms allowing an efficient verification of whether an expression has been visited in any of their stored equivalent forms. We exploit the e-graph to adapt the subtree operators to reduce the chances of revisiting expressions. Our adaptation, called eggp, stores every visited expression in the e-graph, allowing us to filter out from the available selection of subtrees all the combinations that would create already visited expressions. Results show that, for small expressions, this approach improves the performance of a simple GP algorithm to compete with PySR and Operon without increasing computational cost. As a highlight, eggp was capable of reliably delivering short and at the same time accurate models for a selected set of benchmarks from SRBench and a set of real-world datasets.

符号回归遗传编程等式图模型简洁性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。