A self-organized criticality mutation operator for dynamic optimization problems

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.

REFERENCES

• 1: 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
• 2: Peter J. Angeline, Tracking Extrema in Dynamic Environments, Proceedings of the 6th International Conference on Evolutionary Programming VI, p.335-345, April 13-16, 1997
• 3: Thomas Bäck, Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms, Oxford University Press, Oxford, 1996
• 4: Bak, P., Tang, C., K. Wiesenfeld, K. 1987. Self-organized criticality: an explanation of 1/f noise. Physical Review of Letters, 381--384.
• 5: Bak, P., Sneppen. K. 1993. Punctuated equilibrium and criticality in a simple model of evolution. Physical Review of Letters 71, 4083--4086.
• 6: Shummet Baluja, Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Carnegie Mellon University, Pittsburgh, PA, 1994
• 7: Stefan Boettcher , Allon G. Percus, Optimization with extremal dynamics, Complexity, v.8 n.2, p.57-62, November 2002 [doi>10.1002/cplx.10072]
• 8: Eric Bonabeau , Marco Dorigo , Guy Theraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, Inc., New York, NY, 1999
• 9: Branke, J. 1999. Memory enhanced evolutionary algorithms for changing optimization problems. Proceedings of the 1999 Congress on Evolutionary Computation, 1875--1882
• 10: Jürgen Branke , Hartmut Schmeck, Designing evolutionary algorithms for dynamic optimization problems, Advances in evolutionary computing: theory and applications, Springer-Verlag New York, Inc., New York, NY, 2003
• 11: 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
• 12: 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
• 13: 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
• 14: Eiben, A.E., Hinterding R., Michalewicz Z. 1999. Parameter Control in Evolutionary. IEEE Transaction on Evolutionary Computation 3(2), 124--141
• 15: Carlos M. Fernandes , Agostinho C. Rosa , Vitorino Ramos, Binary ant algorithm, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1276965]
• 16: Goldberg, D.E, Deb, K., Horn, J. 1992. Massively multimodality, deception and genetic algorithms. Parallel Problem Solving from Nature II, North-Holland, 37--46
• 17: David E. Goldberg , Robert E. Smith, Nonstationary function optimization using genetic algorithm with dominance and diploidy, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.59-68, October 1987, Cambridge, Massachusetts, United States
• 18: Grefenstette, J.J. 1992. Genetic algorithms for changing environments. Parallel Problem Solving from Nature II. North-Holland, 137--144,
• 19: Michael Guntsch , Martin Middendorf, Applying Population Based ACO to Dynamic Optimization Problems, Proceedings of the Third International Workshop on Ant Algorithms, p.111-122, September 12-14, 2002
• 20: 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
• 21: Chien-feng Huang , Jasleen Kaur , Ana Maguitman , Luis M. Rocha, Agent-Based Model of Genotype Editing, Evolutionary Computation, v.15 n.3, p.253-289, Fall 2007 [doi>10.1162/evco.2007.15.3.253]
• 22: Thiemo Krink , Peter Rickers , René Thomsen, Applying Self-Organised Criticality to Evolutionary Algorithms, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.375-384, September 18-20, 2000
• 23: 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
• 24: Lorrañga, P., Lozano J.A. 2002. Estimation of distribution algorithms: A new tool for evolutionary computation. Boston: Kluwer Academic Publishers, Boston
• 25: Mitchell, M. 1991. When will a GA outperform Hilclimbing? Advances in Neural Information Processing Systems 6, 51--58
• 26: Heinz Mühlenbein, The equation for response to selection and its use for prediction, Evolutionary Computation, v.5 n.3, p.303-346, Fall 1997 [doi>10.1162/evco.1997.5.3.303]
• 27: 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
• 28: Martin Pelikan , David E. Goldberg , Fernando G. Lobo, A Survey of Optimization by Building and Using Probabilistic Models, Computational Optimization and Applications, v.21 n.1, p.5-20, January 2002 [doi>10.1023/A:1013500812258]
• 29: 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
• 30: Renato Tinós , Shengxiang Yang, A self-organizing random immigrants genetic algorithm for dynamic optimization problems, Genetic Programming and Evolvable Machines, v.8 n.3, p.255-286, September 2007 [doi>10.1007/s10710-007-9024-z]
• 31: Yang, S. 2005. Memory-enhanced univariate marginal distribution algorithms. Proceedings of the 2005 Congress on Evolutionary Computation, 2560--2567
• 32: Shengxiang Yang , Xin Yao, Experimental study on population-based incremental learning algorithms for dynamic optimization problems, Soft Computing - A Fusion of Foundations, Methodologies and Applications, v.9 n.11, p.815-834, November 2005 [doi>10.1007/s00500-004-0422-3]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Experimentation

Keywords:
dynamic optimization problems, genetic algorithms, self-organized criticality