Non-linear genetic algorithms for solving problems

• US 4,935,877 A
• Filed: 05/20/1988
• Issued: 06/19/1990
• Est. Priority Date: 05/20/1988
• Status: Expired due to Term

• Current Assignee: John R. Koza
• Original Assignee: John R. Koza
• Inventors: Koza, John R.
• Primary Examiner(s): Lastova, John R.
• Application Number:
  US07/196,973
• Time in Patent Office: 760 Days
• Field of Search: 364/513, 364/200, 364/274, 382/14, 382/15
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: Y10S 706/922 Computer program preparation

Abstract

The present invention is a non-linear genetic algorithm for problem solving. The iterative process of the present invention operates on a population of problem solving entities. First, the activated entities perform, producing results. Then the results are assigned values and associated with the producing entity. Next, entities having relatively high associated values are selected. The selected entities perform either crossover, reproduction, or permutation operations. Lastly, the newly created entities are added to the population.

Claims

1. A process for problem solving, using a population of entities of various sizes and shapes wherein each entity is a hierarchical arrangement of functions and arguments said process comprising iterations of a series of steps, each iteration comprising the steps:

activating each said entity to produce a result by performing each function in said hierarchical arrangement of functions and arguments;

assigning a value to each said result and associating each said value with a corresponding entity which produced each said result, said value indicative of the fitness of said corresponding entity in solving or partially solving a problem;

selecting at least one selected entity from said population using selection criteria, said selection criteria based on said value associated with each said entity, said selection criteria preferring each said entity having a relatively high associated value over each said entity having a relatively low associated value;

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

if said chosen operation is crossover, creating at least one new entity by crossover using a group of entities, said group of entities comprising said selected entity and at least one other entity from said population, such that any new entity created by crossover comprises at least a portion of said selected entity and at least a portion of said other entity, said new entity can differ in size and shape from said selected entity and said other entity;

if said chosen operation is reproduction, retaining said selected entity in said population such that said selected entity remains unchanged;

adding said new entity to said population.

2. The process as described in claim 1 wherein said step of selecting at least one selected entity further comprises selection criteria based on a probability that is, in most cases, proportional to said value associated with said entity.

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

4. The process as described in claim 1 further comprising a step of removing at least one entity having a relatively low associated value.

5. The process as described in claim 1 further comprising the step of maintaining an audit trail for recording the hereditary information of said population.

6. In the process as described 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 entity is permuted, such that portions of each said selected entity are reordered to create at least one new entity from said selected entity.

7. The process as described in claim 1 wherein an individual entity in said population attaining a pre-established value of fitness with respect to solving the problem is designated as the solution to the problem.

8. The process as described in claim 1 wherein a set of entities from said population collectively attaining a pre-established average value of fitness with respect to solving the problem is designated as the solution to the problem.

9. The process as described in claim 1 wherein the initial population of entities is created by randomly generating entities of various sizes and shapes, said entities consisting of hierarchical arrangements of the functions and arguments available for the problem.

14. The process as described in claim 6 wherein said operation of crossover further comprises removing said group from said population.

10. In a computer system having a population of programs of various sizes and structures, an iterative process for problem solving comprising iterations of a series of steps, each iteration of said process comprising the steps:

executing each said program to produce a result;

assigning a value to each said result and associating each said value with a corresponding program which produced each said result, said value indicative of the fitness of said corresponding program in solving or partially solving a problem;

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

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

if said operation is crossover, creating at least one new program by crossover using a group of programs, said group of programs comprising said selected program and at least one other program from said 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 can differ in size and structure from said selected program and said other program;

if said chosen operation is reproduction, retaining said selected program in said population such that said selected program remains unchanged;

adding said new program to said population.

11. The process as described in claim 10 wherein said step of selecting at least one selected program further comprises selection criteria based on a probability that is, in most cases, proportional to said value associated with said program.

12. The process as described in claim 10 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.

13. The process as described in claim 10 further comprising a step of removing at least one program having a relatively low associated value.

15. The process as described in claim 10 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 can vary in size and shape from said selected program and said other program.

16. The process as described in claim 10 further comprising the step of maintaining an audit trail for recording the hereditary information of said population.

17. In the process as described in claim 10 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.

18. The process as described in claim 17 wherein said operation of permutation further comprises permuting a program by rearranging the sub-procedures of said program.

19. The process as described in claim 17 wherein said operation of permutation further comprises permuting a program by rearranging the arguments of the sub-procedures of said program.

20. The process as described in claim 17 wherein said operation of permutation further comprises permutating a program by rearranging the arguments of the sub-procedures of said program and the sub-procedures of said program.

21. The process as described in claim 17 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.

22. The process as described in claim 10 wherein an individual program in said population attaining a pre-established value of fitness with respect to solving the problem is designated as the solution to the problem.

23. The process as described in claim 10 wherein a set of programs from said population collectively attaining a pre-established average value of fitness with respect to solving the problem is designated as the solution to the problem.

24. The process as described in claim 10 wherein the initial population of programs is created by randomly generating programs of various sizes and structures, said programs consisting of hierarchical programming structures, said hierarchical programming structures consisting of the functions and arguments available for the problem.

25. In a parallel processing computer system having a population of 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 iterations of a series of steps, each iteration of each said parallel process comprising the steps:

executing each said program to produce a result;

assigning a value to each said result and associating each said value with a corresponding program which produced each said result, said value indicative of the fitness of said corresponding program in solving or partially solving a problem;

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

choosing and performing an operation, including;

crossover, wherein at least one new program is created by crossover using a group of programs, said group of programs comprising said selected program and at least one other program from said 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 can differ in size and structure from said selected program and said other program;

reproduction, wherein said selected program is retained in said population such that said selected program remains unchanged;

adding said new program to said population.

26. The process as described in claim 25 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.

27. The process as described in claim 25 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 population.

28. The process as described in claim 25 wherein each of said parallel processes operate on a separate sub-population of said population, said process including a step of periodically intermixing sub-populations of said population.

29. The process as described in claim 25 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 population, said process including a step of periodically intermixing sub-populations of said population.

30. The process as described in claim 25 further comprising the step of maintaining an audit trail for recording the hereditary information of said population.

31. In the process as described in claim 25 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.

32. The process as described in claim 25 wherein an individual program in said population attaining a pre-established value of fitness with respect to solving the problem is designated as the solution to the problem.

33. The process as described in claim 25 wherein a set of programs from said population collectively attaining a pre-established average value of fitness with respect to solving the problem is designated as the solution to the problem.

34. The process as described in claim 25 wherein the initial population of programs is created by randomly generating programs of various sizes and structures, said programs consisting of hierarchical programming structures, said hierarchical programming structures consisting of the functions and arguments available for the problem.

35. A computer system for problem solving comprising:

memory means for storing a population of entities of various sizes and shapes, wherein each entity is a hierarchical arrangement of functions and arguments;

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

means for assigning a value to results of executing instructions of said retrieved entities and associating each said value with a corresponding entity which produced each said result, said value indicative of the fitness of said corresponding entity in solving or partially solving the problem, said means for assigning a value coupled to said processing means;

means for selecting at least one selected entity from said population using selection criteria, said selection criteria based on said value associated with each said entity, said selection criteria preferring each said entity having a relatively high associated value over each said entity having a relatively low associated value, said means for selecting coupled to said processing means;

means for choosing and performing an operation on each said selected entity, said chosen operation is one of the operations of crossover or reproduction, said means for choosing and performing an operation coupled to said processing means, said means for choosing and performing an operation comprising;

means for performing the operation of crossover comprising creation of at least one new entity by crossover using a group of entities, said group of entities comprising said selected entity and at least one other entity from said population, such that any new entity created by crossover comprises at least a portion of said selected entity and at least a portion of said other entity, said new entity can differ in size and shape from said selected entity and said other entity;

means for performing the operation of reproduction comprising retention of said selected entity in said population such that said selected entity remains unchanged;

means for adding said new entity to said population of stored entities in said memory means for further execution by said processor, said means for adding coupled to said processing means.

36. The computer system as defined in claim 35, wherein said means for selecting at least one selected entity from said population using selection criteria further comprising selection criteria based on a probability that is proportional to said value associated with said entity.

37. The computer system as defined in claim 35 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 entity is mutated, such that at least one portion of said selected entity is replaced by a randomly generated portion to produce a new entity having portions of said selected entity and randomly generated portions.

38. The computer system as defined in claim 35 wherein said means for selecting at least one selected entity further comprises removing at least one entity having a relatively low associated value when selecting said selected entity having a relatively high associated value.

39. The computer system as defined in claim 35 wherein said memory means can be used to store the status of all said selected and said removed entities.

40. The computer system as defined in claim 35 further comprising a plurality of said processing means for performing parallel operations on said population of said entities.

41. The computer system as described in claim 35 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 entity is permuted, such that portions of each said selected entity are reordered to create at least one new entity from said selected entity.

42. The computer system as described in claim 35 wherein said means for assigning a value further comprises designating an entity as a solution to a problem, wherein an individual entity in said population attains a pre-established value of fitness with respect to solving said problem.

43. The computer system as described in claim 35 wherein said means for assigning a value further comprises designating set of entities from said population as a solution to a problem, wherein said set of entities collectively attain a pre-established average value of fitness with respect to solving said problem.

44. The computer system as described in claim 35 wherein said population of entities stored in said memory means is initially created using means for randomly generating entities of various sizes and shapes, said means for randomly generating entities coupled to said processing means, said entities consisting of hierarchical arrangements of the functions and arguments available for the problem.