Genetic Programming III: Darwinian Invention and Problem Solving

by

John R. Koza (Stanford University)

Forrest H Bennett III (Genetic Programming Inc.)

David Andre (University of California at Berkeley)

Martin A. Keane (Econometrics Inc.)


Published 1999

ISBN 1-55860-543-6

From Morgan Kaufmann Publishers

Order Genetic Programming III directly from Amazon Books now!


"Koza, Bennett, Andre, and Keane's evolutionary algorithm builds more complex and useful structures than the other approaches to computer learning that I have seen." ¾ John McCarthy, Computer Science Department, Stanford University

 

"John Koza and his co-authors continue their relentless pursuit of a holy grail in computer science: automatic programming." ¾ Moshe Sipper, Swiss Federal Institute of Technology (EFTL), Lausanne

 

"John Koza and colleagues have demonstrated that genetic programming can be used to search highly discontinuous spaces and thereby find amazing solutions to practical engineering problems." ¾ Bernard Widrow, Dept. of Electrical Engineering, Stanford University

 

"In this impressive volume, the authors demonstrate that genetic programming is more than an intriguing idea --it is a practical synthesis method for solving hard problems." ¾ Nils J. Nilsson, Computer Science Department, Stanford University

 

"Through careful experiment, keen algorithmic intuition, and relentless application the authors deliver important results that rival those achieved by human designers." ¾ David E. Goldberg, University of Illinois at Urbana-Champaign.


Genetic programming is a method for getting a computer to automatically solve a problem by telling it "what needs to be done" instead of "how to do it."

This new book presents genetically evolved solutions to dozens of problems of optimal control, classification, system identification, function learning, computational molecular biology, and analog electrical circuit design ¾ including filters, amplifiers, computational circuits, source identification circuits, a robot controller circuit, a temperature-measuring circuit, and a voltage reference circuit.

Fourteen of the results are competitive with human-produced results. Ten infringe on previously issued patents or duplicate the functionality of previous patents in novel and creative ways.

· Demonstrates that genetic programming possesses 16 attributes that can reasonably be expected of a system for automatically creating computer programs

· Presents the general-purpose Genetic Programming Problem Solver (GPPS)

· Describes how genetic programming solves a problem by making on-the-fly decisions on whether to use subroutines, loops, recursions, and memory

· Explains how the success of genetic programming arises from seven fundamental differences distinguishing it from conventional approaches to artificial intelligence and machine learning

· Describes the implementation of genetic programming on a parallel computer

· Introduces evolvable hardware in the form of field-programmable gate arrays

Includes an introduction to genetic programming


Click here for information about the accompanying videotape Genetic Programming III Videotape: Human Competitive Machine Intelligence .


For picture of 4 authors of Genetic Programming III: Darwinian Invention and Problem Solving. For picture of Scott Brave (co-author of videotape Genetic Programming III Videotape: Human Competitive Machine Intelligence).


High-Level Table of Contents of the book

I. Introduction
II. Background
III.  Architecture-Altering Operations
IV. Genetic Programming Problem Solver (GPPS)
V.  Automated Synthesis of Analog Electrical Circuits
VI.  Evolvable Hardware
VII.  Discovery of  Cellular Automata Rules
VIII. Discovery of Motifs and Programmatic Motifs for Molecular Biology
IX.  Parallelization and Implementation Issues
X.  Conclusion
 
Appendix A: Acronyms and Abbreviations
Appendix B: Special Symbols
Appendix C: Special Functions
Appendix D: Default Parameters
Appendix E: SPICE Transistor Models
Appendix F: Fonts
 
Bibliography

Part-Level + Chapter-Level Table of Contents of the book

 
I. Introduction
1.Introduction
II. Background
2.Background
III.  Architecture-Altering Operations
3.Previous Methods of Determining the Architecture of a Multi-Part Program
4.  On the Origin of New Functions
5.Architecture-Altering Operations for Subroutines
6.Automatically Defined Iterations
7.Automatically Defined Loops
8.Automatically Defined Recursion
9.Automatically Defined Storage
10.Self-Organization of Hierarchies and Program Architecture
11.Rotating the Tires on an Automobile
12.Boolean Parity Problem using Architecture-Altering Operations for Subroutines
13.Time-Optimal Robot Control Problem using Architecture-Altering Operations for Subroutines
14.Multi-Agent Problem using Architecture-Altering Operations for Subroutines
15.Digit Recognition Problem using Architecture-Altering Operations for Subroutines
16.Transmembrane Segment Identification Problem using Architecture-Altering Operations for Subroutines
17.Transmembrane Segment Identification Problem using Architecture-Altering Operations for Iterations
18.Fibonacci Sequence
19.Cart Centering
IV. Genetic Programming Problem Solver (GPPS)
20.Elements of GPPS 1.0
21.Three Problems Illustrating GPPS 1.0
22.Elements of GPPS 2.0
23.Six Problems Illustrating GPPS 2.0
24.Previous Work on Automated Analog Circuit Synthesis
V.  Automated Synthesis of Analog Electrical Circuits
25.Synthesis of a Lowpass Filter
26.Synthesis of a Highpass Filter
27.Synthesis of a Lowpass Filter Using Automatically Defined Functions
28.Synthesis of a Lowpass Filter Using Architecture-Altering Operations
29.Embryos and Test Fixtures
30.Synthesis of a Lowpass Filter Using Automatically Defined Copy
31.Synthesis of an Asymmetric Bandpass Filter
32.Synthesis of a Two-Band Crossover (Woofer-Tweeter) Filter
33.Synthesis of a Two-Band Crossover (Woofer-Tweeter) Filter Using Architecture-Altering Operations
34.Synthesis of a Three-Band Crossover (Woofer-Midrange-Tweeter) Filter
35.Synthesis of a Double Bandpass Filter Using Subcircuits
36.Synthesis of a Double Bandpass Filter Using Architecture-Altering Operations
37.Synthesis of Butterworth, Chebychev, and Elliptic Filters
38.Synthesis of a Three-Way Source Identification Circuit
39.Synthesis of a Source Identification Circuit with a Changing Number of Sources
40.Lowpass Filter with Parsimony
41.Complete Repertoire of Circuit-Constructing Functions
42.Synthesis of a 10 dB Amplifier Using Transistors
43.Synthesis of a 40 dB Amplifier
44.Synthesis of a 60 dB Amplifier
45.Synthesis of a 96 dB Amplifier with Architecture-Altering Operations
46.Synthesis of an Amplifier with a High Power Supply Rejection Ratio
47.Synthesis of Computational Circuits
48.Synthesis of a Real-Time Robot Controller Circuit with Architecture-Altering Operations
49.Synthesis of a Temperature-Sensing Circuit
50.Synthesis of a Voltage Reference Circuit
51.Synthesis of a MOSFET Circuit
52.Constraints Involving Subcircuits or Topologies
53.Minimal Embryo
54.Comparative Experiments Involving the Lowpass Filter
55.Comparative Experiments Involving the Lowpass Filter and the Automatically Defined Copy
56.The Role of Crossover in Genetic Programming
VI.  Evolvable Hardware
57.Evolvable Hardware and Rapidly Reconfigurable Field-Programmable Gate Arrays
VII.  Discovery of  Cellular Automata Rules
58.Discovery of a Cellular Automata Rule for the Majority Classification Problem
VIII. Discovery of Motifs and Programmatic Motifs for Molecular Biology
59.Automatic Discovery of Protein Motifs
60.Programmatic Motifs and the Cellular Location Problem
IX.  Parallelization and Implementation Issues
61.Computer Time
62.Parallelization of Genetic Programming
63.Implementation Issues
X.  Conclusion
64.Conclusion
 
Appendix A: Acronyms and Abbreviations
Appendix B: Special Symbols
Appendix C: Special Functions
Appendix D: Default Parameters
Appendix E: SPICE Transistor Models
Appendix F: Fonts
 
Bibliography

Book available from

Morgan Kaufmann Publishers

340 Pine Street - 6th Floor

San Francisco, CA 94104 USA

Toll-Free Phone: 800-745-7323

Phone: 415-392-2665.

E-MAIL: mkp@mkp.com

URL: www.mkp.com

1,154 pages - 703 figures

ISBN 1-55860-543-6

Published 1999


Last updated July 30, 2003


· 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.

· 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 on annual GECCO conference (which includes the annual GP conference) on June 26–30, 2004 (Saturday – Wednesday) in Seattle, visit the International Society for Genetic and Evolutionary Computation (ISGEC).

· For information on the annual Euro-Genetic-Programming Conference to be held on April 5-7, 2004 (Monday – Wednesday) at the University of Coimbra in Coimbra Portugal, visit http://www.evonet.info/eurogp2004/