Abstract
This paper describes an alternative mutation control scheme for Genetic Algorithms (GAs) inspired by the Self-Organized Criticality (SOC) theory. The strategy, which mimics a SOC system known as sandpile, is able to generate mutation rates that, unlike those given by other methods of adaptive parameter control, oscillate between very low values and cataclysmic mutations. In order to attain the desired behaviour, the sandpile is not just attached to a GA; it is also modified in an attempt to link its rates to the stage of the search, i.e., the fitness distribution of the population. Due to its characteristics, the sandpile mutation arises as a promising candidate for efficient and yet simple and context-independent approach to dynamic optimization. An experimental study confirms this assumption: a GA with sandpile mutation outperforms a recently proposed SOC-based GA for dynamic optimization. Furthermore, the proposed method does not increase traditional GAs’ parameter set.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bäck, T.: Evolutionary Algorithms in Theory and Practice. Oxford University Press, Oxford (1996)
Bäck, T., Eiben, A.E., van der Vart, N.A.L.: An Empirical Study on GAs ”Without Parameters”. In: Schoenauer, M., et al. (eds.) Proceedings of the 6th International Conference on Parallel Problem Solving from Nature (PPSN VI), pp. 315–324. Springer, London (2000)
Bak, P., Tang, C., Wiesenfeld, K.: Self-organized criticality: an explanation of 1/f noise. Physical Review of Letters 59, 381–384 (1987)
Boettcher, S., Percus, A.G.: Optimization with extremal dynamics. Complexity 8(2), 57–62 (2003)
Branke, J.: Memory enhanced evolutionary algorithms for changing optimization problems. In: Proc. of the 1999 Congress on Evolutionary Computation, pp. 1875–1882. IEEE Press, Los Alamitos (1999)
Branke, J.: Evolutionary optimization in dynamic environments. Kluwer Academic Publishers, Norwell (2002)
Cobb, H.G.: An investigation into the use of hypermutation as an adaptive operator in GAs having continuous, time-dependent nonstationary environments. Tech. Report AIC-90-001, Naval Research Laboratory, Washington, USA (1990)
Eiben, A.E., Hinterding, R., Michalewicz, Z.: Parameter Control in Evolutionary Algorithms. IEEE Trans. on Evolutionary Computation 3(2), 124–141 (1999)
Fernandes, C.M., Merelo, J.J., Ramos, V., Rosa, A.C.: A Self-Organized Criticality Mutation Operator for Dynamic Optimization Problems. In: Proc. of the 2008 Genetic and Evolutionary Computation Conference, pp. 937–944. ACM, New York (2008)
Fernandes, C.M.: Diversity-enhanced GAs for dynamic optimization. Ph.D Thesis, Tech. U. Lisbon (2009), http://geneura.ugr.es/pub/tesis/PhD-CFernandes.pdf
Grefenstette, J.J.: Genetic algorithms for changing environments. In: Parallel Problem Solving from Nature II, pp. 137–144. North-Holland, Amsterdam (1992)
Krink, T., Rickers, P., René, T.: Applying self-organized criticality to Evolutionary Algorithms. In: Deb, K., Rudolph, G., Lutton, E., Merelo, J.J., Schoenauer, M., Schwefel, H.-P., Yao, X. (eds.) PPSN 2000. LNCS, vol. 1917, pp. 375–384. Springer, Heidelberg (2000)
Krink, T., Thomsen, R.: Self-Organized Criticality and mass extinction in Evolutionary Algorithms. In: Proceedings of the 2001 IEEE Congress on Evolutionary Computation (CEC 2001), vol. 2, pp. 1155–1161. IEEE Press, Los Alamitos (2001)
Tinós, R., Yang, S.: A self-organizing RIGA for dynamic optimization problems. Genetic Programming and Evolvable Machines 8, 255–286 (2007)
Yang, S., Yao, X.: Experimental study on PBIL algorithms for dynamic optimization problems. Soft Computing 9(11), 815–834 (2005)
Yang, S.: Genetic Algorithms with Memory- and Elitism-Based Immigrants in Dynamic Environments. Evolutionary Computation 16(3), 385–416 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fernandes, C.M., Laredo, J.L.J., Mora, A.M., Rosa, A.C., Merelo, J.J. (2011). The Sandpile Mutation Operator for Genetic Algorithms. In: Coello, C.A.C. (eds) Learning and Intelligent Optimization. LION 2011. Lecture Notes in Computer Science, vol 6683. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25566-3_43
Download citation
DOI: https://doi.org/10.1007/978-3-642-25566-3_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25565-6
Online ISBN: 978-3-642-25566-3
eBook Packages: Computer ScienceComputer Science (R0)