There are now 36 instances where genetic programming has produced a human-competitive result. Click here for the 8 criteria defining “human-competitive” These human-competitive results include 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. These human-competitive results come from the fields of computational molecular biology, cellular automata, sorting networks, and the synthesis of the design of both the topology and component sizing for complex structures, such as analog electrical circuits, controllers, and antenna.
The goal of getting computers to automatically solve problems is central to artificial intelligence, machine learning, and the broad area encompassed by what Turing called “machine intelligence” (Turing 1948, 1950). The goal is to get a computer to do what needs to be done, without telling it how to do it. The criterion for success was aptly stated by machine learning pioneer Arthur Samuel in his 1983 talk entitled “AI: Where It Has Been and Where It Is Going.”
“[T]he aim [is] ¼ to get machines to exhibit behavior, which if done by humans, would be assumed to involve the use of intelligence.”
Samuel’s criterion reflects the common goal articulated by the pioneers of the 1950s in the fields of artificial intelligence and machine learning. Indeed, getting machines to produce human-like results is the reason for the existence of the fields of artificial intelligence and machine learning. Genetic programming addresses this challenge by providing a method for automatically creating a working computer program from a high-level problem statement of the problem.
The table below lists 36 human-competitive instances (of which we are aware) where genetic programming has produced human-competitive results. Each entry in the table is accompanied by the criteria that establish the basis for the claim of human-competitiveness. Click here for the 8 criteria defining “human-competitive” Twenty-three of the instances in the table below involve patents (as indicated by an “A” in column 3). Eleven of the automatically created results infringe previously issued patents and 10 duplicate the functionality of previously patented inventions in a non-infringing way. The 29th through 34th entries in the table below relate to patents for analog circuits that were issued after January 1, 2000. Referring to the table, 21 of the results relate to previously patented inventions, thus making genetic programming an automated invention machine.
|
|
Claimed instance |
Basis for claim of human-competitiveness |
Reference |
|
1 |
Creation of
a better-than-classical quantum algorithm
for the Deutsch-Jozsa “early promise” problem |
B, F |
Spector, Barnum, and Bernstein 1998 |
|
2 |
Creation of a
better-than-classical quantum algorithm
for Grover’s database search problem |
B, F |
Spector, Barnum, and Bernstein 1999 |
|
3 |
D |
Spector, Barnum, Bernstein, and Swamy 1999; Barnum, Bernstein, and Spector 2000 |
|
|
4 |
D |
Barnum, Bernstein, and Spector 2000 |
|
|
5 |
D |
Spector and Bernstein 2003 |
|
|
6 |
D |
Spector and Bernstein 2003 |
|
|
7 |
Creation of a
soccer-playing program that won its first two games in the Robo Cup 1997
competition |
H |
Luke 1998 |
|
8 |
H |
Andre and Teller 1999 |
|
|
9 |
B, E |
Sections 18.8 and 18.10 of Genetic Programming II and sections 16.5 and 17.2 of Genetic Programming III |
|
|
10 |
Creation of a
sorting network for seven items using only 16 steps |
A, D |
Sections 21.4.4, 23.6, and 57.8.1 of Genetic Programming III |
|
11 |
Rediscovery of the
Campbell ladder topology for lowpass and highpass filters |
A, F |
Section 25.15.1 of Genetic Programming III and section 5.2 of Genetic Programming IV |
|
12 |
Rediscovery
of the Zobel “M-derived half
section” and “constant K” filter
sections |
A, F |
Section 25.15.2 of Genetic Programming III |
|
13 |
A, F |
Section 27.3.7 of Genetic Programming III |
|
|
14 |
Automatic
decomposition of the problem of synthesizing a crossover filter |
A, F |
Section 32.3 of Genetic Programming III |
|
15 |
A, F |
Section 42.3 of Genetic Programming III |
|
|
16 |
A, F |
Section 45.3 of Genetic Programming III |
|
|
17 |
A, D, G |
Section 47.5.3 of Genetic Programming III |
|
|
18 |
Synthesis
of a real-time analog circuit for time-optimal control of a robot |
G |
Section 48.3 of Genetic Programming III |
|
19 |
A, G |
Section 49.3 of Genetic Programming III |
|
|
20 |
A, G |
Section 50.3 of Genetic Programming III |
|
|
21 |
D, E |
Andre, Bennett, and Koza 1996 and section 58.4 of Genetic Programming III |
|
|
22 |
C |
Section 59.8 of Genetic Programming III |
|
|
23 |
A, F |
Section 3.7 of Genetic
Programming IV |
|
|
24 |
Synthesis of an
analog circuit equivalent to Philbrick circuit |
A, F |
Section 4.3 of Genetic
Programming IV |
|
25 |
A, F |
Section 4.4 of Genetic
Programming IV |
|
|
26 |
Simultaneous
synthesis of topology, sizing, placement, and routing of analog electrical
circuits |
A. F, G |
Chapter 5 of Genetic
Programming IV |
|
27 |
Synthesis of topology
for a PID (proportional, integrative, and
derivative) controller |
A, F |
Section 9.2 of Genetic Programming IV |
|
28 |
A, E, F, G |
Chapter 14 of Genetic
Programming IV |
|
|
29 |
A |
Section 15.4.1 of Genetic
Programming IV |
|
|
30 |
Synthesis
of a mixed analog-digital variable capacitor circuit |
A |
Section 15.4.2 of Genetic Programming IV |
|
31 |
A |
Section 15.4.3 of Genetic Programming IV |
|
|
32 |
A |
Section 15.4.4 of Genetic Programming IV |
|
|
33 |
A |
Section 15.4.5 of Genetic Programming IV |
|
|
34 |
A |
Section 15.4.6 of Genetic Programming IV |
|
|
35 |
Creation of
PID tuning rules that outperform the Ziegler-Nichols and Åström-Hägglund
tuning rules |
A, B, D, E, F, G |
Chapter 12 of Genetic Programming IV |
|
36 |
A, B, D, E, F, G |
Chapter 13 of Genetic Programming IV |
· The home page of Genetic Programming Inc. at www.genetic-programming.com.
· For information about the field of genetic programming and the field of genetic and evolutionary computation, visit www.genetic-programming.org
· The home page of John R. Koza at Genetic Programming Inc. (including online versions of most published papers) and the home page of John R. Koza at Stanford University
· For information about John Koza’s course on genetic algorithms and genetic programming at Stanford University
· 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.
· 3,440
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 published by Kluwer Academic Publishers
· For information on the Genetic Programming book series from Kluwer Academic Publishers, see the Call For Book Proposals
· For information about the annual Genetic and Evolutionary Computation (GECCO) conference (which includes the annual GP conference) to be held on June 26–30, 2004 (Saturday – Wednesday) in Seattle and its sponsoring organization, the International Society for Genetic and Evolutionary Computation (ISGEC). For information about the annual Euro-Genetic-Programming Conference to be held on April 5-7, 2004 (Monday – Wednesday) at the University of Coimbra in Coimbra Portugal. For information about the 2003 and 2004 Genetic Programming Theory and Practice (GPTP) workshops held at the University of Michigan in Ann Arbor. For information about Asia-Pacific Workshop on Genetic Programming (ASPGP03) held in Canberra, Australia on December 8, 2003. For information about the annual NASA/DoD Conference on Evolvable Hardware Conference (EH) to be held on June 24-26 (Thursday-Saturday), 2004 in Seattle.
Last updated on December 30, 2003