Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
1998-08-31
2001-12-04
Powell, Mark R. (Department: 2122)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
Reexamination Certificate
active
06327582
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computing systems for discovering efficient programs through genetic programming techniques. More specifically, the invention combines genetic algorithms with graph reduction techniques to produce a computing system which permits the efficient evolution of programs for solving problems whose input is known and which have a function for determining whether one program is better than another.
BACKGROUND OF THE INVENTION
Most computers built today are of a type known as von Neumann machines. These computers require the transfer of data from memory locations, usually identified by some address or label, to a central processor unit (CPU) where some operation is applied to the data. Often, the data is moved again, either back to its original location or to another memory location. This constant movement of data is inefficient and limits the ability to make a truly parallel machine.
Lambda calculus represents another way to manipulate information to obtain desired results. In lambda calculus, special “lambda expressions” are created to describe a system which closely links data to functions. By using these lambda expressions, a universal programming machine can be constructed which produces results equivalent to those produced by von Neumann machines.
An article written by D. A. Turner (“A New Implementation Technique for Applicative Languages”,
Software—Practice and Experience, vol.
9, no. 1, pp. 31-49, 1979) describes a method of constructing a computing system by abstracting lambda expressions to a simpler and more powerful form called combinators. Combinators were first described by Schonfinkel and Curry in the 1930s, but Turner was the first to propose them as a way of building a computing system. Subsequently Clarke, Gladstone, MacLean and Norman described in detail computational hardware which could be built to ease the implementation of such systems. Since then, additional materials have been written about combinators including U.S. Pat. No. 4,734,848 to Yamano et al, describing parallel combinator hardware.
Combinators are an example of a graph reduction system. That is, a system where programs are represented as lists of elements which are transformed by a set of graph reduction operators. While this invention focuses on combinators because of their compactness and proven universality, the invention covers the use of any and all graph reduction systems, including those which work on strings which represent graphs.
Combinators K, S, I, B, C, and W are defined by the following functions and illustrated graphically in FIG.
1
. In each case, f, g, x and y may be functions, operators, constants, or combinator expressions
Kxy=x
Sfgx=fx
(
gx
)
Ix=x
Bfgx=f
(
gx
)
Cfgx=
(
fx
)
g
Wfx=
(
fx
)
x
If programs are viewed as trees of expressions where each branch of the tree represents a separate part of the program, combinators directly alter program trees to change their structure, thereby changing the results of evaluating the tree. Combinator computing systems usually use bracket abstraction to remove references to variables; i.e., input data which changes each time the program is executed. The bracket abstraction method produces a pure combinator expression having no references to input data. Instead the combinators are applied directly to input data arranged as a graph or tree.
John Holland described the idea of using genetics as a model for solving computational problems in his 1975 monograph, Adaptation in natural and artificial systems. Holland suggested that from several sets of randomly chosen initial values, provided only that there is a way to determine if one value is “better” (as defined in some problem-specific way) than another, a solution can be obtained by combining the “genes” these values represent through a mechanism modeled after evolution.
These “genetic algorithms” provide an efficient method of converging on desired values in a large universe of possible values. If a superior value among a large number of possible values is sought, and if values can be characterized in some regular form such as a binary string, then it is possible to move quickly and efficiently toward the best solution by selecting, mating and occasionally mutating these strings from a relatively small pool of candidates providing only that it is possible to assign a value which represents the quality of a value when compared with other values.
Genetic algorithms are usually demonstrated in programs which look for the maximal or optimal value from a known measurement function such as finding function maxima or minima. For example, the “Traveling Salesperson” problem of searching for the most efficient route of travel among a very large number of possible routes is often used to demonstrate genetic algorithms.
Previous attempts at creating programs using genetic algorithm techniques have included combining genetic algorithms with rule-based systems to provide a method of building complex systems for taking actions. This may be thought of as programming by matching binary values to rules and then evolving the values to find the best combination of rules to solve the problem. This is described in Holland and Burks 1987 U.S. Pat. No. 4,697,242.
In another previous attempt, the principles of genetic algorithms were applied to programming by describing LISP programs and program pieces as potential gene elements and then evolving more complex LISP programs from these elements using the rules of genetic algorithms. This is described both in J. R. Koza's books on genetic programming and in his several genetic programming patents (U.S. Pat. Nos. 4,935,877, 5,136,686, and 5,343,554). These patents suggest that gene strings can be of variable length and that they can be related to computer expressions by one-to-one mapping of the genes to program fragments. Thus, the systems created by Koza require the mapping of gene values used in a genetic algorithm to LISP expressions in order to create new programs.
SUMMARY OF THE INVENTION
The present invention describes a computer system capable of being constructed with custom hardware or implemented as a software state machine, which uses genetic programming and graph reduction techniques to create programs which can solve computational problems. This is accomplished by using a genetic program to successively produce more efficient programs represented in the form of graph reduction operator strings.
This invention covers the use of any graph reduction system as the fundamental method of program representation. A graph reduction system is one where the program is represented by a series of operators which transform or reduce a graph (or list) representation of data or program components. This includes graphs which are represented as strings and graph reduction systems based on string manipulations. Because of their conciseness, universality and simplicity, a graph reduction system based on combinators is presented herein. The program being evaluated is represented in a single gene string, no mapping is required with the present invention. Evaluation of each program string is performed by applying the program gene string to input data and measuring the relative “quality” or “fitness” of the resulting output.
The present invention differs from previous attempts at building genetic programming machines in that the program gene strings themselves are programs. Previous attempts mapped the gene strings to program fragments. This mapping of gene strings is time consuming because it requires continuous data transfers to and from various memory locations throughout the evolution process in order to assemble candidate programs for testing. Through the use of combinators, the present invention eliminates the need for mapping gene strings and repeated data transfers associated with such mapping. Thus, the present genetic programming system is faster than other genetic programming systems which employs the mapping of data and variables.
REFERENCES:
patent: 4697242
Holmes Michael B.
Powell Mark R.
Young & Basile P.C.
LandOfFree
Method and system for genetic programming does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for genetic programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for genetic programming will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2583301