nach oben

Soft Computing

Erschienen in:

01.11.2005 | Focus

Experimental study on population-based incremental learning algorithms for dynamic optimization problems

verfasst von: Shengxiang Yang, Xin Yao

Erschienen in: Soft Computing | Ausgabe 11/2005

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Evolutionary algorithms have been widely used for stationary optimization problems. However, the environments of real world problems are often dynamic. This seriously challenges traditional evolutionary algorithms. In this paper, the application of population-based incremental learning (PBIL) algorithms, a class of evolutionary algorithms, for dynamic problems is investigated. Inspired by the complementarity mechanism in nature a Dual PBIL is proposed, which operates on two probability vectors that are dual to each other with respect to the central point in the genotype space. A diversity maintaining technique of combining the central probability vector into PBIL is also proposed to improve PBIL’s adaptability in dynamic environments. In this paper, a new dynamic problem generator that can create required dynamics from any binary-encoded stationary problem is also formalized. Using this generator, a series of dynamic problems were systematically constructed from several benchmark stationary problems and an experimental study was carried out to compare the performance of several PBIL algorithms and two variants of standard genetic algorithm. Based on the experimental results, we carried out algorithm performance analysis regarding the weakness and strength of studied PBIL algorithms and identified several potential improvements to PBIL for dynamic optimization problems.

Vorheriger Artikel A new population based adaptive domination change mechanism for diploid genetic algorithms in dynamic environments

Nächster Artikel Adaptive actor-critic learning for the control of mobile robots by applying predictive models

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

For the convenience of description in this paper we will call the probability vector that has 0.5 for all of its entries central probability vector or just central vector because it represents the central point in the genotype space.

For each bit position of a solution, assuming binary encoded, if a random created real number in the range of [0.0, 1.0] is less than the probability value of corresponding element in the probability vector, the bit is set to 1 (or 0), otherwise it is set to 0 (or 1 respectively).

For the convenience of analyzing experimental results on dynamic problems, we herein call the first period stationary since the behavior of an algorithm on a dynamic problem during this period is the same as that on the relevant stationary problem. And the other nine periods are called dynamic.

Bäck T (1998) On the behavior of evolutionary algorithms in dynamic fitness landscape. In: Proceedings of the 1998 IEEE international conference on evolutionary computation, pp 446–451

Baker JE (1987) Reducing bias and inefficiency in the selection algorithms. In: Grefenstelle JJ (ed) Proceedings of the 2nd international conference on genetic algorithms. Lawrence Erlbaum Associates, pp 14-21

Baluja S (1994) Population-based incremental learning: a method for integrating genetic search based function optimization and competitive learning. Technical report CMU-CS-94-163, Carnegie Mellon University, USA

Baluja S, Caruana R (1995) Removing the genetics from the standard genetic algorithm. In: Proceedings of the 12th international conference on machine learning, pp 38–46

Branke J (1999) Memory enhanced evolutionary algorithms for changing optimization problems. In: Proceedings of the 1999 congress on evolutionary computation 3:1875–1882

Branke J, Kaußler T, Schmidt C, Schmeck H (2000) A multi-population approach to dynamic optimization problems. In: Adaptive computing in design and manufacturing

Branke J (2001) Evolutionary approaches to dynamic optimization problems—updated survey. In: GECCO Workshop on evolutionary algorithms for dynamic optimization problems, pp 134–137

Branke J (2002) Evolutionary optimization in dynamic environments. Kluwer, Dordrecht

Cobb HG (1990) An Investigation into the use of hypermutation as an adaptive operator in genetic algorithms having continuous, time-dependent nonstationary environments. Technical report AIC-90-001, Naval Research Laboratory, Washington

10.

Cobb HG, Grefenstette J (1993) Genetic algorithms for tracking changing environments. In: Proceedings of the 5th international conference on genetic algorithms, pp 523–530

11.

Dasgupta D, McGregor D (1992) Nonstationary function optimization using the structured genetic algorithm. In: Proceedings of the 2nd international conference on parallel problem solving from nature, pp 145–154

12.

Goldberg DE, Smith RE (1987) Nonstationary function optimization using genetic algorithms with dominance and diploidy. In: Grefenstelle JJ (ed) Proceedings of the 2nd international conference on genetic algorithms. Lawrence Erlbaum Associates, pp 59–68

13.

Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading

14.

González C, Lozano JA, Larrañaga P (2000) Analyzing the population based incremental learning algorithm by means of discrete dynamical systems. Complex Syst 12(4):465–479

15.

Grefenstette JJ (1992) Genetic algorithms for changing environments. In: Männer R, Manderick B (eds) Proceedings of the 2nd international conference on parallel problem solving from nature, pp 137–144

16.

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

17.

Höhfeld M, Rudolph G (1997) Towards a theory of population-based incremental learning. In: Proceedings of the 4th IEEE conference on evolutionary computation, pp 1–5

18.

Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor

19.

Larrañaga P, Lozano JA (2002) Estimation of distribution algorithms: a new tool for evolutionary computation. Kluwer, Dordrecht

20.

Lewis J, Hart E, Ritchie G (1998) A comparison of dominance mechanisms and simple mutation on non-stationary problems. In: Proceedings of the 5th int conf on parallel problem solving from nature, pp 139–148

21.

Mitchell M, Forrest S, Holland JH (1992) The royal road for genetic algorithms: fitness landscapes and GA performance. In: Proceedings of the 1st European conference on artificial life, pp 245–254

22.

Mori N, Kita H, Nishikawa Y (1997) Adaptation to changing environments by means of the memory based thermodynamical genetic algorithm. In: Bäck T (ed) Proceedings of the 7th international conference on genetic algorithms. Morgan Kaufmann Publishers, pp 299–306

23.

Morrison RW, De Jong KA (1999) A test problem generator for non-stationary environments. In: Proceedings of the 1999 congress on evolutionary computation, vol 3, pp 2047–2053

24.

Morrison RW, De Jong KA (2000) Triggered hypermutation revisited. In: Proceedings of the 2000 congress on evolutionary computation, pp 1025–1032

25.

Mühlenbein H, Paab G (1996) From recombination of genes to the estimation of distributions I. Binary parameters. In: Voigt H-M, Ebeling W, Rechenberg I, Schwefel H-P (eds) Proceedings of the 4th international conference on parallel problem solving from nature, pp 178–187

26.

Ng KP, Wong KC (1995) A new diploid scheme and dominance change mechanism for non-stationary function optimisation. In: Eshelman LJ (ed) Proceedings of the 6th international conference on genetic algorithms

27.

Servais MP, de Jaer G, Greene JR (1997) Function optimization using multiple-base population based incremental learning. In: Proceedings of the 8th South African workshop on pattern recognition

28.

Trojanowski K, Michalewicz Z (2000) Evolutionary optimization in non-stationary environments. J Comp Sci Technol 1(2):93–124

29.

Whitley LD (1991) Fundamental principles of deception in genetic search. In: Rawlins GJE (ed) Foundations of genetic algorithms, vol 1, pp 221–241

30.

Yang S (2003) Non-stationary problem optimization using the primal-dual genetic algorithm. In: Proceedings of the 2003 congress on evolutionary computation, vol 3, pp 2246–2253

Titel: Experimental study on population-based incremental learning algorithms for dynamic optimization problems
verfasst von: Shengxiang Yang
Xin Yao
Publikationsdatum: 01.11.2005
Verlag: Springer-Verlag
Erschienen in: Soft Computing / Ausgabe 11/2005
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-004-0422-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 11/2005

A new population based adaptive domination change mechanism for diploid genetic algorithms in dynamic environments

Particle swarms and population diversity

A weight adaptation method for fuzzy cognitive map learning

Adaptive actor-critic learning for the control of mobile robots by applying predictive models

Analysis of local operators applied to discrete tracking problems

Editorial: special issue on dynamic optimization problems

Premium Partner