Empirical analysis of ideal recombination on random decomposable problems

ABSTRACT

This paper analyzes the behavior of a selectorecombinative genetic algorithm (GA) with an ideal crossover on a class of random additively decomposable problems (rADPs). Specifically, additively decomposable problems of order k whose subsolution fitnesses are sampled from the standard uniform distribution U[0,1] are analyzed. The scalability of the selectorecombinative GA is investigated for 10,000 rADP instances. The validity of facetwise models in bounding the population size, run duration, and the number of function evaluations required to successfully solve the problems is also verified. Finally, rADP instances that are easiest and most difficult are also investigated.

REFERENCES

• 1: David H. Ackley, A connectionist machine for genetic hillclimbing, Kluwer Academic Publishers, Norwell, MA, 1987
• 2: H. Asoh and H. Mühlenbein. On the mean convergence time of evolutionary algorithms without selection and mutation. Parallel Problem Solving from Nature, 3:98--107, 1994.
• 3: Thomas Bäck, Generalized Convergence Models for Tournament- and (mu, lambda)-Selection, Proceedings of the 6th International Conference on Genetic Algorithms, p.2-8, July 15-19, 1995
• 4: N. Balakrishnan and W. W. S. Chen. Handbook of tables for order statistics from lognormal distributions with applications. Kluwer Academic Publishers, Amsterdam, Netherlands, 1999.
• 5: N. Balakrishnan and A. C. Cohen. Order statistics and inference. Academic Press, New York, NY, 1991.
• 6: N. Balakrishnan and C. R. Rao, editors. Order statistics: Applications . Elsevier, Amsterdam, Netherlands, 1999.
• 7: N. Balakrishnan and C. R. Rao, editors. Order statistics: Theory and methods . Elsevier, Amsterdam, Netherlands, 1999.
• 8: Albert Donally Bethke, Genetic algorithms as function optimizers, University of Michigan, Ann Arbor, MI, 1980
• 9: M. G. Bulmer. The Mathematical Theory of Quantitative Genetics. Oxford University Press, Oxford, 1985.
• 10: K. Deb and D. E. Goldberg. Analyzing deception in trap functions. Foundations of Genetic Algorithms, 2:93--108, 1992. (Also IlliGAL Report No. 91009).
• 11: W. Feller. An Introduction to Probability Theory and its Applications. Wiley, New York, NY, 1970.
• 12: D. E. Goldberg. Simple genetic algorithms and the minimal deceptive problem. In L. Davis, editor, Genetic algorithms and simulated annealing, chapter 6, pages 74--88. Morgan Kaufmann, Los Altos, CA, 1987.
• 13: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 14: D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6:333--362, 1992. (Also IlliGAL Report No. 91010).
• 15: D. E. Goldberg, B. Korb, and K. Deb. Messy genetic algorithms: Motivation, analysis, and first results. Complex Systems, 3(5):493--530, 1989. (Also IlliGAL Report No. 89003).
• 16: David E. Goldberg , Philip Segrest, Finite Markov chain analysis of genetic algorithms, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.1-8, October 1987, Cambridge, Massachusetts, United States
• 17: G. Harik, E. Cantú-Paz, D. E. Goldberg, and B. L. Miller. The gambler's ruin problem, genetic algorithms, and the sizing of populations. Evolutionary Computation, 7(3):231--253, 1999. (Also IlliGAL Report No. 96004).
• 18: R. V. Hogg and A. T. Craig. Introduction to Mathematical Statistics . Macmillan, New York, NY, 5th edition, 1995.
• 19: M. Kimura. Diffusion models in population genetics. Journal of Applied Probability, 1:177--232, 1964.
• 20: G. E. Liepins and M. D. Vose. Representational issues in genetic optimization. Journal of Experimental and Theoretical Artificial Intelligence, 2:101--115, 1990.
• 21: B. L. Miller and D. E. Goldberg. Genetic algorithms, tournament selection, and the effects of noise. Complex Systems, 9(3):193--212, 1995. (Also IlliGAL Report No. 95006).
• 22: Heinz Mühlenbein , Dirk Schlierkamp-Voosen, Predictive models for the breeder genetic algorithm, I.: continuous parameter optimization, Evolutionary Computation, v.1 n.1, p.25-49, Spring 1993
• 23: M. Pelikan, K. Sastry, M. V. Butz, and D. E. Goldberg. Hierarchical BOA on random decomposable problems. IlliGAL Report No. 2006002, University of Illinois at Urbana Champaign, Urbana, IL, January 2006.
• 24: K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master's thesis, University of Illinois at Urbana-Champaign, Urbana, IL, 2001. (Also IlliGAL Report No. 2002004).
• 25: K. Sastry and D. E. Goldberg. Modeling tournament selection with replacement using apparent added noise. Intelligent Engineering Systems Through ArtificialNeuralNetworks, 11:129--134, 2001. (Also IlliGAL Report No. 2001014).
• 26: K. Sastry and D. E. Goldberg. Let's get ready to rumble: Crossover versus mutation head to head. Proceedings of the 2004 Genetic and Evolutionary Computation Conference, 2:126--137, 2004. Also IlliGAL Report No. 2004005.
• 27: K. Sastry, M. Pelikan, and D. E. Goldberg. Analysis of ideal recombination on random decomposable problems. IlliGAL Report No. 2006016, University of Illinois at Urbana-Champaign, Urbana, IL, April 2006.
• 28: D. Thierens and D. E. Goldberg. Convergence models of genetic algorithm selection schemes. Parallel Problem Solving from Nature, 3:116--121, 1994.
• 29: L. D. Whitley. Fundamental principles of deception in genetic search. Foundations of Genetic Algorithms, pages 221--241, 1991.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Experimentation, Performance

Keywords:
additively-decomposable problems, building blocks, convergence time, empirical analysis, genetic algorithms, ideal crossover, population sizing, problem difficulty, scalability analysis, test problems