caa a22 4500 445804815 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110301xx s 000 0 eng 10.1007/s00453-009-9384-2 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9384-2 Sudholt Dirk Technische Universität Dortmund, 44221, Dortmund, Germany aut Hybridizing Evolutionary Algorithms withVariable-Depth Search to Overcome Local Optima [Elektronische Daten] [Dirk Sudholt] Hybridizing evolutionary algorithms with local search has become a popular trend in recent years. There is empirical evidence for various combinatorial problems where hybrid evolutionary algorithms perform better than plain evolutionary algorithms. Due to the rapid development of a highly active field of research, theory lags far behind and a solid theoretical foundation of hybrid metaheuristics is sorely needed. We are aiming at a theoretical understanding of why and when hybrid evolutionary algorithms are successful in combinatorial optimization. To this end, we consider a hybrid of a simple evolutionary algorithm, the (1+1)EA, with a powerful local search operator known as variable-depth search (VDS) or Kernighan-Lin. Three combinatorial problems are investigated: Mincut, Knapsack, and Maxsat. More precisely, we focus on simply structured problem instances that contain local optima which are very hard to overcome for many common metaheuristics. The plain (1+1)EA, iterated local search, and simulated annealing need exponential time for optimization, with high probability. In sharp contrast, the hybrid algorithm using VDS finds a global optimum in expected polynomial time. These results demonstrate the usefulness of hybrid evolutionary algorithms with VDS from a rigorous theoretical perspective. Springer Science+Business Media, LLC, 2010 Evolutionary algorithms nationallicence Hybridization nationallicence Iterated local search nationallicence Memetic algorithms nationallicence Simulated annealing nationallicence Runtime analysis nationallicence Combinatorial optimization nationallicence Algorithmica Springer-Verlag 59/3(2011-03-01), 343-368 0178-4617 59:3<343 2011 59 453 https://doi.org/10.1007/s00453-009-9384-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9384-2 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Sudholt Dirk Technische Universität Dortmund, 44221, Dortmund, Germany aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/3(2011-03-01), 343-368 0178-4617 59:3<343 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer