Method and system for genetic programming

• US 6,327,582 B1
• Filed: 08/31/1998
• Issued: 12/04/2001
• Est. Priority Date: 03/01/1996
• Status: Expired due to Term

• Current Assignee: William P. Worzel
• Original Assignee: William P. Worzel
• Inventors: Worzel, William P.
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): Holmes, Michael B.
• Application Number:
  US09/142,185
• Time in Patent Office: 1,191 Days
• Field of Search: 706/13
• US Class Current: 706/13
• CPC Class Codes: G06F 8/30 Creation or generation of source code
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A computer-implemented method and system for solving a programming problem using genetic programming techniques. A fitness function measures the relative superiority of a first solution with respect to a second solution. The genetic programming system creates multiple program gene strings containing graph reduction operators. Each program gene string represents a potential solution to the programming problem being solved. Input data is applied to each program gene string to generate a solution for each gene string. Each program gene string is evaluated by comparing the solution to the fitness function. The program gene strings are evolved based on the evaluation of their fitness. The gene strings are repeatedly evolved until a termination criteria has been satisfied.

Claims

1. A computer-implemented method of solving a programming problem using genetic programming techniques, said method comprising the steps of:

a. defining a fitness function for measuring the relative superiority of a first solution with respect to a second solution;

b. determining the input data from which the problem will be solved;

c. creating a plurality of program graphs containing graph reduction operators, each program graph representing a potential solution to the problem being solved;

d. applying each program graph to said input data to generate a solution for said programming problem;

e. using said fitness function in a problem specific way to assign a fitness to each said program graph based on said solution produced by applying said program graph to said input data;

f. evolving said program graphs based on the evaluation of their fitness; and

g. repeating steps (d) through (f) until a termination criteria has been satisfied.

11. The method of claim 1, wherein said step of creating a plurality of program graphs further comprises the creation of at least two individual program graphs.

12. The method of claim 11, wherein said creation of said individual program graphs is accomplished by randomly selecting at least one member of a predetermined set of operators and constants.

13. The method of claim 11, wherein said creation of said at least two individual program graphs is accomplished by a sub-graph and adding said sub-graph to at least one of said at least two individual program graphs.

14. The method of claim 1, wherein said evolving of said program graphs further comprises:

selection of at least two program graphs to create a sub-population;

selection of a first target program graph from said sub-population;

selection of a second target graph from said sub-population;

selection of a portion of said first target program graph;

selection of a portion of said second target program graph;

substituting said portion of said first target program graph for said portion of said second target program graph; and

substituting said portion of said second target program graph for said portion of said first target program graph.

15. The method of claim 1, wherein said evolving of said program graphs further comprises replacement of the least superior individual program graphs in said plurality of program graphs with the evolved graphs.

16. The method of claim 1, wherein said evolving of said program graphs further comprises replacement of the least superior individual program graphs in a sub-population of said plurality of program graphs, with the evolved graphs.

17. The method of claim 1, wherein said evolving of said program graphs further comprises replacement of selected graphs in a sub-population of said plurality of program graphs with the evolved graphs.

2. A computer-implemented method of solving a programming problem using genetic programming techniques, said method comprising the steps of:

a. defining a fitness function for measuring the relative superiority of a first solution with respect to a second solution;

b. determining the input data from which the problem will be solved;

c. creating a plurality of program graphs containing graph reduction operators, each program graph representing a potential solution to the problem being solved;

d. applying each program graph to said input data to generate a solution for said programming problem;

e. rating the fitness of said solution for said each program graph using said fitness function to assign a raw fitness to said each program graph based on the result produced by applying said each program graph to said input data, and thereafter scaling the fitness measure produced in a problem specific way;

f. evolving said program graphs based on an evaluation of their fitness; and

g. repeating steps (d) through (f) until a termination criteria has been satisfied.

3. A computer-implemented method of solving a programming problem using genetic programming techniques, said method comprising the steps of:

a. defining a fitness function for measuring the relative superiority of a first solution with respect to a second solution;

b. determining the input data from which the problem will be solved;

c. creating a plurality of program graphs containing graph reduction operators, each program graph representing a potential solution to the problem being solved;

d. applying each program graph to said input data to generate a solution for said programming problem;

e. using said fitness function to assign a fitness to each said program graph based on the solution produced by applying said program graph to said input data;

e. evolving said program graphs based on the evaluation of their fitness; and

f. repeating steps (d) through (f) until a termination criteria has been satisfied.

4. A genetic programming system for solving a programming problem, said system embodied in a custom electronic circuit, comprising:

a genetic program controller for controlling operation of said genetic programming system;

a genetic program memory unit for storing data associated with operation of said genetic programming system, said genetic program memory unit electrically coupled to said genetic program controller;

an input device electrically coupled to said genetic program controller for entering data into said genetic programming system;

a graph reduction machine electrically coupled to said genetic program controller; and

a plurality of program graphs stored within said genetic programming system, said program graphs being evolved to approach a desired solution, said graphs containing graph reduction operators.

5. A genetic programming system for finding a program to solve a problem given a particular input, said system comprising:

a memory device for storing various information;

an input device for entering a set of input data containing information to which a problem solution must be obtained, said input data stored in said memory device;

a fitness function providing a measure for determining the relative superiority of a first solution with respect to a second solution, said fitness function stored in said memory device;

a central processing unit electrically coupled to said memory device;

a plurality of program graphs stored in said genetic programming system, said program graphs containing at least one graph reduction operator.

6. The system of claim 5, wherein said central processing unit comprises agraph reduction unit.

7. In a genetic programming system having a plurality of central processing units electrically coupled together and an input device electrically coupled to said central processing units, a method for finding the best program to solve a problem given a particular input and a method of measuring the relative superiority of a first solution with respect to a second solution, said method comprising the steps of:

defining a fitness function for measuring the relative superiority of a first solution with respect to a second solution;

determining the input parameters from which the problem will be solved;

creating a plurality of program graphs containing graph reduction operators, each program graph representing a potential solution to the problem being solved;

applying each said program graph to said input parameters to generate a solution for said problem;

evaluating each program graph by applying it to sample input data and rating the fitness of the evolved program in a problem specific way;

evolving said program graph based on the evaluation of their fitness; and

repeating the above steps until a termination criteria has been satisfied.

8. In a genetic programming system having a plurality of central processing units electrically coupled together and an input device electrically coupled to said central processing units, a method for finding the best program to solve a problem given a particular input and a method of measuring the relative superiority of a first solution with respect to a second solution, said method comprising the steps of:

defining a fitness function for measuring the relative superiority of a first solution with respect to a second solution;

determining the input parameters from which the problem will be solved;

creating a plurality of program graphs containing graph reduction operators, each program graph representing a potential solution to the problem being solved;

applying each said program graph to said input parameters to generate a solution for said problem;

evaluating the fitness of said solution using said fitness function to assign a raw fitness to each program graph based on said solution produced by applying said program graph to said input parameters and then scaling said fitness measure produced in a problem specific way;

evolving said program graph based on the evaluation of their fitness; and

repeating the above steps until a termination criteria has been satisfied.

9. A genetic programming system for finding a solution to a programming problem having a defined input and a measure for determining the relative superiority of a first solution with respect to a second solution, said system comprising:

means for storing input data in said system;

means for storing a fitness function in said system;

means for storing a termination criteria in said system;

means for storing a plurality of program graphs comprised of graph reduction operators;

means for creating a plurality of program graphs;

means for applying each program graph to said input data to produce an output;

means for evaluating said output with said fitness function to determine a fitness level for each program graph;

means responsive to said fitness level of each program graph for evolving the program graph; and

means for repeatedly evolving and evaluating said program graphs until said termination criteria is satisfied.

10. In a genetic programming system having a plurality of central processing units electrically coupled together and an input device electrically coupled to said central processing units, a method for finding the best program to solve a problem given a particular input and a method of measuring the relative superiority of a first solution with respect to a second solution, said method comprising the steps of:

defining a fitness function for measuring the relative superiority of a first solution with respect to a second solution;

determining the input parameters from which the problem will be solved;

creating a plurality of program graphs containing graph reduction operators, each program graph representing a potential solution to the problem being solved;

applying said input parameters to each program graph to generate a solution for each program graph;

evaluating each program graph by applying it to sample input data;

using a fitness function to create a metric of relative superiority of evolved program graphs based on the results produced from executing the program graphs; and

repeating the above steps until a termination criteria has been satisfied.