Skip to Main content Skip to Navigation
New interface
Book sections

Divide-and-Evolve: a Sequential Hybridization Strategy using Evolutionary Algorithms

Marc Schoenauer 1 Pierre Savéant 2 Vincent Vidal 3 
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : Memetic Algorithms are hybridizations of Evolutionary Algorithms (AEs) with problem-specific heuristics or other meta-heuristics, that are generally used within the EA to locally improve the evolutionary solutions. However, this approach fails when the local method stops working on the complete problem. Divide-and-Evolve is an original approach that evolutionarily builds a sequential slicing of the problem at hand into several, hopefully easier, sub-problems: the embedded (meta-)heuristic is only asked to solve the 'small' problems, and Divide-and-Evolve is thus able to globally solve problems that are intractable when directly fed into the heuristic. The Divide-and-Evolve approach is described here in the context of Temporal Planning Problems (TPPs), and the results on the standard Zeno transportation benchmarks demonstrate its ability to indeed break the complexity barrier. But an even more prominent advantage of the Divide-and-Evolve approach is that it immediately opens up an avenue for multi-objective optimization, even when using single-objective embedded algorithm.
Document type :
Book sections
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Marc Schoenauer Connect in order to contact the contributor
Submitted on : Monday, November 10, 2008 - 10:59:44 PM
Last modification on : Monday, April 4, 2022 - 10:40:39 AM
Long-term archiving on: : Thursday, September 27, 2012 - 12:57:55 PM


Files produced by the author(s)


  • HAL Id : inria-00176967, version 1



Marc Schoenauer, Pierre Savéant, Vincent Vidal. Divide-and-Evolve: a Sequential Hybridization Strategy using Evolutionary Algorithms. Z. Michalewicz and P. Siarry. Advances in Metaheuristics for Hard Optimization, Springer Verlag, pp.179-198, 2007, Natural Computing Series, 978-3-540-72959-4. ⟨inria-00176967⟩



Record views


Files downloads