Progression of Qualitatively More Substantial Results Produced by Genetic Programming

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.

Numerous questions naturally arise in connection with any proposed approach to machine intelligence.

· Is the method formulated with sufficient precision to enable it to be implemented (or is it vagueware)?

· Has the method been successfully demonstrated on a specific single problem (or is it promiseware)?

· Was the method applied to a difficult demonstrative problem (or is it toyware)?

· Did the method top out after succeeding on a single demonstrative problem?

· Has the method solved multiple problems (or is it soloware)?

· Are the multiple problems difficult?

· Did the method top out at this stage?

· Has the method solved problems from multiple domains (or is it nicheware)?

· Are the domains difficult?

· Did the method top out at this stage?

· Were the results human-competitive?

· Can the method profitably take advantage of the increased computational power available by means of parallel processing (or is it serialware)?

· Or, is the method Mooreware—able to take advantage of the exponentially increasing computational power made available by the relentless iteration of Moore’s law?

The 1992 book Genetic Programming: On the Programming of Computers by Means of Natural Selection demonstrated that genetic programming is not vagueware, promiseware, soloware, or nicheware.

The numerous human-competitive results discussed in the 2003 book Genetic Programming IV: Routine Human-Competitive Machine Intelligence establish that it is not toyware.

Table 1 provides a historical perspective on the progression of results produced by genetic programming over the 15-year period between 1987 and 2002. Table 1 lists the five computer systems used to produce our group’s reported work on genetic programming in the 15-year period between 1987 and 2002. Column 7 shows the number of human-competitive results generated by each computer system.

Table 1 Summary of Human-competitive results produced by genetic programming

System	Period of usage	Petacycles (10^15cycles) per day for entire system	Speed-up over previous system	Speed-up over first system in this table	Used for work in book	Human-competitive results
Serial Texas Instruments LISP machine	1987–1994	0.00216	1 (base)	1 (base)	Genetic Programming I and Genetic Programming II	0
64-node Transtech transputer parallel machine	1994–1997	0.02	9	9	A few problems in Genetic Programming III	2
64-node Parsytec parallel machine	1995–2000	0.44	22	204	Most problems in Genetic Programming III	12
70-node Alpha parallel machine	1999–2001	3.2	7.3	1,481	A minority (8) of problems in this book	2
1,000-node Pentium II parallel machine	2000–2002	30.0	9.4	13,900	A majority (28) of the problems in this book	12

The first entry in table 1 is a serial computer. The four subsequent entries are parallel computer systems. The presence of four increasingly powerful parallel computer systems in the table reflects the fact that genetic programming has successfully taken advantage of the increased computational power available by means of parallel processing. That is, genetic programming is not serialware.

Table 1 shows the following:

· There is an order-of-magnitude speed-up (column 4) between each successive computer system in the table. Note that, according to Moore’s law (Moore 1996), exponential increases in computer power correspond approximately to constant periods of time.

· There is a 13,900-to-1 speed-up (column 5) between the fastest and most recent machine (the 1,000-node parallel computer system used for most of the work in this book) and the slowest and earliest computer system in the table (the serial LISP machine).

· The slower early machines generated few or no human-competitive results, whereas the faster more recent machines have generated numerous human-competitive results.

Four successive order-of-magnitude increases in computer power are explicitly shown in table 1. An additional order-of-magnitude increase was achieved by making extraordinarily long runs on the largest machine in the table (the 1,000-node Pentium II parallel machine). The length of the run that produced one of genetically evolved patentable new inventions (a controller) was 28.8 days—almost an order-of-magnitude increase (9.3 times) over the 3.4-day average for other problems described in the 2003 book Genetic Programming IV: Routine Human-Competitive Machine Intelligence. A patent application was filed for the controller produced by this four-week run (Keane, Koza, and Streeter 2002). This genetically evolved controller outperforms controllers employing the widely used Ziegler-Nichols tuning rules and the recently developed Åström-Hägglund tuning rules. If this final 9.3-to-1 increase is counted as an additional speed-up, the overall speed-up between the first and last entries in table 2 is 130,660-to-1.

Table 2 is organized around the five just-explained order-of-magnitude increases in the expenditure of computing power. Column 4 of table 2 characterizes the qualitative nature of the results produced by genetic programming. The table shows the progression of qualitatively more substantial results produced by genetic programming in terms of five order-of-magnitude increases in the expenditure of computational resources.

Table 2 Progression of qualitatively more substantial results produced by genetic programming in relation to five order-of-magnitude increases in computational power

System	Period of usage	Speed-up over previous row in this table	Qualitative nature of the results produced by genetic programming
Serial Texas Instruments LISP machine	1987–1994	1 (base)	· Toy problems of the 1980s and early 1990s from the fields of artificial intelligence and machine learning
64-node Transtech transputer parallel machine	1994–1997	9	·Two human-competitive results involving one-dimensional discrete data (not patent-related)
64-node Parsytec parallel machine	1995–2000	22	· One human-competitive result involving two-dimensional discrete data · Numerous human-competitive results involving continuous signals analyzed in the frequency domain · Numerous human-competitive results involving 20^th-century patented inventions
70-node Alpha parallel machine	1999–2001	7.3	· One human-competitive result involving continuous signals analyzed in the time domain · Circuit synthesis extended from topology and sizing to include routing and placement (layout)
1,000-node Pentium II parallel machine	2000–2002	9.4	· Numerous human-competitive results involving continuous signals analyzed in the time domain · Numerous general solutions to problems in the form of parameterized topologies · Six human-competitive results duplicating the functionality of 21^st-century patented inventions
Long (4-week) runs of 1,000-node Pentium II parallel machine	2002	9.3	· Generation of two patentable new inventions

The order-of-magnitude increases in computer power shown in table 2 correspond closely (albeit not perfectly) with the following progression of qualitatively more substantial results produced by genetic programming:

· toy problems,

· human-competitive results not related to patented inventions,

· 20^th-century patented inventions,

· 21^st-century patented inventions, and

· patentable new inventions.

In other words, genetic programming is able to take advantage of the exponentially increasing computational power made available by iterations of Moore’s law—that is, it is Mooreware.

---

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

· For information about the field of genetic programming in general, visit www.genetic-programming.org

· The home page of John R. Koza at Genetic Programming Inc. (including online versions of most papers) and the home page of John R. Koza 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.

· For information on 3,198 papers (many on-line) on genetic programming (as of June 27, 2003) by over 900 authors, see William Langdon’s bibliography on genetic programming.

· 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 NASA/DoD Conference on Evolvable Hardware Conference (EH) to be held on June 24-26 (Thursday-Saturday), 2004 in Seattle. 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.

---

Last updated on August 27, 2003

---