Name
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s10852-007-9070-9 | J. Math. Model. Algorithms |
Keywords | Field | DocType |
local search,network flow,memetic algorithm,travelling salesman problem,graph partitioning,evolutionary algorithm | Flow network,Memetic algorithm,Mathematical optimization,Crossover,Evolutionary algorithm,Polynomial,Travelling salesman problem,Artificial intelligence,Local search (optimization),Graph partition,Machine learning,Mathematics | Journal |
Volume | Issue | ISSN |
7 | 1 | 1572-9214 |
Citations | PageRank | References |
14 | 0.63 | 21 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Natalio Krasnogor | 1 | 1213 | 85.53 |
| Jim Smith | 2 | 152 | 11.63 |