Simultaneous evolution of the architecture of a multi-part program to solve a problem using architecture altering operations

• US 5,742,738 A
• Filed: 08/04/1994
• Issued: 04/21/1998
• Est. Priority Date: 05/20/1988
• Status: Expired due to Term

• Current Assignee: John R. Koza
• Original Assignee: John R. Koza
• Inventors: Tackett, Walter Alden, Andre, David, Koza, John R.
• Primary Examiner(s): Downs, Robert W.
• Application Number:
  US08/286,134
• Time in Patent Office: 1,356 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 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 process for solving a problem comprising the steps of:

creating a population of programmatic entities;

generating a solution to the problem, wherein the step of generating the solution comprises the steps of

altering an architecture of at least one of the population of programmatic entities, and

evolving the population to generate a new entity, wherein the step of altering and the step of evolving are performed such that a solution to the problem is created while evolving the architecture of said at least one of the population of programmatic entities.

2. The process defined in claim 1 wherein at least one 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 entities in the population has at least one internally invocable sub-entity.

3. The process defined in claim 2 wherein said step of altering the architecture 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.

4. The process defined in claim 2 wherein said step of altering the architecture 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.

5. The process defined in claim 2 wherein said step of altering the architecture 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.

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

7. The process defined in claim 6 wherein the step of altering the architecture further comprises the step of placing a tree structure at an occurrence of an invocation of the deleted portion of the internally invocable sub-entity.

8. The process defined in claim 7 wherein the step of placing a tree structure at an occurrence of the internally invocable sub-entity once deleted comprises the step of randomly generating the tree structure.

9. The process defined in claim 6 further comprising the step of replacing the portion of the internally invocable sub-entity with another internally invocable sub-entity in the programmatic entity containing the internally invocable sub-entity.

10. The process defined in claim 6 further comprising the step of performing macro expansion.

11. The process defined in claim 2 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.

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

13. The process defined in claim 12 wherein the step of altering further comprises the step of placing a tree structure at an occurrence of the argument once deleted.

14. The process defined in claim 13 wherein the step of placing a tree structure at an occurrence of the argument once deleted comprises the step of randomly generating the tree structure.

15. The process defined in claim 12 further comprising the step of replacing the argument with another argument defined for use in the internally invocable sub-entity.

16. The process defined in claim 12 further comprising the step of performing macro expansion.

17. 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.

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

19. The process defined in claim 1 wherein the step of evolving comprises a series of iterative steps, wherein each of said population of programmatic entities is activated to produce a result, and thereafter is subjected to an operation to generate a new entity, said new entity being added to the population, such that a solution to said problem is generated.

20. The process defined in claim 1 wherein each of the population of entities comprises exactly two sub-entities, each of said programmatic entities in the population having only one internally invocable sub-entity with a minimum number of arguments and one externally invocable sub-entity.

21. The process defined in claim 20 wherein the minimum number of arguments comprises a single argument.

22. The process defined in claim 1 wherein the step of creating a population of programmatic entities comprises creating a population of entities, where each of the population of entities has only an externally invocable sub-entity.

23. The process defined in claim 1 wherein the step of creating a population of programmatic entities comprises creating a population of entities where at least two of the entities have different architectures.

24. A process for solving a problem comprising the steps of:

creating a population of programmatic entities;

evolving the population, wherein the step of evolving comprises the step of altering an architecture of at least one of the population of programmatic entities, wherein the step of altering comprises duplicating an internally invocable sub-entity of said at least one of the population and adding the duplicated internally invocable sub-entity to said at least one of the population as a new internally invocable sub-entity, said step of altering further comprising the step of changing a portion of references referencing the duplicated internally invocable sub-entity to reference the new internally invocable sub-entity.

25. A process for solving a problem comprising the steps of:

creating a population of programmatic entities;

evolving the population, wherein the step of evolving comprises the step of altering an architecture of at least one of the population of programmatic entities, wherein the step of altering comprises duplicating an argument in an internally invocable sub-entity of said at least one of the population to create an additional argument and changing a portion of occurrences of the duplicated argument in said at least one of the population internally invocable sub-entity to the additional argument, wherein an architecture of a programmatic entity is simultaneously evolved with a solution to the problem, such that a new programmatic entity is generated.

26. A process for solving a problem comprising the steps of:

creating a population of programmatic entities; and

evolving the population, wherein the step of evolving comprises the step of altering an architecture of at least one of the population of programmatic entities, wherein the step of altering comprises deleting an argument of an internally invocable sub-entity of said at least one of the population and eliminating occurrences of said argument throughout said internally invocable sub-entity, wherein an architecture of a programmatic entity is simultaneously evolved with a solution to the problem, such that a new programmatic entity is generated.

27. The process defined in claim 26 wherein the step of altering further comprises the step of placing a tree structure at an occurrence of the argument once deleted.

28. The process defined in claim 27 wherein the step of placing a tree structure at an occurrence of the argument once deleted comprises the step of randomly generating the tree structure.

29. The process defined in claim 27 wherein the tree structure comprises a variable.

30. The process defined in claim 26 further comprising the step of deleting each instantiation of the argument at each occurrence of said internally invocable sub-entity in said at least one of the population.

31. A process for solving a problem comprising the steps of:

creating a population of programmatic entities; and

evolving the population, wherein the step of evolving comprises the step of altering an architecture of at least one of the population of programmatic entities, wherein the step of altering comprises deleting an internally invocable sub-entity of said at least one of the population and eliminating occurrences of said internally invocable sub-entity throughout said at least one of the population, wherein an architecture of a programmatic entity is simultaneously evolved with a solution to the problem, such that a new programmatic entity is generated.

32. The process defined in claim 31 further comprising the step of placing a tree structure at an occurrence of the internally invocable sub-entity once deleted.

33. The process defined in claim 31 wherein the tree structure comprises a randomly generated tree structure.

34. The process defined in claim 31 wherein the tree structure comprises a variable.

35. A process for solving a problem comprising the steps of:

creating a population of programmatic entities;

evolving the population, wherein the step of evolving comprises the step of altering an architecture of at least one of the population of programmatic entities, wherein the step of altering comprises creating an internally invocable sub-entity of said at least one of the population to create an additional internally invocable sub-entity and adding the additional internally invocable sub-entity to said at least one of the population, wherein at least one architecture of a programmatic entity is simultaneously evolved with a solution to the problem, such that a new programmatic entity is generated.

36. A process for solving a problem comprising the steps of:

creating a population of programmatic entities;

evolving the population, wherein the step of evolving comprises the step of altering an architecture of at least one of the population of programmatic entities, wherein the step of altering comprises creating an argument in an internally invocable sub-entity of said at least one of the population, wherein at least one architecture of a programmatic entity is simultaneously evolved with a solution to the problem, such that a new programmatic entity is generated.

37. An apparatus for solving a problem comprising:

means for creating a population of programmatic entities;

means for generating a solution to the problem comprising

means for altering an architecture of at least one of the population of programmatic entities, and

means for evolving the population to generate a new entity, wherein the means for altering and the means for evolving operate to create a solution to the problem while evolving the architecture of said at least one of the population of programmatic entities.

38. The apparatus defined in claim 37 further comprising means for duplicating a portion of an internally invocable sub-entity from a programmatic entity in the population of programmatic entities.

39. The apparatus defined in claim 38 wherein said portion comprises an internally invocable sub-entity.

40. The apparatus defined in claim 38 wherein said portion comprises an argument of an internally invocable sub-entity.

41. The apparatus defined in claim 37 wherein the means for altering comprises means for deleting a portion of an internally invocable sub-entity from a programmatic entity in the population of programmatic entities.

42. The apparatus defined in claim 41 wherein said portion comprises an internally invocable sub-entity.

43. The apparatus defined in claim 41 wherein the means for altering further comprises means for placing a tree structure at an occurrence of an invocation of the deleted internally invocable sub-entity.

44. The apparatus defined in claim 41 wherein said portion comprises an argument of an internally invocable sub-entity.

45. The apparatus defined in claim 44 wherein the means for altering further comprises means for placing a tree structure at an occurrence of the argument once deleted.

46. The apparatus defined in claim 44 further comprising means for replacing the argument with another argument defined for use in the internally invocable sub-entity.

47. The apparatus defined in claim 37 further comprising means for replacing an internally invocable sub-entity with another internally invocable sub-entity in a programmatic entity.

48. The apparatus defined in claim 37 wherein the means for altering comprises means for creating an internally invocable sub-entity from a portion of an internally invocable sub-entity.

49. The apparatus defined in claim 37 wherein the means for altering comprises means for creating an argument for an internally invocable sub-entity.

50. A process for solving a problem comprising the steps of:

maintaining a population of programmatic entities; and

modifying one or more programmatic entities in the population so as to evolve the population of programmatic entities to create a solution to the problem, said step of modifying including the step of altering an architecture of at least one of the population.

51. An apparatus for solving a problem comprising:

means for maintaining a population of programmatic entities; and

means for modifying one or more programmatic entities in the population so as to evolve the population of programmatic entities to create a solution to the problem, said means for modifying including means for altering an architecture of at least one of the population.