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, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
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.
Type de document :
Chapitre d'ouvrage
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
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00176967
Contributeur : Marc Schoenauer <>
Soumis le : lundi 10 novembre 2008 - 22:59:44
Dernière modification le : jeudi 10 mai 2018 - 02:06:23
Document(s) archivé(s) le : jeudi 27 septembre 2012 - 12:57:55

Fichier

TGV-paradigm.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

460

Téléchargements de fichiers

733