nach oben

Natural Computing

Erschienen in:

01.06.2016

Global memory schemes for dynamic optimization

verfasst von: Yesnier Bravo, Gabriel Luque, Enrique Alba

Erschienen in: Natural Computing | Ausgabe 2/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Nowadays, it is common to find research problems (in system biology, mobile applications, etc.) that change over time, requiring algorithms which dynamically adapt the search to the new conditions. In most of them, the utilization of some information from the past allows to quickly adapt after a change. This is the idea underlining the use of memory in this field, what involves key design issues concerning the memory content, the process of update, and the process of retrieval. In this article, we focus on global memory schemes, which are the most intuitive and popular ones, and perform an integral analysis of current design variants based on a comprehensive set of benchmarks. Results show the benefits and drawbacks of each strategy, as well as the effect of the algorithm and problem features in the memory performance.

Vorheriger Artikel Development of firefly algorithm via chaotic sequence and population diversity to enhance the image contrast

Nächster Artikel On the model updating operators in univariate estimation of distribution algorithms

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 "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

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

Alba E, Nakib A, Siarry P (2013) Metaheuristics for dynamic optimization. Springer, BerlinCrossRef

Bendtsen CN, Krink T (2002) Dynamic memory model for non-stationary optimization. In: IEEE congress on evolutionary computation, pp 145–150

Bosman PAN (2007) Learning and anticipation in online dynamic optimization. In: Yang S, Ong YS, Jin Y (eds) Evol comput in dynamic and uncertain environments. Springer, Berlin, pp 129–152CrossRef

Branke J (1999) Memory enhanced evolutionary algorithms for changing optimization problems. In: IEEE congress on evolutionary computation, vol 3, pp 1875–1882

Branke J, Kaußler T, Schmidt C, Schmeck H (2000) A multipopulation approach to dynamic optimization problems. Adaptive comp in design and manufacturing. LNCS, Springer, Berlin

Brest J, Zamuda A, Boskovic B, Maucec MS, Zumer V (2009) Dynamic optimization using self-adaptive differential evolution. IEEE Congr Evol Comput. doi:10.1109/CEC.2009.4982976

Cao Y, Luo W (2010) A novel updating strategy for associative memory scheme in cyclic dynamic environments. In: International Workshop on Advanced Computational Intelligence. Suzhou, pp 32–39

Cobb HG (1990) An investigation into the use of hypermutation as an adaptive operator in genetic algorithms having continuous, time-dependent nonstationary environments. NAVAL RESEARCH LAB, Washington

Eggermont J, Lenaerts T, Poyhonen S, Termier A (2001) Raising the dead: extending evolutionary algorithms with a case-based memory. In: Miller JF et al (eds) Genetic Programming. Proc of EuroGP. Springer, Berlin, pp 280–290CrossRef

Eshelman LJ, Schaffer JD (1993) Real-coded genetic algorithms and interval-schemata. In: Whitley LD (ed) Foundations of Genetic Algorithms 2. Morgan Kaufmann, Los Altos, pp 187–202

Goldberg DE, Smith RE (1987) Nonstationary function optimization using genetic algorithms with dominance and diploidy. In: International conference on genetic algorithms. Morgan Kaufmann, Los Altos, pp 59–68

Grefenstette JJ (1992) Genetic algorithms for changing environments. In: Maenner R, Manderick B (eds) Parallel problem solving from nature. North-Holland, Amsterdam, pp 137–144

Halder U, Das S, Maity D (2013) A cluster-based differential evolution algorithm with external archive for optimization in dynamic environments. IEEE Trans Cybern 43(3):881–897CrossRef

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

Kennedy J, Eberhart R (1995) Particle swarm optimization. In: IEEE international conference on neural networks. vol 4, pp 1942–1948. doi:10.1109/ICNN.1995.488968

Lepagnot J, Nakib A, Oulhadj H, Siarry P (2013) A multiple local search algorithm for continuous dynamic optimization. J Heuristics 19(1):35–76CrossRef

Lewis EHJ, Ritchie G (1998) A comparison of dominance mechanisms and simple mutation on non-stationary problems. In: Parallel problem solving from nature. Springer, Berlin, pp 139–148

Li C, Yang S, Nguyen TT, Yu EL, Yao X, Jin Y, Beyer H-G, Suganthan PN (2008) Benchmark generator for CEC 2009 competition on dynamic optimization. Technical Report. University of Leicester and University of Birmingham, UK

Li C, Yang S, Alej D, Pelta R (2011) Benchmark generator for the IEEE WCCI-2012 competition on evolutionary computation for dynamic optimization problems. Technical Report. University of Leicester and University of Birmingham, UK

Louis SJ, Xu Z (1996) Genetic algorithms for open shop scheduling and re-scheduling. In: Proceedings of the 11th international conference on computers and their application, ISCA, Winona, MN, pp 99–102

Lozano M, Herrera F, Krasnogor N, Molina D (2004) Real-coded Memetic Algorithms with crossover hill-climbing. Evol Comput 12(3):273–302CrossRef

Maurice C Standard PSO 2007 (Spso-07) Tech Report [online] http://www.particleswarm.info/Programs.html

Mavrovouniotis M, Yang S (2012) Ant colony optimization with memory-based immigrants for the dynamic vehicle routing problem. In: IEEE congress on evolutionary computation, pp 1–8

Mori N, Kita H, Nishikawa Y (1997) Adaptation to changing environments by means of the memory based thermodynamical genetic algorithm. Int Conf on Genetic Algorithms. Morgan Kaufmann, Los Altos, pp 299–306

Muhlenbein H, Schlierkamp-Voosen D (1993) Predictive models for the breeder genetic algorithm I. continuous parameter optimization. Evol Comput 1:25–49CrossRef

Ng KP, Wong KC (1997) A new diploid scheme and dominance change mechanism for non-stationary function optimisation. Int Conf Genetic Algorithms. Morgan Kaufmann, Los Altos, pp 159–166

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

Richter H, Yang S (2008) Memory based on abstraction for dynamic fitness functions. In: Giacobini M et al (eds) Applications of Evolutionary Computing, vol LNCS 4974. Springer, Berlin, pp 596–605CrossRef

Richter H, Yang S (2009) Learning behavior in abstract memory schemes for dynamic optimization problems. Soft Comput 13(12):1163–1173CrossRefMATH

Simões A, Costa E (2007) Improving memory’s usage in evolutionary algorithms for changing environments. In: IEEE congress on evolutionary computation, pp 276–283

Simões A, Costa E (2008) Evolutionary algorithms for dynamic environments: prediction using linear regression and Markov chains. In: Parallel problem solving from nature. Springer, Berlin, vol 5199, pp 306–315

Simões A, Costa E (2011) Memory-based CHC algorithms for the dynamic traveling salesman problem. Genetic and evolutionary computation conference (GECCO). ACM, New York, pp 1037–1044

Trojanowski K, Michalewicz Z (1999) Searching for optima in non-stationary environments. In: Congress on evolutionary computation. Washington, DC, pp 1843–1850

Tseng L Y, Chen C (2008) Multiple trajectory search for large scale global optimization. In: IEEE congress on evolutionary computation, pp 3052–3059

Wang H, Yang S, Ip WH, Wang D (2012) A memetic particle swarm optimisation algorithm for dynamic multi-modal optimisation problems. Int J Syst Sci 43(7):1268–1283MathSciNetCrossRefMATH

Wineberg M, Oppacher F (2003) A linear time algorithm for determining population diversity in evolutionary computation. Intell Syst Control. Salzburg, Austria, pp 270–275

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

Yang S (2003) Non-stationary problem optimization using the primal-dual genetic algorithm. Congr Evol Comput 3:2246–2253

Yang S (2005a) Memory-enhanced univariate marginal distribution algorithms for dynamic optimization problems. Congr Evol Comput. doi:10.1109/CEC.2005.1555015

Yang S (2005b) Memory-based immigrants for genetic algorithms in dynamic environments. In: Proceedings of the 2005 genetic and evolutionary computation conference, GECCO–05, ACM, New York, NY, pp 1115–1122

Yang S (2007) Explicit memory schemes for evolutionary algorithms in dynamic environments. In: Yang S, Yew-Soon, Jin Y (eds) Evolutionary computation in dynamic and uncertain environments. doi:10.1007/978-3-540-49774-5_1

Yang S (2008) Genetic algorithms with memory and elitism-based immigrants in dynamic environments. IEEE Trans Evol Comput. doi:10.1162/evco.2008.16.3.385

Yang S, Li C (2010) A clustering particle swarm optimizer for locating and tracking multiple optima in dynamic environments. IEEE Trans Evol Comput. doi:10.1109/TEVC.2010.2046667

Yang S, Yao X (2005) Experimental study on population-based incremental learning algorithms for dynamic optimization problems. Soft Comput. doi:10.1007/s00500-004-0422-3 MATH

Yang S, Yao X (2008) Population-based incremental learning with associative memory for dynamic environments. IEEE Trans Evol Comput. doi:10.1109/TEVC.2007.913070

Zhu T, Luo W, Li Z (2011) An adaptive strategy for updating the memory in evolutionary algorithms for dynamic optimization. In: IEEE symposium on computational intelligence in dynamic and uncertain environments, pp 8–15

Titel: Global memory schemes for dynamic optimization
verfasst von: Yesnier Bravo
Gabriel Luque
Enrique Alba
Publikationsdatum: 01.06.2016
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 2/2016
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-015-9497-2

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 "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2016

The computational capability of chemical reaction automata

Minimal output unstable configurations in chemical reaction networks and deciders

Physarum in silicon: the Greek motorways study

On the model updating operators in univariate estimation of distribution algorithms

Adaptive niche quantum-inspired immune clonal algorithm

On decidability and closure properties of language classes with respect to bio-operations

Premium Partner