Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
1999-04-12
2003-03-11
Black, Thomas (Department: 2121)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
Reexamination Certificate
active
06532453
ABSTRACT:
FIELD OF THE INVENTION
The field of the invention is computer-implemented genetic algorithms; more particularly, the present invention relates to automatically creating computer programs to solve problems using computer-implemented genetic algorithms, including embodiments that use automatically defined stores, loops, and recursions.
BACKGROUND OF THE INVENTION
A central challenge of computer science is to get a computer to solve a complex problem without explicitly telling the computer how to do it (e.g., 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.
Genetic programming is an automatic technique that is capable of creating complex designs and structures, such as computer programs. Genetic programming approaches a problem in terms of “what needs to be done” as opposed to “how to do it.” For example, genetic programming has demonstrated that it is capable of generating computer programs from a given problem definition. Genetic programming creates a variety of computer programs because it employs a probabilistic process of natural selection to evolve computer constructs and because it is unencumbered by the preconceptions that often channel human thinking down familiar paths.
Genetic Algorithms
A genetic algorithm provides a method of improving a given set of objects. The processes of natural selection and survival of the fittest provide a theoretical base for the genetic algorithm. In
Adaptation in Artificial and Natural Systems
(MIT Press 1975), Professor John H. Holland presents a mathematical theory of adaptation for both natural and artificial systems. An important part of Holland's book describes a “genetic algorithm” patterned after nature's methods for biological adaptation. In a later work, Holland (1986) describes a classifier system that employs a genetic algorithm and a bucket brigade algorithm to solve problems. U.S. Pat. No. 4,697,242 (Holland et al.) and U.S. Pat. No. 4,881,178 (Holland et al.) describe classifier systems that use fixed length binary strings in conjunction with a genetic algorithm. The fixed length binary strings of a classifier represent IF-THEN rules.
Genetic Programming
“Genetic programming” (also called the “non-linear genetic algorithm” or the “hierarchical genetic algorithm” in previous years) is described in the book entitled
Genetic Programming: On the Programming of Computers by Means of Natural Selection
, Koza, John R., Cambridge, Mass.: The MIT Press, 1992, the book entitled
Genetic Programming II: Automatic Discovery of Reusable Programs
, Koza, John R., Cambridge, Mass.: The MIT Press, 1994, and in U.S. Pat. Nos. 4,935,877, 5,136,686, 5,148,513, 5,343,554, 5,742,738, and 5,867,397.
Genetic programming is referred to as “non-linear” or “hierarchical” because the original genetic algorithm described by Holland in 1975 operated on linear strings of characters (resembling chromosomes in nature), whereas genetic programming operates on hierarchical program trees of various sizes and shapes.
Genetic programming is capable of evolving computer programs that solve, or approximately solve, a variety of problems from a variety of fields. Genetic programming starts with a “primordial ooze” of randomly generated programs composed of the available programmatic ingredients and then applies the principles of animal husbandry to breed a new (and often improved) population of programs. Genetic programming performs the breeding in a domain-independent way using the Darwinian principle of survival of the fittest, an analog of the naturally-occurring genetic operation of crossover (sexual recombination), and occasional mutation. The crossover operation is designed to create syntactically valid offspring programs (given closure amongst the set of ingredients). Genetic programming combines the expressive high-level symbolic representations of computer programs with the near-optimal efficiency of improvement associated with Holland's genetic algorithm. A program that solves (or approximately solves) a given problem often emerges from this process.
As demonstrated in the book,
Genetic Programming II: Automatic Discovery of Reusable Programs
Koza, John R., Cambridge, Mass.: The MIT Press, 1994, genetic programming can evolve multi-part programs consisting of a main program and one or more reusable, parameterized, hierarchically-called subprograms (called automatically defined functions or ADFs).
A basic embodiment of genetic programming breeds computer programs to solve problems by executing the following steps:
(1) Generate an initial population of random compositions of the functions and terminals of the problem (i.e., computer programs).
(2) Iteratively perform the following substeps until the termination criterion has been satisfied:
(A) Execute each program in the population and assign it a fitness value using the fitness measure.
(B) Create a new population of computer programs by applying the following operations. The operations are applied to computer program(s) chosen from the population with a probability based on fitness.
(i) Reproduction: Copy an existing program to the new population.
(ii) Crossover: Create new offspring program(s) for the new population by recombining randomly chosen parts of two existing programs.
(iii) Mutation: Create one new offspring program for the new population by randomly mutating a randomly chosen part of one existing program.
(3) The program that is identified by the method of result designation (e.g., the best-so-far individual) is designated as the result of the genetic algorithm for the run. This result may be a solution (or an approximate solution) to the problem.
Other genetic programming processes may use additional operations such as “permutation,” “define building block” (also called “encapsulation”), or the architecture-altering operations discussed below.
Before applying genetic programming to a problem, the user must perform five major preparatory steps, as shown in FIG.
1
B. The preparatory steps of genetic programming are the user's way of communicating the high-level statement of the problem to the genetic programming system. The preparatory steps identify what the user provides to the genetic programming system before launching a run of genetic programming. The preparatory steps serve to unmistakably distinguish between what the user supplies to the genetic programming system and what the system delivers.
In one embodiment, the five major preparatory steps for genetic programming entail determining: (1) the set of terminals (e.g., the actual variables of the problem, zero-argument functions, and random constants, if any) for each branch of the to-be-evolved computer program; (2) the set of primitive functions for each to-be-evolved branch; (3) the fitness measure (or other arrangement for explicitly or implicitly measuring fitness); (4) the parameters for controlling the run; and (5) the termination criterion and the method of result designation for the run. In addition, when automatically defined operations are used, the architecture of the programs to be evolved must be determined in some way (not shown). A traditional approach is for the user to specify the architecture prior to the run of genetic programming. In this approach, the user performs an architecture-defining preparatory step prior to the run of genetic programming.
FIG. 1B
shows the results
115
of the preparatory steps as input to genetic programming
105
to produce a computer program
110
.
Before applying genetic programming to a problem, where a multi-part program is to be evolved, it is the user's responsibility to specify the architecture of the computer program. In one embodiment, the architecture of a computer program consists of the number of result-producing branches (which is just one for a one-output program), the number of function-defining branches with the number or arguments possessed by each fu
Andre David
Bennett, III Forrest H
Keane Martin A.
Koza John R.
Black Thomas
Blakely , Sokoloff, Taylor & Zafman LLP
Booker Kelvin
Koza John R.
LandOfFree
Genetic programming problem solver with automatically... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Genetic programming problem solver with automatically..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Genetic programming problem solver with automatically... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3033424