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

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 metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/inria-00176967
Contributor : Marc Schoenauer <>
Submitted on : Monday, November 10, 2008 - 10:59:44 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM
Long-term archiving on: Thursday, September 27, 2012 - 12:57:55 PM

File

TGV-paradigm.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00176967, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

525

Files downloads

895