Top

Evolutionary Intelligence

Published in:

01-06-2011 | Special Issue

On the role of age diversity for effective aging operators

Authors: Thomas Jansen, Christine Zarges

Published in: Evolutionary Intelligence | Issue 2/2011

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Aging is a general mechanism that some randomized search heuristics employ to increase the diversity of their collection of search points. A more diverse collection of search points is believed to improve the search heuristic’s performance for difficult problems. The most prominent randomized search heuristics with aging are evolutionary algorithms and artificial immune systems. While it is known that randomized search heuristics with aging can be very much more efficient than randomized search heuristics without aging the details of the origin of such benefits are difficult to understand. We contribute to this understanding by presenting a detailed and structured analysis of aging. We prove that in addition to diversity with respect to search points diversity with respect to age plays a key role. We analyze different ways of dealing with age diversity by means of theoretical as well as empirical analyses. Major results include a more structured understanding of aging and showcases where age diversity can make the difference between efficient and completely inefficient optimization.

previous article Surrogate-assisted clonal selection algorithms for expensive optimization problems

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

All line numbers from Algorithm 1.

Ackley DA (1987) A connectionist machine for genetic hillclimbing. Kluwer Academic Publishers, Berlin

Castrogiovanni M, Nicosia G, and Rascunà R (2007) Experimental analysis of the aging operator for static and dynamic optimisation problems. In: Apolloni B, Howlett RJ, Jain LC (eds) Proceedings of the 11th international conference on knowledge-based and intelligent information and engineering systems (KES 2007). Lecture notes in computer science, vol 4694. Springer, pp 804–811

Choi D-H (2002) Cooperative mutation based evolutionary programming for continuous function optimization. Oper Res Lett 30(3):195–201MathSciNetMATHCrossRef

Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. MIT Press, Cambridge

Cutello V, Lee D, Leone S, Nicosia G, Pavone M (2006) Clonal selection algorithm with dynamic population size for bimodal search spaces. In: Jiao L, Wang L, Gao X, Liu J, Wu F (eds) Proceedings of the 2nd international conference on advances in natural computation (ICNC 2006). Lecture notes in computer science, vol 4221. Springer, pp 949–958

Cutello V, Morelli G, Nicosia G, and Pavone M (2005) Immune algorithms with aging operators for the string folding problem and the protein folding problem. In: Raidl GR, Gottlieb J (eds) Proceedings of the 5th European conference on evolutionary computation in combinatorial optimization (EvoCOP 2005). Lecture notes in computer science, vol 3448. Springer, pp 80–90

Cutello V and Nicosia G (2002) Multiple learning using immune algorithms. In: Proceedings of the 4th international conference on recent advances in soft computing (RASC 2002), pp 102–107

Cutello V, Nicosia G, Pavone M (2003) A hybrid immune algorithm with information gain for the graph coloring problem. In: Proceedings of the 5th annual conference on genetic and evolutionary computation (GECCO 2003). Lecture notes in computer science, vol 2723. Springer, pp 171–182

Cutello V, Nicosia G, Pavone M (2004) Exploring the capability of immune algorithms: a characterization of hypermutation operators. In: Nicosia G, Cutello V, Bentley PJ, Timmis J (eds) Proceedings of the 3rd international conference on artificial immune systems (ICARIS 2004). Lecture notes in computer science, vol 3239. Springer, pp 263–276

10.

Cutello V, Nicosia G, Pavone M (2004) An immune algorithm with hyper-macromutations for the Dill’s 2d hydrophobic-hydrophilic model. In: Proceedings of the 6th IEEE congress on evolutionary computation (CEC 2004). IEEE Press, pp 1074–1080

11.

Cutello V, Nicosia G, Pavone M (2007) An immune algorithm with stochastic aging and Kullback entropy for the chromatic number problem. J Combin Optim 14(1):9–33MathSciNetMATHCrossRef

12.

Cutello V, Nicosia G, Pavone M, Timmis J (2007) An immune algorithm for protein structure prediction on lattice models. IEEE Trans Evol Comput 11(1):101–117CrossRef

13.

Cutello V, Nicosia G, Romeo M, Oliveto PS (2007). On the convergence of immune algorithms. In: Proceedings of the IEEE symposium on foundations of computational intelligence (FOCI 2007). IEEE Press, pp 409–415

14.

Dasgupta D, Niño LF (2008) Immunological computation: theory and applications. Auerbach

15.

Feller W (1968) An introduction to probability theory and its applications, Vol I. Wiley, Hoboken

16.

Friedrich T, Oliveto PS, Sudholt D, Witt C (2009) Analysis of diversity-preserving mechanisms for global exploration. Evol Comput 17(4):455–476CrossRef

17.

Ghosh A, Tsutsui S, Tanaka H (1996) Individual aging in genetic algorithms. In: Australian New Zealand conference on intelligent information systems. IEEE Press, pp 276–279

18.

Harik G, Cantú-Paz E, Goldberg D, Miller B (1999) The gambler’s ruin problem, genetic algorithms, and the sizing of populations. Evol Comput 7(3):231–253CrossRef

19.

Hornby GS (2006) ALPS: the age-layered population structure for reducing the problem of premature convergence. In: Proceedings of the 8th annual conference on genetic and evolutionary computation (GECCO 2006). ACM Press, pp 815–822

20.

Hornby GS (2009) Steady-state ALPS for real-valued problems. In: Proceedings of the 11th annual conference on genetic and evolutionary computation (GECCO 2009). ACM, pp 795–802

21.

Hornby GS (2010) A steady-state version of the age-layered population structure EA. In: Goldberg DE, Koza JR, Riolo R, O’Reilly U-M, McConaghy T (eds) Genetic programming theory and practice VII, genetic and evolutionary computation. Springer, LK, pp 87–102

22.

Horoba C, Jansen T, Zarges C (2009) Maximal age in randomized search heuristics with aging. In: Proceedings of the 11th annual conference on genetic and evolutionary computation (GECCO 2009). ACM Press, pp 803–810

23.

Jansen T, Wegener I (2002) On the analysis of evolutionary algorithms—a proof that crossover really can help. Algorithmica 34(1):47–66MathSciNetMATHCrossRef

24.

Jansen T, Zarges C (2009) Comparing different aging operators. In: Proceedings of the 8th international conference on artificial immune systems (ICARIS 2009). Lecture notes in computer science, vol 5666. Springer, pp 95–108

25.

Jansen T, Zarges C (2010) Aging beyond restarts. In: Proceedings of the 12th annual conference on genetic and evolutionary computation (GECCO 2010). ACM Press, pp. 705–712

26.

Jansen T, Zarges C (2010) On the benefits of aging and the importance of details. In: Proceedings of the 9th international conference on artificial immune systems (ICARIS 2010). Lecture notes in computer science, vol 6209. Springer, pp. 61–74

27.

De Jong KA (2006) Evolutionary computation. MIT Press, Cambridge

28.

Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Sci Agric 220:671–680MathSciNet

29.

Kubota N, Fukuda T (1997) Genetic algorithms with age structure. Soft Comput 1(4):155–161

30.

Motwani R, Raghavan P (1995) Randomized algorithms. Cambridge University Press, CambridgeMATH

31.

Schwefel H-P and Rudolph G (1995) Contemporary evolution strategies. In: Morán F, Moreno A, Guervós JJM, and Chacón P (eds) Proceedings of the 3rd European conference on artificial life (ECAL 1995). Lecture notes in computer science, vol 929. Springer, pp 893–907

32.

Stracquadanio G, Drago C, Romano V, Nicosia G (2010) An immunological algorithm for doping profile optimization in semiconductors design. In: Proceedings of the 9th international conference on artificial immune systems (ICARIS 2010). Lecture notes in computer science, vol 6209, Springer, pp 213–222.

33.

Witt C (2006) Runtime analysis of the (μ + 1) EA on simple pseudo-Boolean functions. Evol Comput 14(1):65–86MathSciNet

Title: On the role of age diversity for effective aging operators
Authors: Thomas Jansen
Christine Zarges
Publication date: 01-06-2011
Publisher: Springer-Verlag
Published in: Evolutionary Intelligence / Issue 2/2011
Print ISSN: 1864-5909
Electronic ISSN: 1864-5917
DOI: https://doi.org/10.1007/s12065-011-0051-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner