A Fresh Look at Lamarckian Evolution and the Baldwin Effect

Problem
This paper addresses the under-explored roles of Baldwinian and Lamarckian evolution in evolutionary algorithms (EAs), which have not dominated the literature or practical applications despite their theoretical potential. The authors present a preprint that rigorously compares these evolutionary strategies against the more commonly utilized Darwinian evolution, filling a gap in empirical and theoretical understanding of their effectiveness in solving optimization problems.

Method
The authors conduct a comprehensive empirical evaluation using a suite of experiments on six datasets from the GraphBench benchmark, specifically targeting the Maximum Independent Set and Maximum Cut problems. They implement various evolutionary algorithms, including Baldwinian, Lamarckian, and Darwinian approaches, and assess their performance against recent deep learning baselines and specialized heuristic solvers. The theoretical contribution includes an extension of the Deceptive Leading Block benchmark to arbitrary block lengths, allowing for the derivation of upper and lower bounds on expected runtime using modern theoretical runtime analysis techniques. The study also identifies a set of generalist parameters that yield high performance across all evolutionary types.

Results
The empirical results demonstrate that both Baldwinian and Lamarckian evolution consistently outperform Darwinian evolution across the majority of tested scenarios. Specifically, the EAs not only surpass recent deep learning baselines but also approach the performance of highly specialized heuristic and exact solvers. The theoretical analysis reveals that for block lengths greater than two, Baldwinian evolution exhibits asymptotic superiority over Lamarckian evolution, which in turn outperforms Darwinian evolution. The authors note that when considering the computational cost of local search in fitness evaluations, the performance ordering may vary based on implementation, yet Baldwinian evolution remains the fastest from small block lengths onward.

Limitations
The authors acknowledge that their findings are based on specific problem domains (Maximum Independent Set and Maximum Cut) and may not generalize to all optimization problems. They also do not address the potential computational overhead introduced by local search procedures in detail, which could impact the practical applicability of their results. Additionally, the study does not explore the scalability of these evolutionary strategies in larger or more complex datasets beyond those tested.

Why it matters
This work has significant implications for the design and application of evolutionary algorithms in optimization tasks. By demonstrating the superior performance of Baldwinian and Lamarckian strategies, the authors provide a compelling case for their integration into practical EAs, potentially leading to more efficient solutions in various domains. The identification of generalist parameters also offers a valuable resource for practitioners, facilitating the adoption of these strategies in real-world applications. Furthermore, the theoretical insights into runtime performance contribute to a deeper understanding of evolutionary dynamics, which could inspire future research in algorithm design and optimization.

Authors: Inès Benito, Johannes F. Lutzeyer, Benjamin Doerr
Source: arXiv:2605.28703
URL: https://arxiv.org/abs/2605.28703v1