Skip to Main content Skip to Navigation
New interface
Conference papers

Divide-and-Evolve: a New Memetic Scheme for Domain-Independent Temporal Planning

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 : An original approach, termed Divide-and-Evolve is proposed to hybridize Evolutionary Algorithms (EAs) with Operational Research (OR) methods in the domain of Temporal Planning Problems (TPPs). Whereas standard Memetic Algorithms use local search methods to improve the evolutionary solutions, and thus fail when the local method stops working on the complete problem, the Divide-and-Evolve approach splits the problem at hand into several, hopefully easier, sub-problems, and can thus solve globally problems that are intractable when directly fed into deterministic OR algorithms. But the most prominent advantage of the Divide-and-Evolve approach is that it immediately opens up an avenue for multi-objective optimization, even though the OR method that is used is single-objective. Proof of concept approach on the standard (single-objective) Zeno transportation benchmark is given, and a small original multi-objective benchmark is proposed in the same Zeno framework to assess the multi-objective capabilities of the proposed methodology, a breakthrough in Temporal Planning.
Document type :
Conference papers
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Marc Schoenauer Connect in order to contact the contributor
Submitted on : Monday, January 9, 2006 - 5:30:29 PM
Last modification on : Monday, April 4, 2022 - 10:40:39 AM
Long-term archiving on: : Saturday, April 3, 2010 - 9:01:41 PM




Marc Schoenauer, Pierre Savéant, Vincent Vidal. Divide-and-Evolve: a New Memetic Scheme for Domain-Independent Temporal Planning. EvoCOP2006, Apr 2006, Budapest, pp.247-260. ⟨inria-00000975⟩



Record views


Files downloads