[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

A general cost-benefit-based adaptation framework for multimeme algorithms

  • Regular Research Paper
  • Published:
Memetic Computing Aims and scope Submit manuscript

Abstract

As memetic algorithms (MA) are a crossbreed between local searchers and evolutionary algorithms (EA) spreading of computational resources between evolutionary and local search is a key issue for a good performance, if not for success at all. This paper summarises and continues previous work on a general cost-benefit-based adaptation scheme for the choice of local searchers (memes), the frequency of their usage, and their search depth. This scheme eliminates the MA strategy parameters controlling meme usage, but raises new ones for steering the adaptation itself. Their impact is analysed and it will be shown that in the end the number of strategy parameters is decreased significantly as well as their range of meaningful values. In addition to this the number of fitness evaluations is reduced drastically. Both are necessary prerequisites for many practical applications as well as for the acceptance of the method by practitioners. Although the introduced framework is tailored to EAs producing more than one offspring per mating, it is also suited for those with only one child per pairing. So there are no preconditions to the EA for the described adaptation scheme to be applied.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Auger A, Hansen N (2005) Performance evaluation of an advanced local search evolutionary algorithm. In: Conference proceedings of IEEE congress on evolutionary computation, CEC 2005, pp 1777–1784

  2. Auger A, Hansen N (2005) A restart CMA evolution strategy with increasing population size. In: Conference proceedings of IEEE congress on evolutionary computation, CEC 2005, pp 1769–1776

  3. Bader-El-Den M, Poli R, Fatima S (2009) Evolving timetabling heuristics using a grammar-based genetic programming hyper-heuristic framework. J Memet Comput 1(3): 205–219

    Article  Google Scholar 

  4. Bäck T (1992) GENEsYs 1.0. http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/genetic/ga/systems/genesys/0.html. Accessed 11 Aug 2009

  5. Bambha NK, Bhattacharyya SS, Zitzler E, Teich J (2004) Systematic integration of parameterized local search into evolutionary algorithms. IEEE Trans Evolut Comput 8(2): 137–155

    Article  Google Scholar 

  6. Blume C (1991) GLEAM—a system for intuitive learning. In: Schwefel H-P, Männer R (eds) Conference proceedings of PPSN I, LNCS 496. Springer, Berlin, pp 48–54

    Google Scholar 

  7. Blume C, Gerbe M (1994) Deutliche Senkung der Produktionskosten durch Optimierung des Ressourceneinsatzes. In: atp, vol 36(5), Oldenbourg Verlag, München, pp 25–29 (in German)

  8. Blume C, Jakob W (2002) GLEAM—an evolutionary algorithm for planning and control based on evolution strategy. In: Cantú-Paz E (ed) Conference proceedings of GECCO 2002, LBP, pp 31–38

  9. Blume C, Jakob W (2009) GLEAM - General Learning Evolutionary Algorithm and Method: ein Evolutionärer Algorithmus und seine Anwendungen. (in German), vol. 32 of Schriftenreihe des Instituts für Angewandte Informatik - Automatisierungstechnik. KIT Scientific Publishing, Karlsruhe

  10. Box MJ (1965) A new method of constrained optimization and a comparison with other methods. Comput J 8: 42–52

    MATH  MathSciNet  Google Scholar 

  11. Burke E, Kendall G, Newall J, Hart E, Ross P, Schulenberg S (2003) Hyper-heuristics: an emerging direction in modern search technology. In: Glover F, Kochenberg GA (eds) Handbook of metaheuristics. Kluwer, Dordrecht, pp 457–474

    Google Scholar 

  12. Caponio A, Cascella GL, Neri F, Salvatore N, Sumner M (2007) Fast adaptive memetic algorithm for online and offline control design of PMSM drives. IEEE Trans Syst Man Cybern Part B 37(1): 28–41

    Article  Google Scholar 

  13. Davis, L (eds) (1991) Handbook of genetic algorithms. Van Nostrand Reinhold, NY

    Google Scholar 

  14. Eiben AE, Hinterding R, Michalewicz Z (1999) Parameter control in evolutionary algorithms. IEEE Trans Evolut Comput 3(2): 124–141

    Article  Google Scholar 

  15. Gruau F, Whitley D (1993) Adding learning to the cellular development of neural networks: evolution and the Baldwin effect. Evolut Comput 1(3): 213–233

    Article  Google Scholar 

  16. Gorges-Schleuter M (1990) Genetic algorithms and population structures—a massively parallel algorithm. Dissertation, Department of Computer Science, University of Dortmund, Germany

  17. Gorges-Schleuter M (1998) A comparative study of global and local selection in evolution strategies. In: Eiben AE, Bäck T, Schoenauer M, Schwefel H-P (eds) Conference proceedings of PPSN V, LNCS 1498. Springer, Berlin, pp 367–377

    Google Scholar 

  18. Gorges-Schleuter M et al (1999) An analysis of local selection in evolution strategies. In: Banzhaf W (eds) Conference proceedings of GECCO 1999. Morgan Kaufmann, San Francisco, pp 847–854

    Google Scholar 

  19. Hart WE (1994) Adaptive global optimization with local search. Dissertation, University of California, USA

  20. Hart WE, Krasnogor N, Smith JE (2004) Editorial introduction. Evolut Comput 12(3):v–vi (special issue on Memetic Algorithms)

  21. Hart WE, Krasnogor N, Smith JE (eds) (2004) Recent advances in memetic algorithms. In: Studies in fuzziness and soft computing, vol 166, Springer

  22. Hansen B (2006) Compilation of results on the 2005 CEC benchmark function set. CoLab, Institute of Computational Science, ETH Zurich, Technical Report. http://www3.ntu.edu.sg/home/epnsugan/index_fileq/CEC-05/compareresults.pdf. Accessed 18 Aug 2009

  23. Jakob W et al (2002) HyGLEAM—an approach to generally applicable hybridization of evolutionary algorithms. In: Merelo JJ (eds) Conference proceedings of PPSN VII, LNCS 2439. Springer, Berlin, pp 527–536

    Google Scholar 

  24. Jakob W, Blume C, Bretthauer G (2004) Towards a generally applicable self-adapting hybridization of evolutionary algorithms. In: Conference proceedings of GECCO 2004, LNCS 3102, Springer, Berlin, pp 790–791 and LBP

  25. Jakob W et al (2006) Towards an adaptive multimeme algorithm for parameter optimisation suiting the engineers’ needs. In: Runarsson TP (eds) Conference proceedings of PPSN IX, LNCS 4193. Springer, Berlin, pp 132–141

    Google Scholar 

  26. Jakob W et al (2008) A cost-benefit-based adaptation scheme for multimeme algorithms. In: Jakob W (eds) Conference proceedings of parallel processing and applied mathematics 2007. Springer, LNCS 4967, pp 509–519

    Chapter  Google Scholar 

  27. Jakob W, Quinte A, Stucky K-U, Süß W (2008) Fast multi-objective scheduling of jobs to constrained resources using a hybrid evolutionary algorithm. In: Rudolph G (eds) Conference proceedings of PPSN X, LNCS 5199. Springer, Berlin, pp 1031–1040

    Google Scholar 

  28. Krasnogor N, Smith JE (2001) Emergence of profitable search strategies based on a simple inheritance algorithm. In: Conference proceedings of GECCO 2001, M. Kaufmann, San Francisco, pp 432–439

  29. Krasnogor N, Blackburne BP, Burke EK, Hirst JD (2002) Multimeme algorithms for protein structure prediction. In: Conference proceedings of PPSN VII, LNCS 2439, Springer, Berlin, pp 769–778, citation: p 772

  30. Krasnogor N (2002) Studies on the theory and design space of memetic algorithms. Dissertation, University West of England, UK

  31. Krasnogor N, Smith J (2005) A tutorial for competent memetic algorithms: model, taxonomy, and design issues. IEEE Trans Evolut Comput 5(9): 474–488

    Article  Google Scholar 

  32. Law NL, Szeto KY (2007) Adaptive genetic algorithm with mutation and crossover matrices. In: Veloso MM (ed) Conference proceedings of IJCAI-07, pp 2330–2333

  33. Land MWS (1998) Evolutionary algorithms with local search for combinatorial optimization. Dissertation, University of California, USA

  34. Lozano M, Herrera F, Krasnogor N, Molina D (2004) Real-coded memetic algorithms with crossover hill-climbing. Evolut Comput 12(2): 273–302

    Article  Google Scholar 

  35. Meuth R, Lim MH, Ong YS, Wunsch DC II (2009) A proposition on memes and meta-memes in computing for high-order learning. J Memet Comput 1(2): 85–100

    Article  Google Scholar 

  36. Nelder JA, Mead RA (1965) Simplex method for function minimization. Comput J 7: 308–313

    MATH  Google Scholar 

  37. Neri F, Tirronen V, Kärkkäinen T, Rossi T (2007) Fitness diversity based adaptation in multimeme algorithms: a comparative study. In: Conference proceedings of IEEE congress on evolutionary computing, CEC 2007, pp 2374–2381

  38. Neri F, Toivanen J, Cascella GL, Ong YS (2007) An adaptive multimeme algorithm for designing HIV multidrug therapies. IEEE/ACM Trans Comput Biol Bioinform 4(2): 264–278

    Article  Google Scholar 

  39. Neri F, Tirronen V (2008) On memetic differential evolution frameworks: a study of advantages and limitations in hybridization. In: Conference proceedings of IEEE congress on evolutionary computing, CEC 2008, pp 2135–2142

  40. Neri F, Tirronen V (2009) Scale factor local search in differential evolution. J Memet Comput 1(2): 153–171

    Article  Google Scholar 

  41. Nguyen QH, Ong YS, Krasnogor N (2007) A study on design issues of memetic algorithm. In: Conference proceedings of IEEE congress on evolutionary computing, CEC 2007, pp 2390–2397

  42. Noman N, Iba H (2008) Accelerating differential evolution using an adaptive local search. IEEE Trans Evolut Comput 12(1): 107–125

    Article  Google Scholar 

  43. Ong YS, Keane AJ (2004) Meta-Lamarckian learning in memetic algorithms. IEEE Trans Evolut Comput 8(2): 99–110

    Article  Google Scholar 

  44. Ong YS, Lim MH, Zhu N, Wong KW (2006) Classification of adaptive memetic algorithms: a comparative study. IEEE Trans Syst Man Cybern Part B 36(1): 141–152

    Article  Google Scholar 

  45. Orvosh D, Davis L (1993) Shall we repair? Genetic algorithms, combinatorial optimization, and feasibility constraints. In: Forrest S (ed) Conference proceedings of Morgan Kaufmann, San Mateo, CA, p 650

  46. Posik P (2005) Real-parameter optimization using the mutation step co-evolution. In: Conference proceedings of IEEE congress on evolutionary computing, CEC 2005, pp 872–879

  47. Rosenbrock HH (1960) An automatic method for finding the greatest or least value of a function. Comput J 3: 175–184

    Article  MathSciNet  Google Scholar 

  48. Schwefel H-P (1995) Evolution and optimum seeking. Wiley, New York

    Google Scholar 

  49. Smith JE (2003) Co-evolving memetic algorithms: a learning approach to robust scalable optimisation. In: Conference proceedings of IEEE congress on evolutionary computing, CEC 2003, pp 498–505

  50. Smith JE et al (2008) Self-adaptation in evolutionary algorithms for combinatorial optimisation. In: Cotta C (eds) Adaptive and multilevel metaheuristics, SCI 136. Springer, Berlin, pp 31–57

    Chapter  Google Scholar 

  51. Sudholt D (2009) The impact of parameterization in memetic evolutionary algorithms. Theor Comput Sci. doi:10.1016/j.tcs.2009.03.003

  52. Suganthan PN, Hansen N, Liang JJ, Deb K, Chen Y-P, Auger A, Tiwari S (2005) Problem definition and evaluation criteria for the CEC 2005 special session on real-parameter optimization. Technical report, Nanyang Technical University, Singapore and KanGAL Technical Report #2005005, IIT Kanpur, India. Available at http://www.ntu.edu.sg/home/epnsugan

  53. Szeto KY, Zhang J (2005) Adaptive genetic algorithm and quasi-parallel genetic algorithm: application to low-dimensional physics. In: Conference proceedings of large-scale scientific computing (LSSC 2005), LNCS 3743, Springer, Berlin, pp 189–196

  54. Takahara S, Kusumoto Y, Miyamoto S (2001) An adaptive meta-heuristic approach using partial optimization to non-convex polygons allocation problem. In: Conference proceedings of fuzzy systems 2001, IEEE, vol 3, pp 1191–1194

  55. Tirronen V, Neri F (2009) Differential evolution with fitness diversity self-adaptation. In: Chiong R (eds) Nature-inspired algorithms for optimisation, SCI 193. Springer, Berlin, pp 199–234

    Chapter  Google Scholar 

  56. Whitley D, Gordon V, Mathias K et al (1994) Lamarckian evolution, the Baldwin effect and function optimization. In: Davidor Y (eds) Conference proceedings of PPSN III, LNCS 866. Springer, Berlin, pp 6–14

    Google Scholar 

  57. Yang J-M, Kao C-Y (2000) Integrating adaptive mutations and family competition into genetic algorithms as function optimizer. Soft Comput 4(2): 89–102

    Article  Google Scholar 

  58. Zitzler E, Teich J, Bhattacharyya SS (2000) Optimizing the efficiency of parameterized local search within global search: a preliminary study. In: Conference proceedings of IEEE congress on evolutionary computing, CEC 2000, pp 365–372

Download references

Author information

Authors and Affiliations

  1. Karlsruhe Institute of Technology (KIT), Institute of Applied Computer Science (IAI), P. O. Box 3640, 76021, Karlsruhe, Germany

    Wilfried Jakob

Authors
  1. Wilfried Jakob
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wilfried Jakob.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Jakob, W. A general cost-benefit-based adaptation framework for multimeme algorithms. Memetic Comp. 2, 201–218 (2010). https://doi.org/10.1007/s12293-010-0040-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12293-010-0040-9

Keywords