Carlos M. Fernandes
ABSTRACT
This paper investigates a new method for Genetic Algorithms' mutation rate control, based on the Sandpile Model: Sandpile Mutation. The Sandpile is a complex system operating at a critical state between chaos and order. This state is known as Self-Organized Criticality (SOC) and is characterized by displaying scale invariant behavior. In the precise case of the Sandpile Model, by randomly and continuously dropping "sand grains" on top of a two dimensional grid lattice, a power-law relationship between the frequency and size of sand "avalanches" is observed. Unlike previous off-line approaches, the Sandpile Mutation dynamics adapts during the run of the algorithm in a self-organized manner constrained by the fitness values progression. This way, the mutation intensity not only changes along the search process, but also depends on the convergence stage of the algorithm, thus increasing its adaptability to the problem context. The resulting system evolves a wide range of mutation rates during search, with large avalanches appearing occasionally. This particular behavior appears to be well suited for function optimization in dynamic environments, where large amounts of genetic novelty are regularly needed in order to track the moving extrema. Experimental results confirm these assumptions.
- Abbass, H. A., Sastry K., and Goldberg, D. E. 2004. Oiling the wheels of change: The role of adaptive automatic problem decomposition in non-stationary environments. Technical Report 2004029, Illigal, University of Illinois at Urbana-Champaign, IL, USA]]Google Scholar
- Angeline, P. 1997. Tracking Extrema in Dynamic Environments. Proceedings of the 6th International Conf. on Evolutionary Programming, Springer, 335--345.]] Google ScholarDigital Library
- Back, T. 1996.Evolutionary Algorithms in Theory and Practice. Oxford University Press.]] Google ScholarDigital Library
- Bak, P., Tang, C., K. Wiesenfeld, K. 1987. Self-organized criticality: an explanation of 1/f noise. Physical Review of Letters, 381--384.]]Google Scholar
- Bak, P., Sneppen. K. 1993. Punctuated equilibrium and criticality in a simple model of evolution. Physical Review of Letters 71, 4083--4086.]]Google ScholarCross Ref
- 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.]] Google ScholarDigital Library
- Boettcher, S., Percus A.G. 2003. Optimization with extremal dynamics. Complexity 8(2), 57--62.]] Google ScholarDigital Library
- Bonabeau, E., Dorigo, M., Threraulaz, G. 1999. Swarm intelligence: from natural to artificial systems. Oxford University Press]] Google ScholarDigital Library
- Branke, J. 1999. Memory enhanced evolutionary algorithms for changing optimization problems. Proceedings of the 1999 Congress on Evolutionary Computation, 1875--1882]]Google ScholarCross Ref
- Branke, J., Schmeck, H. 2002. Designing evolutionary algorithms for dynamic optimization problems. Theory and Application of Evolutionary Computation: Recent Trends, 239--262]] Google ScholarDigital Library
- Cedeno, W., Vemuri. V.R. 1997. On the use of niching for dynamic landscapes. Proceedings of the 1997 Conference on Evolutionary Computation, IEEE, 361--367]]Google ScholarCross Ref
- Cobb H.G. 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, USA]]Google Scholar
- Colorni, A., Dorigo M., and Maniezzo, V. 1992. Distributed Optimization by Ant Colonies. Proceedings of the 1st European Conference on Artificial Life, MIT Press, 134--142]]Google Scholar
- Eiben, A.E., Hinterding R., Michalewicz Z. 1999. Parameter Control in Evolutionary. IEEE Transaction on Evolutionary Computation 3(2), 124--141]] Google ScholarDigital Library
- Fernandes, C., Rosa A.C., and Ramos V. 2007. Binary Ant Algorithm. Proceedings of the 2007 Genetic and Evolutionary Computation Conference, ACM, 41--48]] Google ScholarDigital Library
- Goldberg, D.E, Deb, K., Horn, J. 1992. Massively multimodality, deception and genetic algorithms. Parallel Problem Solving from Nature II, North-Holland, 37--46]]Google Scholar
- Goldberg, D.E., Smith, R.E. 1987. Nonstationary function optimization using genetic algorithms with dominance and diploidy. Proceedings of the 2nd International Conference on Genetic Algorithms, ACM, 59--68]] Google ScholarDigital Library
- Grefenstette, J.J. 1992. Genetic algorithms for changing environments. Parallel Problem Solving from Nature II. North-Holland, 137--144,]]Google Scholar
- Guntsch, M., Middendorf, M. 2002. Applying population based ACO to dynamic optimization problems. Proceedings of 3rd International Workshop ANTS 2002, LNCS 2463, 111--122]] Google ScholarDigital Library
- Harik, G. R. 1999. Linkage learning via probabilistic modeling in the ECGA. IlliGAL Report No. 99010, Illigal, University of Illinois at Urbana-Champaign, IL, USA]]Google Scholar
- Huang, C., Kaur, J., Maguitman, A., and Rocha, L. 2007 Agent-based model of genotype editing. Evolutionary Computation 15(3), 253--289.]] Google ScholarDigital Library
- Krink, T., Rickers P., René T. 2000. Applying self-organised criticality to evolutionary algorithms. Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, 375--384]] Google ScholarDigital Library
- Krink, T., Thomsen, R. 2001. Self-Organized Criticality and Mass Extinction in Evolutionary Algorithms. Proceedings of the 2001 Congress on Evolutionary Computation, vol.2, 1155--1161]]Google ScholarCross Ref
- Lorrañga, P., Lozano J.A. 2002. Estimation of distribution algorithms: A new tool for evolutionary computation. Boston: Kluwer Academic Publishers, Boston]]Google Scholar
- Mitchell, M. 1991. When will a GA outperform Hilclimbing? Advances in Neural Information Processing Systems 6, 51--58]]Google Scholar
- Muehlenbein, H. 1998. The equation for response to selection and its use for prediction. Evolutionary Computation 5(3), 303--346]] Google ScholarDigital Library
- Ochoa, G., Madler-Kron C., Rodriguez R., Jaffe K. 2005. Assortative mating in genetic algorithms for dynamic problems. Proceedings of the 2005 EvoWorkshops, 617--622]] Google ScholarDigital Library
- Pelikan, M., Goldberg D., Lobo F. 1999. A Survey of Optimization by Building and Using Probabilistic Models, Computational Optimization and Applications 21(1), 5--20]] Google ScholarDigital Library
- Ramos, V., Fernandes C., and Rosa A.C. 2005. On self-regulated swarms, societal memory, speed and dynamics, Proceedings of ALifeX, MIT Press, 393--399]]Google Scholar
- Tinós, R. and Yang, S. 2007. A self-organizing random immigrants genetic algorithm for dynamic optimization problems. Genetic Programming and Evolvable Machines 8, 255--286]] Google ScholarDigital Library
- Yang, S. 2005. Memory-enhanced univariate marginal distribution algorithms. Proceedings of the 2005 Congress on Evolutionary Computation, 2560--2567]]Google Scholar
- Yang, S. and Yao, X. 2005. Experimental study on population-based incremental learning algorithms for dynamic optimization problems. Soft Computing 9(11), 815--834]] Google ScholarDigital Library
Index Terms
- A self-organized criticality mutation operator for dynamic optimization problems
Recommendations
A self-organizing random immigrants genetic algorithm for dynamic optimization problems
In this paper a genetic algorithm is proposed where the worst individual and individuals with indices close to its index are replaced in every generation by randomly generated individuals for dynamic optimization problems. In the proposed genetic ...
Genetic algorithm with adaptive elitism-based immigrants for dynamic optimization problems
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computationWe propose a genetic algorithm with adaptive elitism-based immigrants which tunes the balance between elitism-based immigrants and random immigrants by itself. Experimental results show that our genetic algorithm with adaptive elitism-based immigrants ...
The sandpile mutation Genetic Algorithm: an investigation on the working mechanisms of a diversity-oriented and self-organized mutation operator for non-stationary functions
This paper reports the investigation on the sandpile mutation, an unconventional mutation control scheme for binary Genetic Algorithms (GA) inspired by the Self-Organized Criticality (SOC) theory. The operator, which is based on a SOC system known as ...
Comments