Search papers, labs, and topics across Lattice.
This paper revisits Lamarckian and Baldwinian evolution within evolutionary algorithms (EAs), comparing them rigorously against Darwinian evolution using empirical and theoretical methods. Empirically, experiments on GraphBench datasets for Maximum Independent Set and Maximum Cut problems show that Baldwinian and Lamarckian evolution consistently outperform Darwinian approaches and often surpass deep learning baselines. Theoretically, runtime analysis on an extended Deceptive Leading Block benchmark demonstrates that Baldwinian evolution is asymptotically faster than Lamarckian, which is faster than Darwinian, especially when accounting for local search costs.
Evolutionary algorithms augmented with local search (Baldwinian and Lamarckian evolution) can handily beat deep learning baselines on graph problems, suggesting a resurgence for these classic techniques.
Baldwinian and Lamarckian evolution have existed for a long time in evolutionary algorithms (EAs) without ever dominating the academic literature or practical applications. In this work, we use modern empirical and theoretical methods to revisit Lamarckian and Baldwinian evolution and rigorously compare them with the generic Darwinian evolution. On the empirical side, we run a comprehensive suite of experiments on graphs from six different datasets from the recent GraphBench benchmark on Maximum Independent Set and Maximum Cut problems. Our results show that Baldwinian and Lamarckian evolution consistently outperform Darwinian evolution, confirming the great potential of local search augmented evolutionary algorithms. Notably, in the great majority of cases, all EAs outperform recent deep learning baselines and approach the performance of highly specialised heuristic and exact solvers. We furthermore report a high-performing set of generalist parameters for all studied evolution types that we hope will be of use to practitioners in future. On the theoretical side, we extend the existing Deceptive Leading Block benchmark to arbitrary block length and use tools from modern theoretical runtime analysis to prove upper and lower bounds on the expected runtime. For block lengths greater than two, Baldwinian evolution is asymptotically faster than Lamarckian which is asymptotically faster than Darwinian evolution. When accounting for the cost of the local search procedure in fitness evaluations, the ordering depends on the implementation with Baldwinian evolution staying fastest from small block lengths onwards, explaining its strong empirical performance.
