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

ABSTRACT

Hereditary Repulsion (HR) is a selection method coupled with a fitness constraint that substantially improves the performance and consistency of evolutionary algorithms. This also manifests as improved generalisation in the evolved GP expressions. We examine the behaviour of HR on the difficult Parity 5 problem using a population size of only 24 individuals. The negative effects of convergence are amplified under these circumstances and we progress through a series of insights and experiments which dramatically improve the consistency of the algorithm, resulting in a 70% success rate with the same small population. By contrast, a steady state GP system using a population of 5000 only had a success rate of 8%. We then confirm the effectiveness of these results in a number of arbitrary problem domains.

REFERENCES

• 1: D. Eby, R. C. Averill, B. Gelfand, W. F. Punch, O. M. III, and E. D. Goodman. An injection island ga for flywheel design optimization. In 5th European Congress on Intelligent Techniques and Soft Computing, volume 3, 1997.
• 2: G. S. Hornby. Alps: the age-layered population structure for reducing the problem of premature convergence. In Gecco 2005, 2005.
• 3: N. McPhee and N. Hopper. Analysis of genetic diversity through population history. In Gecco, pages 1112--1120, 1999.
• 4: G. Murphy and C. Ryan. Manipulation of convergence in evolutionary systems. In Genetic Programming Theory and Practise. Springer US, 2007.
• 5: G. Murphy and C. Ryan. A simple powerful constraint for genetic programming. In EuroGP, 2008.
• 6: F. A. Naoyuki Kubota, Toshio Fukuda and K. Shimojima. Genetic algorithm with age structure and its application to self organising manufacturing system. In IEEE Symposium on Emerging Technologies and Factory Automation, 1994.
• 7: B. Sareni and L. Krahenbuhl. Fitness sharing and niching methods revisited. In IEEE Transactions on Evolutionary Computation, volume 2. IEEE Computational Intelligence Society, 1998.
• 8: D. J. Siddique, M. X.-Y. Lin, R. M., and C. J. Automated detection of nodules in the ct lung images using multi-modal genetic algorithm. In IEEE Transactions on Evolutionary Computation, volume 1. IEEE Computational Intelligence Society, 2003.
• 9: M. J. Streeter. The root causes of code growth in genetic programming. In EuroGP, 2003.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms, Theory

Keywords:
bloat control, genetic programming