arXiv cs.AI· Duc-Cuong Dang, Roman Kalkreuth, Andre Opris·· 1 天前AI 评分24
笛卡尔遗传编程在 Max 问题上的运行时分析：证得指数级加速
Runtime Analysis of Cartesian Genetic Programming on Max: A Proven Exponential Speedup
AI 导读
论文首次为笛卡尔遗传编程（CGP）在经典基准 Max 问题上给出可证明的性能保证：(1+1) CGP 使用常见变异算子演化出等价最优解的期望时间至多为 O(log^9 n)，相对树状 GP 已知的超线性期望运行时间实现了指数级加速。该结果揭示了图式程序表示的紧凑性与搜索效率，实验与理论结论相互印证，论文已被 NeurIPS 2026 接收为 poster。
正文 · AI 翻译
摘要：遗传编程（GP）是一种受自然进化启发的搜索范式，用于自动发现表达式、函数和计算机程序。笛卡尔遗传编程（CGP）是 GP 的一种变体，它使用基于图的模型来编码候选程序，与传统的基于树的遗传编程（TGP）形成对比。自二十年前诞生以来，CGP 主要被进行实证分析，因此关于其理论性能保证知之甚少。本文分析了 CGP 在 Max 问题上的表现，而该问题此前仅针对 TGP 进行过严格研究，并已证明其期望运行时间与最优程序长度 $n$ 呈超线性关系。我们证明，采用常见变异算子的（$1$+$1$）~CGP 进化出具有相同输出的等价最优解的期望时间为 $n$ 的多对数级，具体至多为 $O(\log^9{n})$。这一结果非常显著，因为它表明切换到 CGP 可实现指数级加速。我们的结果揭示了基于图的程序表示的优势与紧凑性，以及 CGP 如何高效地在其搜索空间和适应度空间中导航。这是 CGP 在一个已确立的基准问题上首次得到证明的性能保证。实验补充了我们的理论发现。
| 评论： | 被接收为 NeurIPS 2026 的海报展示。将发表于会议论文集 |
| 主题： | 机器学习（cs.LG）；人工智能（cs.AI）；神经与进化计算（cs.NE） |
| 引用为： | arXiv:2611.16013 [cs.LG] |
| （或 arXiv:2611.16013v1 [cs.LG] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2611.16013 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Roman Kalkreuth [查看电子邮件]
[v1]
2026年11月11日 星期三 21:13:49 UTC（241 KB）
来源：arXiv cs.AI · arxiv.org