A self-organized criticality mutation operator for dynamic optimization problems

• DOI: 10.1145/1389095.1389275
• Publication Date: 2008-07-22T13:46:39Z
• Authors: Carlos M. Fernandes; J. J. Merelo; Vitorino Ramos; Agostinho C. Rosa
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

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.