36 Human-Competitive Results Produced by Genetic Programming

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

Creation of a quantum algorithm for the depth-two AND/OR query problem that is better than any previously published result

D

Spector, Barnum, Bernstein, and Swamy 1999; Barnum, Bernstein, and Spector 2000

4

Creation of a quantum algorithm for the depth-one OR query problem that is better than any previously published result

D

Barnum, Bernstein, and Spector 2000

5

Creation of a protocol for communicating information through a quantum gate that was previously thought not to permit such communication

D

Spector and Bernstein 2003

6

Creation of a novel variant of quantum dense coding

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

Creation of a soccer-playing program that ranked in the middle of the field of 34 human-written programs in the Robo Cup 1998 competition

H

Andre and Teller 1999

9

Creation of four different algorithms for the transmembrane segment identification problem for proteins

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

Rediscovery of the Cauer (elliptic) topology for filters

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

Rediscovery of a recognizable voltage gain stage and a Darlington emitter-follower section of an amplifier and other circuits

A, F

Section 42.3 of Genetic Programming III

16

Synthesis of 60 and 96 decibel amplifiers

A, F

Section 45.3 of Genetic Programming III

17

Synthesis of analog computational circuits for squaring, cubing, square root, cube root, logarithm, and Gaussian functions

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

Synthesis of an electronic thermometer

A, G

Section 49.3 of Genetic Programming III

20

Synthesis of a voltage reference circuit

A, G

Section 50.3 of Genetic Programming III

21

Creation of a cellular automata rule for the majority classification problem that is better than the Gacs-Kurdyumov-Levin (GKL) rule and all other known rules written by humans

D, E

Andre, Bennett, and Koza 1996 and section 58.4 of Genetic Programming III

22

Creation of motifs that detect the D–E–A–D box family of proteins and the manganese superoxide dismutase family

C

Section 59.8 of Genetic Programming III

23

Synthesis of topology for a PID-D2 (proportional, integrative, derivative, and second derivative) controller

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

Synthesis of a NAND circuit

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

Rediscovery of negative feedback

A, E, F, G

Chapter 14 of Genetic Programming IV

29

Synthesis of a low-voltage balun circuit

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

Synthesis of a high-current load circuit

A

Section 15.4.3 of Genetic Programming IV

32

Synthesis of a voltage-current conversion circuit

A

Section 15.4.4 of Genetic Programming IV

33

Synthesis of a cubic function generator

A

Section 15.4.5 of Genetic Programming IV

34

Synthesis of a tunable integrated active filter

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

Creation of three non-PID controllers that outperform a PID controller using the Ziegler-Nichols or Åström-Hägglund tuning rules

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