Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.18666 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911077273436160 |
|---|---|
| author | Fidalgo, Nicholas Ye, Puyuan |
| author_facet | Fidalgo, Nicholas Ye, Puyuan |
| contents | The theory of evolvability, introduced by Valiant (2009), formalizes evolution as a constrained learning algorithm operating without labeled examples or structural knowledge. While theoretical work has established the evolvability of specific function classes under idealized conditions, the framework remains largely untested empirically. In this paper, we implement a genetic algorithm that faithfully simulates Valiant's model and conduct extensive experiments across six Boolean function classes: monotone conjunctions, monotone disjunctions, parity, majority, general conjunctions, and general disjunctions. Our study examines evolvability under uniform and non-uniform distributions, investigates the effects of fixed initial hypotheses and the removal of neutral mutations, and highlights how these constraints alter convergence behavior. We validate known results (e.g., evolvability of monotone conjunctions, non-evolvability of parity) and offer the first empirical evidence on the evolvability of majority and general Boolean classes. Our findings reveal sharp performance drops at intermediate dimensions and expose the essential role of neutral mutations in escaping fitness plateaus. We also demonstrate that evolvability can depend strongly on the input distribution. These insights clarify practical limits of evolutionary search and suggest new directions for theoretical work, including potential refinements to evolvability definitions and bounds. Our implementation provides a rigorous, extensible framework for empirical analysis and serves as a testbed for future explorations of learning through evolution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_18666 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Simulating Evolvability as a Learning Algorithm: Empirical Investigations on Distribution Sensitivity, Robustness, and Constraint Tradeoffs Fidalgo, Nicholas Ye, Puyuan Computational Complexity Neural and Evolutionary Computing The theory of evolvability, introduced by Valiant (2009), formalizes evolution as a constrained learning algorithm operating without labeled examples or structural knowledge. While theoretical work has established the evolvability of specific function classes under idealized conditions, the framework remains largely untested empirically. In this paper, we implement a genetic algorithm that faithfully simulates Valiant's model and conduct extensive experiments across six Boolean function classes: monotone conjunctions, monotone disjunctions, parity, majority, general conjunctions, and general disjunctions. Our study examines evolvability under uniform and non-uniform distributions, investigates the effects of fixed initial hypotheses and the removal of neutral mutations, and highlights how these constraints alter convergence behavior. We validate known results (e.g., evolvability of monotone conjunctions, non-evolvability of parity) and offer the first empirical evidence on the evolvability of majority and general Boolean classes. Our findings reveal sharp performance drops at intermediate dimensions and expose the essential role of neutral mutations in escaping fitness plateaus. We also demonstrate that evolvability can depend strongly on the input distribution. These insights clarify practical limits of evolutionary search and suggest new directions for theoretical work, including potential refinements to evolvability definitions and bounds. Our implementation provides a rigorous, extensible framework for empirical analysis and serves as a testbed for future explorations of learning through evolution. |
| title | Simulating Evolvability as a Learning Algorithm: Empirical Investigations on Distribution Sensitivity, Robustness, and Constraint Tradeoffs |
| topic | Computational Complexity Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2507.18666 |