36 Human-Competitive Results Produced by Genetic Programming

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 20^th-century invention, 6 instances where genetic programming has done the same with respect to a 21^st-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 29^th through 34^th 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