Non-linear genetic process for data encoding and for solving problems using automatically defined functions

• US 5,343,554 A
• Filed: 05/11/1992
• Issued: 08/30/1994
• Est. Priority Date: 05/20/1988
• Status: Expired due to Term

• Current Assignee: John R. Koza, Lloyd Ayers
• Original Assignee: John R. Koza
• Inventors: Koza, John R., Rice, James P.
• Primary Examiner(s): MacDonald, Allen R.
• Application Number:
  US07/881,507
• Time in Patent Office: 841 Days
• Field of Search: 395/13
• 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 using automatic function definitions, for solving problems using recursion and for performing data encoding. The present invention includes an apparatus and process for creating a population and then evolving that population to generate a result. When solving problems using automatic function definition, the apparatus and process initially creates a population of entities. Each of said entities has sub-entities of 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. The population is then evolved to generate a solution to the problem. When using the process to solve problems using recursion, the entities in the population are constructed in such a manner as explicitly to represent the termination predicate, the base case and the non-base case of the recursion. Each entity has access to a name denoting that entity so as allow recursive references. The population is then evolved to generate a solution to the problem. When encoding a set of data values into a procedure capable of approximating those data values, the apparatus and process initially creates a population of entities. The population is then evolved to generate a solution to the problem.

Claims

1. In a computing system having at least one processor and at least one memory, a computer implemented process for solving a problem comprising the steps of:

creating a population of programmatic entities having sub-entities, wherein at least one of said sub-entities is externally invocable and at least one of said programmatic entities in the population has at least one internally invocable sub-entity, said at least one externally invocable sub-entity including at least one invocation of an internally invocable sub-entity; and

evolving said population, including the step of executing the population of programmatic entities, wherein said at least one externally invocable sub-entity invokes said at least one internally invocable sub-entity to produce results and, wherein said step of evolving further includes the step of generating at least one new programmatic entity in response to the results.

2. The process defined in claim 1 wherein said step of evolving comprises a series of iterative steps, wherein said series of iterative steps includes executing each of said programmatic entities to produce a result, thereafter subjecting at least one of said programmatic entities to an operation for evolving said at least one of said programmatic entities to generate a new programmatic entity, and adding said new programmatic entity to said population.

3. The process defined in claim 1 wherein the step of creating a population includes the step of creating at least one internally invocable sub-entity within at least one of said programmatic entities that references another internally invocable sub-entity within said at least one of said programmatic entities.

4. The process defined in claim 1 wherein said at least one externally invocable sub-entity includes at least one action.

5. The process defined in claim 1 wherein said at least one externally invocable sub-entity includes material.

6. The process defined in claim 5 wherein material comprises material provided to said at least one externally invocable sub-entity.

7. The process defined in claim 5 wherein material comprises material provided to said at least one internally invocable sub-entity.

8. The process defined in claim 1 wherein said at least one internally invocable sub-entity includes material.

9. The process defined in claim 1 wherein said at least one internally invocable sub-entity includes at least one action.

11. The process defined in claim 4 wherein said crossover operation is restrained such that said designated portion of said at least another programmatic entity in said new programmatic entity includes only those actions, material and references to internally invocable sub-entities that have been given a meaning by the other than the designed portion of said selected programmatic entity.

12. The process defined in claim 11 further comprising the step of determining actions, materials and references to internally invocable sub-entities that have meaning to said selected programmatic entity.

10. In computing system having at least one processor and at least one memory, a computer implemented process for problem solving using a population of programmatic entities, wherein each of said programmatic entities includes sub-entities, wherein at least one of said sub-entities is externally invocable and at least one of said programmatic entities in the population has at least one internally invocable sub-entity, said at least one externally invocable sub-entity including at least one invocation of an internally invocable sub-entity, said process comprising iterations of a series of steps, each iteration comprising the steps:

executing each said programmatic entity to produce a result;

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

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

retaining said selected programmatic entity such that said selected programmatic entity remains unchanged if said chosen operation is reproduction;

creating at least one new programmatic entity by crossover using a group of programmatic entities if said chosen operation is crossover, said group of programmatic entities comprising said selected programmatic entity and at least another programmatic entity, wherein a portion of the selected programmatic entity and a portion of said at least another programmatic entity are designed, such that the new programmatic entity created by crossover comprises said portion of said selected programmatic entity other than said designed portion and said designated portion of said at least another programmatic entity, said new programmatic entity differing in size and shape from said selected programmatic entity and said at least another programmatic entity when the designated portion of said selected programmatic entity and said designated portion of said at least another programmatic entity differ in size and shape; and

adding said new programmatic entity to said population.

13. The process defined in claim 10 wherein said step of creating includes creating at least one programmatic entity having a first internally invocable sub-entity referring to a second internally invocable sub-entity within that programmatic entity, such that said internally invocable sub-entity invokes said second internally invocable sub-entity within said at least one programmatic entity when executed.

14. The process defined in claim 10 wherein the step of executing includes the step of said at least one internally invocable sub-entity invoking itself recursively.

15. The process defined in claim 10 wherein the step of executing includes executing one of said programmatic entities having at least one internally invocable sub-entity, such that said at least one internally invocable sub-entity invokes itself by referring to another internally invocable sub-entity in said one of said programmatic entities.

16. The process defined in claim 10 wherein said step of selecting at least one programmatic entity further comprises selection criteria based on a probability that is proportional to said fitness associated with said programmatic entity.

17. The process defined 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 programmatic entity is mutated, such that at least one designated portion of said selected programmatic entity is replaced by a randomly generated portion, such that the randomly generated portion contains only actions, material and references to internally invocable sub-entities that have been given meaning by the other than said designated portion of said selected programmatic entity.

18. The process defined in claim 10 further comprising a step of removing at least one programmatic entity having a relatively low associated fitness.

19. The process defined in claim 10 further including the steps of determining if an individual programmatic entity in said population attains a pre-established fitness with respect to a solution to the problem and designating said individual programmatic entity as the solution to the problem.

20. The process defined in claim 10 wherein the initial population of programmatic entities includes programs created by randomly generating programs of various sizes and structures, said programmatic entities consisting of hierarchical sub-entities, said hierarchical sub-entities including at least either actions and material available for the problem.

21. The process defined in claim 10 wherein the steps of executing includes executing more than one programmatic entity simultaneously.

22. The process defined in claim 10 wherein said step of executing includes selecting more than one programmatic entity simultaneously.

23. The process defined in claim 10 wherein said step of choosing and performing is performed simultaneously for more than one programmatic entity.

24. The process defined in claim 10 wherein if said operation of reproduction is chosen for at least one of said programmatic entities then said step of executing is not repeated for said at least one of said programmatic entities.

25. In a computing system having at least one processor and a memory, a computer implemented process for solving a problem comprising the steps of:

creating an initial population of programmatic entities having sub-entities, wherein at least one of said sub-entities produces a result upon execution and at least one of said programmatic entities in the population has at least one function defining sub-entity, said one of said at least one sub-entity capable of including at least one invocation of a function defining sub-entity; and

evolving said population to generate a solution to said problem, wherein said step of evolving includes the step of executing each said programmatic entity to produce a result, wherein the function defining sub-entity is invoked by said one of the programmatic entities that produces results, such that the solution to said problem is derived from results produced by evolving said population.

26. The process defined in claim 25 wherein the step of creating an initial population includes the step of creating at least one programmatic entity having a function defining sub-entity that remains constant, such that the function defining sub-entity does not undergo evolution.

27. The process defined in claim 25 wherein said function defining sub-entity includes at least one action.

28. The process defined in claim 25 wherein said function defining sub-entity includes material.

29. The process defined in claim 28 wherein material comprises material provided to said one of said programmatic entities that produces results.

30. The process defined in claim wherein material comprises material provided to said function defining sub-entity.

31. A computing system for solving problems comprising a processor and a memory means coupled to said processor for storing a population of programmatic entities, wherein each of said programmatic entities is comprised of sub-entities, wherein at least one of said sub-entities is externally invocable and at least one of said programmatic entities in the population has at least one internally invocable sub-entity, said at least one externally invocable sub-entity including at least one invocation of an internally invocable sub-entity, said computing system further comprising:

means for executing each said programmatic entity to produce a result, said means for executing coupled to said memory means;

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

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

means for creating at least one new programmatic entity by crossover using a group of programmatic entities if said chosen operation is crossover, said group of programmatic entities comprising said selected programmatic entity and at least another programmatic entity, wherein a portion of the selected programmatic entity and a portion of said at least another programmatic entity are designated, such that said new programmatic entity created by crossover comprises the portion of said selected programmatic entity other than said designated portion and said designated portion of said at least another programmatic entity, wherein said crossover operation is restrained such that said designated portion of said at least another programmatic entity in said new programmatic entity includes only those actions, material and references to internally invocable sub-entities that have been given a meaning by the other than the designated portion of said selected programmatic entity, said new programmatic entity differing in size and shape from said selected programmatic entity and said at least another programmatic entity when the designated portion of said selected programmatic entity and said designated portion of said at least another programmatic entity differ in size and shape, said means for creating coupled to said memory means;

means for retaining said selected programmatic entity such that said selected programmatic entity remains unchanged if said chosen operation is reproduction, said means for retaining coupled to said memory means;

means for adding said new programmatic entity to said population, said means for adding coupled to said memory means.

32. The computing system defined in claim 31 wherein the means for executing includes means for invoking said sub-entities wherein at least one internally invocable sub-entity refers to and invokes another internally invocable sub-entity, such that said another internally invocable sub-entity is executed.

33. The computing system defined in claim 31 further comprising means for selecting at least one programmatic entity further comprising selection criteria based on a probability that is proportional to said fitness associated with said program.

34. The computing system defined in claim 31 further comprising means for choosing and performing the operation of mutation, such that if said chosen operation is mutation, a step of mutation occurs before said adding step, wherein said selected programmatic entity is mutated, wherein at least one portion of said selected programmatic entity is replaced by a randomly generated portion, such that said randomly generated portion contains only actions, material and references to internally invocable sub-entities having meaning in said selected programmatic entity.

35. The computing system defined in claim 31 further comprising means for removing at least one programmatic entity having a relatively low associated value.

36. The computing system defined in claim 31 further comprising means for removing said group from said population.

37. The computing system defined in claim 31 further including means for designating the solution coupled to the processor, wherein said means for designating the solution designates an individual programmatic entity in said population attaining a pre-established fitness is designated as the solution to the problem.

38. The computing system defined in claim 31 further comprising means for creating the initial population of programmatic entities by randomly generating programmatic entities of various size and structures, said programmatic entities having hierarchical sub-entities that include at least one action and material available for the problem.

39. The computing system defined in claim 31 wherein said means for executing executes said at least one programmatic entity, wherein at least one internally invocable sub-entity invokes itself recursively.

40. The computing system defined in claim 31 wherein means for executing executes said at least one programmatic entity, wherein at least one internally invocable sub-entity in one of said programmatic entities invokes itself by referring to another internally invocable sub-entity in said one of said programmatic entities.

41. In a computing system having at least one processor and a memory, a computer implemented process for automatically encoding a set of data values into a procedure for at least approximating said set of data values, using a population of programmatic entities of various sizes and shapes, wherein each programmatic entity is a hierarchical arrangement of actions and material, said process comprising iterations of a series of steps which generate said procedure, each iteration comprising the steps:

executing each said programmatic entity to produce a result;

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

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

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

retaining said selected programmatic entity such that said selected programmatic entity remains unchanged if said chosen operation is reproduction;

adding said new programmatic entity to said population.

42. The process defined in claim 41 wherein said set of data values corresponds to an image, wherein the step of executing each said programmatic entity produces a result approximating the image, and wherein the process further comprises the step of designating the programmatic entity that represents the image as having a relatively high associated fitness over each said programmatic entity having a relatively low associated fitness, such that said process performs image compression.

43. The process defined in claim 41 wherein said set of data values corresponds to an image, wherein the step of executing each said programmatic entity produces a result approximating the image, and wherein the process further comprises the step of designating the programmatic entity that represents the image as having a relatively high associated fitness over each said programmatic entity having a relatively low associated fitness, such that said process performs image encoding.

44. The process defined in claim 42 or claim 43 wherein each of said set of data values is a data structure, such that each data structure represents a plurality of components, and further wherein the step of designating that program having a relatively high associated fitness selects based on the quality of the approximation to the data values produced by said selected programmatic entity.

45. The process defined in claim 41 wherein each of said set of data values is a data structure, such that each data structure represents a plurality of components, and further wherein a programmatic entity having a relatively high associated fitness is selected based on the quality of the approximation to the data values produced by said selected programmatic entity.

46. The process defined in claim 41 further comprising the step of designating an individual programmatic entity in said population attaining a pre-established value of fitness with respect to encoding said data as an encoding that represents said data, said process including the step of translating said programmatic entity representing an encoding of said data into an executable form while maintaining the logical consistency of said programmatic entity representing said encoding of said data.

47. The process defined in claim 41 wherein said step of executing executes more than one programmatic entity simultaneously.

48. The process defined in claim 41 wherein said executing step is performed simultaneously for more than one element of said set of data for at least one programmatic entity.

49. The process defined in claim 41 wherein said iterating a series of steps is performed simultaneously for more than one programmatic entity.

50. A computing system for automatically encoding a set of data values into a procedure for at least approximating said set of data values comprising a processor and a memory means coupled to said processor for storing a population of programmatic entities of various sizes and shapes, wherein each programmatic entity is a hierarchical arrangement of actions and material appropriate to the domain of data values, said computing system further comprising:

means for executing each said programmatic entity to produce a result by performing said hierarchical arrangement of functions, said means for executing coupled to said memory means;

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

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

means for creating at least one new programmatic entity by crossover using a group of programmatic entities if said chosen operation is crossover, said group of programmatic entities comprising said selected programmatic entity and at least another programmatic entity, such that any new programmatic entity created by crossover comprises at least a portion of said selected programmatic entity and at least a portion of said at least another programmatic entity, said new programmatic entity differing in size and shape from said selected programmatic entity and said at least another programmatic entity when said at least a portion of said selected program and said at least a portion of said at least another program differ in size and shape, said means for creating coupled to said memory means;

means for retaining said selected programmatic entity such that said selected programmatic entity remain unchanged if said chosen operation is reproduction, said means for retaining coupled to said memory means;

means for adding said new programmatic entity to said population, said means for adding coupled to said memory means, wherein said computing system generates a computer program representing said data, such that said data is encoded.

51. In a computing system having at least one processor and at least one memory, a computer implemented process for solving a problem using a population of named programmatic entities of various sizes and shapes, wherein each programmatic entity has a hierarchical arrangement of actions and material, at least one programmatic entity containing at least one reference to itself by use of said name, said process comprising iterations of a series of steps, each iteration comprising the steps:

executing each said programmatic entity to produce a result, wherein at least one of the programmatic entities invokes itself recursively;

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

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

creating at least one new programmatic entity by crossover using a group of programmatic entities if said chosen operation is crossover, said group of programmatic entities comprising said selected programmatic entity and at least another programmatic entity, wherein a portion of the selected programmatic entity and a portion of said at least another programmatic entity are designated, such that the new programmatic entity created by crossover comprises said portion of said selected programmatic entity other than said designated portion and said designated portion of said at least another programmatic entity, said new programmatic entity differing in size and shape from said selected programmatic entity and said at least another programmatic entity when the designated portion of said selected programmatic entity and said designated portion of said at least another programmatic entity differ in size and shape;

retaining said selected programmatic entity such that said selected programmatic entity remains unchanged if said chosen operation is reproduction;

adding said new programmatic entity to said population.

52. The process defined in claim 51 wherein the step of executing includes executing more than one programmatic entity is activated simultaneously.

53. The process defined in claim 51 wherein said iterating a series of steps is performed simultaneously for more than one programmatic entity.

54. A computing system for solving a problem comprising at least one processor and at least one memory means coupled to said at least one processor for storing a population of named programmatic entities of various sizes and shapes, wherein each programmatic entity has a hierarchical arrangement of actions and material, said programmatic entity containing at least one reference to itself by use of a name, said computing system comprising:

means for executing each said programmatic entity to produce a result by performing said hierarchical arrangement of functions, wherein at least one programmatic entity invokes itself recursively, said means for executing coupled to said memory means;

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

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

means for creating at least one new programmatic entity by crossover using a group of programmatic entities if said chosen operation is crossover, said group of programmatic entities comprising said selected programmatic entity and at least another programmatic entity, wherein a portion of the selected programmatic entity and a portion of said at least another programmatic entity are designated, such that the new programmatic entity created by crossover comprises said portion of said selected programmatic entity other than said designated portion and said designated portion of said at least another programmatic entity, said new programmatic entity differing in size and shape from said selected programmatic entity and said at least another programmatic entity when the designated portion of said selected programmatic entity and said designated portion of said at least another programmatic entity differ in size and shape;

means for retaining said selected programmatic entity such that said selected programmatic entity remains unchanged if said chosen operation is reproduction, said means for retaining coupled to said memory means;

means for adding said new programmatic entity to said population, said means for adding coupled to said memory means, wherein said computing system generates a computer program representing said data, such that said data is encoded.

55. In a computing system, a computer implemented process for solving an original problem comprising the stages of:

(a) decomposing said original problem into at least one subproblem;

(b) finding at least one solution to said at least one subproblem; and

(c) assembling said at least one solution to said at least one subproblem into a solution to said original problem;

wherein stages (a)-(c) are implemented using a series of steps including

creating a population of programmatic entities having sub-entities, wherein at least one of said sub-entities is externally invocable and at least one of said programmatic entities in the population has at least one internally invocable sub-entity, said at least one externally invocable sub-entity including at least one invocation of internally invocable sub-entities; and

evolving said population, including the step of executing the programmatic entities, wherein said at least one externally invocable sub-entity performing said at least one invocation of at least one of said internally invocable sub-entities to produce results and, wherein said step of evolving further includes the step of generating at least one new programmatic entity in response to the results, such that at least one of the programmatic entities in said population is designated a solution to the problem.

56. The process defined in claim 55 wherein said at least one externally invocable sub-entity includes at least one action.

57. The process defined in claim 55 wherein said at least one externally invocable sub-entity includes material.

58. The process defined in claim 57 wherein material comprises material provided to said at least one externally invocable sub-entity.

59. The process defined in claim 57 wherein material comprises material provided to said at least one internally invocable sub-entity.

60. The process defined in claim 55 wherein said at least one internally invocable sub-entity includes material.

61. The process defined in claim 55 wherein said at least one internally invocable sub-entity includes at least one action.