Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
A Simple Proof for the Usefulness of Crossover in Black-Box Optimization
verfasst von : Eduardo Carvalho Pinto, Carola Doerr
Erschienen in: Parallel Problem Solving from Nature – PPSN XV
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The idea to recombine two or more search points into a new solution is one of the main design principles of evolutionary computation (EC). Its usefulness in the combinatorial optimization context, however, is subject to a highly controversial discussion between EC practitioners and the broader Computer Science research community. While the former, naturally, report significant speedups procured by crossover, the belief that sexual reproduction cannot advance the search for high-quality solutions seems common, for example, amongst theoretical computer scientists. Examples that help understand the role of crossover in combinatorial optimization are needed to promote an intensified discussion on this subject.
We contribute with this work an example of a crossover-based genetic algorithm (GA) that provably outperforms any mutation-based black-box heuristic on a classic benchmark problem. The appeal of our examples lies in its simplicity: the proof of the result uses standard mathematical techniques and can be taught in a basic algorithms lecture.
Our theoretical result is complemented by an empirical evaluation, which demonstrates that the superiority of the GA holds already for quite small problem instances.