Welcome to

www.genetic-programming.org

(a source of information about the field of genetic programming and the field of genetic and evolutionary computation)

Last updated July 8, 2007

Job for scientific research programmer at Genetic Programming Inc. (posted July 8, 2007)

Genetic programming (GP) is an automated method for creating a working computer program from a high-level problem statement of a problem. Genetic programming starts from a high-level statement of “what needs to be done” and automatically creates a computer program to solve the problem.

There are now 36 instances where genetic programming has automatically produced a result that is competitive with human performance, including  15 instances where genetic programming has created an entity that either infringes or duplicates the functionality of a previously patented 20th-century invention, 6 instances where genetic programming has done the same with respect to a 21st-centry invention, and 2 instances where genetic programming has created a patentable new invention.

Given these results, we say that “Genetic programming now routinely delivers high-return human-competitive machine intelligence.” Click here for our definitions of “human-competitive,”  ”high return” and the “AI ratio” (“artificial-to-intelligence” ratio),  “routine,” and “machine intelligence.” This statement is the most important point of the 2003 book Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Click here to read chapter 1 of Genetic Programming IV in PDF format.  Click here for 2004 awards for human-competitive results (based on presentations at the GECCO-2004 conference in Seattle on June 27, 2004).

The fact that genetic programming can evolve entities that are competitive with human-produced results suggests that genetic programming can be used as an automated invention machine to create new and useful patentable inventions. In acting as an invention machine, evolutionary methods, such as genetic programming, have the advantage of not being encumbered by preconceptions that limit human problem-solving to well-troden paths. Genetic programming has delivered a progression of qualitatively more substantial results in synchrony with five approximately order-of-magnitude increases in the expenditure of computer time (over the 15-year period from 1987 to 2002).

Genetic programming has 16 important attributes that one would reasonably expect of a system for automatic programming (sometimes also called program synthesis or program induction). Genetic programming has seven important differences from conventional approaches to artificial intelligence (AI) and machine learning (ML). For additional information, click here for PowerPoint (PPT) presentation on genetic programming (about 5 Megabytes) similar to that presented at the 2003 Accelerating Change Conference on September 13, 2003 and similar to the overview lecture given on September 24, 2003 in John Koza’s course at Stanford University on genetic algorithms (GA) and genetic programming (GP).

How Genetic Programming (GP) Works

Genetic programming starts with a primordial ooze of thousands of randomly created computer programs. This population of programs is progressively evolved over a series of generations. The evolutionary search uses the Darwinian principle of natural selection (survival of the fittest) and analogs of various naturally occurring operations, including crossover (sexual recombination), mutation, gene duplication, gene deletion. Genetic programming sometimes also employs developmental processes by which an embryo grows into fully developed organism. Old Chinese saying says “animated gif is worth one mega-word,” so click here for short tutorial of “What is GP?” including about two dozen animated gifs. This short tutorial contains a discussion of the preparatory steps of a run of genetic programming, the executional steps (that is, the flowchart of genetic programming), an illustrative simple run of genetic programming for a problem of symbolic regression of a quadratic polynomial, a discussion of developmental genetic programming for the automatic synthesis of both the topology and sizing of analog electrical circuits (potentially also including placement and routing), and the use of a turtle to draw complex structures (such as antenna). In addition, genetic programming can automatically create, in a single run, a general (parameterized) solution to a problem in the form of a graphical structure whose nodes or edges represent components and where the parameter values of the components are specified by mathematical expressions containing free variables. That is, genetic programming can automatically create a general solution to a problem in the form of a parameterized topology.

Information about the Field of Genetic Programming (GP) and the Field of Genetic and Evolutionary Computation (GEC)

The technique of genetic programming (GP) is one of the techniques of the field of genetic and evolutionary computation (GEC) which, in turn, includes techniques such as genetic algorithms (GA), evolution strategies (ES), evolutionary programming (EP), grammatical evolution (GE), and machine code (linear genome) genetic programming.

Conferences about Genetic Programming (GP) and Genetic and Evolutionary Computation (GEC)

  • Past GP conferences for 1996, 1997, and 1998 (including the SGA-98, the Symposium on Genetic Algorithms)
  • Past Euro-GP conferences for 1998, 1999, 2000, 2001, 2002, and 2003
  • Past GECCO conferences (Genetic and Evolutionary Computation Conferences) for 1999, 2000, 2001, 2002, 2003, and 2004. Starting in 1999, the annual GECCO conference includes the annual Genetic Programming Conference

News about Genetic Programming

· For May 2003 IEEE Intelligent Systems article “What’s AI done for me lately? Genetic programming’s human-competitive results”, visit IEEE Intelligent Systems. Click here for PDF file.

· For February 2003 Scientific American article “Evolving inventions” on genetic programming by John Koza, Martin A. Keane, and Matthew J. Streeter, visit Scientific American.

· For Salon article on "Software that Writes Software" by Alexis Willihnganz (August 10, 1999)

· For E. E. Times article on automatic synthesis of analog electrical circuits using genetic programming.

· For article in Computerbits on genetic programming.

· For Scientific American article by W. Wayt Gibbs on genetic programming.

· For Business Week article (June 23, 1997) entitled "Stanford Eggheads and Entrepreneurs"

· For Business Week article (August 25, 1997) entitled "What Matters is How Smart You Are"

· For U. S. News and World Report article on evolutionary computation and genetic programming.

· For Slashdot.org posting (August 10, 1999).

· For the451.com article entitled "Re-inventing the 'invention machine" (April 14, 2000).

Applications of Genetic Programming

There are numerous applications of genetic programming including

  • “black art” problems, such as the automated synthesis of analog electrical circuits, controllers, antennas, networks of chemical reactions, and other areas of design,
  • “programming the unprogrammable” (PTU) involving the automatic creation of computer programs for unconventional computing devices such as cellular automata, multi-agent systems, parallel systems, field-programmable gate arrays, field-programmable analog arrays, ant colonies, swarm intelligence, distributed systems, and the like,
  • “commercially usable new inventions” (CUNI) involving the use of genetic programming as an automated "invention machine" for creating commercially usable new inventions, and

We are constantly looking for new domain areas in which to apply the techniques of genetic programming to achieve human-competitive machine intelligence.

Parallelization of Genetic Programming

In July 1999, Genetic Programming Inc. started operating a new 1,000-node Beowulf-style parallel cluster computer consisting of 1,000 Pentium II 350 MHz processors and a host computer. Click here for technical discussion of parallel genetic programming and building the 1,000-Pentium Beowulf-style parallel cluster computer. About half of the 36 human-competitive results produced by genetic programming were obtained using computing systems that were substantially smaller than the 1,000-Pentium computer mentioned above. Fifteen of these human-competitive results were obtained on a 1995-vintage parallel computer system composed of 64 PowerPC 80 MHz processors with a spec95fp rating. This 1995-vintage computer has total computational power equal to only about 1/60 of that of the 1000-Pentium machine mentioned above. Five of these results were obtained on a 70-Alpha machine (whose spec95fp rating is 1/9 of that of the 1,000-Pentium machine mentioned above). One of these human competitive results were obtained with a 1994-vintage machine (whose spec95fp rating is 1/1,320 of that of the 1,000-Pentium machine mentioned above). The individual processors in the1,000-Pentium machine have (as of July 2003) about 1/8 the speed of processors contained in commercially available $999 laptops, so that the 1,000-Pentium machine is approximately equivalent to a 125-processor machine with 2003-vintage processors.

1000-Pentium Beowulf-Style Cluster Computer

(left and right sides) (July 29, 1999)

 

For picture of uninterruptable power supply (UPS) for new 1000-Pentium computer. Design and contracting of site for 1000-Pentium computer by Gordon Prill Inc. of Mountain View, California. The 1,000-Pentium machine was assembled by Stan Fox of the COMPAQ Sunnyvale Staging Center. For picture of earlier 70-node parallel computer with Senator Barbara Boxer (California), John Koza (back row), Oscar Stiffelman (front row), Forrest H Bennett III, and William Mydlowec. For picture of earlier 70-node parallel computer with Ellen Goldberg (President of Santa Fe Institute), John Koza, Forrest H Bennett III, and Oscar Stiffelman.

John Koza Publications on Genetic Programming

  • 2003 book Genetic Programming IV: Routine Human-Competitive Machine Intelligence from Kluwer Academic Publishers (by John R. Koza, Martin A. Keane, Matthew J. Streeter, William Mydlowec, Jessen Yu, and Guido Lanza ) (ISBN 1-4020-7446-8) Kluwer Academic Publisher also publishes a DVD disk Genetic Programming IV: Video: Routine Human-Competitive Machine Intelligence (by John R. Koza, Martin A. Keane, Matthew J. Streeter, William Mydlowec, Jessen Yu, Guido Lanza, and David Fletcher) that is bound into this 2003 book.

  • Stanford University technical reports from the Computer Science Department and Stanford BioMedical Informatics of which I am author or co-author can be obtained on the web, including
    • STAN-TR-CS 1314 (1990) entitled Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems
    • STAN-TR-CS 1528 (1994) entitled Architecture-Altering Operations for Evolving the Architecture of a Multi-Part Program in Genetic Programming
    • STAN-TR-CS 1542 (1995) entitled Parallel Genetic Programming on a Network of Transputers
    • SMI-95-0586 (1995) entitled A Programming Course in Bioinformatics for Computer and Information Science Students
    • SMI-2000-0851 (2000) entitled Reverse Engineering and Automatic Synthesis of Metabolic Pathways from Observed Data Using Genetic Programming

Click here for list of patents.

Please send corrections or additions to this page to:

John R. Koza

Post Office Box K

Los Altos, California 94023 USA

OFFICE PHONE: 650-960-8180

FAX: 650-941-9430

E-mail: koza@stanford.edu

E-mail: koza@genetic-programming.com

E-mail: koza@genetic-programming.org

· For information about the annual Genetic and Evolutionary Computation Conference (GECCO) operated by the Association for Computing Special Interest Group on Genetic and Evolutionary Computation (SIGEVO)

· For information about the annual Human-Competitive Awards (the “humies”) in genetic and evolutionary computation offered at the annual Genetic and Evolutionary Computation Conference (GECCO)

· The home page of Genetic Programming Inc. at www.genetic-programming.com.

· The home page of John R. Koza (including online versions of most published papers)

· For information about John Koza’s course on genetic algorithms and genetic programming at Stanford University

· For information about National Popular Vote

· Information about the 1992 book Genetic Programming: On the Programming of Computers by Means of Natural Selection, the 1994 book Genetic Programming II: Automatic Discovery of Reusable Programs, the 1999 book Genetic Programming III: Darwinian Invention and Problem Solving, and the 2003 book Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Click here to read chapter 1 of Genetic Programming IV book in PDF format.

· 4,000+ published papers on genetic programming (as of November 28, 2003) in a searchable bibliography (with many on-line versions of papers) by over 880 authors maintained by William Langdon’s and Steven M. Gustafson.

· For information on the Genetic Programming and Evolvable Machines journal

· For information on the Genetic Programming book series, see the Call For Book Proposals