Process for problem solving using spontaneously emergent self-replicating and self-improving entities

• US 5,390,282 A
• Filed: 06/16/1992
• Issued: 02/14/1995
• Est. Priority Date: 06/16/1992
• 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): Downs, Robert W.
• Application Number:
  US07/899,627
• Time in Patent Office: 973 Days
• Field of Search: 395/13
• US Class Current: 706/13
• CPC Class Codes: G06N 3/004 Artificial life, i.e. computing arrangements simulating life
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

An apparatus and process for solving problems using self-replicating and self-improving entities. The present invention includes an apparatus and process for solving a problem using a population of entities, wherein each of the entities is an arrangement of actions and material which are capable of including an incorporation action and are capable of including an emission action. The present invention also includes a process and apparatus for activating each of the entities by presenting each of the entities with at least one combination of environmental material. If an entity has an incorporation action then that entity searches the population for a part of one of the entities and then incorporates the portion of the one entity associated with the part into itself. If the entity includes an emission action then the entity searches the population for a part and then the entity produces at least one emission, such that if the entity responds effectively to a combination of environmental material then the emission enters the population and if the entity fails to respond effectively then the emission fails to enter the population. The activation continues until one of the entities responds effectively to a specified number of combinations of material, such that a solution to the problem is generated.

Claims

1. A process for solving a problem using a population of programs, wherein each of said programs is an arrangement of functions and terminals that include at least either an incorporation function or an emission function, said process comprising the steps of:

activating each program by presenting each of said programs with at least one combination of environmental conditions,

if said each program includes an incorporation function then said program searching said population for a part of one of said programs and then incorporating the portion of said one program associated with said part into said each program,

if said program includes an emission function then said program searching said population for a part and then said each program producing at least one emission, and if said each program responds effectively to said at least one combination then said at least one emission the population and if said each program fails to respond effectively then said at least one emission not entering the population;

generating a solution to the problem by continuing the step of activating until one of said programs responds effectively to a specified number of combinations of environmental conditions.

2. The process as in claim 1 further comprising the step of removing said each program from the population if said each program fails to respond effectively.

3. The process as in claim 1 further comprising the step of:

said each program searching for said part using a template.

4. The process as in claim 3 further comprising the step of:

said each program searching for said part using a template by searching for an exact match of said template.

5. The process as defined in claim 4, 6, or 7 wherein the match is a partial match.

6. The process as in claim 3 further comprising the step of:

said each program searching for said part using a template by searching for a complimentary match of said template.

7. The process as in claim 3 further comprising the step of:

said each program for said part using a template by searching for a corresponding match of said template.

8. The process as defined in claim 3 wherein said step of said each program searching comprises said each program searching only at a designated location of each of said programs for said template if said each program has an incorporation function.

9. The process as defined in claim 3 wherein said step of said each program searching comprises said each program searching only at a designated location of each of said programs for said template if said each program is performing an emission function.

10. The process as defined in claim 3 further comprising the step of:

said each entity searching using a template listing.

11. The process as defined in claim 10 further comprising the step of reordering the population by choosing from said template listing.

12. The process as defined in claim 1 wherein said step of incorporating includes incorporating the entirety of said one program if said each program is performing an incorporation function.

13. The process as defined in claim 1 wherein said step of producing an emission includes producing an emission having copy of the portion of said one program associated with said part into said each program.

14. The process as defined in claim 13 wherein said portion comprises the entirety of said one program.

15. The process as defined in claim 1 further comprising the step of continually activating each of said programs for a specified time, and removing said program from said population after said specified time.

16. The process as defined in claim 15 wherein said specified time is one program lifetime, wherein said step Of removing includes removing said entity after said each program has been activated a number of times compatible with that lifetime.

17. The process as defined in claim 1 wherein said step of searching includes;

each program searching itself first and then searching the other of said programs in said population.

18. A process for solving a problem using functions and terminals, said process comprising the steps of:

creating a population of programs of various sizes and shapes, wherein each program is a hierarchical arrangement of functions and terminals;

activating each program by presenting each of said programs with at least one combination of environmental conditions,

if said each program includes an incorporation function then said program searching said population for a part of one of said programs and then incorporating the portion of said one program associated with said part into said each program,

if said program includes an emission function then said program searching said population for a part and then said each program producing at least one emission, and if said each program responds effectively to said at least one combination then said at least one emission entering the population and if said each program fails to respond effectively then said at least one emission not entering the population;

generating a solution to the problem by continuing the step of activating until one of said programs responds effectively to a specified number of combinations of environmental conditions.

19. The process as in claim 18 further comprising the step of:

said program searching itself first and then searching the other programs in said population.

20. The process as in claim 18 further comprising the step of:

said program searching only the top of the hierarchical arrangement of the programs in the population.

21. The process as in claim 18 further comprising the step of:

said program only searching a predetermined number of said programs in the population.

22. The process as in claim 18 further comprising the step of maintaining the population at a predetermined size.

23. The process as in claim 22 wherein the step of maintaining comprises culling the population.

24. The process as in claim 23 wherein said step of culling the population includes culling the population using a uniform random probability distribution.

25. The process as in claim 18 further comprising the step of:

said each entity searching using a template.

26. The process as in claim 25 further comprising the step of:

said each entity searching using a template listing.

27. A computing system for solving a problem comprising at least one processor and a memory means coupled to said processor for storing a population of computer programs, wherein each of said programs is comprised of functions and terminals, said computing system further including:

means for activating each of said programs, wherein said means for activating presents each of said programs with at least one combination of environmental conditions, wherein if said each program includes an incorporation function then said at least one processor searches said population for a part of one of said programs and then incorporates the portion of said one program associated with said part into said each program, and wherein if said at least one processor includes an emission function then said program searches said population for a part and then said each program produces at least one emission, such that if said each program responds effectively to said at least one combination then said at least one emission enters the population and if said each program fails to respond effectively then said at least one emission fails to enter the population; and

means for continually invoking said means for activating, said means for continually invoking coupled to said means for activating and said memory means, wherein said means for continually invoking invokes said means for activating until one of said programs responds effectively to a specified number of combinations of environmental conditions, wherein a solution to the problem is generated.

28. The computing system as in claim 27 wherein said means for activating searches using a template.

29. The computing system as in claim 28 further comprising means for creating and storing a template listing.