Memetic algorithms beat evolutionary algorithms on the class of hurdle problems

ABSTRACT

Memetic algorithms are popular hybrid search heuristics that integrate local search into the search process of an evolutionary algorithm in order to combine the advantages of rapid exploitation and global optimisation. However, these algorithms are not well understood and the field is lacking a solid theoretical foundation that explains when and why memetic algorithms are effective.

We provide a rigorous runtime analysis of a simple memetic algorithm, the (1+1) MA, on the Hurdle problem class, a landscape class of tuneable difficulty that shows a "big valley structure", a characteristic feature of many hard problems from combinatorial optimisation. The only parameter of this class is the hurdle width w, which describes the length of fitness valleys that have to be overcome. We show that the (1+1) EA requires Θ(n^w) expected function evaluations to find the optimum, whereas the (1+1) MA with best-improvement and first-improvement local search can find the optimum in Θ(n² + n³/w²) and Θ(n³/w²) function evaluations, respectively. Surprisingly, while increasing the hurdle width makes the problem harder for evolutionary algorithms, the problem becomes easier for memetic algorithms. We discuss how these findings can explain and illustrate the success of memetic algorithms for problems with big valley structures.

References

1. Fawaz Alanazi and Per Kristian Lehre. Runtime analysis of selection hyper-heuristics with classical learning mechanisms. In IEEE Congress on Evolutionary Computation (CEC 2014), pages 2515--2523, 2014.
2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. 3rd edition, 2009.
3. Michael J. Dinneen and Kuai Wei. On the analysis of a (1+1) adaptive memetic algorithm. In IEEE Workshop on Memetic Computing (MC), pages 24--31, 2013.
4. Christian Gießen. Hybridizing evolutionary algorithms with opportunistic local search. In Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation (GECCO '13), pages 797--804, 2013.
5. Doug R Hains, Darrell L Whitley, and Adele E Howe. Revisiting the big valley search space structure in the tsp. Journal of the Operational Research Society, 62 (2):305--312, 2011.
6. Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. On the runtime analysis of generalised selection hyper-heuristics for pseudo-boolean optimisation. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '17), pages 849--856, 2017.
7. Helena R. Lourenço, Olivier C. Martin, and Thomas Stützle. Iterated local search. In Handbook of Metaheuristics, volume 57 of International Series in Operations Research & Management Science, pages 321--353. 2002.
8. Peter Merz and Bernd Freisleben. Memetic algorithms and the fitness landscape of the graph bi-partitioning problem. In Parallel Problem Solving from Nature (PPSN V), pages 765--774, 1998.
9. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. 1995.
10. Ferrante Neri and Carlos Cotta. Memetic algorithms and memetic computing optimization: A literature review. Swarm and Evolutionary Computation, 2:1--14, 2012.
11. Ferrante Neri, Carlos Cotta, and Pablo Moscato, editors. Handbook of Memetic Algorithms, volume 379 of Studies in Computational Intelligence. 2012.
12. Gabriela Ochoa and Nadarajen Veerapen. Deconstructing the big valley search space hypothesis. In Proceedings of the 16th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP 2016), pages 58--73, 2016.
13. Tiago Paixão, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenovś. Towards a runtime comparison of natural and artificial evolution. Algorithmica, 78 (2):681--713, 2017.
14. Adam Prügel-Bennett. When a genetic algorithm outperforms hill-climbing. Theoretical Computer Science, 320(1):135 -- 153, 2004.
15. Colin R. Reeves. Landscapes, operators and heuristic search. Annals of Operations Research, 86(0):473--490, 1999.
16. Jialong Shi, Qingfu Zhang, and Edward P. K. Tsang. EB-GLS: an improved guided local search based on the big valley structure. Memetic Computing, abs/1709.07576, 2017.
17. Dirk Sudholt. Local search in evolutionary algorithms: the impact of the local search frequency. In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC '06), volume 4288 of LNCS, pages 359--368, 2006.
18. Dirk Sudholt. On the analysis of the (1+1) memetic algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '06), pages 493--500, 2006.
19. Dirk Sudholt. The impact of parametrization in memetic evolutionary algorithms. Theoretical Computer Science, 410(26):2511--2528, 2009.
20. Dirk Sudholt. Hybridizing evolutionary algorithms with variable-depth search to overcome local optima. Algorithmica, 59(3):343--368, 2011.
21. Dirk Sudholt. Memetic evolutionary algorithms. In Anne Auger and Benjamin Doerr, editors, Theory of Randomized Search Heuristics - Foundations and Recent Developments, number 1 in Series on Theoretical Computer Science, pages 141--169. 2011.
22. Dirk Sudholt and Christine Zarges. Analysis of an iterated local search algorithm for vertex coloring. In 21st International Symposium on Algorithms and Computation (ISAAC 2010), volume 6506 of LNCS, pages 340--352, 2010.
23. Kuai Wei and Michael J. Dinneen. Runtime analysis comparison of two fitness functions on a memetic algorithm for the clique problem. In IEEE Congress on Evolutionary Computation (CEC '14), pages 133--140, 2014.
24. Kuai Wei and Michael J. Dinneen. Runtime analysis to compare best-improvement and first-improvement in memetic algorithms. In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO '14), pages 1439--1446, 2014.
25. Carsten Witt. Analysis of an iterated local search algorithm for vertex cover in sparse random graphs. Theoretical Computer Science, 425(0):117--125, 2012.

Index Terms

• Theory of computation

  • Theory and algorithms for application domains

    • Theory of randomized search heuristics