Parsimony pressure made easy

ABSTRACT

The parsimony pressure method is perhaps the simplest and most frequently used method to control bloat in genetic programming. In this paper we first reconsider the size evolution equation for genetic programming developed in [26] and rewrite it in a form that shows its direct relationship to Price's theorem. We then use this new formulation to derive theoretical results that show how to practically and optimally set the parsimony coefficient dynamically during a run so as to achieve complete control over the growth of the programs in a population. Experimental results confirm the effectiveness of the method, as we are able to tightly control the average program size under a variety of conditions. These include such unusual cases as dynamically varying target sizes such that the mean program size is allowed to grow during some phases of a run, while being forced to shrink in others.

REFERENCES

• 1: L. Altenberg. The Schema Theorem and Price's Theorem. In L. D. Whitley and M. D. Vose, editors, Foundations of Genetic Algorithms 3, Estes Park, Colorado, USA, 31 July-2 Aug. 1994. Morgan Kaufmann. Published 1995.
• 2: P. J. Angeline. An investigation into the sensitivity of genetic programming to the frequency of leaf selection during subtree crossover. In J. R. Koza, et al., editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 21--29, Stanford University, CA, USA, 28-31 July 1996. MIT Press.
• 3: W. Banzhaf , W. B. Langdon, Some Considerations on the Reason for Bloat, Genetic Programming and Evolvable Machines, v.3 n.1, p.81-91, March 2002 [doi>10.1023/A:1014548204452]
• 4: Raphael Crawford-Marks , Lee Spector, Size Control Via Size Fair Genetic Operators In The PushGP Genetic Programming System, Proceedings of the Genetic and Evolutionary Computation Conference, p.733-739, July 09-13, 2002
• 5: Stephen Dignum , Riccardo Poli, Generalisation of the limiting distribution of program sizes in tree-based genetic programming and analysis of its effects on bloat, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277277]
• 6: Anikó Ekárt , S. Z. Németh, Selection Based on the Pareto Nondomination Criterion for Controlling Code Growth in Genetic Programming, Genetic Programming and Evolvable Machines, v.2 n.1, p.61-73, March 2001 [doi>10.1023/A:1010070616149]
• 7: H. Iba. Complexity-based fitness evaluation for variable length representation. Position paper at the Workshop on Evolutionary Computation with Variable Size Representation at ICGA-97, 20 July 1997.
• 8: Hitoshi Iba , Hugo de Garis , Taisuke Sato, Genetic programming using a minimum description length principle, Advances in genetic programming, MIT Press, Cambridge, MA, 1994
• 9: Hitoshi Iba , Taisuke Sato , Hugo de Garis, Temporal Data Processing Using Genetic Programming, Proceedings of the 6th International Conference on Genetic Algorithms, p.279-286, July 15-19, 1995
• 10: K. E. Kinnear, Jr. Evolving a sort: Lessons in genetic programming. In Proceedings of the 1993 International Conference on Neural Networks, volume 2, pages 881--888, San Francisco, USA, 28 Mar.-1 Apr. 1993. IEEE Press.
• 11: K. E. Kinnear, Jr. Fitness landscapes and difficulty in genetic programming. In Proceedings of the 1994 IEEE World Conference on Computational Intelligence, volume 1, pages 142--147, Orlando, Florida, USA, 27-29 June 1994. IEEE Press.
• 12: M. Kotanchek, G. Smits, and E. Vladislavleva. Pursuing the pareto paradigm tournaments, algorithm variations & ordinal optimization. In R. L. Riolo, et al., editors, Genetic Programming Theory and Practice IV, volume 5 of Genetic and Evolutionary Computation, chapter 3. Springer, Ann Arbor, 11-13 May 2006.
• 13: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 14: W. B. Langdon. The evolution of size in variable length representations. In 1998 IEEE International Conference on Evolutionary Computation, pages 633--638, Anchorage, Alaska, USA, 5-9 May 1998. IEEE Press.
• 15: W. B. Langdon, Size Fair and Homologous Tree Crossovers for Tree Genetic Programming, Genetic Programming and Evolvable Machines, v.1 n.1-2, p.95-119, April 2000 [doi>10.1023/A:1010024515191]
• 16: W. B. Langdon and R. Poli. Fitness causes bloat. In P. K. Chawdhry, et al., editors, Soft Computing in Engineering Design and Manufacturing, pages 13--22. Springer-Verlag London, 23-27 June 1997.
• 17: Foundations of genetic programming, Springer-Verlag New York, Inc., New York, NY, 2002
• 18: William B. Langdon , Tery Soule , Riccardo Poli , James A. Foster, The evolution of size and shape, Advances in genetic programming: volume 3, MIT Press, Cambridge, MA, 1999
• 19: S. Luke. Two fast tree-creation algorithms for genetic programming. IEEE Transactions on Evolutionary Computation, 4(3):274--283, Sept. 2000.
• 20: Nicholas Freitag McPhee , Justin Darwin Miller, Accurate Replication in Genetic Programming, Proceedings of the 6th International Conference on Genetic Algorithms, p.303-309, July 15-19, 1995
• 21: Nicholas Freitag McPhee , Riccardo Poli, Using Schema Theory To Explore Interactions Of Multiple Operators, Proceedings of the Genetic and Evolutionary Computation Conference, p.853-860, July 09-13, 2002
• 22: Riccardo Poli, General Schema Theory for Genetic Programming with Subtree-Swapping Crossover, Proceedings of the 4th European Conference on Genetic Programming, p.143-159, April 18-20, 2001
• 23: R. Poli. A simple but theoretically-motivated method to control bloat in genetic programming. In C. Ryan, et al., editors, Genetic Programming, Proceedings of the 6th European Conference, EuroGP 2003, LNCS, pages 211--223, Essex, UK, 14-16 Apr. 2003. Springer-Verlag.
• 24: R. Poli, W. B. Langdon, and S. Dignum. On the limiting distribution of program sizes in tree--based genetic programming. In M. Ebner, et al., editors, Proceedings of the 10th European Conference on Genetic Programming, volume 4445 of LNCS, pages 193--204, Valencia, Spain, 11 - 13 Apr. 2007. Springer.
• 25: R. Poli, W. B. Langdon, and N. F. McPhee. A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk, 2008. (With contributions by J. R. Koza).
• 26: Riccardo Poli , Nicholas Freitag McPhee, General schema theory for genetic programming with subtree-swapping crossover: Part II, Evolutionary Computation, v.11 n.2, p.169-206, Summer 2003 [doi>10.1162/106365603766646825]
• 27: G. R. Price. Selection and covariance. Nature, 227, August 1:520--521, 1970.
• 28: J. Rosca. Generality versus size in genetic programming. In J. R. Koza, et al., editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 381--387, Stanford University, CA, USA, 28-31 July 1996. MIT Press.
• 29: J. Rosca. A probabilistic model of size drift. In R. L. Riolo and B. Worzel, editors, Genetic Programming Theory and Practice, chapter 8, pages 119--136. Kluwer, 2003.
• 30: J. P. Rosca. Analysis of complexity drift in genetic programming. In J. R. Koza, et al., editors, Genetic Programming 1997: Proceedings of the Second Annual Conference, pages 286--294, Stanford University, CA, USA, 13-16 July 1997. Morgan Kaufmann.
• 31: J. P. Rosca and D. H. Ballard. Complexity drift in evolutionary computation with tree representations. Technical Report NRL5, University of Rochester, Computer Science Department, Rochester, NY, USA, Dec. 1996.
• 32: Justinia P. Rosca , Dana H. Ballard, Rooted-tree schemata in genetic programming, Advances in genetic programming: volume 3, MIT Press, Cambridge, MA, 1999
• 33: Terence Soule , James A. Foster, Effects of code growth and parsimony pressure on populations in genetic programming, Evolutionary Computation, v.6 n.4, p.293-309, Winter 1998 [doi>10.1162/evco.1998.6.4.293]
• 34: T. Soule and J. A. Foster. Removal bias: a new cause of code growth in tree based evolutionary programming. In 1998 IEEE International Conference on Evolutionary Computation, pages 781--186, Anchorage, Alaska, USA, 5-9 May 1998. IEEE Press.
• 35: Byoung-Tak Zhang , Heinz Mühlenbein, Balancing accuracy and parsimony in genetic programming, Evolutionary Computation, v.3 n.1, p.17-38, Spring 1995 [doi>10.1162/evco.1995.3.1.17]

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
bloat, genetic programming, parsimony pressure