Home

Fractals and Evolutionary Algorithms

First interactions between Evolutionary Algorithms and Fractals were for the resolution of some difficult optimisation problems encountered in Fractal Analysis: Among them the famous inverse problem for Iterated Function Systems, which is a challenging problem in image and signal compression [3,4,7,17,21,24]. However Fractal analysis provides a theoretical tool that help to understand some aspects of EA behaviour [13,14,16,18,23].

As usual in such domains there are two main approaches to understand the complex dynamic behaviour of these algorithms:

• To make as few as possible hypotheses on the functions to be optimised in order to obtain some global (simple) results. Markov models, [2,5,10,20], Schema theory [8,9,11,12] belong to this item.

• To obtain some more precise results by setting restrictive hypotheses on the fitness function : NK Landscapes [19], Evolutionary Strategies on sphere models [1], for example.

If we investigate how fractal irregularity analysis can be used to refine some theoretical analysis of EA, in the framework of this second item, i.e. when some assumptions on the irregularity of the fitness function are made:

• Some results [16] relate the irregularity of the fitness function to its ``difficulty'' (according to the usual intuition of EA practitioner), and provide information about how to modify some of the GA parameters in order to improve its performances. An important application of such a theoretical analysis provides a mean of measuring (of course to a certain extent, due to the intrinsic limitations of the model) the influence of the chromosome encoding. Some experimentations with the Gray encoding have also been performed [15].

• Then in [14] a preliminary analysis has been developed, derived from Freidlin-Wentzell theory, related to the convergence of a simple EA model. This opens the way to convergence speed bounds with respect to some statistical measures on the fitness function (likely related to irregularity).

Fractal irregularity analysis has been proven useful in various domains (physics, finance, image and signal analysis, see [6,22]). It is now clear that it has open the way to new theoretical investigations for the analysis of EA behaviour. This allow us to suggest that irregularity analysis may be a tool of interest for the theoretical investigation of other stochastic optimisation heuristics.

See also the C code for the fractal test functions

References

1. D. V. Arnold and H.-G. Beyer. Efficiency and mutation strength adaptation of the (mu,lambda,1)-es in a noisy environment. In Günter Rudolph Xin Yao Evelyne Lutton Juan Julian Merelo Hans-Paul Schwefel Marc Schoenauer, Kalyanmoy Deb, editor, Parallel Problem Solving from Nature - PPSN VI 6th International Conference, Paris, France, September 16-20 2000. Springer Verlag. LNCS 1917.

2. R. Cerf. Artificial Evolution, European Conference, AE 95, Brest, France, September 1995, Selected papers, volume Lecture Notes in Computer Science 1063, chapter Asymptotic convergence of genetic algorithms, pages 37-54. Springer Verlag, 1995.

3. Pierre Collet, Evelyne Lutton, Frédéric Raynal, and Marc Schoenauer. Individual gp: an alternative viewpoint for the resolution of complex problems. In GECCO99, Genetic and Evolutionary Computation Conference, July 13 - 17, 1999, Orlando, Florida, USA., 1999.

4. K. Daoudi, E. Lutton, and J. Lévy Véhel. Fractal modeling of speech signals. In Fractals in Engineering, 1994. 1-4 June, Montreal.

5. Thomas E. Davis and Jose C. Principe. A Simulated Annealing Like Convergence Theory for the Simple Genetic Algorithm. In Proceedings of the Fourth International Conference on Genetic Algorithm, pages 174-182, 1991. 13-16 July.

6. Michel Dekking, Jacques Lévy Véhel, Evelyne Lutton, and Claude Tricot (Eds). Fractals : Theory and Applications in Engineering.
Springer Verlag, 1999. ISBN 1-85233-163-1.

7. B. Goertzel. Fractal image compression with the genetic algorithm. Complexity International, 1, 1994.

8. D. E. Goldberg. Genetic Algorithms and Walsh functions : Part I, a gentle introduction. TCGA Report No. 88006, University of Alabama, Tuscaloosa, US, 1988.

9. D. E. Goldberg. Genetic Algorithms and Walsh functions : Part II, deception and its analysis. TCGA Report No. 89001, University of Alabama, Tuscaloosa, US, 1989.

10. D. E. Goldberg and P. Segrest. Finite Markov Chain Analysis of Genetic Algorithms. In Genetic Algorithms and their Applications : Proceedings of the Second International Conference on Genetic Algorithms, pages 1-8, 1987.

11. David A. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company, inc., Reading, MA, January 1989.

12. J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 1975.

13. J. Juliany and M. D. Vose. The genetic algorithm fractal. Evolutionary Computation, 2(2):165-180, 1994.

14. Y. Landrin-Schweitzer and E. Lutton. Perturbation theory for evolutionary algorithms: towards an estimation of convergence speed. In Günter Rudolph Xin Yao Evelyne Lutton Juan Julian Merelo Hans-Paul Schwefel Marc Schoenauer, Kalyanmoy Deb, editor, Parallel Problem Solving from Nature - PPSN VI 6th International Conference, Paris, France, September 16-20 2000. Springer Verlag. LNCS 1917.

15. Benoit Leblanc and Evelyne Lutton. Bitwise regularity coefficients as a tool for deception analysis of a genetic algorithm. Technical Report RR-3274, INRIA research report, 1997. October.

16. E. Lutton and J. Lévy Véehel. Hölder functions and deception of genetic algorithms. IEEE transactions on Evolutionary computation, 2(2):56-72, July 1998.

17. E. Lutton, J. Lévy Véhel, G. Cretin, P. Glevarec, and C. Roll. Mixed ifs: resolution of the inverse problem using genetic programming. Complex Systems, 9:375-398, 1995. (see also Inria Research Report No 2631).

18. Evelyne Lutton. Evolutionary Algorithms in Engineering and Computer Science, chapter Genetic Algorithms and Fractals. John Wiley and Sons, 1999.

19. C. R. Reeves. Experiments with tuneable fitness landscapes. In Günter Rudolph Xin Yao Evelyne Lutton Juan Julian Merelo Hans-Paul Schwefel Marc Schoenauer, Kalyanmoy Deb, editor, Parallel Problem Solving from Nature - PPSN VI 6th International Conference, Paris, France, September 16-20 2000. Springer Verlag. LNCS 1917.

20. G. Rudolph. Asymptotical convergence rates of simple evolutionary algorithms under factorizing mutation distributions. In Artificial Evolution, European Conference, AE 97, Nimes, France, October 1997. Springer Verlag, 1997.

21. L. Vences and I. Rudomin. Fractal compression of single images and image sequences using genetic algorithms, 1994. The Eurographics Association.

22. Jacques Lévy Véhel, Evelyne Lutton, and Claude Tricot (Eds). Fractals in Engineering : From Theory to Industrial Applications. Springer Verlag, 1997. ISBN 3-540-76182-9.

23. M.D. Vose. Formalizing genetic algorithms. In Genetic Algorithms, Neural Networks and Simulated Annealing Applied to Problems in Signal and Image processing. The institute of Electrical and Electronics Engineers Inc., 8th-9th May 1990. Kelvin Conference Centre, University of Glasgow.

24. E. R. Vrscay. Fractal Geometry and Analysis, chapter Iterated function Systems: theory, applications and the inverse problem, pages 405-468. 1991.

See also (in the publications list) :

home