Learnable non-darwinian evolution

• US 6,523,016 B1
• Filed: 04/12/2000
• Issued: 02/18/2003
• Est. Priority Date: 04/12/1999
• Status: Expired due to Fees

• Current Assignee: George Mason Intellectual Properties, Inc.
• Original Assignee: George Mason University
• Inventors: Michalski, Ryszard S.
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): Holmes, Michael B.
• Application Number:
  US09/548,286
• Time in Patent Office: 1,042 Days
• Field of Search: 706/12, 706/23, 706/13, 706/14, 703/6
• US Class Current: 706/12
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

The present invention relates to novel systems and methods in which a machine learning mode is used to generate new populations in an evolutionary process. A preferred embodiment of the present invention called Learnable Evolution Model (briefly, LEM) employs a machine learning mode at selected steps of evolutionary computation to determine reasons why certain individuals in a population are superior to others in performing a designated class of tasks. These reasons, expressed as inductive hypotheses, are used to create a new generation of individuals (phenotypes or genotypes). An evolutionary process in LEM can alternate between a machine learning mode and a Darwinian evolution mode switching to another mode, in any effective order, when a mode termination condition is met, or it can rely on a repetitious application of the machine learning mode with randomly or methodologically generated populations.

Claims

1. A method of generating solutions to problems by learnable evolution model (LEM), comprising:

a) inputting a population of solutions to a problem;

b) executing a Machine-Learning mode, comprising;

i) sorting a population of solutions into at least a high quality group, medium quality (which can be empty), and a low quality group, where the quality is determined by a fitness function;

ii) obtaining a description of the high quality group, where the description is obtained using a machine-learning method or system and the description distinguishes the high quality group from the low quality group, and optionally, a description of a low quality group that distinguishes it from the high quality group;

iii) generating a Machine-Learning mode population of Machine-Learning mode solutions, where the Machine-Leaming mode solutions satisfy the description of the high quality group, and optionally, do not satisfy the description of the low quality group;

c) repeating step b) until a predetermined Machine-Learning mode termination condition is met;

d) repeating steps a)-c) until a predetermined LEM termination condition is met.

2. A method of claim 1, wherein the population of step (a) is generated randomly, by avoid-past-failures, by select-elite, by use-recommendations method, or some other method.

3. A method of claim 1, further comprising:

executing a Darwinian evolution mode, comprising;

i) generating a Darwinian evolution mode of Darwinian evolution mode solutions to the problem by applying a Darwinian evolutionary method to the starting population or the Machine-Learning mode population.

9. A method of claim 1, wherein the solutions in a) comprise continuous variables, further comprising assigning values to the variables by fixed discretization and/or adaptive anchoring discretization.

10. A method of claim 9, wherein the values are assigned by adaptive anchoring discretization.

11. A method of claim 10, wherein adaptive anchoring discretization comprises determining a consecutive order approximation.

12. A method of claim 3, wherein the solutions in a) comprise continuous variables, further comprising assigning values to the variables by fixed discretization and/or adaptive anchoring discretization.

4. A method of generating solutions by learnable evolution model (LEM), comprising:

a) inputting a population of solutions to a problem;

b) executing a Machine-Learning mode and a Darwinian evolution mode,

wherein the Machine-Learning mode comprises;

i) sorting a population of solutions into at least a high quality group, medium quality (can be empty), and a low quality group, where the quality is determined by a fitness function;

ii) obtaining a description of the high quality group, where the description is obtained using a machine-learning method or system and the description distinguishes the high quality group from the low quality group;

iii) generating a new population of new solutions, where the new solutions satisfies the description of the high quality solutions; and

wherein the Darwinian evolutionary mode comprises;

i) generating a new population of new solutions to the problem by applying a Darwinian evolutionary method to the population.

5. A method of claim 4, comprising alternating between the Machine-Learning mode and Darwinian evolution mode, wherein each mode is performed repetitively, switching to the next mode when a predetermined mode termination condition is met.

6. A method of claim 4 or 5, wherein said method is initiated in the Machine-earning mode.

7. A method of claim 4 or 5, wherein said method is initiated in the Darwinian Evolution mode.

8. A method of claim 4, wherein the Darwinian evolution and Machine-Learning modes are performed repetitively until a predetermined learnable evolution model termination condition is met.

13. A method of generating solutions by learnable evolution model (LEM), comprising:

a) inputting a starting population of starting solutions to a problem;

b) executing a Darwinian evolutionary mode, comprising;

i) generating a new population of new solutions to the problem by applying a Darwinian evolutionary method to the starting population;

c) executing a Machine-Learning mode, comprising;

i) sorting the first new population of solutions into at least a high quality group, medium quality (can be empty), and a low quality group, where the quality is determined by a fitness function;

ii) obtaining a description of the high quality group, where the description is obtained using a machine-learning method or system and the description distinguishes the high quality group from the low quality group;

iii) generating a new population of new solutions, where the new solutions satisfies the description of the high quality solutions of the current generation and some number of past generations.

14. A system for generating solutions by learnable evolution model (LEM), comprising:

a) a Darwinian evolution mode means, wherein said Darwinian evolution mode means comprises a means for generating a new population of new solutions to a problem by applying a Darwinian evolutionary method to a starting population of solutions;

b) a Machine-Learning mode means, wherein said Machine-Learning mode means comprises;

a means for sorting a population of solutions into at least a high quality group, medium quality, and a low quality group, where the quality is determined by a fitness function;

a means for obtaining a description of the high quality group, where the description is obtained using a machine-learning method or system and the description distinguishes the high quality group from the low quality group; and

a means for generating a new population of new solutions, where the new solutions satisfies the description of the high quality solutions.

15. A system for generating solutions by learnable evolution model (LEM), comprising:

a Machine-Learning mode means, wherein said Machine-Learning mode means comprises;

a means for sorting a population of solutions into at least a high quality group, medium quality, and a low quality group, where the quality is determined by a fitness function;

a means for obtaining a description of the high quality group, where the description is obtained using a machine-learning method or system and the description distinguishes the high quality group from the low quality group; and

a means for generating a new population of new solutions, where the new solutions satisfies the description of the high quality solutions, regenerating this method with new population generated randomly or by some method many times until the LEM termination condition is met (the best solution is satisfactory or allocated resources have been exhausted).