Convergence to global optima for genetic programming systems with dynamically scaled operators

ABSTRACT

This work shows asymptotic convergence to global optima for a family of dynamically scaled genetic programming systems where the underlying population consists of a fixed number of creatures (individuals) each of arbitrary size. The genetic programming systems use common mutation and crossover operators as well as fitness-proportional selection. In addition, the mutation and crossover rates are annealed to zero in predefined fashion over the course of the algorithm, and power-law scaling is used for the (possibly population-dependent) initial fitness function with (unbounded) logarithmic growth in the exponent.We assume that a set of globally optimal creatures for the optimization problem instance exists. In addition, it is assumed that the ratio of the best fitness of globally optimal creatures vs the fitness of other creatures is greater or equal a constant ρ>1 in any population they jointly reside in. We discuss how both conditions can usually be satisfied in application settings. Under the above conditions, a selected, traceable sequence of probability distributions over the possible states of the properly scaled genetic programming system converge in time towards the convex set of probability distributions over uniform populations that contain only globally optimal creatures.

REFERENCES

• 1: E. Aarts and P. van Laarhoven. Simulated annealing: An introduction. Statist. Neerlandica, 43:31--52, 1989.
• 2: P. Angeline. Subtree crossover: Building block engine or macromutation. In J. R. Koza, et al, editors, Genetic Programming 97, pages 9--17. Morgan Kaufmann, San Francisco, CA, USA, 1997.
• 3: Thomas Back , David B. Fogel , Zbigniew Michalewicz, Handbook of Evolutionary Computation, IOP Publishing Ltd., Bristol, UK, 1997
• 4: Wolfgang Banzhaf , Frank D. Francone , Robert E. Keller , Peter Nordin, Genetic programming: an introduction: on the automatic evolution of computer programs and its applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 5: S. Droste. Genetic programming with guaranteed quality. In J. R. Koza et al, editors, Genetic Programming 98, pages 54--59. Morgan Kaufmann, San Francisco, CA, USA, 1998.
• 6: David B. Fogel, Evolutionary computation: toward a new philosophy of machine intelligence, IEEE Press, Piscataway, NJ, 1995
• 7: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 8: D. L. Isaacson and R. W. Madsen. Markov Chains: Theory and Applications. Prentice-Hall, Upper Saddle River, NJ, USA, 1961.
• 9: J. R. Koza. Genetic Programming. MIT Press, Cambridge, MA, USA, 1992.
• 10: S. Lang. Analysis I. Addison-Wesley, Boston, MA, USA, 1969.
• 11: Foundations of genetic programming, Springer-Verlag New York, Inc., New York, NY, 2002
• 12: Sean Luke , Liviu Panait, Lexicographic Parsimony Pressure, Proceedings of the Genetic and Evolutionary Computation Conference, p.829-836, July 09-13, 2002
• 13: S. Luke and L. Spector. A revised comparison of crossover and mutation in genetic programming. In J. R. KozaetAl, editors, Genetic Programming 98, pages 208--213. Morgan Kaufmann, San Francisco, CA, USA, 1998.
• 14: R. Poli. Recursive conditional schema theorem, convergence and population sizing in genetic algorithms. In W. N. Martin and W. M. Spears, editors, Foundations of Genetic Algorithms 6, pages 143--163. Morgan Kaufmann, San Francisco, CA, USA, 2000.
• 15: J. E. Rowe and N. F. McPhee. The effects of crossover and mutation operators on variable length linear structures. In L. Spector, et al, editors, Genetic and Evolutionary Computation Conference, pages 535--542. Morgan Kaufmann, San Francisco, CA, USA, 2001.
• 16: W. Rudin. Functional Analysis. McGraw-Hill, New York, NY, USA, 1973.
• 17: H. H. Schaefer. Topological Vector Spaces. Springer, Berlin, Germany, 1970.
• 18: Theory of genetic algorithms, Theoretical Computer Science, v.259 n.1-2, p.1-61, May 28, 2001 [doi>10.1016/S0304-3975(00)00406-0 ]
• 19: L. M. Schmitt. Asymptotic convergence of scaled genetic algorithms to global optima - a gentle introduction to the theory. In A. Menon, editor, Frontiers of Evolutionary Computation, pages 157--192. Kluwer, Dordrecht, The Netherlands, 2004.
• 20: Lothar M. Schmitt, Theory of genetic algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling, Theoretical Computer Science, v.310 n.1-3, p.181-231, 01 January 2004 [doi>10.1016/S0304-3975(03)00393-1]
• 21: L. M. Schmitt. Classification with scaled genetic algorithms in a coevolutionary setting. In R. PolietAl, editors, Genetic and Evolutionary Computation Conference, pages 138--149. Springer, Berlin, Germany, 2004. LNCS 3103.
• 22: Hans-Paul Paul Schwefel, Evolution and Optimum Seeking: The Sixth Generation, John Wiley & Sons, Inc., New York, NY, 1993
• 23: D. H. Wolpert and W. G. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):67--82, 1997.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

General Terms:
Algorithms

Keywords:
convergence to global optima, genetic programming