Simultaneous evolution of the architecture of a multi-part program while solving a problem using architecture altering operations

• US 6,058,385 A
• Filed: 03/07/1997
• Issued: 05/02/2000
• Est. Priority Date: 05/20/1988
• Status: Expired due to Term

• Current Assignee: David Andre, John R. Koza, Walter Alden Tackett
• Original Assignee: David Andre, John R. Koza, Walter Alden Tackett
• Inventors: Andre, David, Tackett, Walter Alden, Koza, John R.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Shah, Sanjiv
• Application Number:
  US08/813,894
• Time in Patent Office: 1,152 Days
• Field of Search: 395/10-13, 395/50-51, 395/60-61, 706/10, 706/11, 706/13, 706/45, 706/46, 706/54, 706/52
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

An apparatus and method for solving problems where a population is created and evolved to generate a result. While solving the problem, the architecture of entities in the population are altered. Each of said entities may include internally and externally invoked sub-entities. The externally invoked sub-entities are capable of having actions, invocations of sub-entities which are invoked internally, and material. Also, each sub-entity which is invoked internally is capable of including actions, invocations of internally invocable sub-entities, material provided to the externally invocable sub-entity, and material.

Claims

1. A computer-implemented process for solving a problem comprising the computer-implemented steps of:

creating a population of programmatic entities;

generating a solution to the problem, wherein the step of generating the solution comprises the computer-implemented steps of;

selecting at least one entity from a population of programmatic entities using selection criteria that is based on fitness;

choosing an operation that creates a new entity;

if the chosen operation is an architecture altering operation, then performing the architecture altering operation to alter the architecture of said at least one entity of the population of programmatic entities;

adding said new entity created by the chosen operation to the population.

2. The process defined in claim 1 wherein the step of performing the architecture altering operation comprises the steps of:

duplicating a portion of an internally invocable sub-entity from a programmatic entity in the population of programmatic entities to create a duplicated portion of the internally invocable sub-entity; and

adding the duplicated portion of the internally invocable sub-entity to the programmatic entity.

3. The process defined in claim 1 wherein the step of performing the architecture altering operation comprises the steps of:

duplicating an internally invocable sub-entity from a programmatic entity in the population of programmatic entities to create a duplicated internally invocable sub-entity; and

adding the duplicated internally invocable sub-entity to the programmatic entity.

4. The process defined in claim 1 wherein the step of performing the architecture altering operation comprises the steps of:

duplicating an argument of an internally invocable sub-entity from a programmatic entity in the population of programmatic entities to create a duplicated argument; and

adding the duplicated argument to the programmatic entity.

5. The process defined in claim 1 wherein said step of performing the architecture altering comprises deleting a portion of an internally invocable sub-entity from a programmatic entity in the population of programmatic entities.

6. The process defined in claim 1 wherein said step of altering the architecture comprises the step of deleting an internally invocable sub-entity from a programmatic entity in the population of programmatic entities.

7. The process defined in claim 1 wherein the step of altering the architecture comprises the step of creating an internally invocable sub-entity from a portion of a sub-entity.

8. The process defined in claim 1 wherein the step of altering the architecture comprises the step of creating an argument for an internally invocable sub-entity.

9. In a system having a population of program entities of various sizes and shapes, wherein each program entity comprises a hierarchical arrangement of functions and terminals, wherein at least one of said functions in at least one of said program entities stores information by setting at least one memory variable, a process comprising iterations of a series of computer-implemented steps, each iteration comprising the computer-implemented steps of:

executing program entities by performing each function in said hierarchical arrangement of functions and terminals, including executing said at least one of said functions in said at least one program entity to store information by setting said at least one memory variable;

selecting said at least one program entity from said population using selection criteria that is based on fitness using selection criteria which tends to prefer program entities having a relatively good fitness over program entities with relatively poor fitness;

choosing an operation that creates a new program entity;

if said chosen operation is crossover, then selecting a group of at least two program entities from said population including said at least one program entity based on the fitness of said at least two program entities, and performing said crossover operation;

if said chosen operation is not crossover, then selecting at least one program entity based on the fitness of said at least two program entities, and performing said chosen operation; and

adding said new program entity created by said chosen operation to said population.

10. In a system having a population of entities of various sizes and shapes, wherein each program entity comprises a hierarchical arrangement of functions and terminals, wherein at least one of said functions in at least one of said program entities accesses information stored in at least one memory variable, a process comprising iterations of a series of computer-implemented steps, each iteration comprising the computer-implemented steps of:

executing program entities by performing each function in said hierarchical arrangement of functions and terminals, including executing said at least one of said functions in said at least one program entity to access information stored in at said at least one memory variable;

selecting said at least one program entity from said population using selection criteria that is based on fitness using selection criteria which tends to prefer program entities having a relatively good fitness over program entities with relatively poor fitness;

choosing an operation that creates a new program entity;

if said chosen operation is crossover, then selecting a group of at least two program entities from said population including said at least one program entity based on the fitness of said at least two program entities, and performing said crossover operation;

if said chosen operation is not crossover, then selecting at least one program entity based on the fitness of said at least two entities, and performing said chosen operation; and

adding said new program entity created by said chosen operation to said population.

11. In a system having a population of program entities of various sizes and shapes, wherein each program entity comprises a hierarchical arrangement of functions and terminals, wherein at least one of said functions in at least one of said program entities is an operation with side effects on the state of the system, a process comprising iterations of a series of computer-implemented steps, each iteration comprising the computer-implemented steps of:

executing program entities by performing each function in said hierarchical arrangement of functions and terminals, including executing said at least one of said functions in said at least one program entity to cause the side effects on the state of the system;

selecting said at least one program entity from said population using selection criteria that is based on fitness using selection criteria which tends to prefer program entities having a relatively good fitness over program entities with relatively poor fitness;

choosing an operation that creates a new program entity;

if said chosen operation is crossover, then selecting a group of at least two program entities from said population including said at least one program entity based on the fitness of said at least two program entities, and performing said crossover operation;

if said chosen operation is not crossover, then selecting at least one program entity based on the fitness of said at least two program entities, and performing said chosen operation; and

adding said new program entity created by said chosen operation to said population.

12. In a system having a population of program entities of various sizes and shapes, wherein each program entity comprises a hierarchical arrangement of functions and terminals, wherein at least one of said functions in at least one of said program entities is a transcendental function, a process comprising iterations of a series of computer-implemented steps, each iteration comprising the computer-implemented steps of:

executing program entities by performing each function in said hierarchical arrangement of functions and terminals, including executing said transcendental function in said at least one program entity;

selecting said at least one program entity from said population using selection criteria that is based on fitness using selection criteria which tends to prefer program entities having a relatively good fitness over program entities with relatively poor fitness;

choosing an operation that creates a new program entity;

if said chosen operation is crossover, then selecting a group of at least two program entities from said population including said at least one program entity based on the fitness of said at least two program entities, and performing said crossover operation;

if said chosen operation is not crossover, then selecting at least one program entity based on the fitness of said at least two program entities, and performing said chosen operation; and

adding said new program entity created by said chosen operation to said population.

13. In a system having a population of program entities of various sizes and shapes, wherein each program entity comprises a hierarchical arrangement of functions and terminals, wherein at least one of said functions in at least one of said program entities is modified to yield a value for values of its arguments that ordinarily would not yield a value that is acceptable as an input to another function, a process comprising iterations of a series of computer-implemented steps, each iteration comprising the computer-implemented steps of:

executing program entities by performing each function in said hierarchical arrangement of functions and terminals, including executing said at least one of said functions in said at least one program entity to yield the value for values of its arguments that ordinarily would not yield a value that is acceptable as an input to another function;

selecting said at least one program entity from said population using selection criteria that is based on fitness using selection criteria which tends to prefer program entities having a relatively good fitness over program entities with relatively poor fitness;

choosing an operation that creates a new program entity;

if said chosen operation is crossover, then selecting a group of at least two program entities from said population including said at least one program entity based on the fitness of said at least two program entities, and performing said crossover operation;

if said chosen operation is not crossover, then selecting at least one program entity based on the fitness of said at least two program entities, and performing said chosen operation; and

adding said new program entity created by said chosen operation to said population.

14. In a system having a population of program entities of various sizes and shapes, wherein each program entity comprises a hierarchical arrangement of functions and terminals, wherein at least one of said functions in at least one of said program entities is yields a symbolic output, a process comprising iterations of a series of computer-implemented steps, each iteration comprising the computer-implemented steps of:

executing program entities by performing each function in said hierarchical arrangement of functions and terminals, including executing said at least one of said functions in said at least one program entity to yield the symbolic output;

selecting said at least one program entity from said population using selection criteria that is based on fitness using selection criteria which tends to prefer program entities having a relatively good fitness over program entities with relatively poor fitness;

choosing an operation that creates a new program entity;

if said chosen operation is crossover, then selecting a group of at least two program entities from said population including said at least one program entity based on the fitness of said at least two program entities, and performing said crossover operation;

if said chosen operation is not crossover, then selecting at least one program entity based on the fitness of said at least two program entities, and performing said chosen operation; and

adding said new program entity created by said chosen operation to said population.

15. In a system having a population of program entities of various sizes and shapes, wherein each program entity comprises a hierarchical arrangement of functions and terminals, wherein at least one of said functions in at least one of said program entities receives program segments as arguments and sequentially evaluates each of said segments, a process comprising iterations of a series of computer-implemented steps, each iteration comprising the computer-implemented steps of:

executing program entities by performing each function in said hierarchical arrangement of functions and terminals, including executing said at least one of said functions in said at least one program entity to sequentially evaluate each of said segments received as arguments;

selecting said at least one program entity from said population using selection criteria that is based on fitness using selection criteria which tends to prefer program entities having a relatively good fitness over program entities with relatively poor fitness;

choosing an operation that creates a new program entity;

if said chosen operation is crossover, then selecting a group of at least two program entities from said population including said at least one program entity based on the fitness of said at least two program entities, and performing said crossover operation;

if said chosen operation is not crossover, then selecting at least one program entity based on the fitness of said at least two program entities, and performing said chosen operation; and

adding said new program entity created by said chosen operation to said population.

16. In a system having a population of program entities of various sizes and shapes, wherein each program entity comprises a hierarchical arrangement of functions and terminals, wherein at least one of said functions in at least one of said program entities is an iterative function that performs steps until a condition is satisfied, a process comprising iterations of a series of computer-implemented steps, each iteration comprising the computer-implemented steps of:

executing program entities by performing each function in said hierarchical arrangement of functions and terminals, including executing said at least one of said functions in said at least one program entity to iteratively perform steps until a condition is satisfied;

selecting said at least one program entity from said population using selection criteria that is based on fitness using selection criteria which tends to prefer program entities having a relatively good fitness over program entities with relatively poor fitness;

choosing an operation that creates a new program entity;

if said chosen operation is crossover, then selecting a group of at least two program entities from said population including said at least one program entity based on the fitness of said at least two program entities, and performing said crossover operation;

if said chosen operation is not crossover, then selecting at least one program entity based on the fitness of said at least two program entities, and performing said chosen operation; and

adding said new program entity created by said chosen operation to said population.

17. In a system having a population of program entities of various sizes and shapes, wherein each program entity comprises a hierarchical arrangement of functions and terminals, a process comprising iterations of a series of computer-implemented steps, each iteration comprising the computer-implemented steps of:

executing program entities by performing each function in said hierarchical arrangement of functions and terminals, wherein execution of one of the program entities produces a plurality of outputs;

selecting said at least one program entity from said population using selection criteria that is based on fitness using selection criteria which tends to prefer program entities having a relatively good fitness over program entities with relatively poor fitness;

choosing an operation that creates a new program entity;

if said chosen operation is crossover, then selecting a group of at least two program entities from said population including said at least one program entity based on the fitness of said at least two program entities, and performing said crossover operation;

if said chosen operation is not crossover, then selecting at least one program entity based on the fitness of said at least two program entities, and performing said chosen operation; and

adding said new program entity created by said chosen operation to said population.

18. A process for solving a problem using a parallel processing computer system having a population of various sizes and structures, said process comprising the step of performing a group of processes, wherein more than one process is performed simultaneously, each process of said group of processes comprising iterations of a series of computer-implemented steps, each iteration comprising the computer-implemented steps of:

executing programmatic program entities;

selecting said at least one program entity from said population using selection criteria that is based on fitness using selection criteria which tends to prefer program entities having a relatively good fitness over program entities with relatively poor fitness;

performing an operation on at least one programmatic program entity selected from the population to create a new program entity;

adding said new program entity created by said chosen operation to said population.

19. The process defined in claim 18 wherein each of said parallel processes operate on a separate sub-population.

20. The process defined in claim 18 wherein said process further comprises the step of periodically intermixing sub-populations of said population.

21. The process defined in claim 18 wherein an initial population of programmatic program entities is created by randomly generating programmatic program entities of various sizes and structures, said programmatic program entities comprising hierarchical programming structures having functions and arguments available for the problem.