Abstract
Genetic programming is an automatic method for creating a computer program or other complex structure to solve a problem. This paper first reviews various instances where genetic programming has previously produced human-competitive results. It then presents new human-competitive results involving the automatic synthesis of the design of both the parameter values (i.e., tuning) and the topology of controllers for two illustrative problems. Both genetically evolved controllers are better than controllers designed and published by experts in the field of control using the criteria established by the experts. One of these two controllers infringes on a previously issued patent. Other evolved controllers duplicate the functionality of other previously patented controllers. The results in this paper, in conjunction with previous results, reinforce the prediction that genetic programming is on the threshold of routinely producing human-competitive results and that genetic programming can potentially be used as an “invention machine” to produce patentable new inventions.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
E. E. Altshuler and D. S. Linden, Process for the Design of Antennas using Genetic Algorithm, United States Patent 5,719,794, 1998. Applied for on July 19, 1995. Issued on February 17, 1998.
B. Andersson, P. Svensson, P. Nordin, and M. Nordahl, “Reactive and memory-based genetic programming for robot control,” in Genetic Programming: Second European Workshop. EuroGP'99. Proceedings, Lecture Notes in Computer Science, R. Poli, P. Nordin, W. B. Langdon, and T. C. Fogarty (eds.), Springer-Verlag, Berlin, Germany, 1991, vol. 1598, pp. 161-172.
D. Andre, F. H. Bennett, III, and J. R. Koza, “Discovery by genetic programming of a cellular automata rule that is better than any known rule for the majority classification problem,” in Genetic Programming 1996: Proceedings of the First Annual Conference, Stanford University, July 28-31, 1996, J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo (eds.), MIT Press, Cambridge, MA, 1996, pp. 3-11.
D. Andre and A. Teller, “Evolving team Darwin United,” in RoboCup-98: Robot Soccer World Cup II, Lecture Notes in Computer Science, M. Asada, and H. Kitano (eds.), Springer-Verlag, Berlin, 1999, vol. 1604, pp. 346-352.
P. J. Angeline, “An alternative to indexed memory for evolving programs with explicit state representations,” in Genetic Programming 1997: Proceedings of the Second Annual Conference, July 13-16, 1997, Stanford University, J. R. Koza, K. Deb, M. Dorigo, D. B. Fogel, M. Garzon, H. Iba, and R. L. Riolo (eds.), Morgan Kaufmann, San Francisco, CA, 1997, pp. 423-430.
P. J. Angeline, “Multiple interacting programs: A representation for evolving complex behaviors,” Cybernetics and Systems vol. 29 (8) pp. 779-806, 1998.
P. J. Angeline, “Evolving predictors for chaotic time series,” in Proceedings of SPIE Volume 3390: Application and Science of Computational Intelligence, S. Rogers, D. Fogel, J. Bezdek, and B. Bosacchi (eds.), SPIE—The International Society for Optical Engineering, Bellingham, WA, 1998, pp. 170-180.
P. J. Angeline and D. B. Fogel, “An evolutionary program for the identification of dynamical systems,” in Proceedings of SPIE Volume 3077: Application and Science of Artificial Neural Networks III, S. Rogers (ed.), SPIE—The International Society for Optical Engineering, Bellingham, WA, 1997, pp. 409-417.
P. J. Angeline and K. E. Kinnear, Jr. (eds.). Advances in Genetic Programming 2, The MIT Press: Cambridge, MA, 1996.
K. J. Astrom and T. Hagglund, PID Controllers: Theory, Design, and Tuning, second edition, Instrument Society of America: Research Triangle Park, NC, 1995.
W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith (eds.), GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference, July 13-17, 1999, Orlando, Florida, Morgan Kaufmann, San Francisco, CA, 1999.
W. Wolfgang, P. Nordin, R. E. Keller, and F. D. Francone, Genetic Programming—An Introduction, Morgan Kaufmann, San Francisco, CA and dpunkt, Heidelberg, 1998.
W. Banzhaf, P. Nordin, R. Keller, and M. Olmer, “Generating adaptive behavior for a real robot using function regression with genetic programming,” in Genetic Programming 1997: Proceedings of the Second Annual Conference, July 13-16, 1997, Stanford University, J. R. Koza, K. Deb, M. Dorigo, D. B. Fogel, M. Garzon, H. Iba, and R. L. Riolo (eds.), Morgan Kaufmann, San Francisco, CA, 1997, pp. 35-43.
W. Banzhaf, R. Poli, M. Schoenauer, and T. C. Fogarty, Genetic Programming: First European Workshop, EuroGP'98, Paris, France, April 1998 Proceedings, April 1998, Paris, France, Lecture Notes in Computer Science, Springer-Verlag, Berlin, Germany, 1998, vol. 1391.
F. H Bennett, III, J. R. Koza, M. A. Keane, J. Yu, W. Mydlowec, and O. Stiffelman, “Evolution by means of genetic programming of analog circuits that perform digital functions,” in GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference, July 13-17, 1999, Orlando, Florida, W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith (eds.), Morgan Kaufmann, San Francisco, CA, 1999, pp. 1477-1483.
F. H Bennett, III, J. R. Koza, J. Shipman, and O. Stiffelman, “Building a parallel computer system for $18,000 that performs a half peta-flop per day,” in GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference, July 13-17, 1999, Orlando, Florida, W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith (eds.), Morgan Kaufmann, San Francisco, CA, 1999, pp. 1484-1490.
S. P. Boyd, and C. H. Barratt, Linear Controller Design: Limits of Performance, Prentice Hall: Englewood Cliffs, NJ, 1991.
A. E. Bryson and Y-C. Ho, Applied Optimal Control, Hemisphere Publishing: New York, 1975.
A. Callender, and A. B. Stevenson, Automatic Control of Variable Physical Characteristics, United States Patent 2,175,985. Filed February 17, 1936 in United States. Filed February 13, 1935 in Great Britain. Issued October 10, in United States, 1939.
G. A. Campbell, Electric Wave Filter. U.S. Patent 1,227,113. Filed July 15, 1915. Issued May 22, 1917, 1917.
W. Cauer, Artificial Network. U.S. Patent 1,958,742. Filed June 8, 1928 in Germany. Filed December 1, 1930 in United States. Issued May 15, 1934, 1934.
W. Cauer, Electric Wave Filter. U.S. Patent 1,989,545. Filed June 8, 1928. Filed December 6, 1930 in United States. Issued January 29, 1935, 1935.
W. Cauer, Unsymmetrical Electric Wave Filter. Filed November 10, 1932 in Germany. Filed November 23, 1933 in United States. Issued July 21, 1936, 1936.
K. Chellapilla, and D. B. Fogel, “Evolution, neural networks, games, and intelligence,” Proceedings _. of the IEEE vol. 87 (9) pp. 1471-1496, 1999.
L. S. Crawford, V. H. L. Cheng, and P. K. Menon, “Synthesis of flight vehicle guidance and control laws using genetic search methods,” in Proceedings of 1999 Conference on Guidance, Navigation, and Control, American Institute of Aeronautics and Astronautics, Reston, VA, Paper AIAA-99-4153, 1999.
S. Darlington, Semiconductor Signal Translating Device, U.S. Patent 2,663,806. Filed May 9, 1952. Issued December 22, 1953, 1953.
L. D. Dewell, and P. K. Menon, “Low-thrust orbit transfer optimization using genetic search,” in Proceedings of 1999 Conference on Guidance, Navigation, and Control, American Institute of Aeronautics and Astronautics, Reston, VA, Paper AIAA-99-4151, 1999.
R. C. Dorf, and R. H. Bishop, Modern Control Systems, eighth edition, Addison-Wesley: Menlo Park, CA, 1998.
L. J. Fogel, A. J. Owens, and M. J. Walsh, Artificial Intelligence through Simulated Evolution, John Wiley: New York, 1966.
T. Higuchi, T. Niwa, T. Tanaka, H. Iba, H. de Garis, and T. Furuya, “Evolving hardware with genetic learning: A first step towards building a Darwin machine,” in From Animals to Animats 2: Proceedings of the Second International Conference on Simulation of Adaptive Behavior, J.-A. Meyer, H. L. Roitblat, and S. W. Wilson (eds.), The MIT Press, Cambridge, MA, 1993, pp. 417-424.
J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press: Ann Arbor, MI, 1975.
J. H. Holland, K. J. Holyoak, R. E. Nisbett, and P. A. Thagard, Induction: Processes of Inference, Learning, and Discovery, The MIT Press: Cambridge, MA, 1986.
H. S. Jones, Control Apparatus. United States Patent 2,282,726. Filed October 25, 1939. Issued May 12, 1942, 1942.
H. Juille, “Evolution of non-deterministic incremental algorithms as a new approach for search in state spaces,” in Proceedings of the Sixth International Conference on Genetic Algorithms, L. J. Eshelman (ed.), Morgan Kaufmann, San Francisco, CA, 1995, pp. 351-358.
H. Juille, and J. B. Pollack, “Coevolving the “ideal” trainer: Application to the discovery of cellularautomata rules,” in Genetic Programming 1998: Proceedings of the Third Annual Conference, July 22-25, 1998, University of Wisconsin, Madison, Wisconsin, J. R. Koza, W. Banzhaf, K. Chellapilla, K. Deb, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, and R. L. Riolo (eds.), Morgan Kaufmann, San Francisco, CA, 1998, pp. 519-527.
K. E. Kinnear, Jr. (ed.), Advances in Genetic Programming, The MIT Press: Cambridge, MA, 1994.
J. R. Koza, “Hierarchical genetic algorithms operating on populations of computer programs,” in Proceedings of the 11th International Joint Conference on Artificial Intelligence, Morgan Kaufmann: San Mateo, CA, vol. 1, 1989, pp. 768-774.
J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press: Cambridge, MA, 1992.
J. R. Koza, Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press: Cambridge, MA, 1994.
J. R. Koza, Genetic Programming II Videotape: The Next Generation, MIT Press: Cambridge, MA, 1994.
J. R. Koza, W. Banzhaf, K. Chellapilla, K. Deb, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, and R. Riolo (eds.), Genetic Programming 1998: Proceedings of the Third Annual Conference, Morgan Kaufmann, San Francisco, CA, 1998.
J. R. Koza and F. H Bennett, III, Automatic Synthesis, Placement, and Routing of Electrical Circuits by Means of Genetic Programming,” in Advances in Genetic Programming 3, L. Spector, W. B. Langdon, U.-M. O'Reilly, and P. Angeline (eds.), The MIT Press, Cambridge, MA, 1999, chap. 6, pp. 105-134.
J. R. Koza, F. H Bennett, III, D. Andre, and M. A. Keane, Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann: San Francisco, CA, 1999.
J. R. Koza, F. H Bennett, III, M. A. Keane, J. Yu, W. Mydlowec, and O. Stiffelman, “Searching for the impossible using genetic programming,” in GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference, July 13-17, 1999, Orlando, Florida, W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith (eds.), Morgan Kaufmann, San Francisco, CA, 1999, pp. 1083-1091.
J. R. Koza, F. H Bennett, III, D. Andre, M. A. Keane, and S. Brave, Genetic Programming III Videotape: Human-Competitive Machine Intelligence, Morgan Kaufmann: San Francisco, CA, 1999, forthcoming.
J. R. Koza, K. Deb, M. Dorigo, D. B. Fogel, M. Garzon, H. Iba, and R. L. Riolo (eds.), Genetic Programming 1997: Proceedings of the Second Annual Conference, Morgan Kaufmann, San Francisco, CA, 1997.
J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo (eds.), Genetic Programming 1996: Proceedings of the First Annual Conference, The MIT Press, Cambridge, MA, 1996.
J. R. Koza and J. P. Rice, Genetic Programming: The Movie, MIT Press: Cambridge, MA, 1992.
I. M. Kroo, J. H. McMasters, and R. J. Pavek, Large Airplane with Nonplanar Wing. U.S. Design Patent number USD0363696. Applied for on June 23, 1993. Issued October 31, 1995, 1995.
W. B. Langdon, Genetic Programming and Data Structures: Genetic ProgrammingqData StructuressAutomatic Programming!, Kluwer Academic Publishers: Amsterdam, 1998.
K. F. Man, K. S. Tang, S. Kwong, and W. A. Halang, Genetic Algorithms for Control and Signal Processing, Springer-Verlag: London, 1997.
K. F. Man, K. S. Tang, S. Kwong, and W. A. Halang, Genetic Algorithms: Concepts and Designs, Springer-Verlag: London, 1999.
P. Marenbach, K. D. Bettenhausen, and S. Freyer, “Signal path oriented approach for generation of dynamic process models,” in Genetic Programming 1996: Proceedings of the First Annual Conference, July 2831, 1996, Stanford University, J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo (eds.), MIT Press, Cambridge, MA, 1996, pp. 327-332.
P. K. Menon, M. Yousefpor, T. Lam, and M. L. Steinberg, “Nonlinear flight control system synthesis using genetic programming. Proceedings of 1995 Conference on Guidance, Navigation, and Control,” in American Institute of Aeronautics and Astronautics, Reston, VA, 1995, pp. 461-470.
D. G. O'Connor and R. J. Nelson, Sorting System with N-Line Sorting Switch. United States Patent number 3,029,413. Issued April 10, 1962, 1962.
K. Ogata, Modern Control Engineering, third edition. Prentice Hall: Upper Saddle River, NJ, 1997.
G. A. Philbrick, Delayed Recovery Electric Filter Network. Filed May 18, 1951. U.S. Patent 2,730,679. Issued January 10, 1956, 1956.
R. Poli, P. Nordin, W. B. Langdon, and T. C. Fogarty, Genetic Programming: Second European Workshop, EuroGP99, Goteborg, Sweden, May 1999, Proceedings, Lecture Notes in Computer Science, Springer-Verlag, Berlin, Germany, 1999, vol. 1598.
T. Quarles, A. R. Newton, D. O. Pederson, and A. Sangiovanni-Vincentelli, SPICE 3 Version 3F5 User's Manual, Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA, March 1994.
I. Rechenberg, Cybernetic solution path of an experimental problem, Royal Aircraft Establishment, Ministry of Aviation, Library Translation 1112, Farnborough, 1965.
I. Rechenberg, Evolutionsstrategie: Optimierung Technischer Systeme nach Prinzipien der Biolgischen Evolution, Verlag Frommann-Holzboog: Stuttgart-Bad Cannstatt, 1973.
C. Ryan, Automatic Re-engineering of Software Using Genetic Programming, Kluwer Academic Publishers: Amsterdam, 1999.
A. L. Samuel, “Some studies in machine learning using the game of checkers,” IBM Journal of Research and Development vol. 3 (3) pp. 210-229, 1959.
A. L. Samuel, “AI: Where it has been and where it is going,” in Proceedings of the Eighth International Joint Conference on Artificial Intelligence, Morgan Kaufmann, Los Altos, CA, 1983, pp. 1152-1157.
L. Spector, H. Barnum, and H. J. Bernstein, “Genetic programming for quantum computers,” in Genetic Programming 1998: Proceedings of the Third Annual Conference, J. R. Koza, W. Banzhaf, K. Chellapilla, K. Deb, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, and R. Riolo (eds.), Morgan Kaufmann, San Francisco, CA, 1998, pp. 365-373.
L. Spector, H. Barnum, and H. J. Bernstein, “Quantum computing applications of genetic programming,” in Advances in Genetic Programming 3, L. Spector, W. B. Langdon, U.-M. O'Reilly, and P. Angeline eds., The MIT Press, Cambridge, MA, 1999, pp. 135-160.
L. Spector, H. Barnum, H. J. Bernstein, and N. Swamy, “Finding a better-than-classical quantum AND/OR algorithm using genetic programming,” in IEEE. Proceedings of 1999 Congress on Evolutionary Computation, IEEE Press, Piscataway, NJ, 1999, pp. 2239-2246.
L. Spector, W. B. Langdon, U.-M. O'Reilly, and P. Angeline (eds.), Advances in Genetic Programming 3, The MIT Press: Cambridge, MA, 1999.
T. L. Sterling, J. Salmon, D. J. Becker, and D. F. Savarese, How to Build a Beowulf: A Guide to Implementation and Application of PC Clusters, MIT Press: Cambridge, MA, 1999.
G. D. Sweriduk, P. K. Menon, and M. L. Steinberg, “Robust command augmentation system design using genetic search methods,” in Proceedings of 1998 Conference on Guidance, Navigation, and Control, American Institute of Aeronautics and Astronautics, Reston, VA, 1998, pp. 286-294.
G. D. Sweriduk, P. K. Menon, and M. L. Steinberg, “Design of a pilot-activated recovery system using genetic search methods,” in Proceedings of 1998 Conference on Guidance, Navigation, and Control, American Institute of Aeronautics and Astronautics, Reston, VA, 1999.
A. Teller, Evolving Programmers: SMART Mutation, Computer Science Department, Carnegie Mellon University, Technical Report CMU-CS-96, 1996.
A. Teller, “Evolving programmers: The co-evolution of intelligent recombination operators,” Advances in Genetic Programming 2, P. J. Angeline and K. E. Kinnear, Jr. (eds.), The MIT Press: Cambridge, MA, 1996.
A. Teller, “Algorithm Evolution with Internal Reinforcement for Signal Understanding,” Computer Science Department, Carnegie Mellon University, Pittsburgh, Pennsylvania, PhD Thesis, 1998.
A. Teller, “The internal reinforcement of evolving algorithms,” Advances in Genetic Programming 3, L. Spector, W. B. Langdon, U.-M. O'Reilly, and P. Angeline (eds.), The MIT Press: Cambridge, MA, 1999.
A. Teller and M. Veloso, Learning Tree Structured Algorithms for Orchestration into an Object Recognition System, Computer Science Department, Carnegie Mellon University, Technical Report CMU-CS-95-101, 1995.
A. Teller and M. Veloso, “Program evolution for data mining,” in Special Issue on Genetic Algorithms and Knowledge Bases, S. Louis (ed.), The International Journal of Expert Systems, JAI Press 3 pp. 216-236, 1995.
A. Teller and M. Veloso, “A controlled experiment: evolution for learning difficult problems,” in Proceedings of Seventh Portuguese Conference on Artificial Intelligence, Springer-Verlag, 1995, pp. 165-176.
A. Teller and M. Veloso, “Algorithm Evolution for Face Recognition: What Makes a Picture Difficult?,” in Proceedings of the IEEE International Conference on Evolutionary Computation, IEEE Press, 1995.
A. Teller and M. Veloso, “Language Representation Progression in PADO,” in Proceedings of AAAI Fall Symposium on Artificial Intelligence, AAAI Press, Menlo Park, CA, 1995.
A. Teller and M. Veloso, “PADO: A new learning architecture for object recognition,” Symbolic Visual Learning, K. Ikeuchi, and M. Veloso (eds.), Oxford University Press, 1996, pp. 81-116.
A. Teller and M. Veloso, “Neural programming and an internal reinforcement policy,” Simulated Evolution and Learning, Lecture Notes in Artificial Intelligence, X. Yao, J.-H. Kim, and T. Furuhashi (eds.), Springer-Verlag: Heidelberg, Germany, 1997, vol. 1285, pp. 279-286.
A. M. Turing, “Intelligent machines. Pages 21-23,” in Mechanical Intelligence: Collected Works of A. M. Turing, D. C. Ince (ed.), North-Holland: Amsterdam, 1948, pp. 107-128.
A. M. Turing, “Computing machinery and intelligence,” Mind vol. 59 (236) pp. 433-460. Reprinted in Mechanical Intelligence: Collected Works of A. M. Turing, D. C. Ince (ed.), Amsterdam, North-Holland, 1992, pp. 133-160.
D. Whitley, F. Gruau, and L. Preatt, “Cellular encoding applied to neurocontrol,” in Proceedings of the Sixth International Conference on Genetic Algorithms, L. J. Eshelman (ed.), Morgan Kaufmann, San Francisco, CA, 1995, pp. 460-467.
O. J. Zobel, Wave Filter. U.S. Patent 1,538,964. Filed January 15, 1921. Issued May 26, 1925, 1925.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Koza, J.R., Keane, M.A., Yu, J. et al. Automatic Creation of Human-Competitive Programs and Controllers by Means of Genetic Programming. Genetic Programming and Evolvable Machines 1, 121–164 (2000). https://doi.org/10.1023/A:1010076532029
Issue Date:
DOI: https://doi.org/10.1023/A:1010076532029