Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-24T16:47:52.543Z Has data issue: false hasContentIssue false
  • English
  • Français

Human-competitive machine invention by means of genetic programming

Published online by Cambridge University Press:  12 June 2008

John R. Koza
John R. Koza
Affiliation:
Biomedical Informatics Program, Department of Medicine, Stanford University, Stanford, California, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

Genetic programming is a systematic method for getting computers to automatically solve problems. Genetic programming uses the Darwinian principle of natural selection and analogs of recombination (crossover), mutation, gene duplication, gene deletion, and certain mechanisms of developmental biology to progressively breed, over a series of many generations, an improved population of candidate solutions to a problem. This paper makes the points that genetic programming now routinely delivers human-competitive machine intelligence for problems of automated design and can serve as an automated invention machine.

Keywords

Automated DesignComputer-Aided DesignDevelopmental Genetic ProgrammingGenetic ProgrammingHuman-Competitive Results
Type
Research Article
Information
AI EDAM , Volume 22 , Issue 3 , August 2008 , pp. 185 - 193
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Andre, D., Bennett, F.H. III, & Koza, J.R. (1996). Discovery by genetic programming of a cellular automata rule that is better than any known rule for the majority classification problem. Genetic Programming 1996: Proc. 1st Annual Conf. (Koza, J.R., Goldberg, D.E., Fogel, D.B., & Riolo, R.L., Eds.), pp. 3–11. Cambridge, MA: MIT Press.Google Scholar
Andre, D., & Teller, A. (1999). Evolving team Darwin United. In RoboCup–98: Robot Soccer World Cup II, Lecture Notes in Computer Science (Asada, M., & Kitano, H. Eds.), Vol. 1604, pp. 346–352. Berlin: Springer–Verlag.CrossRefGoogle Scholar
Angeline, P.J., & Kinnear, K.E. Jr., (Eds.). 1996). Advances in Genetic Programming 2. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Antonisse, H.J., & Keller, K. (1987). Genetic operators for high-level knowledge representations. Proc. 2nd Int. Conf. Genetic Algorithms. Mahwah, NJ: Erlbaum.Google Scholar
Babovic, V. (1996). Emergence, Evolution, Intelligence: Hydroinformatics. Rotterdam: Balkema.Google Scholar
Banzhaf, W., Nordin, P., Keller, R.E., & Francone, F.D. (1998). Genetic Programming—An Introduction. San Francisco, CA/Heidelberg: Morgan Kaufmann/dpunkt.CrossRefGoogle Scholar
Bickel, A.S., & Bickel, R.W. (1987). Tree structured rules in genetic algorithms. Proc. 2nd Int. Conf. Genetic Algorithms. Mahwah, NJ: Erlbaum.Google Scholar
Blickle, T. (1997). Theory of Evolutionary Algorithms and Application to System Synthesis. TIK–Schriftenreihe Number 17. Zurich: vdf Hochschul Verlag AG an der ETH Zuerich.Google Scholar
Brave, S. (1996). Evolving deterministic finite automata using cellular encoding. Genetic Programming 1996: Proc. 1st Annual Conf. (Koza, J.R., Goldberg, D.E., Fogel, D.B., & Riolo, R.L., Eds.), pp. 39–44. Cambridge, MA: MIT Press.Google Scholar
Cho, S.-B., Nguyen, H.X., & Shan, Y. (Eds.). (2003). Proc. 1st Asian-Pacific Workshop on Genetic Programming. Accessed at www.aspgp.orgGoogle Scholar
Cramer, N.L. (l985). A representation for the adaptive generation of simple sequential programs. Proc. Int. Conf. Genetic Algorithms and Their Applications. Mahwah, NJ: Erlbaum.Google Scholar
Deb, K., Poli, R., Banzhaf, W., Beyer, H.-G., Burke, E., Darwen, P., Dasgupta, D., Floreano, D., Foster, J., Harman, M., Holland, O., Lanzi, P.L., Spector, L., Tettamanzi, A., Thierens, D., & Tyrrell, A. (Eds.). (2004). Genetic and Evolutionary Computation—GECCO 2004: Genetic and Evolutionary Computation Conf., Lecture Notes in Computer Science, Vol. 3102. Berlin: Springer.Google Scholar
Dellaert, F., & Beer, R.D. (1994). Toward an evolvable model of development for autonomous agent synthesis. Artificial Life IV: Proc. 4th Int. Workshop on the Synthesis and Simulation of Living Systems (Brooks, R., & Maes, P., Eds.), pp. 246–257. Cambridge, MA: MIT Press.Google Scholar
Forsyth, R. (1981). BEAGLE—A Darwinian Approach to Pattern Recognition. Kybernetes 10, 159–166.Google Scholar
Fujiki, C. (l986). An evaluation of Holland's genetic algorithm applied to a program generator. MS Thesis. University of Idaho, Computer Science Department.Google Scholar
Fujiki, C., & Dickinson, J. (l987). Using the genetic algorithm to generate LISP source code to solve the prisoner's dilemma. Proc. 2nd Int. Conf. Genetic Algorithms. Mahwah, NJ: Erlbaum.Google Scholar
Gruau, F. (1992 a). Cellular Encoding of Genetic Neural Networks. Technical Report 92-21. Ecole Normale Supérieure de Lyon, Laboratoire de l'Informatique du Parallélisme.Google Scholar
Gruau, F. (1992 b). Genetic synthesis of Boolean neural networks with a cell rewriting developmental process. Proc. Workshop on Combinations of Genetic Algorithms and Neural Networks 1992 (Schaffer, J.D., & Whitley, D., Eds.). Los Alamitos, CA: IEEE Press.Google Scholar
Gruau, F. (1993). Genetic synthesis of modular neural networks. Proc. 5th Int. Conf. Genetic Algorithms (Forrest, S., Ed.), pp. 318–325. San Mateo, CA: Morgan Kaufmann.Google Scholar
Gruau, F. (1994 a). Neural Network Synthesis using Cellular Encoding and the Genetic Algorithm. PhD Thesis. Ecole Normale Supérieure de Lyon.Google Scholar
Gruau, F. (1994 b). Genetic micro programming of neural networks. In Advances in Genetic Programming (Kinnear, K.E. Jr., Ed.), pp. 495–518. Cambridge, MA: MIT Press.Google Scholar
Gruau, F., & Whitley, D. (1993). Adding learning to the cellular development process: a comparative study. Evolutionary Computation 1(3), 213–233.CrossRefGoogle Scholar
Hemmi, H., Mizoguchi, J., & Shimohara, K. (1994). Development and evolution of hardware behaviors. Artificial Life IV: Proc. 4th Int. Workshop on the Synthesis and Simulation of Living Systems (Brooks, R., & Maes, P., Eds.), pp. 371–376. Cambridge, MA: MIT Press.Google Scholar
Hicklin, J.F. (1986). Application of the genetic algorithm to automatic program generation. MS Thesis. University of Idaho, Computer Science Department.Google Scholar
Holland, J.H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Ann Arbor, MI: University of Michigan Press.Google Scholar
Holland, J.H., & Reitman, J.S. (1978). Cognitive systems based on adaptive algorithms. In Pattern-Directed Inference Systems (Waterman, D.A., & Hayes-Roth, F., Eds.), pp. 313–329. New York: Academic.CrossRefGoogle Scholar
Iba, H. (1996). Genetic Programming. Tokyo: Tokyo Denki University Press [in Japanese].Google Scholar
Jacob, C. (1997). Principia Evolvica: Simulierte Evolution mit Mathematica. Heidelberg: dpunkt.verlag.Google Scholar
Jacob, C. (2001). Illustrating Evolutionary Computation with Mathematica. San Francisco, CA: Morgan Kaufmann.Google Scholar
Keijzer, M., Tettamanzi, A., Collet, P., van Hemert, J., Tomassini, M. (Eds.). (2005). Genetic Programming: 8th European Conf. (EuroGP 2005), Lecture Notes in Computer Science, Vol. 3447. Heidelberg: Springer–Verlag.CrossRefGoogle Scholar
Kinnear, K.E. Jr., (Ed.). (1994). Advances in Genetic Programming. Cambridge, MA: MIT Press.Google Scholar
Kitano, H. (1996). Morphogenesis for evolvable systems. In Toward Evolvable Hardware, Lecture Notes in Computer Science (Sanchez, E., & Tomassini, M., Eds.), Vol. 1062, pp. 99–117. Berlin: Springer–Verlag.CrossRefGoogle Scholar
Koza, J.R. (1989). Hierarchical genetic algorithms operating on populations of computer programs. Proc. 11th Int. Joint Conf. Artificial Intelligence, Vol. 1, pp. 768–774. San Mateo, CA: Morgan Kaufmann.Google Scholar
Koza, J.R. (1990). Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems. Technical Report STAN-CS-90-1314, Stanford University, Computer Science Department.Google Scholar
Koza, J.R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press.Google Scholar
Koza, J.R. (1993). Discovery of rewrite rules in Lindenmayer systems and state transition rules in cellular automata via genetic programming. Symp. Pattern Formation (SPF–93), Claremont, CA, February 13.Google Scholar
Koza, J.R. (1994 a). Genetic Programming II: Automatic Discovery of Reusable Programs. Cambridge, MA: MIT Press.Google Scholar
Koza, J.R. (1994 b). Genetic Programming II Videotape: The Next Generation. Cambridge, MA: MIT Press.Google Scholar
Koza, J.R., Al-Sakran, S.H., & Jones, L.W. (2005). Automated re-invention of six patented optical lens systems using genetic programming. Proc. Genetic and Evolutionary Computation Conf. (GECCO–2005) (Beyer, H.-G., et al. Eds.), pp. 1953–1960. New York: ACM Press.Google Scholar
Koza, J.R., Banzhaf, W., Chellapilla, K., Deb, K., Dorigo, M., Fogel, D.B., Garzon, M.H., Goldberg, D.E., Iba, H., & Riolo, R. (Eds.). (1998). Genetic Programming 1998: Proc. 3rd Annual Conf. San Francisco, CA: Morgan Kaufmann.Google Scholar
Koza, J.R., Bennett, F.H. III, Andre, D., & Keane, M.A. (1996 a). Toward evolution of electronic animals using genetic programming. Artificial Life V: Proc. 5th Int. Workshop on the Synthesis and Simulation of Living Systems (Langton, C.G., & Shimohara, K., Eds.), pp. 327–334. Cambridge, MA: MIT Press.Google Scholar
Koza, J.R., Bennett, F.H. III, Andre, D., & Keane, M.A. (1996 b). Four problems for which a computer program evolved by genetic programming is competitive with human performance. Proc. 1996 IEEE Int. Conf. Evolutionary Computation, pp. 1–10. New York: IEEE Press.Google Scholar
Koza, J.R., Bennett, F.H. III, Andre, D., & Keane, M.A. (1996 c). Automated design of both the topology and sizing of analog electrical circuits using genetic programming. Proc. Artificial Intelligence in Design ’96 (Gero, J.S., & Sudweeks, F., Eds.), pp. 151–170. Dordrecht: Kluwer Academic.CrossRefGoogle Scholar
Koza, J.R., Bennett, F.H. III, Andre, D., & Keane, M.A. (1996 d). Automated WYWIWYG design of both the topology and component values of analog electrical circuits using genetic programming. Genetic Programming 1996: Proc. First Annual Conf. (Koza, J.R., Goldberg, D.E., Fogel, D.B., & Riolo, R.L., Eds.), pp. 123–131. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Koza, J.R., Bennett, F.H. III, Andre, D., & Keane, M.A. (1996 e). Reuse, parameterized reuse, and hierarchical reuse of substructures in evolving electrical circuits using genetic programming. Proc. Int. Conf. Evolvable Systems: From Biology to Hardware (ICES–96), Lecture Notes in Computer Science (Higuchi, T., Iwata, M., & Liu, W., Eds.), Vol. 1259, pp. 312–326. Berlin: Springer–Verlag.Google Scholar
Koza, J.R., Bennett, F.H. III, Andre, D., & Keane, M.A. (1999). Genetic Programming III: Darwinian Invention and Problem Solving. San Francisco, CA: Morgan Kaufmann.Google Scholar
Koza, J.R., Bennett, F.H. III, Andre, D., Keane, M.A., & Brave, S. (1999). Genetic Programming III Videotape: Human-Competitive Machine Intelligence. San Francisco, CA: Morgan Kaufmann.Google Scholar
Koza, J.R., Deb, K., Dorigo, M., Fogel, D.B., Garzon, M., Iba, H., & Riolo, R.L. (Eds.). (1997). Genetic Programming 1997: Proc. 2nd Annual Conf. San Francisco, CA: Morgan Kaufmann.Google Scholar
Koza, J.R., Goldberg, D.E., Fogel, D.B., & Riolo, R.L. (Eds.). (1996). Genetic Programming 1996: Proc. 1st Annual Conf. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Koza, J.R., Keane, M.A., & Streeter, M.J. (2003). Evolving inventions. Scientific America. 288(2), 52–59.CrossRefGoogle ScholarPubMed
Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., & Lanza, G. (2003). Genetic Programming IV: Routine Human-Competitive Machine Intelligence. New York: Kluwer Academic.Google Scholar
Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., Lanza, G., & Fletcher, D. (2003). Genetic Programming IV Video: Routine Human-Competitive Machine Intelligence. New York: Kluwer Academic.Google Scholar
Koza, J.R., Keane, M.A., Yu, J., Bennett, F.H. III, & Mydlowec, W. (2000). Automatic creation of human-competitive programs and controllers by means of genetic programming. Genetic Programming and Evolvable Machines 1, 121–164.CrossRefGoogle Scholar
Koza, J.R., & Rice, J.P. (1992). Genetic Programming: The Movie. Cambridge, MA: MIT Press.Google Scholar
Langdon, W.B. (1998). Genetic Programming and Data Structures: Genetic Programming + Data Structures = Automatic Programming! Amsterdam: Kluwer.CrossRefGoogle Scholar
Langdon, W.B., & Poli, R. (2002). Foundations of Genetic Programming. Berlin: Springer–Verlag.CrossRefGoogle Scholar
Lipson, H. (2004). How to draw a straight line using a GP: benchmarking evolutionary design against 19th century kinematic synthesis. Genetic and Evolutionary Conf. 2005 Late-Breaking Papers (Keijzer, M., Ed.). Seattle, WA: International Society for Genetic and Evolutionary Computation.Google Scholar
Lohn, J.D., Hornby, G.S., & Linden, D.S. (2004). An evolved antenna for deployment on NASA's Space Technology 5 Mission. In Genetic Programming Theory and Practice II (O'Reilly, U.-M., Riolo, R.L., Yu, G., & Worzel, W., Eds.), Chap. 18. Boston: Kluwer Academic.Google Scholar
Luke, S. (1998). Genetic programming produced competitive soccer softbot teams for RoboCup97. Genetic Programming 1998: Proc. Third Annual Conf. (Koza, J.R., et al. , Eds.), pp. 214–222. San Francisco, CA: Morgan Kaufmann.Google Scholar
Luke, S., & Spector, L. (1996). Evolving graphs and networks with edge encoding: Preliminary report. In Late-Breaking Papers at the Genetic Programming 1996 Conf. (Koza, J.R., Ed.), pp. 117–124. Stanford, CA: Stanford University Bookstore.Google Scholar
Nordin, P. (1997). Evolutionary Program Induction of Binary Machine Code and its Application. Munster, Germany: Krehl Verlag.Google Scholar
Ryan, C. (1999). Automatic Re-engineering of Software Using Genetic Programming. Amsterdam: Kluwer Academic.Google Scholar
Sims, K. (1994). Evolving 3D morphology and behavior by competition. Artificial Life IV: Proc. 4th Int. Workshop on the Synthesis and Simulation of Living Systems (Brooks, R., & Maes, P., Eds.), pp. 28–39. Cambridge, MA: MIT Press.Google Scholar
Smith, S.F. (1980). A learning system based on genetic adaptive algorithms. PhD Dissertation. University of Pittsburgh.Google Scholar
Spector, L. (2004). Automatic Quantum Computer Programming: A Genetic Programming Approach. Boston: Kluwer Academic.Google Scholar
Spector, L., Barnum, H., & Bernstein, H.J. (1998). Genetic programming for quantum computers. Genetic Programming 1998: Proc. 3rd Annual Conf. (Koza, J.R., et al. , Eds.), pp. 365–373. San Francisco, CA: Morgan Kaufmann.Google Scholar
Spector, L., Barnum, H., & Bernstein, H.J. (1999). Quantum computing applications of genetic programming. In Advances in Genetic Programming 3 (Spector, L., Langdon, W.B., O'Reilly, U.-M., & Angeline, P., Eds.), pp. 135–160. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Spector, L., Barnum, H., Bernstein, H.J., & Swamy, N. (1999). Finding a better-than-classical quantum AND/OR algorithm using genetic programming. IEEE Proc. 1999 Congr. Evolutionary Computation, pp. 2239–2246. Piscataway, NJ: IEEE Press.Google Scholar
Spector, L., Langdon, W.B., O'Reilly, U.-M., & Angeline, P. (Eds.). (1999). Advances in Genetic Programming 3. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Spector, L., & Stoffel, K. (1996 a). Ontogenetic programming. 1996. Genetic Programming 1996: Proc. 1st Annual Conf. (Koza, J.R., Goldberg, D.E., Fogel, D.B., & Riolo, R.L., Eds.), pp. 394–399. Cambridge, MA: MIT Press.Google Scholar
Spector, L., & Stoffel, K. (1996 b). Automatic generation of adaptive programs. From Animals to Animats 4: Proc. 4th Int. Conf. Simulation of Adaptive Behavior (Maes, P., Mataric, M.J., Meyer, J.-A., Pollack, J., & Wilson, S.W., Eds.), pp. 476–483. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Tunstel, E., & Jamshidi, M. (1996). On genetic programming of fuzzy rule-based systems for intelligent control. International Journal of Intelligent Automation and Soft Computing 2(3), 273–284.Google Scholar
Turing, A.M. (1948). Intelligent machinery. Reprinted in Ince, D.C. (Ed.). (1992). Mechanical Intelligence: Collected Works of A. M. Turing, pp. 107–127. Amsterdam: North Holland. Also reprinted in Meltzer B., & Michie D. (Eds.). (1969). Machine Intelligence 5. Edinburgh: Edinburgh University Press.Google Scholar
Turing, A.M. (1950). Computing machinery and intelligence. Mind 59(236), 433–460. Reprinted Ince D.C. (Ed.). (1992). Mechanical Intelligence: Collected Works of A. M. Turing, pp. 133–160. Amsterdam: North Holland.CrossRefGoogle Scholar
Whitley, D., Gruau, F., & Preatt, L. (1995). Cellular encoding applied to neurocontrol. Proc. 6th Int. Conf. Genetic Algorithms (Eshelman, L.J., Ed.), pp. 460–467. San Francisco, CA: Morgan Kaufmann.Google Scholar
Wilson, S.W. (1987). The genetic algorithm and biological development. Genetic Algorithms and Their Applications: Proc. 2nd Int. Conf. Genetic Algorithms (Grefenstette, J.J., Ed.), pp. 247–251. Hillsdale, NJ: Erlbaum.Google Scholar
Wong, M.L., & Leung, K.S. (2000). Data Mining Using Grammar Based Genetic Programming and Applications. Amsterdam: Kluwer Academic.Google Scholar
Yu, G., Worzel, W., & Riolo, R. (Eds.). 2005. Genetic Programming Theory and Practice III. New York: Springer.Google Scholar