Lamarckian and Baldwinian EAs beat Darwinian on graph benchmarks
New study proves learning-augmented evolution outperforms traditional EAs on 6 datasets
Get AI news that actually matters
One email a day. Zero fluff. Join 10,000+ professionals.
In a paper accepted at PPSN 2026, Benito, Lutzeyer, and Doerr from École Polytechnique systematically compare three flavors of evolutionary algorithms — Darwinian, Lamarckian, and Baldwinian — on graph optimization problems. Using the GraphBench benchmark with six datasets, they tackle Maximum Independent Set and Maximum Cut. Their empirical results show that Baldwinian and Lamarckian EAs consistently beat standard Darwinian EAs, and in most cases outperform recent deep learning baselines, approaching the performance of highly specialized heuristic and exact solvers. They also provide a set of generalist parameters for practitioners.
On the theoretical side, the team extends the Deceptive Leading Block benchmark to arbitrary block length. Using modern runtime analysis, they prove upper and lower bounds on expected runtime. For block lengths greater than two, Baldwinian evolution is asymptotically faster than Lamarckian, which is itself faster than Darwinian. When accounting for the cost of local search in fitness evaluations, the ordering shifts slightly, but Baldwinian remains fastest from small block lengths onward, explaining its strong empirical performance.
- Baldwinian and Lamarckian EAs outperform Darwinian EAs on all 6 GraphBench datasets for Maximum Independent Set and Maximum Cut
- The paper provides provable asymptotic speedups: for block lengths >2, Baldwinian > Lamarckian > Darwinian
- All three EA types beat deep learning baselines and approach specialized solvers in most cases
Why It Matters
This work provides both theoretical and practical evidence that learning-augmented evolution can significantly accelerate optimization, with direct implications for graph problems.