Non-linear genetic process for use with plural co-evolving populations

• US 5,148,513 A
• Filed: 09/18/1990
• Issued: 09/15/1992
• Est. Priority Date: 05/20/1988
• Status: Expired due to Term

• Current Assignee: John R. Koza
• Original Assignee: John R. Koza
• Inventors: Rice, James P., Koza, John R.
• Primary Examiner(s): MacDonald, Allen R.
• Application Number:
  US07/584,259
• Time in Patent Office: 728 Days
• Field of Search: 364/513, 395/13
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A non-linear genetic process for problem solving using co-evolving populations of entities is disclosed. The iterative process of the present invention operates on a plurality of populations of problem solving entities. First, an activated entity in one of the plurality of populations (evolving population) performs, producing a result. The result is assigned a value and the value is associated with the producing entity. The value assigned is computed relative to the performance of the entity in a population different from the evolving population (one of the environmental populations). Next, entities having relatively high associated values are selected from the evolving population. The selected entities perform either crossover or fitness proportionate reproduction. In addition, other operations such as mutation, permutation, define building blocks and editing may be used. Next, the newly created entities are added to the evolving population. Finally, one of the environmental populations switch roles with the evolving population and the process repeats for the new evolving population and the new environmental populations.

Claims

1. In a parallel processing computer system having at least one processor, a memory, and a plurality of populations of programs of various sizes and structures and wherein more than one program can be executed simultaneously, a group of parallel processes for problem solving wherein more than one parallel process of said group of parallel processes can be performed simultaneously, each parallel process of said group of parallel processes comprising the steps of:

(i) designating one of said plurality of populations as the evolving population wherein the remaining populations of said plurality of populations are designated co-evolving environmental populations;

(ii) iterating a series of steps, said series of steps including;

a) assigning a fitness value to a program of said evolving population and associating said fitness value with a corresponding program, said fitness value indicative of the relative fitness of said corresponding program in relation to said co-evolving environmental populations;

b) selecting at least one program from said evolving population using selection criteria, said selection criteria based on said fitness value associated with each said program, said selection criteria preferring each said program having a relatively high associated fitness value over each said program having a relatively low associated fitness value;

c) choosing and performing an operation, wherein said chosen operation is one of the operations of crossover or reproduction;

d) creating, if said operation is crossover, at least one new program by crossover using a group of programs from said evolving population, said group of programs comprising said selected program and at least one other program from said evolving population, such that any new program created by crossover comprises at least a portion of said selected program and at least a portion of said other program, said new program capable of differing in size and structure from said selected program and said other program;

e) reproducing, if said chosen operation is reproduction, said selected program in said evolving population, such that said selected program remains unchanged; and

f) adding said new program to said evolving population; and

(iii) terminating when a solution is found.

2. The process as claimed in claim 1 wherein said step of choosing and performing an operation further comprising the operation of mutation which occurs before said adding step, wherein said selected program is mutated, such that at least one portion of said selected program is replaced by a randomly generated portion to produce a new program having portions of said selected program and randomly generated portions.

3. The process as claimed in claim 1 wherein said step of choosing and performing an operation includes performing one of said operations for each of said parallel processes and all said parallel processes operate on said evolving population.

4. The process as claimed in claim 1 wherein each of said parallel processes operate on a separate sub-population of said evolving population, said process including a step of periodically intermixing sub-populations of said evolving population.

5. The process as claimed in claim 1 wherein said step of choosing and performing an operation includes performing one of said operations for each of said parallel processes and each of said parallel processes operate on a separate sub-population of said evolving population.

6. The process as claimed in claim 1 wherein said fitness value for said program of said evolving population is assigned relative to a combination of one program from each of a plurality of co-evolving environmental populations.

7. The process as claimed in claim 1 wherein said step of choosing and performing an operation further comprising the operation of permutation, such that if said chosen operation is permutation, a step of permutation occurs before said adding step, wherein said selected program is permuted, such that portions of each said selected program are recordered to create at least one new program from said selected program.

8. The process as claimed in claim 1 wherein said step of selecting at least one program further comprises selection criteria based on a probability that is proportional to said value associated with said program.

9. The process as claimed in claim 1 wherein said step of selecting at least one program further comprises selection criteria based on choosing the better of two randomly selected individual programs.

10. The process as claimed in claim 1 wherein initial populations of programs are created by randomly generating programs of various size and structures, said programs consisting of hierarchical programming structures, said hierarchical programming structures consisting of the functions and arguments available for the problem.

11. A computer system for problem solving comprising:

memory means for storing a plurality of populations of programs of various sizes and structures, each said program being a hierarchical arrangement of functions and arguments;

processing means coupled to said memory means for retrieving said programs stored in said memory means, said processing means executing instructions determined by said retrieved programs;

means for designating one of said plurality of populations as the evolving population wherein the remaining populations of said plurality of populations are designated as co-evolving environmental populations;

means for assigning a fitness value to a program of said evolving population and associating said fitness value with a corresponding program, said fitness value indicative of the relative fitness of said corresponding program in relation to said co-evolving environmental populations;

means for selecting at least one program from said evolving population using selection criteria, said selection criteria based on said fitness value associated with each said program, said selection criteria preferring each said program having a relatively high associated fitness value over each said program having a relatively low associated fitness value;

means for choosing and performing an operation, wherein said chosen operation is one of the operations of crossover or reproduction;

means for creating, if said operation is crossover, at least one new program by crossover using a group of programs from said evolving population, said group of programs comprising said selected program and at least one other program from said evolving population, such that any new program created by crossover comprises at least a portion of said selected program and at least a portion of said other program, said new program capable of differing in size and structure from said selected program and said other program;

means for reproducing, if said chosen operation is reproduction, said selected program in said evolving population, such that said selected program remains unchanged;

means for adding said new program to said evolving population; and

means for terminating when a solution is found.

12. The computer system as claimed in claim 11, wherein said means for selecting at least one program from said evolving population using selection criteria further comprising selection criteria based on a probability that is proportional to said fitness value associated with said program.

13. The computer system as claimed in claim 11 wherein said means for choosing and performing an operation further comprising the operation of mutation such that if said chosen operation is mutation, said selected program is mutated, such that at least one portion of said selected program is replaced by a randomly generated portion to produce a new program having portions of said selected program and randomly generated portions.

14. The computer system as claimed in claim 11 wherein said means for selecting further comprises means for removing at least one program having a relatively low associated fitness value when selecting a program having a relatively high associated fitness value.

15. The computer system as claimed in claim 11 wherein said memory means is used to store the status of all selected and removed programs.

16. The computer system as claimed in claim 11 further comprising a plurality of said processing means for performing parallel operations on said plurality of populations of programs.

17. The computer system as claimed in claim 11 wherein said means for choosing and performing an operation further comprising the operation of permutation, such that if said chosen operation is permutation, said selected program is permuted, such that portions of each said selected program are reordered to create at least one new program from said selected program.

18. The computer system as claimed in claim 11 wherein said means for assigning a fitness value assigns a fitness value indicative of the relative fitness of a program in opposing said co-evolving environmental populations.

19. The computer system as claimed in claim 11 wherein said means for assigning a fitness value assigns a fitness value for a program of said evolving population relative to a combination of one program from each of a plurality of co-evolving environmental populations.

20. The computer system as claimed in claim 11 wherein said plurality of populations of programs stored in said memory means is initially created using means for randomly generating programs of various sizes and structures, said means for randomly generating programs coupled to said processing means, said programs consisting of heierarchical arrangements of the functions and arguments available for the problem.

21. In a computer system having at least one processor, a memory, and a plurality of populations of programs of various sizes and structures, a process for problem solving comprising the steps of:

(i) designating one of said plurality of populations as the evolving population wherein the remaining populations of said plurality of populations are designated co-evolving environmental populations;

(ii) iterating a series of steps, said series of steps including;

a) assigning a fitness value to a program of said evolving population and associating said fitness value with a corresponding program, said fitness value indicative of the relative fitness of said corresponding program in relation to said co-evolving environmental populations;

b) selecting at least one program from said evolving population using selection criteria, said selection criteria based on said fitness value associated with each said program, said selection criteria preferring each said program having a relatively high associated fitness value over each said program having a relatively low associated fitness value;

c) choosing and performing an operation, wherein said chosen operation is one of the operations of crossover or reproduction;

d) creating, if said operation is crossover, at least one new program by crossover using a group of programs from said evolving population, said group of programs comprising said selected program and at least one other program from said evolving population, such that any new program created by crossover comprises at least a portion of said selected program and at least a portion of said other program, said new program capable of differing in size and structure from said selected program and said other program;

e) reproducing, if said chosen operation is reproduction, said selected program in said evolving population, such that said selected program remains unchanged; and

f) adding said new program to said evolving population; and

(iii) terminating when a solution is found.

22. The process as claimed in claim 21 wherein said iterating a series of steps is performed simultaneously for more than one program.

23. The process in claim 21 wherein said step of assigning a fitness value comprising:

executing a program of said evolving population to produce a result by performing said hierarchical arrangement of functions in relation to at least one program from at least one co-evolving environmental population; and

assigning a value to said result and associating said value with a corresponding program from said evolving population which produced said result, said value indicative of the relative fitness of said corresponding program in opposing said co-evolving environmental population, said value relative to the results produced by programs of said co-evolving environmental population.

24. The process as claimed in claim 21 wherein said fitness value for said program of said evolving population is assigned relative to a combination of one program from each of a plurality of co-evolving environmental populations.

25. The process as claimed in claim 21 wherein said step of selecting at least one selected program further comprises selection criteria based on a probability that is proportional to said value associated with said program.

26. The process as claimed in claim 21 wherein said step of selecting at least one selected program further comprises selection criteria based on choosing the better of two randomly selected individual programs.

27. The process as claimed in claim 21 wherein said operation of crossover further comprises taking sub-procedures from at least one said selected program and at least one other program to create a new program, said new program is created solely from sub-procedures of said selected program and sub-procedures of said other program, said new program capable of varying in size and structure from said selected program and said other program.

28. The process as claimed in claim 21 wherein said step of choosing and performing an operation further comprising the operation of permutation, such that if said chosen operation is permutation, a step of permutation occurs before said adding step, wherein said selected program is permuted, such that portions of each said selected program are reordered to create at least one new program from said selected program.

29. The process as claimed in claim 21 wherein said step of choosing and performing an operation further comprises the operation of mutation such that if said chosen operation is mutation, a step of mutation occurs before said adding step, wherein said selected program is mutated, such that at least one portion of said selected program is replaced by a randomly generated portion to produce a new program having portions of said selected program and randomly generated portions.

30. The process in claim 21 wherein said step of choosing and performing an operation further comprising an operation of define building block such that if said chosen operation is said define building block operation, a step of define building block occurs before said adding step, wherein a portion of said selected program is replaced by an invocation of a building block function, said building block function being defined as the hierarchical arrangement of functions and arguments originally associated with said selected portion of said selected program.

31. The process in claim 21 wherein said step of choosing and performing an operation further comprising an operation of editing such that if said chosen operation is said editing operation, a step of editing occurs before said adding step, wherein said selected program is edited, such that predetermined editing rules are applied to said selected program to produce a modified hierarchical structure of said selected program.

32. The process as claimed in claim 21 further comprising a step of removing at least one program having a relatively low associated value.

33. The process as claimed in claim 21 wherein said operation of permutation further comprises permuting a program by rearranging the sub-procedures of said program.

34. The process as claimed in claim 21 wherein said operation of permutation further comprises permuting a program by rearranging the arguments of the sub-procedures of said program.

35. The process as claimed in claim 21 wherein said operation of permutation further comprises permuting a program by rearranging the arguments of the sub-procedures of said program and the sub-procedures of said program.

36. The process as claimed in claim 21 wherein said operation of permutation further comprises permuting a program by redistributing the arguments of all the sub-procedures of said program amongst all the sub-procedures, and reordering the sub-procedures of said program.

37. The process as claimed in claim 21 wherein an individual program in said plurality of populations attaining a pre-established value of fitness with respect to solving the problem is designated as the solution to the problem.

38. The process as claimed in claim 21 wherein a set of programs from one of said plurality of populations collectively attaining a pre-established degree of fitness with respect to solving the problem is designated as the solution to the problem.

39. The process as claimed in claim 21 wherein the entirety of one said population of programs is designated as the solution to a problem and wherein each program in said designated population is equally likely to be selected as a solution to be executed for solving the problem.

40. The process as claimed in claim 21 further including steps for providing a quick fitness calculation for evaluating the fitness of a program in relation to the fitness of programs in said co-evolving environmental populations, said steps including:

storing said fitness value assigned in said assigning step, said fitness value being stored in a memory, said storing step being performed after said assigning step; and

retrieving said fitness value stored in said memory, said retrieving step being performed prior to said assigning step if said memory already contains a fitness value associated with an equivalent combination of programs, said retrieving step performed instead of computing a fitness value for said program.

41. The process as claimed in claim 21 wherein the initial plurality of populations of programs are created by randomly generating programs of various sizes and structures, said programs consisting of hierarchical arrangements of the functions and arguments available for the problem.

42. The process as claimed in claim 21 wherein said populations evolve in relation to a global environment.

43. The process as claimed in claim 21 wherein more than one program is activated simultaneously.

44. The process as claimed in claim 21 wherein said assigning step is performed simultaneously for one program of said evolving population in relation to more than one program of said co-evolving environmental population.

45. The process as claimed in claim 21 wherein said assigning step is performed simultaneously for more than one program.