(1) the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result,
Automated Reverse Engineering of nonlinear Dynamical Systems
(2) the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper,
Josh Bongard
329 Votey Hall
University of Vermont
33 Colchester Ave.
Burlington, VT 05405
josh.bongard@uvm.edu
802-656-4665
Hod Lipson
216 Upson Hall
Cornell University
Ithaca, NY 14853-7501
hod.lipson@cornell.edu
607-255-1686
(3) the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition),
Josh Bongard
(4) the abstract of the paper(s),
Complex nonlinear dynamics arise in many fields of science and engineering, but uncovering the underlying differential equations directly from observations poses a challenging task. The ability to symbolically model complex networked systems is key to understanding them, an open problem in many disciplines. Here we introduce for the first time a method that can automatically generate sets of symbolic equations for a nonlinear coupled dynamical system directly from time series data. This method is applicable to any system that can be described using sets of ordinary nonlinear differential equations, and assumes that the time series of all variables are observable (possibly with some noise). Previous automated symbolic modeling approaches of coupled physical systems produced linear models or required a nonlinear model to be provided manually. The advance presented here is made possible by allowing the method to model each (possibly coupled) variable separately, intelligently perturbing and destabilizing the system in order to extract its less observable characteristics, and automatically simplifying the equations during modeling. We demonstrate this method on four simulated and two real systems spanning mechanics, ecology, and systems biology. Unlike numerical models, symbolic models have explanatory value, suggesting that automated reverse engineering approaches for model-free symbolic nonlinear system identification may play an increasing role in our ability to understand progressively complex systems in the future.
(5) a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies,
(B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal.
(G) The result solves a problem of indisputable difficulty in its field.
(6) a statement stating why the result satisfies the criteria that the contestant claims (see the examples below as a guide to aid in constructing this part of the submission),
Our paper introduces a coevolutionary genetic-programming method that produces mathematical models of coupled, nonlinear systems with several state variables. Two such example systems were successfully modeled by our approach: a physical damped pendulum, and historical data from an interacting predatory and prey species.
After consulting world experts on the history of the mechanical pendulum, it would appear that the first reported algebraic model describing pendula was published by H. Kamerlingh Onnes in his dissertation "Nieuwe bewijzen voor de aswenteling der aarde" from the University of Gronigen. The significance of this work was pointed up by Schulz-DuBois in his 1970 American Journal of Physics article "Foucault Pendulum Experiment by Kamerlingh Onnes and Degenerate Perturbation Theory" (38(2): 173-188), in which he 'pays homage to' the work of Kamerlingh Onnes, underscoring its significance. The form of the equations is still presented to this day in engineering textbooks as the mathematical description of a damped pendulum. Our method consistently rediscovers this equation's form and very closely matches the numerical parameters in less than 30 seconds on a standard desktop PC, starting from different random populations, and using actual data from a physical pendulum.
Our method, with little alteration, also successfully generated a mathematical model describing the interaction between a predatory and prey species. The first model of such a system was proposed in 1925 by the American biophysicist Alfred Lotka and the Italian mathematician Vito Volterra (Volterra, V. 1928: Variations and fluctuations of the number of individuals in animal species living together. Journal du conseil/Conseil International pour lexploration de la mer 3: 351). Their equations still form the basis of many models of population dynamics today. Although slightly different in form, the equations synthesized by our method capture and communicate the same information about the two species as the Lotka-Volterra equations: which species is the prey, and which the predator; the rate at which the prey population decreases in response to predation; and the rate at which the predator population increases in response to the prey. Again, our method consistently and rapidly converges on the same model form, with similar numbers for the relevant parameters.
Our method also meets criteria (G), in that it is able to generate sets of coupled, nonlinear ordinary differential equations to describe systems with more than five state variables. Manually writing down coupled, nonlinear ODEs for physical systems is indisputably difficult, as indicated by the lack of such models in the literature. For instance, the most complex such model published for one of the most well-studied dynamical systems in nature, the metabolic pathway in E. coli bacteria, contains only five nonlinear ODEs (Yildirim, N., Mackey, M. C. (2003) "Feedback Regulation in the Lactose Operon: A Mathematical Modeling Study and Comparison with Experimental Data", Biophysical Journal 84: 2841-2851).
(7) a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable);
Bongard J., Lipson H. (2007), "Automated Reverse Engineering of nonlinear Dynamical Systems", Proceedings of the National Academy of Science, in press.
(8) a statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors; and
Any prize money, if any, is to be divided equally among the co-authors.
(9) a statement stating why the judges should consider the entry as "best" in comparison to other entries that may also be "human-competitive."
It seems likely that our paper is the only one that presents an evolutionary method that produces human-competitive results across several diverse domains, including ecology, genetics and mechanics. Secondly, the fact that this paper will appear in PNAS indicates that it was favorably reviewed by renowned scientists outside of the evolutionary computation field. This indicates that our method is not simply a new way to do evolutionary computation, but may serve as a useful tool that can successfully compete with scientists in the endeavor of creating models of large, coupled, nonlinear phenomena.