Memetic algorithms: The polynomial local search complexity theory perspective

Krasnogor, Natalio; Smith, Jim

Abstract

In previous work (Krasnogor, http://www.cs.nott.ac.uk/~nxk/papers.html . In: Studies on the Theory and Design Space of Memetic Algorithms. Ph.D. thesis, University of the West of England, Bristol, UK, 2002; Krasnogor and Smith, IEEE Trans Evol Algorithms 9(6):474-488, 2005) we develop a syntax-only classification of evolutionary algorithms, in particular so-called memetic algorithms (MAs). When "syntactic sugar" is added to our model, we are able to investigate the polynomial local search (PLS) complexity of memetic algorithms. In this paper we show the PLS-completeness of whole classes of problems that occur when memetic algorithms are applied to the travelling salesman problem using a range of mutation, crossover and local search operators. Our PLS-completeness results shed light on the worst case behaviour that can be expected of a memetic algorithm under these circumstances. Moreover, we point out in this paper that memetic algorithms for graph partitioning and maximum network flow (both with important practical applications) also give rise to PLS-complete problems. © 2007 Springer Science + Business Media B.V.

• Journal Article Type: Article
• Publication Date: Mar 1, 2008
• Deposit Date: Feb 13, 2013
• Journal: Journal of Mathematical Modelling and Algorithms
• Print ISSN: 1570-1166
• Electronic ISSN: 1572-9214
• Publisher: Springer Verlag
• Peer Reviewed: Peer Reviewed
• Volume: 7
• Issue: 1
• Pages: 3-24
• DOI: https://doi.org/10.1007/s10852-007-9070-9
• Keywords: memetic algorithms, genetic local search hybrids, evolutionary hybrid algorithms, travelling salesman problem, graph partitioning, polynomial local search, multimeme algorithms, meta-lamarckian algorithms, hyper-heuristics
• Public URL: https://uwe-repository.worktribe.com/output/1019856
• Publisher URL: http://dx.doi.org/10.1007/s10852-007-9070-9
• Contract Date: Nov 15, 2016