nach oben

Soft Computing

Erschienen in:

07.06.2016 | Focus

Adaptive-mutation compact genetic algorithm for dynamic environments

verfasst von: Chigozirim J. Uzor, Mario Gongora, Simon Coupland, Benjamin N. Passow

Erschienen in: Soft Computing | Ausgabe 8/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In recent years, the interest in studying nature-inspired optimization algorithms for dynamic optimization problems (DOPs) has been increasing constantly due to its importance in real-world applications. Several techniques such as hyperselection, change prediction, hypermutation and many more have been developed to address DOPs. Among these techniques, the hypermutation scheme has proved beneficial for addressing DOPs, but requires that the mutation factors be picked a priori and this is one of the limitations of the hypermutation scheme. This paper investigates variants of the recently proposed adaptive-mutation compact genetic algorithm (amcGA). The amcGA is made up of a change detection scheme and mutation schemes, where the degree of change regulates the probability of mutation (i.e. the probability of mutation is directly proportional to the degree of change). This paper also presents a change trend scheme for the amcGA so as to boost its performance whenever a change occurs. Experimental results show that the change trend and mutation schemes have an impact on the performance of the amcGA in dynamic environment and also indicate that the effect of the schemes depends on the dynamics of the environment as well as the dynamic problem being considered.

Vorheriger Artikel Adaptive learning with covariate shift-detection for motor imagery-based brain–computer interface

Nächster Artikel A Hadamard-type inequality for fuzzy integrals based on r-convex functions

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

Ahn CW, Ramakrishna RS (2003) Elitism-based compact genetic algorithms. IEEE Trans Evol Comput 7(4):367–385CrossRef

Bektas T (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3):209–219CrossRef

Branke J (1999) Memory enhanced evolutionary algorithms for changing optimization problems. In: In congress on evolutionary computation CEC99, Citeseer

Branke J, Kaußler T, Smidt C, Schmeck H (2000) A multi-population approach to dynamic optimization problems. In: Parmee IC (ed) Evolutionary design and manufacture. Springer, pp 299–307

Branke J, Orbayı M, Uyar Ş (2006) The role of representations in dynamic knapsack problems. In: Rothlauf F, Branke J, Cagnoni S, Costa E, Cotta C, Drechsler R, Lutton E, Machado P, Moore JH, Romero J, Smith GD, Squillero G, Takagi H (eds) Applications of evolutionary computing. Springer, pp 764–775

Bui LT, Michalewicz Z, Parkinson E, Abello M (2012) Adaptation in dynamic environments: a case study in mission planning. IEEE Trans Evol Comput 16(2):190–209CrossRef

Cobb H, Grefenstette J (1993) Genetic algorithms for tracking changing environments, Morgan Kaufmann Publishers Inc, San Francisco, CA, pp 523–530

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

Dasgupta D, McGregor DR (1993) SGA: a structured genetic algorithm. University of Strathclyde, Department of Computer Science

Dasgupta D, McGregor DR (1992) Nonstationary function optimization using the structured genetic algorithm. In: PPSN, pp 145–154

Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197CrossRef

Eiben A, Smit S (2012) Evolutionary algorithm parameters and methods to tune them. In: Youssef H, Eric M, Frédéric S (eds) Autonomous search. Springer, pp 15–36

Eiben A, Schut M, de Wilde A (2006) Boosting genetic algorithms with self-adaptive selection. In: IEEE congress on evolutionary computation. CEC 2006. pp 477–482

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

Fernandes CM, Guervós JJM, Rosa AC (2009) Using dissortative mating genetic algorithms to track the extrema of dynamic deceptive functions. CoRR abs/0904.3063

Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning, 1st edn. Addison-Wesley, BostonMATH

Goldberg DE (2002) The design of innovation: lessons from and for competent genetic algorithms. Kluwer Academic Publishers, NorwellCrossRefMATH

Goldberg DE, Smith RE (1987) Nonstationary function optimization using genetic algorithms with dominance and diploidy. In: ICGA, pp 59–68

Gongora M, Passow B, Hopgood A (2009) Robustness analysis of evolutionary controller tuning using real systems. In: IEEE Congress on evolutionary computation. CEC ’09, pp 606–613

Grefenstette JJ et al (1992) Genetic algorithms for changing environments. PPSN, vol 2. San Francisco, CA, pp 137–144

Hansen N, Kern S (2004) Evaluating the cma evolution strategy on multimodal test functions. In: Yao X, Burke EK, Lozano JA, Smith J, Merelo-Guervos JJ, Bullinaria JA, Rowe JE, Tivno P, Kaban A, Schwefel H-P (eds) Parallel problem solving from nature-PPSN VIII. Springer, pp 282–291

Hansen N, Ostermeier A (1996) Adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation. In: Proceedings of IEEE international conference on evolutionary computation, pp 312–317. doi:10.1109/ICEC.1996.542381

Hansen N, Ostermeier A (2001) Completely derandomized self-adaptation in evolution strategies. Evol Comput 9(2):159–195CrossRef

Harik G, Lobo F, Goldberg D (1999) The compact genetic algorithm. IEEE Trans Evol Comput 3(4):287–297CrossRef

Harik G, Lobo F, Sastry K (2006) Linkage learning via probabilistic modeling in the extended compact genetic algorithm (ecga). In: Pelikan M, Sastry K, CantPaz E (eds) Scalable optimization via probabilistic modeling, studies in computational intelligence, vol 33. Springer, Berlin, pp 39–61CrossRef

Hatzakis I, Wallace D (2006) Dynamic multi-objective optimization with evolutionary algorithms: a forward-looking approach. In: Proceedings of the 8th annual conference on genetic and evolutionary computation. ACM, New York, GECCO ’06, pp 1201–1208

Higuchi T, Iwata M, Keymeulen D, Sakanashi H, Murakawa M, Kajitani I, Takahashi E, Toda K, Salami N, Kajihara N, Otsu N (1999) Real-world applications of analog and digital evolvable hardware. IEEE Trans Evol Comput 3(3):220–235CrossRef

Jin Y, Branke J (2005) Evolutionary optimization in uncertain environments-a survey. IEEE Trans Evol Comput 9(3):303–317CrossRef

Juang CF (2004) A hybrid of genetic algorithm and particle swarm optimization for recurrent network design. IEEE Trans Syst Man Cybern B Cybern 34(2):997–1006CrossRef

Larraanaga P, Lozano JA (2001) Estimation of distribution algorithms: a new tool for evolutionary computation. Kluwer Academic Publishers, Norwell

Martins JP, Fonseca CM, Delbem AC (2014) On the performance of linkage-tree genetic algorithms for the multidimensional knapsack problem. Neurocomputing 146:17–29CrossRef

Mininno E, Cupertino F, Naso D (2008) Real-valued compact genetic algorithms for embedded microcontroller optimization. IEEE Trans Evol Comput 12(2):203–219CrossRef

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

Nelson AL, Barlow GJ, Doitsidis L (2009) Fitness functions in evolutionary robotics: a survey and analysis. Robot Auton Syst 57(4):345–370CrossRef

Nguyen TT, Yang S, Branke J (2012) Evolutionary dynamic optimization: a survey of the state of the art. Swarm Evol Comput 6:1–24CrossRef

Passow B, Gongora M, Coupland S, Hopgood A (2008) Real-time evolution of an embedded controller for an autonomous helicopter. In: IEEE congress on evolutionary computation. CEC 2008 (IEEE World Congress on Computational Intelligence), pp 2538–2545

Pedersen GK, Yang Z (2006) Multi-objective pid-controller tuning for a magnetic levitation system using nsga-ii. In: Proceedings of the 8th annual conference on genetic and evolutionary computation. ACM, New York, GECCO ’06, pp 1737–1744

Pelikan M, Goldberg D, Lobo F (2000) A survey of optimization by building and using probabilistic models. In: Proceedings of the 2000 American control conference, vol 5, pp 3289–3293

Rohlfshagen P, Yao X (2009) The dynamic knapsack problem revisited: a new benchmark problem for dynamic combinatorial optimisation. In: Giacobini M, Brabazon A, Cagnoni S, Di Caro G, Ekrt A, Esparcia-Alczar A, Farooq M, Fink A, Machado P (eds) Applications of evolutionary computing. Lecture notes in computer science, vol 5484. Springer, Berlin, pp 745–754

Sastry K, Abbass HA, Goldberg D (2005) Sub-structural niching in non-stationary environments. In: Geoffrey IW, Xinghuo Y (eds) AI 2004: advances in artificial intelligence. Springer, pp 873–885

Shah R, Reed P (2011) Comparative analysis of multiobjective evolutionary algorithms for random and correlated instances of multiobjective d-dimensional knapsack problems. Eur J Oper Res 211(3):466–479MathSciNetCrossRef

Simões A, Costa E (2009a) Improving prediction in evolutionary algorithms for dynamic environments. In: Proceedings of the 11th annual conference on genetic and evolutionary computation. ACM, pp 875–882

Simões A, Costa E (2009b) Prediction in evolutionary algorithms for dynamic environments using markov chains and nonlinear regression. In: Proceedings of the 11th annual conference on genetic and evolutionary computation. ACM, pp 883–890

Uzor C, Gongora M, Coupland S, Passow B (2014a) Adaptive mutation in dynamic environments. In: 14th UK workshop on computational intelligence (UKCI), pp 1–7

Uzor CJ, Gongora M, Coupland S, Passow BN (2014b) Real-world dynamic optimization using an adaptive-mutation compact genetic algorithm. In: 2014 IEEE Symposium on computational intelligence in dynamic and uncertain environments (CIDUE), pp 17–23

Vavak Frank, Fogarty Terence C, Jukes Ken (1996) A genetic algorithm with variable range of local search for tracking changing environments. In: Voigt H-M, Ebeling W, Rechenberg I, Schwefel H-P (eds) Parallel problem solving from nature PPSN IV. Springer, pp 376–385

Wang H, Yang S, Ip W, Wang D (2009) Adaptive primal-dual genetic algorithms in dynamic environments. IEEE Trans Syst Man Cybern B Cybern 39(6):1348–1361CrossRef

Whitley D (1991) Fundamental principles of deception. In: Foundations of genetic algorithms 1991 (FOGA 1), pp 221–241

Woldesenbet Y, Yen G (2009) Dynamic evolutionary algorithm with variable relocation. IEEE Trans Evol Comput 13(3):500–513CrossRef

Yang S (2008) Genetic algorithms with memory-and elitism-based immigrants in dynamic environments. Evol Comput 16(3):385–416CrossRef

Yang S, Richter H (2009) Hyper-learning for population-based incremental learning in dynamic environments. In: IEEE congress on evolutionary computation. CEC ’09, pp 682–689

Yang S, Tinós R (2007) A hybrid immigrants scheme for genetic algorithms in dynamic environments. Int J Autom Comput 4(3):243–254CrossRef

Yang S, Tinos R (2008) Hyper-selection in dynamic environments. In: IEEE congress on evolutionary computation. CEC 2008 (IEEE World Congress on Computational Intelligence), pp 3185–3192

Yang S, Yao X (2005) Experimental study on population-based incremental learning algorithms for dynamic optimization problems. Soft Comput 9(11):815–834CrossRefMATH

Yang S, Yao X (2008) Population-based incremental learning with associative memory for dynamic environments. IEEE Trans Evol Comput 12(5):542–561CrossRef

Yang S, Jiang Y, Nguyen TT (2013) Metaheuristics for dynamic combinatorial optimization problems. IMA J Manag Math 24(4):451–480MathSciNetCrossRefMATH

Yu E, Suganthan P (2009) Evolutionary programming with ensemble of explicit memories for dynamic optimization. In: IEEE congress on evolutionary computation. CEC ’09, pp 431–438

Yu X, Tang K, Yao X (2008) An immigrants scheme based on environmental information for genetic algorithms in changing environments. In: IEEE congress on evolutionary computation. CEC 2008 (IEEE World Congress on Computational Intelligence), pp 1141–1147

Zhu H, Jiao L, Pan J (2006) Multi-population genetic algorithm for feature selection. In: Jiao L, Wang L, Gao X, Liu J, Wu F (eds) Advances in natural computation. Lecture notes in computer science, vol 4222. Springer, Berlin, pp 480–487CrossRef

Titel: Adaptive-mutation compact genetic algorithm for dynamic environments
verfasst von: Chigozirim J. Uzor
Mario Gongora
Simon Coupland
Benjamin N. Passow
Publikationsdatum: 07.06.2016
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 8/2016
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-016-2195-x

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 8/2016

Scalable privacy-enhanced traffic monitoring in vehicular ad hoc networks

Ant colony optimization with immigrants schemes for the dynamic railway junction rescheduling problem with multiple delays

Quantum-inspired multi-objective optimization evolutionary algorithm based on decomposition

Sifter: an approach for robust fuzzy rule set discovery

Artificial bee colony algorithm for clustering: an extreme learning approach

Evolutionary approaches to signal decomposition in an application service management system