Skip to main content

Advertisement

SpringerLink
Log in

Memetic Algorithms: The Polynomial Local Search Complexity Theory Perspective

  • Published:
Journal of Mathematical Modelling and Algorithms

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aarts, E.M.H., Lenstra, J.K.: Introduction. In: Aarts, E.H.L., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization, pp. 1–17. Wiley, New York (1997)

    Google Scholar 

  2. Alekseeva, E., Kochetov, Y., Plyasunov, A.: Complexity of local search for the p-median problem. In: Proceedingss of MEC-VNS: 18th Mini Euro Conference on VNS (2005)

  3. Anderson, E.J., Glass, C.A., Potts, C.N.: Machine scheduling. In: Aarts, E.H.L., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization. Wiley, New York (1997)

    Google Scholar 

  4. Areibi, S., Moussa, M., Abdullah, H.: A comparison of genetic-memetic algorithms and other heuristic search techniques. In: Proceedings of the 2001 International Conference on Artificial Intelligence IC-AI 2001. Las Vegas, NV, USA (2001)

  5. Back, T., Fogel, D.B., Michalewicz, Z.: Handbook of Evolutionary Computation. IOP Publishing (1997)

  6. Baum, E.B., Bone, D., Garret, C.: Where genetic algorithms excel. Evol. Comput. 9(1), 93–124 (2001)

    Article  Google Scholar 

  7. Brimberg, J., Hansen, P., Mladenovic, N., Taillard, E.: Improvements and comparison of heuristics for solving the multisource weber problem. Oper. Res. 48(3), 444–460 (2000)

    Google Scholar 

  8. Freisleben, B., Merz, P.: New genetic local search operators for the traveling salesman problem. In: Voigt, H.-M., Ebeling, W., Rechenberg, I., Schwefel, H.-P. (eds.) Proceedings of the 4th Conference on Parallel Problem Solving from Nature - PPSN IV. Lecture Notes in Computer Science, vol. 1141, pp. 890–900. Springer (1996)

  9. Gutin, G., Yeo, A.: Polynomial approximation algorithms for the tsp and the qap with a factorial domination number. Discrete Appl. Math. 119, 107–116 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  10. Gutin, G., Yeo, A., Zverovich, A.: Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the tsp. Discrete Appl. Math. 117, 81–86 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  11. Goldberg, D.E., Lingle, R.: Alleles, loci, and the travelling salesman problem. In: Proceedings of the First International Conference on Genetic Algorithms and their Applications. Lawrence Erlbaum Associates (1985)

  12. Hansen, P., Brimberg, J., Mladenovic, N., Urosevic, D.: Primal-dual variable neighborhood search for the simple plant location problem. INFORMS Journal on Computing (2007) (in press)

  13. Hansen, P., Mladenovic, N.: Variable neighborhood search for the p-median. Location Sci. 5(4), 207–226 (1998)

    Article  Google Scholar 

  14. Hansen, P., Mladenovic, N.: An introduction to variable neighborhood search. Metaheuristics, Advances and Trends in Local Search Paradigms for Optimization, pp. 433–458 (1999)

  15. Hansen, P., Mladenovic, N.: Variable neighborhood search: Principles and applications. European J. Oper. Res. 130, 449–467 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  16. Hart, W.E.: Adaptive global optimization with local search. Ph.D. thesis, University of California, San Diego (1994)

  17. Hart, W.E.: A convergence analysis of unconstrained and bound constrained evolutionary pattern search. Evol. Comput. 9(1) (2001)

  18. Hart, W.E., Krasnogor, N., Smith, J.E. (eds.): Recent Advances in Memetic Algorithms and Related Search Technologies. Springer (2004)

  19. Hart, W.E., Belew, R.K.: Optimizing an arbitrary function is hard for the genetic algorithm. In: Proceedings of the 4th International Conference on Genetic Algorithms, pp. 190–195. (June 1991)

  20. He, J., Yao, X.: Drif analysis and average time complexity of evolutionary algorithms. Artif. Intell. 127, 57–85 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  21. Johnson, D.S., McGeoch, L.A.: The traveling salesman problem: a case study. In: Aarts, E.H.L., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization, pp. 215–310. Wiley, New York (1997)

    Google Scholar 

  22. Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search. J. Comput. Syst. Sci. 37, 79–100 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  23. Konig, R., Dandekar, T.: Improving genetic algorithms for protein folding simulations by systematic crossover. BioSystems 50, 17–25 (1999)

    Article  Google Scholar 

  24. Krasnogor, N.: 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)

  25. Krasnogor, N., Smith, J.E.: A tutorial for competent memetic algorithms: Model, taxonomy and design issues. IEEE Trans. Evol. Algorithms 9(5), 474–488 (2005)

    Article  Google Scholar 

  26. Krentel, M.W.: Structure in locally optimal solutions. In: 30th Annual Symposium on Foundations of Computer Science, pp. 216–222. IEEE Computer Society Press, Los Alamitos, CA (1989)

  27. Land, M.W.S.: Evolutionary algorithms with local search for combinatorial optimization. Ph.D. thesis, University of California, San Diego (1998)

  28. Merz, P.: Memetic algorithms for combinatorial optimization problems: fitness landscapes and effecitve search strategies. Ph.D. thesis, Parallel Systems Research Group. Department of Electrical Engineering and Computer Science, University of Siegen (2000)

  29. Merz, P., Freisleben, B.: Memetic algorithms and the fitness landscape of the graph bi-partitioning problem. In: Eiben, A.E., Back, T., Schoenauer, M., Schwefel, H.-P. (eds.) Proceedings of the 5th Conference on Parallel Problem Solving from Nature – PPSN V. Lecture Notes in Computer Science, vol. 1498, pp. 765–774. Springer (1998)

  30. Merz, P., Freisleben, B.: Fitness landscapes and memetic algorithm design. In: Corne, D., Glover, F., Dorigo, M. (eds.) New Ideas in Optimization. McGraw-Hill (1999)

  31. Merz, P., Freisleben, B.: Fitness landscapes, memetic algorithms, and greedy operators for graph bipartitioning. J. Evol. Comput. 8(1), 61–91 (2000)

    Article  Google Scholar 

  32. Mladenovic, N.: A variable neighborhood algorithm: a new metaheuristic for combinatorial optimization. Technical report, Abstract of papers presented at Optimization Days, Montreal, Canada (1995)

  33. Moon, B.R., Lee, Y.S., C.Y Kim: Genetic vlsi circuit partitioning with two-dimensional geographic crossover and zigzag mapping. In: Proceedings of the 1997 ACM symposium on Applied computing, pp. 274–278. ACM Press (2001)

  34. Moscato, P.: Memetic algorithms’ home page, accessed (2005)

  35. Moscato, P.A.: On evolution, search, optimization, genetic algorihtms and martial arts: towards memetic algorithms. Technical Report Caltech Concurrent Computation Program Report 826, Caltech, Caltech, Pasadena, CA (1989)

  36. Muhlenbein, H., Gorges-Schleuter, M., Kramer, O.: Evolution algorithms in combinatorial optimization. Parallel Comput. 7, 65–85 (1988)

    Article  Google Scholar 

  37. Papadimitriou, C.H.: The complexity of the lin-kernighan heuristic for the traveling salesman problem. SIAM J. Comput. 21, 450–465 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  38. Paun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer (1998)

  39. Rayward-Smith, V.J.,: A unified approach to tabu search, simulated annealing and genetic algorithms. Applications of Modern Heuristic Methods, pp. 17–38 (1995)

  40. Reinelt, G.: Tsplib (http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/tsplib95/tsplib.html), accessed (November 2005)

  41. Salustowicz, R.P., Schmidhuber, J.: Probabilistic incremental program evolution. Evol. Comput. 5(2), 123–141 (1997)

    Google Scholar 

  42. Shumacher, C., Vose, M.D., Whitley, L.D.: The no free lunch and problem description length. In: Spector, L., Goodman, E.D., Wu, A., Langdon, W.B., Voigt, H.M., Gen, M., Sen, S., Dorigo, M., Pezeshk, S., Garzon, M.H., Burke, E.K. (eds.) GECCO 2001: Proceedings of the Genetic and Evolutionary Computation Conference. Morgan Kaufmann (2001)

  43. Rana, S.: The role of local optima in evolutionary search. Ph.D. thesis, Department of Computer Sciences, Colorado University (2000)

  44. Jones, T.: Evolutionary algorithms, fitness landscapes and searh. Ph.D. thesis, Univesity of New Mexico, Albuquerque, NM (1995)

  45. Unger, R., Moult, J.: Genetic algorithms for protein folding simulations. J. Mol. Biol. 231(1), 75–81 (1993)

    Article  Google Scholar 

  46. Vitany, P.M.B.: A discipline of evolutionary programming. Theor. Comput. Sci. 241, 1–2, 3–23 (2000)

    Article  Google Scholar 

  47. Vose, M.D., Wright, A.H.: Form invariance and implicit parallelism. Evol. Comput. 9(3), 355–370 (2001)

    Article  Google Scholar 

  48. Wegener, I., Scharnow, J., Tinnefeld, K.: Fitness landscapes based on sorting and shortest paths problems. In: Proceedings of the Parallel Problem Solving from Nature VII. Lecture Notes In Computer Science (2002)

  49. Whitley, D.: Permutations. In: Bäck, T., Fogel, D.B., Michalewicz, Z. (eds.) Evolutionary Computation 1: Basic Algorithms and Operators, chapter 33.3, pp. 274–284. Institute of Physics Publishing, Bristol (2000)

  50. Wolpert, D., Macready, W.: No free lunch theorems for optimization. IEEE Transactions in Evolutionary Computation, pp. 67–82 (1997)

  51. Wolpert, D.H., Macready, W.G.: No free lunch theorems for search. Technical report SFI-TR-95-02-010, Santa Fe Institute, New Mexico (1995)

  52. Yannakakis, M. Computational complexity. In: Aarts, E., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization, pp. 19–55. Wiley (1997)

Download references

Author information

Authors and Affiliations

  1. Automated Scheduling, Optimisation and Planning Research Group, School of Computer Science and IT, University of Nottingham, Nottingham, UK

    Natalio Krasnogor

  2. Faculty of Computing, Engineering and Mathematical Sciences, University of the West of England, Bristol, UK

    Jim Smith

Authors
  1. Natalio Krasnogor
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jim Smith
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Natalio Krasnogor.

Electronic Supplementary Material

Below is the link to the electronic supplementary material.

(PDF 190 kb)

Rights and permissions

Reprints and permissions

About this article

Cite this article

Krasnogor, N., Smith, J. Memetic Algorithms: The Polynomial Local Search Complexity Theory Perspective. J Math Model Algor 7, 3–24 (2008). https://doi.org/10.1007/s10852-007-9070-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10852-007-9070-9

Keywords

Mathematics Subject Classifications (2000)

Search

Navigation