A Fractal Representation for Real Optimization

Daniel Ashlock and Justin Schonfeld
Accepted to the 2007 Congress on Evolutionary Computation

Abstract PDF eprint

The chaos game, in which a moving point is repeatedly averaged toward randomly selected vertices of a triangle, is one method of generating the fractal called the Sierpinski triangle. The sequence of vertices, called generators, used to reach a given point of the Sierpinski triangle yields a map from strings over a three-character alphabet to points in the plane. This study generalizes that representation to give a character-string representation for points in Rn . This is a novel representation for evolutionary optimization. With the correct generating points the method is proven to search its entire target domain at an easily controlled resolution. The representation can be used to achieve the same goals as niche specialization at a far lower computational cost because the optima located are specified by strings which can be stored and searched in standard string dictionaries. An implementation of the algorithm called the multiple optima Sierpinski searcher(MOSS) is found to be substantially faster at locating diverse collections of optima than a standard optimizer. The Sierpinski representation has a number of natural mathematical properties that are described in the paper. These include the ability to adapt both it search domain and its resolution on the fly during optimization.