首次分析CGP演化布尔函数的运行时间，揭示其高效与局限性
Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions
- 基于图结构的遗传编程，用最少门电路构造逻辑与函数
- 在严格选择下需O(nD⁵)次评估，非严格选择可降至O(nD⁴)
- 允许冗余连接能加速搜索，但对异或函数却需指数时间
笛卡尔遗传编程（CGP）是一种基于图表示的实用遗传编程方法。本文首次对使用完整训练集演化布尔函数的CGP运行时间进行理论分析。证明了在最多D≥n−1个二元门、最小函数集且采用严格生存选择的情况下，期望所需适应度评估次数为O(nD⁵)；若采用非严格选择，则可优化至O(nD⁴)。分析揭示了CGP搜索的有趣特性，此前仅通过实验观察到：允许接受同等优秀解（包括不贡献性能的连通门）可带来加速，从而改善渐进时间复杂度。相比之下，我们还证明了对异或函数的演化需指数时间。针对逻辑与函数的实验结果验证了理论发现。此外，使用不完整训练集可进一步降低平均评估次数，同时保持良好泛化能力。
原文摘要 · Abstract (English)
Cartesian Genetic Programming (CGP) is among the practical and popular forms of Genetic Programming as it uses a graph-based representation of programs. This paper presents a first runtime analysis of CGP in evolving Boolean functions using complete training sets. We prove an asymptotic bound $O(n D^5)$ for the expected number of fitness evaluations of CGP to construct a conjunction of $n$ inputs using at most $D \geq n-1$ binary gates, a minimal function set, and even with a strict survival selection. When the non-strict selection is used, the bound is improved to $O(n D^4)$. Our analysis reveals interesting characteristics of CGP induced search, which have been only observed empirically. In particular, enabling the acceptance of equally good solutions, including those with connected gates non-contributing to fitness, can lead to a speedup, and consequently a better asymptotic time bound. In contrast to conjunctions, we also prove a negative result which shows that CGP requires exponential time to evolve an exclusive disjunction. Experiments evolving conjunctions complement our theoretical findings. The use of incomplete training sets is found to further reduce the average number of fitness evaluations while maintaining a good level of generalisation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。