Skip to main content
SpringerLink
Log in

Dynamic function optimisation with hybridised extremal dynamics

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

Abstract

Dynamic function optimisation is an important research area because many real-world problems are inherently dynamic in nature. Over the years, a wide variety of algorithms have been proposed to solve dynamic optimisation problems, and many of these algorithms have used the Moving Peaks (MP) benchmark to test their own capabilities against other approaches. This paper presents a detailed account of our hybridised Extremal Optimisation (EO) approach that has achieved hitherto unsurpassed results on the three standardised scenarios of the MP problem. Several different components are used in the hybrid EO, and it has been shown that a large proportion of the quality of its outstanding performance is due to the local search component. In this paper, the behaviour of the local search algorithms used is analysed, and the roles of other components are discussed. In the concluding remarks, the generalisation ability of this method and its wider applicability are highlighted.

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
¥17,985 /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 includes VAT (Japan)

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. Angeline PJ (1997) Tracking extrema in dynamic environments. In: Proceedings of the 6th international conference on evolutionary programming VI, LNCS, vol 1213. Springer, Berlin, pp 335–345

  2. Ayvaz D, Topcuoglu H, Gurgen F (2006) A comparative study of evolutionary optimisation techniques in dynamic environments. In: Proceedings of the genetic and evolutionary computation conference (GECCO 2006), Seattle, pp 1397–1398

  3. Bak P, Sneppen K (1993) Punctuated equilibrium and criticality in a simple model of evolution. Phys Rev Lett 74: 4083–4086

    Article  Google Scholar 

  4. Balle P, Fischer M, Fussel D, Nelles O, Isermann R (1998) Integrated control, diagnosis and reconfiguration of a heat exchanger. IEEE Control Syst Mag 18: 52–63

    Article  Google Scholar 

  5. Benasla L, Belmadani A, Rahli M (2008) Hooke-jeeves’ method applied to a new economic dispatch problem formulation. J Inf Sci Eng 24: 907–917

    Google Scholar 

  6. Blackwell T (2003) Swarms in dynamic environments. In: Proceedings of the genetic and evolutionary computation conference (GECCO 2003), Chicago, pp 1–12

  7. Blackwell T, Branke J (2004) Multi-swarm optimization in dynamic environments. In: Applications of evolutionary computing, LNCS, vol 3005. Springer, Berlin, pp 489–500

  8. Blackwell T, Branke J (2006) Multi-swarms, exclusion and anti-convergence in dynamic environments. IEEE Trans on Evol Comput 10(4): 51–58

    Google Scholar 

  9. Boettcher S (1999) Extremal optimization of graph partitioning at the percolation threshold. J Phys A Math Gen 32: 5201–5211

    Article  MATH  MathSciNet  Google Scholar 

  10. Boettcher S, Percus A (2000) Nature’s way of optimizing. Artif Intell 119(1): 275–286

    Article  MATH  Google Scholar 

  11. Boettcher S, Percus AG (1999) Extremal optimization: Methods derived from co-evolution. In: Proceedings of the genetic and evolutionary computation conference (GECCO 1999), Orlando, FL, pp 825–832

  12. Branke J (1999) Memory enhanced evolutionary algorithms for changing optimization problems. In: Proceedings of the IEEE congress on evolutionary computation (CEC 1999), Washington, DC, pp 1875–1882

  13. Branke J, Schmeck H (2002) Designing evolutionary algorithms for dynamic optimization problems. In: Tsutsui S, Ghosh A (eds) Theory and application of evolutionary computation: recent trends. Springer, Berlin, pp 239–362

    Google Scholar 

  14. Branke J, Kaußler T, Schmidt C, Schmeck H (2000) A multi-population approach to dynamic optimization problems. In: Parmee I (eds) Adaptive computing in design and manufacturing (ACDM 2000). Springer, Berlin, pp 299–308

    Google Scholar 

  15. Bui L, Branke J, Abbass H (2005) Diversity as a selection pressure in dynamic environments. In: Proceedings of the genetic and evolutionary computation conference (GECCO 2005), Washington, DC, pp 1557–1558

  16. Bui L, Branke J, Abbass H (2005) Multiobjective optimization for dynamic environments. In: Proceedings of the IEEE congress on evolutionary computation (CEC 2005), Edinburgh, pp 2349–2356

  17. Chiong R, Neri F, McKay R (2009) Nature that breeds solutions. In: Chiong R (eds) Nature-inspired informatics for intelligent applications and knowledge discovery: implications in business, science and engineering, information science reference, chap 1. IGI Global, Hershey, pp 1–24

    Google Scholar 

  18. Grefenstette JJ (1999) Evolvability in dynamic fitness landscapes: a genetic algorithm approach. In: Proceedings of the IEEE congress on evolutionary computation (CEC 1999), Washington, DC, pp 2031–2038

  19. Hooke R, Jeeves T (1961) Direct search solutions of numerical and statistical problems. J Assoc Comput Mach 8: 212–229

    MATH  Google Scholar 

  20. Janson S, Middendorf M (2004) A hierachical particle swarm optimizer for dynamic optimization problems. In: Applications of evolutionary computing, LNCS, vol 3005. Springer, Berlin, pp 513–524

  21. De Jong KA (1975) An analysis of the behavior of a class of genetic adaptive systems. PhD thesis, University of Michigan

  22. Li J, Balazs M, Parks G, Clarkson P (2002) A species conserving genetic algorithm for multimodal function optimization. Evol Comput 10(3): 207–234

    Article  Google Scholar 

  23. Li X (2004) Adaptively choosing neighbourhood bests using species in a particle swarm optimizer for multimodal function optimization. In: Proceedings of the genetic and evolutionary computation conference (GECCO 2004), Seattle, pp 105–116

  24. Li X, Branke J, Blackwell T (2006) Particle swarm with speciation and adaptation in a dynamic environment. In: Proceedings of the genetic and evolutionary computation conference (GECCO 2006), Seattle, pp 51–58

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

    Article  Google Scholar 

  26. Lung R, Dumitrescu D (2007) A collaborative model for tracking optima in dynamic environments. In: Proceedings of the IEEE congress on evolutionary computation (CEC 2007), Singapore, pp 564–567

  27. Lung R, Dumitrescu D (2009) Evolutionary swarm cooperative optimization in dynamic environments. Natural Comput. doi:10.1007/s11047-009-9129-9

  28. Mendes R, Mohais A (2005) Dynde: A differential evolution for dynamic optimization problems. In: Proceedings of the IEEE congress on evolutionary computation (CEC 2005), Edinburgh, pp 2808–2815

  29. Meyer K, Nasut S, Bishop M (2006) Stochastic diffusion search: partial function evaluation in swarm intelligence dynamic optimization. In: Abraham A, Grosan C, Ramos V (eds) Stigmergic optimization, studies in computational intelligence, vol 31. Springer, Berlin, pp 185–207

    Google Scholar 

  30. Moser I (2008) Applying extremal optimisation to dynamic optimisation problems. PhD thesis, Swinburne University of Technology, Australia

  31. Moser I (2009) Hooke–jeeves revisited. In: Proceedings of the IEEE congress on evolutionary computation (CEC 2009), Trondheim, pp 2670–2676

  32. Moser I, Chiong R (2009) A Hooke–Jeeves based memetic algorithm for solving dynamic optimisation problems. In: Proceedings of the 4th international conference on hybrid artificial intelligence systems (HAIS 2009), LNAI, vol 5572. Springer, Berlin, pp 301–309

  33. Moser I, Hendtlass T (2007) A simple and efficient multi- component algorithm for solving dynamic function optimisation problems. In: Proceedings of the IEEE congress on evolutionary computation (CEC 2007), Singapore, pp 252–259

  34. Neri F, del Toro Garcia X, Cascella GL, Salvatore N (2008) Surrogate assisted local search on pmsm drive design. COMPEL Intl J Comput Math Electr Electr Eng 27(3): 573–592

    Article  MATH  Google Scholar 

  35. Parrott D, Li X (2004) A particle swarm model for tracking multiple peaks in a dynamic environment using speciation. In: Proceedings of the IEEE congress on evolutionary computation (CEC 2004), Portland, pp 105–116

  36. Ronnewinkel C, Martinetz T (2001) Explicit speciation with few a priori parameters for dynamic optimization problems. In: GECCO workshop on evolutionary algorithms for dynamic optimization problems, San Francisco, pp 31–34

  37. Trojanowski K (2007) B-cell algorithm as a parallel approach to optimization of moving peaks benchmark tasks. In: Proceedings of the 6th international conference on computer information systems and industrial management applications, Elk, Poland, pp 143–148

  38. Wang H, Wang D, Yang S (2007) Triggered memory-based swarm optimisation in dynamic environments. In: Applications of evolutionary computing, LNCS, vol 4448. Springer, Berlin, pp 637–646

  39. Weise T, Zapf M, Chiong R, Nebro A (2009) Why is optimization difficult?. In: Chiong R (eds) Nature-inspired algorithms for optimisation, studies in computational intelligence, vol 193. Springer, Berlin, pp 1–50

    Chapter  Google Scholar 

  40. Yang S (2005) Memory-based immigrants for genetic algorithms in dynamic environments. In: Proceedings of the genetic and evolutionary computation conference (GECCO 2005), Washington, DC, pp 1115–1122

  41. Zou X, Wang M, Zhou A, Mckay B (2004) Evolutionary optimization based on chaotic sequence in dynamic environments. In: Proceedings of the IEEE international conference on networking, sensing and control, Taipei, Taiwan, pp 1364–1369

Download references

Author information

Authors and Affiliations

  1. Faculty of Information and Communication Technologies, Swinburne University of Technology, Victoria, 3122, Australia

    Irene Moser

  2. School of Computing and Design, Swinburne University of Technology (Sarawak Campus), Jalan Simpang Tiga, 93350, Kuching, Sarawak, Malaysia

    Raymond Chiong

Authors
  1. Irene Moser
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Raymond Chiong
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Raymond Chiong.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Moser, I., Chiong, R. Dynamic function optimisation with hybridised extremal dynamics. Memetic Comp. 2, 137–148 (2010). https://doi.org/10.1007/s12293-009-0027-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12293-009-0027-6

Keywords

Search

Navigation