Abstract
Memetic algorithms are hybridizations of evolutionary algorithms (EAs) 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
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
F. Bacchus. The 2000 AI Planning Systems Competition. Artificial Intelligence Magazine, 22(3):47–56, 2001
A.H. Brie and P. Morignot. Genetic Planning Using Variable Length Chromosomes. In 15th Int. Conf. on Automated Planning and Scheduling, 2005
T. Bylander. The Computational Complexity of Propositional STRIPS planning. Artificial Intelligence, 69(1-2):165–204, 1994
K. Deb, S. Agrawal, A. Pratab, and T. Meyarivan. A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization. In M. Schoenauer et al., editor, PPSN’2000, pages 849–858. Springer-Verlag, LNCS 1917, 2000
C. Desquilbet. Détermination de trajets optimaux par algorithmes génétiques. Rapport de stage d’option B2 de l’Ecole Polytechnique. Palaiseau, France, Juin 1992 Advisor: Marc Schoenauer. In French
A.E. Eiben and M. Schoenauer. Evolutionary Computing. Information Processing Letter, 82(1):1–6, 2002
A.E. Eiben and J.E. Smith. Introduction to Evolutionary Computing. Springer Verlag, 2003
R. Fikes and N. Nilsson. STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence, 1:27–120, 1971
M. Fox and D. Long. The Automatic Inference of State Invariants in TIM. Journal of Artificial Intelligence Research, 9:367–421, 1998
M. Fox and D. Long. PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains. Journal of Artificial Intelligence Research, 20:61–124, 2003
H. Geffner. Perspectives on Artificial Intelligence Planning. In Proc. AAAI-2002, pages 1013–1023, 2002
J. J. Grefenstette. Incorporating Problem Specific Knowledge in Genetic Algorithms. In Davis L., editor, Genetic Algorithms and Simulated Annealing, pages 42–60. Morgan Kaufmann, 1987
W.E. Hart, N. Krasnogor, and J.E.Smith, editors. Evolutionary Computation – Special Issue on Memetic Algorithms, Volume 12:3. MIT Press, 2004
W.E. Hart, N. Krasnogor, and J.E. Smith, editors. Recent Advances in Memetic Algorithms. Studies in Fuzziness and Soft Computing, Vol. 166. Springer Verlag, 2005
J. Hoffmann, J. Porteous, and L. Sebastia. Ordered Landmarks in Planning. Journal of Artificial Intelligence Research, 22:215–278, 2004
Jörg Hoffmann and Stefan Edelkamp. The Deterministic Part of IPC-4: An Overview. Journal of Artificial Intelligence Research, 24:519–579, 2005
J. Koehler and J. Hoffmann. On Reasonable and Forced Goal Orderings and their Use in an Agenda-Driven Planning Algorithm. Journal of Artificial Intelligence Research, 12:338–386, 2000
R. Korf. Planning as Search: A Quantitative Approach. Artificial Intelligence, 33:65–88, 1987
D. Long and M. Fox. The 3rd International Planning Competition: Results and Analysis. Journal of Artificial Intelligence Research, 20:1–59, 2003
D. McDermott. PDDL – The Planning Domain Definition language. At http://ftp.cs.yale.edu/pub/mcdermott, 1998
D. McDermott. The 1998 AI Planning Systems Competition. Artificial Intelligence Magazine, 21(2):35–56, 2000
P. Merz and B. Freisleben. Fitness Landscapes and Memetic Algorithm Design. In David Corne, Marco Dorigo, and Fred Glover, editors, New Ideas in Optimization, pages 245–260. McGraw-Hill, London, 1999
N. J. Radcliffe and P. D. Surry. Fitness variance of formae and performance prediction. In L. D. Whitley and M. D. Vose, editors, Foundations of Genetic Algorithms 3, pages 51–72. Morgan Kaufmann, 1995
J.L. Schlabach, C.C. Hayes, and D.E. Goldberg. FOX-GA: A Genetic Algorithm for Generating and Analyzing Battlefield Courses of Action. Evolutionary Computation, 7(1):45–68, 1999
Marc Schoenauer, Pierre Savéant, and Vincent Vidal. Divide-and-Evolve: a new memetic scheme for domain-independent temporal planning. In J. Gottlieb and G. Raidl, editors, Proc. EvoCOP’06. Springer Verlag, 2006
D. Smith and D. S. Weld. Temporal Planning with Mutual Exclusion Reasoning. In Proc. IJCAI-99, pages 326–337, 1999
L. Spector. Genetic Programming and AI Planning Systems. In Proc. AAAI 94, pages 1329–1334. AAAI/MIT Press, 1994
V. Vidal and H. Geffner. Branching and Pruning: An Optimal Temporal POCL Planner based on Constraint Programming. In Proc. AAAI-2004, pages 570–577, 2004
V. Vidal and H. Geffner. Branching and Pruning: An Optimal Temporal POCL Planner based on Constraint Programming (to appear). Artificial Intelligence, 2005
D. S. Weld. An Introduction to Least Commitment Planning. AI Magazine, 15(4):27–61, 1994
D. Whitley, T. Starkweather, and D. Fuquay. Scheduling problems and traveling salesman: The genetic edge recombination operator. In J. D. Schaffer, editor, Proc. 3 rd Intl Conf. on Genetic Algorithms. Morgan Kaufmann, 1989
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Schoenauer, M., Savéant, P., Vidal, V. (2007). Divide-and-Evolve: a Sequential Hybridization Strategy Using Evolutionary Algorithms. In: Siarry, P., Michalewicz, Z. (eds) Advances in Metaheuristics for Hard Optimization. Natural Computing Series. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72960-0_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-72960-0_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72959-4
Online ISBN: 978-3-540-72960-0
eBook Packages: Computer ScienceComputer Science (R0)