Entry for the 2010 "Humies" Awards for Human-Competitive Results
--------------------------------------------------------------------------
(1) PAPER TITLE
--------------------------------------------------------------------------
Solving Iterated Functions Using Genetic Programming
-------------------------------------------------------------------------
(2) AUTHORS
-------------------------------------------------------------------------
Michael Schmidt
100 Fairview Sq. 6D
Ithaca, NY 14850
(608) 385-6363
mds47@cornell.edu
Hod Lipson
216 Upson Hall, Cornell University
Ithaca, NY 14853-7501, USA
(607) 255-1686
hod.lipson@cornell.edu
-------------------------------------------------------------------------
(3) CORRESPONDING AUTHOR
-------------------------------------------------------------------------
Michael Schmidt
-------------------------------------------------------------------------
(4) PAPER 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-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.
-------------------------------------------------------------------------
(5) HUMAN COMPETITIVE CRITERIA
-------------------------------------------------------------------------
(E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions.
(F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered.
(G) The result solves a problem of indisputable difficulty in its field.
-------------------------------------------------------------------------
(6) WHY CRITERIA IS SATISFIED
-------------------------------------------------------------------------
A challenging (and infamous) iterated function problem has circulated as a test of one's intelligence over the past few decades, particularly among physicists and in math competitions (Fractals 1999, Mathvn 2009). This problem asks to find an analytical function f(x) such that f(f(x)) = x^2 - 2. In fact, those who first solved this problem are still celebrated within various communities. Renowned physicist Michael Fisher is rumored to have solved the puzzle within five minutes (Journal of Statistical Physics 2003); however, few have matched this feat.
Slow progress has been made toward the analysis and solving of iterated functions including this problem. Current solutions require recognizing relations of Chebyshev polynomials or substituting special functional forms. These methods however, make assumptions which lead to specific solutions; in fact there may and often do exist other valid or more general solutions.
In this paper, we not only show that genetic programming can readily solve these types of problems (including the most challenging variants) faster than any human, but can also find different and more general solutions. Finally, we present a new and previously unknown solution to the infamous f(f(x)) = x^2 - 2 problem, discovered automatically by a genetic programming in under two minutes.
For these reasons, this entry satisfies three of the human-competitive criteria:
(E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions.
(F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered.
(G) The result solves a problem of indisputable difficulty in its field.
-------------------------------------------------------------------------
(7) FULL PAPER CITATION
-------------------------------------------------------------------------
Schmidt M., Lipson H. (2009) "Solving Iterated Functions Using Genetic Programming," In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'09): Late Breaking Papers, p. 2149-2154.
-------------------------------------------------------------------------
(8) STATEMENT ON PRIZE MONEY
-------------------------------------------------------------------------
Prize money, if any, is to be divided equally among the co-authors
-------------------------------------------------------------------------
(9) STATEMENT ON WHY THIS ENTRY IS THE BEST
-------------------------------------------------------------------------
This paper demonstrates that genetic programming is competitive and surpasses human ability to solve iterated function problems both in speed and generality of the iterated function form. This entry may be considered "best" based on the discovery of a new solution to a long-developed and infamous problem in physics and mathematics. More importantly however, the ability to solve iterated functions more easily and generally could impact many fields from computer science, to dynamical systems, where few tools exist to analyze iterated relationships.