Program optimization by random tree sampling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Program optimization by random tree sampling

Full text

Pdf (727 KB)

Source

Genetic And Evolutionary Computation Conference archive
Proceedings of the 11th Annual conference on Genetic and evolutionary computation table of contents

Montreal, Québec, Canada

SESSION: Track 10: genetic programming table of contents

Pages 1131-1138

Year of Publication: 2009

ISBN:978-1-60558-325-9

Authors

Makoto Tanji	University of Tokyo, Tokyo, Japan
Hitoshi Iba	University of Tokyo, Tokyo, Japan

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 28, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1569901.1570053 What is a DOI?

ABSTRACT

This paper describes a new program evolution method named PORTS (Program Optimization by Random Tree Sampling) which is motivated by the idea of preservation and control of tree fragments. We hypothesize that to reconstruct building blocks efficiently, tree fragments of any size should be preserved into the next generation, according to their differential fitnesses. PORTS creates a new individual by sampling from the promising trees by traversing and transition between trees instead of subtree crossover and mutation. Because the size of a fragment preserved during a generation update follows a geometric distribution, merits of the method are that it is relatively easy to predict the behavior of tree fragments over time and to control sampling size, by changing a single parameter. Our experimental results on three benchmark problems show that the performance of PORTS is competitive with SGP (Simple Genetic Programming). And we observed that there is a significant difference of fragment distribution between PORTS and simple GP.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Lawrence Beadle and Colin G. Johnson. Semantically driven crossover in genetic programming. In 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), 2008.
	2	Jason M. Daida , Robert R. Bertram , Stephen A. Stanhope , Jonathan C. Khoo , Shahbaz A. Chaudhary , Omer A. Chaudhri , John A. Ii Polito, What Makes a Problem GP-Hard? Analysis of a Tunably Difficult Problem in Genetic Programming, Genetic Programming and Evolvable Machines, v.2 n.2, p.165-191, June 2001 [doi>10.1023/A:1011504414730]
	3	Steven Gustafson, Edmund K. Burke, and Graham Kendall. Genetic Programming, chapter Sampling of Unique Structures and Behaviours in Genetic Programming, pages 279--288. Springer Berlin / Heidelberg, 2004.
	4	Tuan-Hao Hoang , Nguyen Xuan Hoai , Nguyen Thi Hien , RI McKay , Daryl Essam, ORDERTREE: a new test problem for genetic programming, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144141]
	5	Kim Harries and Peter Smith. Exploring alternative operators and search strategies in genetic programming. In Genetic Programming 1997: Proceedings of the Second Annual Conference, 1997.
	6	John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
	7	John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
	8	Moshe Looks, On the behavioral diversity of random programs, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277283]
	9	Hammad Majeed , Conor Ryan, Using context-aware crossover to improve the performance of GP, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144146]
	10	M. Mitchell, S. Forrest, and J.H. Holland. The royal road for genetic algorithms: Fitness landscapes and ga performance. In Towards a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life, 1992.
	11	Una-May O'Reilly , Franz Oppacher, Program Search with a Hierarchical Variable Lenght Representation: Genetic Programming, Simulated Annealing and Hill Climbing, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.397-406, October 09-14, 1994
	12	Riccardo Poli , Nicholas Freitag McPhee , Leonardo Vanneschi, The impact of population size on code growth in GP: analysis and empirical validation, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389341]
	13	Bill Punch , Doug Zongker , Erik Goodman, The royal tree problem, a benchmark for single and multiple population genetic programming, Advances in genetic programming: volume 2, MIT Press, Cambridge, MA, 1996
	14	Y. Shan, R.I. McKay, and et al. R. Baxter. Grammar model-based program evolution. In Proceedings of The Congress on Evolutionary Computation, 2004.
	15	Terence Soule , Robert B. Heckendorn, An Analysis of the Causes of Code Growth in Genetic Programming, Genetic Programming and Evolvable Machines, v.3 n.3, p.283-309, September 2002 [doi>10.1023/A:1020115409250]
	16	Hasegawa Yoshihiko and Hitoshi Iba. A bayesian network apporach to program generation. IEEE Transaction on Evolutionary Computation, 12, No. 6:750 to 764, 2008.