Estimating the distribution and propagation of genetic programming building blocks through tree compression

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Estimating the distribution and propagation of genetic programming building blocks through tree compression

Full text

Pdf (441 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 1011-1018

Year of Publication: 2009

ISBN:978-1-60558-325-9

Authors

Robert I. McKay	Seoul National University, Seoul, South Korea
Xuan Hoai Nguyen	Seoul National University, Seoul, South Korea
James R. Cheney	University of Edinburgh, Edinburgh, United Kingdom
MinHyeok Kim	Seoul National University, Seoul, South Korea
Naoki Mori	Osaka Prefecture University, Osaka, Japan
Tuan Hao Hoang	University of New South Wales (ADFA), Canberra, Australia

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): 3, Downloads (12 Months): 20, 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.1570038 What is a DOI?

ABSTRACT

Shin et al [19] and McKay et al [15] previously applied tree compression and semantics-based simplification to study the distribution of building blocks in evolving Genetic Programming populations. However their method could only give static estimates of the degree of repetition of building blocks in one generation at a time, supplying no information about the flow of building blocks between generations. Here, we use a state-of-the-art tree compression algorithm, xmlppm, to estimate the extent to which frequent building blocks from one generation are still in use in a later generation.

While they compared the behaviour of different GP algorithms on one specific problem -- a simple symbolic regression problem -- we extend the analysis to a more complex problem, a symbolic regression problem to find a Fourier approximation to a sawtooth wave, and to a Boolean domain, odd parity.

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	James Cheney, Compressing XML with Multiplexed Hierarchical PPM Models, Proceedings of the Data Compression Conference, p.163, March 27-29, 2001
	2	J. Cleary and I. Witten. Data compression using adaptive coding and partial string matching. IEEE Transactions on Communications, 32:396--402, 1984.
	3	Nichael Lynn Cramer, A Representation for the Adaptive Generation of Simple Sequential Programs, Proceedings of the 1st International Conference on Genetic Algorithms, p.183-187, July 01, 1985
	4	C. Ferreira. Gene expression programming and the automatic evolution of computer programs. In L. N. de Castro and F. J. Von Zuben, editors, Recent Developments in Biologically Inspired Computing, chapter 6, pages 82--103. Idea Group Publishing, 2004.
	5	N. X. Hoai, R. I. B. McKay, and D. Essam. Representation and structural difficulty in genetic programming. IEEE Transactions on Evolutionary Computation, 10(2):157--166, Apr. 2006.
	6	T.-H. Hoang, D. Essam, R. I. B. McKay, and X. H. Nguyen. Building on success in genetic programming: Adaptive variation and developmental evaluation. In L. Kang, Y. Liu, and S. Zeng, editors, Advances in Computation and Intelligence: Proceedings of the 2007 International Symposium on Intelligent Computation and Applications (ISICA), volume 4683 of Lecture Note in Computer Science, pages 137--146. Springer-Verlag, Wuhan, China, Sept 21-23 2007.
	7	A. Joshi, L. Levy, and M. Takahashi. Tree adjunct grammars. J. Comput. Syst. Sci., 10:136--163, 1975.
	8	John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
	9	John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
	10	J. Kevin Lanctot , Ming Li , En-hui Yang, Estimating DNA sequence entropy, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.409-418, January 09-11, 2000, San Francisco, California, United States
	11	W. B. Langdon and W. Banzhaf. Repeated patterns in tree genetic programming. In M. Keijzer, A. Tettamanzi, P. Collet, J. I. van Hemert, and M. Tomassini, editors, Proceedings of the 8th European Conference on Genetic Programming, volume 3447 of Lecture Notes in Computer Science, pages 190--202, Lausanne, Switzerland, 30 Mar. - 1 Apr. 2005. Springer.
	12	W. B. Langdon and W. Banzhaf. Repeated sequences in linear genetic programming genomes. Complex Systems, 15(4):285--306, 2005.
	13	A. Lindenmayer. Mathematical models for cellular interaction in development, parts i and ii. Journal of Theoretical Biology, 18:280--299 and 300--315, 1968.
	14	R. I. McKay, T. H. Hoang, D. L. Essam, and X. H. Nguyen. Developmental evaluation in genetic programming: the preliminary results. In P. Collet, M. Tomassini, M. Ebner, S. Gustafson, and A. Ekárt, editors, Proceedings of the 9th European Conference on Genetic Programming, volume 3905 of Lecture Notes in Computer Science, pages 280--289, Budapest, Hungary, 10 - 12 Apr. 2006. Springer.
	15	R. I. B. McKay, J. Shin, T. H. Hoang, X. H. Nguyen, and N. Mori. Using compression to understand the distribution of building blocks in genetic programming populations. In D. Srinivasan and L. Wang, editors, 2007 IEEE Congress on Evolutionary Computation, pages 2501--2508, Singapore, 25-28 Sept. 2007. IEEE Computational Intelligence Society, IEEE Press.
	16	Craig G. Nevill-Manning , Ian H. Witten, Protein Is Incompressible, Proceedings of the Conference on Data Compression, p.257, March 29-31, 1999
	17	Peter Nordin , Wolfgang Banzhaf, Evolving Turing-Complete Programs for a Register Machine with Self-modifying Code, Proceedings of the 6th International Conference on Genetic Algorithms, p.318-327, July 15-19, 1995
	18	M. O'Neill and C. Ryan. Grammatical evolution. IEEE Transactions on Evolutionary Computation, 5(4):349--358, Aug. 2001.
	19	J. Shin, M. Kang, B. McKay, X. Nguyen, T.-H. Hoang, N. Mori, and D. Essam. Analysing the regularity of genomes using compression and expression simplification. In M. Ebner, M. O'Neill, A. Ekárt, L. Vanneschi, and A. I. Esparcia-Alcázar, editors, Proceedings of the 10th European Conference on Genetic Programming, volume 4445 of Lecture Notes in Computer Science, pages 251--260, Valencia, Spain, 11 - 13 Apr. 2007. Springer.
	20	Lee Spector , Kilian Stoffel, Ontogenetic programming, Proceedings of the First Annual Conference on Genetic Programming, July 28-31, 1996, Stanford, California
	21	G. C. Wilson and M. I. Heywood. Context-based repeated sequences in linear genetic programming. In M. Keijzer, A. Tettamanzi, P. Collet, J. I. van Hemert, and M. Tomassini, editors, Proceedings of the 8th European Conference on Genetic Programming, volume 3447 of Lecture Notes in Computer Science, pages 240--249, Lausanne, Switzerland, 30 Mar. - 1 Apr. 2005. Springer.
	22	J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 24:530--536, 1978.