Genetic algorithm

• US 5,255,345 A
• Filed: 09/01/1992
• Issued: 10/19/1993
• Est. Priority Date: 02/17/1988
• Status: Expired due to Fees

• Current Assignee: Craig G. Shaefer
• Original Assignee: The Rowland Institute For Science, Inc.
• Inventors: Shaefer, Craig G.
• Primary Examiner(s): MacDonald, Allen R.
• Application Number:
  US07/938,761
• Time in Patent Office: 413 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
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

In one aspect, an optimization method finds the best solution to a problem of the kind for which there is a space of possible solutions; in the method, tokens (e.g., chromosomes) take on values that represent trial solutions in accordance with a representational scheme that defines the relationships between given token values and corresponding trial solutions; by an iterative process, the values of the tokens are changed to explore the solution space and to converge on the best solution; and for at least some iterations, characteristics of the tokens and/or the trial solutions are analyzed and the representational scheme for later iterations is modified based on the analysis for earlier iterations without interrupting the succession of iterations. In another aspect, a set of operators is made available to enable a user to implement any one of at least two different algorithms.

Claims

1. An improvement to a computer problem solving method of the kind which specifies tokens whose values represent trial solutions in accordance with a representational scheme for representing said trial solutions, said computer performing successive iterations of a process on said stored tokens to cause the values of the tokens to converge on best solutions, the improvement comprising

performing a computer measurement across a population of the tokens, and

the computer controlling one of said successive iterations of said process on said stored tokens in response to the computer measurement across the population.

2. The improvement of claim 1 wherein said step of performing a computer measurement comprises performing a computer measurement of the convergence of said tokens.

3. An improvement to a computer problem solving method of the kind which specifies tokens whose values represent trial solutions in accordance with a representational scheme for representing said trial solutions, said computer performing successive iterations of a process on said stored tokens to cause the values of the tokens to converge on best solutions, the improvement comprising

performing a computer measurement of the first, second, or fourth moments across a population of the tokens, and

the computer controlling one of said successive iterations of said process on said stored tokens in response to the computer measurement across the population.

4. A computer method for selectively implementing at least two different problem solving algorithms on a computer, each algorithm being of the kind in which one or more trial solutions for a problem are represented by one or more tokens maintained in computer memory in accordance with a representational scheme, and in which the desired solution is reached by computer processing said tokens iteratively to modify their values, wherein in each iteration one or more computer-invoked operators may be applied to change either the token values or the trial solutions, said method comprising

storing in memory a set of computer-invokable available operators sufficient to perform multiple different problem solving algorithms,

a computer user selecting from the set of available operators a subset of operators for implementing one of the algorithms,

the computer performing the one algorithm using the subset of operators, and

repeating the selecting and performing steps for a second of the algorithms.

5. The method of claim 4 wherein for each of the algorithms the one or more tokens define a solution space to be searched via computer to reach the desired solution, said method further comprising

the computer user defining a single consistent solution space to be searched by more than one of the problem solving algorithms.

6. The method of claim 5 wherein the search space has the same size for all of the algorithms.

7. The method of claim 5 further comprising

the computer user inplementing a succession of different said algorithms using said consistent search space,

the computer tracking the operation of each of the different algorithms, and

the computer generating corresponding tracking information for each algorithm, the tracking information for different algorithms being comparable.

8. The method of claim 7 wherein the tracking information includes at least one of:

the relative number of iterations required by the different algorithms to reach a solution, the solution reached, or the sequence of trial solutions traversed.

9. The method of claim 8 wherein said operators include at least random mutation, homotopy, and crossover, and said algorithms include Monte Carlo, simulated annealing, homotopy, and genetic algorithms.

10. The method of claim 9 wherein said operators further comprise operators that alter said representational scheme based on measurement of said search space and/or said trial solutions.

11. An improvement of a computer method for finding the best solution, in terms of a predetermined definition of the relative merit of a given solution, to a problem which has a range of possible solutions, the method including representing a set of possible solutions by a corresponding set of values, and, in successive iterations, revising the set of values based on the relative merits of the corresponding solutions, the improvement comprising

storing in a computer a representational scheme which defines characteristics of values used to represent possible solutions, and

modifying by computer said characteristics defined in said representational scheme in response to the values belonging to the set of values in a given said iteration, and without interrupting the succession of iterations.