Solving iterated functions using genetic programming

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Solving iterated functions using genetic programming

Full text

Pdf (447 KB)

Source

Genetic And Evolutionary Computation Conference archive
Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers table of contents

Montreal, Québec, Canada

SESSION: Late-breaking papers table of contents

Pages 2149-2154

Year of Publication: 2009

ISBN:978-1-60558-505-5

Authors

Michael Douglas Schmidt	Cornell University, Ithaca, NY, USA
Hod Lipson	Cornell University, Ithaca, NY, USA

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): 16, Downloads (12 Months): 41, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	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/1570256.1570292 What is a DOI?

ABSTRACT

An iterated function f(x) is a function that when composed with itself, produces a given expression f(f(x))=g(x). Iterated functions are essential constructs in fractal theory and dynamical systems, but few analysis techniques exist for solving them analytically. Here we propose using genetic programming to find analytical solutions to iterated functions of arbitrary form. We demonstrate this technique on the notoriously hard iterated function problem of finding f(x) such that f(f(x))=x²--2. While some analytical techniques have been developed to find a specific solution to problems of this form, we show that it can be readily solved using genetic programming without recourse to deep mathematical insight. We find a previously unknown solution to this problem, suggesting that genetic programming may be an essential tool for finding solutions to arbitrary iterated functions.

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	R. Brown, "On Solving Nonlinear Functional, Finite Difference, Composition, and Iterated Equations," Fractals, vol. 7, pp. 277--282, 1999.
	2	B.A. Brown, A.R. Brown, and M.F. Shlesinger, "Solutions of Doubly and Higher Order Iterated Equations," Journal of Statistical Physics, vol. 110, pp. 1087--1097, 2003.
	3	"Mathvn journal problems," in Mathvn. vol. 01/2009 mathvn.org, 2009.
	4	Andrzej Bielecki , Barbara Strug, Finding an iterated function systems based representation for complex visual structures using an evolutionary algorihm, Machine Graphics & Vision International Journal, v.16 n.1, p.171-189, January 2007
	5	A. Bielecki and B. Strug, "An Evolutionary Algorithm for Solving the Inverse Problem for Iterated Function Systems for a Two Dimensional Image," in Computer Recognition Systems, 2005, pp. 347--354.
	6	John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
	7	M. Ben, J.W. Mark, and W.B. Geoffrey, "Using a Tree Structured Genetic Algorithm to Perform Symbolic Regression," in First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, GALESIA. vol. 414, 1995, pp. 487--492.
	8	Edwin D. De Jong , Jordan B. Pollack, Multi-Objective Methods for Tree Size Control, Genetic Programming and Evolvable Machines, v.4 n.3, p.211-233, September 2003 [doi>10.1023/A:1025122906870]
	9	Michael Schmidt , Hod Lipson, Comparison of tree and graph encodings as function of problem complexity, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277288]
	10	X.H. Nguyen, R.I. McKay, and D.L. Essam, "Solving the Symbolic Regression Problem with Tree-Adjunct Grammar Guided Genetic Programming: The Comparative Results," in The Australian Journal of Intelligent Information Processing Systems. vol. 7, 2001, pp. 114--121.
	11	J. Bongard and H. Lipson, "Automated reverse engineering of nonlinear dynamical systems," Proceedings of the National Academy of Sciences, vol. 104, pp. 9943--9948, 2007.
	12	M. Schmidt and H. Lipson, "Distilling Free-Form Natural Laws from Experimental Data," Science, vol. 324, pp. 81--85, 2009.
	13	W. Stein, "Sage Mathematics Software (Version 3.4)," The Sage Development Team, http://www.sagemath.org/, 2009.
	14	M.D. Schmidt and H. Lipson, "Coevolution of Fitness Maximizers and Fitness Predictors," in Proceedings of the Genetic and Evolutionary Computation Conference, Late Breaking Paper, 2005.
	15	M.D. Schmidt and H. Lipson, "Co-evolving Fitness Predictors for Accelerating and Reducing Evaluations," in Genetic Programming Theory and Practice IV. vol. 5, 2006, pp. 113--130.
	16	M.D. Schmidt and H. Lipson, "Coevolution of Fitness Predictors," IEEE Transactions on Evolutionary Computation, vol. 12, pp. 736--749, Dec 2008.
	17	Samir W. Mahfoud, Niching methods for genetic algorithms, University of Illinois at Urbana-Champaign, Champaign, IL, 1996
	18	F. Francisco, S. Giandomenico, T. Marco, and V. Leonardo, "Parallel Genetic Programming," in Parallel Metaheuristics, 2005, pp. 127--153.
	19	G. Christian, P. Marc, and D. Marc, "A Robust Master-Slave Distribution Architecture for Evolutionary Computations," in Genetic and Evolutionary Computation Conference Late Breaking Papers, 2003, pp. 80--87.