Abstract
When dealing with dynamic environments two major aspects must be considered in order to improve the algorithms’ adaptability to changes: diversity and memory. In this paper we propose and study a new evolutionary algorithm that combines two populations, one playing the role of memory, with a biological inspired recombination operator to promote and maintain diversity. The size of the memory mechanism may vary along time. The size of the (usual) search population may also change in such a way that the sum of the individuals in the two populations does not exceed an established limit. The two populations have minimum and maximum sizes allowed that change according to the stage of the evolutionary process: if an alteration is detected in the environment, the search population increases its size in order to readapt quickly to the new conditions. When it is time to update memory, its size is increased if necessary. A genetic operator, inspired by the biological process of conjugation, is proposed and combined with this memory scheme. Our ideas were tested under different dynamics and compared with other approaches on two benchmark problems. The obtained results show the efficacy, efficiency and robustness of the investigated algorithm.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Branke, J.: Memory Enhanced Evolutionary Algorithms for Changing Optimization Problems. In: Proc. of the 1999 IEEE Congress on Evolutionary Computation, pp. 1875-1882 (1999)
Branke, J.: Evolutionary Optimization in Dynamic Environments. Kluwer, Norwell, MA (2001)
Branke, J., Kaußler,T., Schmidt, C., Schmeck, H.: A Multi-Population Approach to Dynamic Optimization Problems. Adaptive Computing in Design and Manufacture (ACDM 2000) pp. 299-308 (2000)
Cobb, H.: An Investigation into the Use of Hypermutation as an Adaptive Operator in Genetic Algorithms Having Continuous, Time-Dependent Non-Stationary Environments. Technical Report AIC-90-001 (1990)
Goldberg, D.E., Smith, R.E.: Nonstationary Function Optimization using Genetic Algorithms with Dominance and Diploidy. In: Proc. of the 2nd Int. Conference. on Genetic Algorithms, pp. 59-68 (1987)
Grefenstette, J.J.: Genetic Algorithms for Changing Environments. Conference Parallel Problem Solving from Nature 2, 137–144 (1992)
Harvey, I.: The Microbial Genetic Algorithm. Unpublished (1996)
Liles, W., De Jong, K.: The Usefulness of Tag Bits in Changing Environments. Proceedings of 1999 IEEE Congress on Evolutionary Computation, pp. 2054-2060 (1999)
Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs, 3rd edn. Springer-Verlag, Berlin Heidelberg New York (1999)
Morrison, R.W., De Jong, K.: Triggered Hypermutation Revisited. In: Proc. of the 1999 IEEE Congress on Evolutionary Computation, pp. 1025-1032 (1999)
Ng, K.P., Wong, K.C., New, A.: Diploid Scheme and Dominance Change Mechanism for Non-stationary Function Optimization. In: Proc. of the 6th Int. Conference on Genetic Algorithms, pp. 159-166 (1995)
Russell, P.J.: Genetics, 5th edn. Addison-Wesley, London, UK (1998)
Uyar, A.S., Harmanci, A.E.: A New Population Based Adaptive Domination Change Mechanism for Diploid Genetic Algorithms in Dynamic Environments. Soft Computing, vol. 9, pp. 803–814 (2005)
Simões, A., Costa, E.: Transposition: A Biologically Inspired Mechanism to Use with Genetic Algorithms. In: Proc. of the 4th Int. Conf. on Artificial Neural Networks, pp. 612- 619 (1999)
Simões, A., Costa, E.: An Immune System-Based Genetic Algorithm to Deal with Dynamic Environments: Diversity and Memory. In: Proc. of the 6th Int. Conference on Artificial Neural Networks, pp. 168-174 (2003)
Simões, A., Costa, E.: Variable-size Memory Evolutionary Algorithm to Deal with Dynamic Environments: an empirical study. CISUC Technical Report, TR 2006/004 - ISSN 0874-338X (November 2006)
Smith, P.: Conjugation: A Bacterially Inspired Form of Genetic. Late Breaking Papers at the Genetic Programming 1996 Conference (1996)
Wineberg, M., Oppacher, F.: Enhancing GA’s Ability to Cope with Dynamic Environments. In: Proc. of the 2000 Genetic and Evolutionary Comput. Conf. pp. 3-10 (2000)
Yang, S., Comparative, A.: Study of Immune System Based Genetic Algorithms in Dynamic Environments. In: Proc. of the 2006 Genetic and Evolutionary Computation Conference, pp. 1377-1384 (2006)
Yang, S.: Associative Memory Scheme for Genetic Algorithms in Dynamic Environments. In: Basin, D., Rusinowitch, M. (eds.) IJCAR 2004. LNAI (LNCS), vol. 3097, pp. 788–799. Springer, Berlin Heidelberg New York (2004)
Yang, S., Yao, X.: Experimental Study on Population-Based Incremental Learning Algorithms for Dynamic Optimization problems. Soft Computing 11, 815–834 (2005)
Yang, S.: Memory-Based Immigrants for Genetic Algorithms in Dynamic Environments. Proc. of the 2005 Genetic and Evolutionary Computation Conference 2, 1115–1122 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Simões, A., Costa, E. (2007). Variable-Size Memory Evolutionary Algorithm to Deal with Dynamic Environments. In: Giacobini, M. (eds) Applications of Evolutionary Computing. EvoWorkshops 2007. Lecture Notes in Computer Science, vol 4448. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71805-5_68
Download citation
DOI: https://doi.org/10.1007/978-3-540-71805-5_68
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-71804-8
Online ISBN: 978-3-540-71805-5
eBook Packages: Computer ScienceComputer Science (R0)