16 Attributes of a System for Automatic Programming
Genetic programming has 16 attributes of what is sometimes called automatic programming or program synthesis or program induction).
One of the central challenges of computer science is to get a computer to solve a problem without explicitly programming it. In particular, it would be desirable to have a problem-independent system whose input is a high-level statement of a problem's requirements and whose output is a working computer program that solves the given problem. Paraphrasing Arthur Samuel (1959), this challenge concerns
"How can computers be made to do what needs to be done, without being told exactly how to do it?"
Genetic programming is a biologically inspired, domain-independent method that automatically creates a computer program from a high-level statement of a problem's requirements. Starting with a primordial ooze of thousands of randomly created computer programs, genetic programming progressively breeds a population of computer programs over a series of generations. Genetic programming applies the Darwinian principle of survival of the fittest, analogs of naturally occurring operations such as sexual recombination (crossover), mutation, gene duplication, and gene deletion, and certain mechanisms of developmental biology.
When we talk about a computer program, we mean an entity that receives inputs, performs computations, and produces outputs. Computer programs perform basic arithmetic and conditional computations on variables of various types (including integer, floating-point, and Boolean variables), perform iterations and recursions, store intermediate results in memory, organize groups of operations into reusable subroutines, pass information to subroutines in the form of dummy variables (formal parameters), receive information from subroutines in the form of return values, and organize subroutines and a main program into a hierarchy.
We think that a system for automatically creating computer programs should create entities that possess most or all of the above essential features of computer programs (or reasonable equivalents thereof). A non-definitional list of attributes for a system for automatically creating computer programs would include the following 16 items:
Attribute No. 1 (Starts with "What needs to be done"): It starts from a high-level statement specifying the requirements of the problem.
Attribute No. 2 (Tells us "How to do it"): It produces a result in the form of a sequence of steps that can be executed on a computer.
Attribute No. 3 (Produces a computer program): It produces an entity that can run on a computer.
Attribute No. 4 (Automatic determination of program size): It has the ability to automatically determine the exact number of steps that must be performed and thus does not require the user to prespecify the size of the solution.
Attribute No. 5 (Code reuse): It has the ability to automatically organize useful groups of steps so that they can be reused.
Attribute No. 6 (Parameterized reuse): It has the ability to reuse groups of steps with different instantiations of values (formal parameters or dummy variables).
Attribute No. 7 (Internal storage): It has the ability to use internal storage in the form of single variables, vectors, matrices, arrays, stacks, queues, lists, relational memory, and other data structures.
Attribute No. 8 (Iterations, loops, and recursions): It has the ability to implement iterations, loops, and recursions.
Attribute No. 9 (Self-organization of hierarchies): It has the ability to automatically organize groups of steps into a hierarchy.
Attribute No. 10 (Automatic determination of program architecture): It has the ability to automatically determine whether to employ subroutines, iterations, loops, recursions, and internal storage, and the number of arguments possessed by each subroutine, iteration, loop, recursion.
Attribute No. 11 (Wide range of programming constructs): It has the ability to implement analogs of the programming constructs that human computer programmers find useful, including macros, libraries, typing, pointers, conditional operations, logical functions, integer functions, floating-point functions, complex-valued functions, multiple inputs, multiple outputs, and machine code instructions.
Attribute No. 12 (Well-defined): It operates in a well-defined way. It unmistakably distinguishes between what the user must provide and what the system delivers.
Attribute No. 13 (Problem-independent): It is problem-independent in the sense that the user does not have to modify the system's executable steps for each new problem.
Attribute No. 14 (Wide applicability): It produces a satisfactory solution to a wide variety of problems from many different fields.
Attribute No. 15 (Scalability): It scales well to larger versions of the same problem.
Attribute No. 16 (Competitive with human-produced results): It produces results that are competitive with those produced by human programmers, engineers, mathematicians, and designers.
The main point of the recent book, Genetic Programming III: Darwinian Invention and Problem Solving, and its accompanying videotape is that genetic programming currently unconditionally possesses 13 of the 16 attributes that can reasonably be expected of a system for automatically creating computer programs and that genetic programming at least partially possesses the last three attributes in the above list. The "Conclusion" of the book (chapter 64) inventories the results demonstrated in the book in relation to the degree to which genetic programming currently possesses the above 16 attributes.
Attribute No. 16 is especially important because it reminds us that the ultimate goal of a system for automatically creating computer programs is to produce useful programs not merely programs that solve "toy" or "proof of principle" problems. As Samuel (1983) said,
[T]he aim [is] ... to get machines to exhibit behavior, which if done by humans, would be assumed to involve the use of intelligence.
See human-competitive machine intelligence for a list of instances where genetic programming has automatically created a computer program that is competitive with a human-produced result.
Additional information on genetic programming can be found in the 1999 book Genetic Programming III: Darwinian Invention and Problem Solving and its accompanying videotape. Visit www.genetic-programming.org for citations and links to numerous other authored books, edited collections of papers, conference proceedings, and individual published papers concerning genetic programming.
· 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
Langdons 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 2630, 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