Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Using a dynamic systems model for the Simple Genetic Algorithm due to Vose[1], we analyze the fixed point behavior of the model without crossover applied to functions of unitation. Unitation functions are simplified fitness functions that reduce the search space into a smaller number of equivalence classes. This reduction allows easier computation of fixed points. We also create a dynamic systems model from a simple nondecreasing EA like the (1+1) EA and variants, then analyze this models on unitation classes.

REFERENCES

• 1: Michael D. Vose, The Simple Genetic Algorithm: Foundations and Theory, MIT Press, Cambridge, MA, 1998
• 2: Strogatz, S.H., Nonlinear Dynamics and Chaos. Addison-Wesley, Reading, MA,1994
• 3: J. E. Rowe, The dynamical systems model of the simple genetic algorithm, Theoretical aspects of evolutionary computing, Springer-Verlag, London, 2001
• 4: Rowe, J.: Population fixed-points for functions of unitation. In Foundations of Genetic Algorithms. Vol. 5. Colin Reeves, and Wolfgang Banzhaf (eds.). Morgan Kaufmann, (1998) 69--84.
• 5: Wright A.H., Rowe J.E., Neil, J.R.: Analysis of the Simple Genetic Algorithm on the Single-peak and Double-peak Landscapes, Proc. of the 2002 Congress on Evolutionary Computation, Fogel et al. Editors, IEEE Press (1999), 214--219.
• 6: Deb, K., Goldberg, D.E.: Analyzing Deception in Trap Functions. In Foundations of Genetic Algorithms, Vol. 2. D Whitley, editor. Morgan Kaufmann, (1992): 93--108.
• 7: Brin, M., Stuck, G., Introduction to Dynamical Systems. Cambridge University Press, New York (2002).
• 8: Rudolph, G, Convergence Properties of Evolutionary Algorithms. Verlag Kovac, Hamburg, (1997)
• 9: Droste, S., Jansen, T., Wegener, I., Dynamic parameter control in simple evolutionary algorithms, Foundations of Genetic Algorithms, Vol. 6, Worthy Martin and William Spears (eds.) Morgan Kaufmann (2001), pp. 275--294.
• 10: Metropolis, A.W. Rosenbluth, M.N. Rosenbluth. A.H. Teller and E. Teller, "Equation of State Calculations by Fast Computing Machines," J. Chem. Phys. 21 (1953) 1087--1092.
• 11: Mühlenbein, How genetic algorithms really work. I. Mutation and hillclimbing, Proc. PPSN II (Parallel Problem Solving from Nature), (1992), pp. 15--25.
• 12: H. M. Taylor and S. Karlin. An Introduction to Stochastic Modeling, 3th Ed. Academic Press, 1998.
• 13: Kirkpatrick, S., CD Gelatt Jr., MP Vecchi, "Optimization by Simulated Annealing",Science, 220, 4598, 671--680, 1983
• 14: Thomas Bäck, Optimal Mutation Rates in Genetic Search, Proceedings of the 5th International Conference on Genetic Algorithms, p.2-8, June 01, 1993

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
artificial intelligence, fixed points, genetic algorithms, infinite population models, theory of evolutionary algorithms, unitation functions