Optimization techniques using genetic algorithms

• US 5,222,192 A
• Filed: 09/03/1992
• Issued: 06/22/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/939,420
• Time in Patent Office: 292 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 interrrupting 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. A computer method for finding the best solution to a problem of the kind for which there is a space of possible solutions, comprising

providing by computer a representational scheme for representing trial solutions as values of tokens in said solution space, said representational scheme defining characteristics of said tokens,

using said representational scheme to represent by computer trial solutions in said solution space as values of tokens,

maintaining said tokens in computer memory,

computer processing said tokens iteratively to modify their values in a manner for causing the values of the tokens to converge on the best solution,

in at least some computer processing iterations, analyzing characteristics of said tokens and/or the set of trial solutions, and

computer modifying the representational scheme for later computer processing iterations based on the analysis of earlier iterations, and without interrupting the succession of iterations.

2. The method of claim 1 wherein

said tokens comprise subtokens whose values represent trial values of parameters that belong to said trial solutions, said subtokens being maintained in computer memory,

characteristics of individual subtokens are analyzed, and

the representational scheme is computer modified with respect to individual subtokens on the basis of corresponding analyzed subtoken characteristics.

3. The method of claim 1 wherein

said tokens are each represented in said representational scheme as a string of characters,

said representational scheme defines the number of characters in said string, said number corresponding to the resolution with which the values of said tokens represent said trial solutions, and

said step of computer modifying the representational scheme includes computer invoking at least one operator for adjusting said number of characters in order to change said resolution.

4. The method of claim 3 wherein said operator is invoked on the basis of a measurement of convergence of the population of tokens.

5. The method of claim 1 wherein said representational scheme includes an adaptive translation mapping for converting values of tokens to corresponding trial solutions, and said modifying step includes invoking at least one operator for changing said adaptive translation mapping.

6. The method of claim 5 wherein said adaptive translation mapping defines upper and lower boundaries on said trial solutions and said operator changes at least one of said boundaries.

7. The method of claim 6 wherein said operator randomly perturbs said boundaries.

8. The method of claim 6 wherein said operator shifts said boundaries towards lower values.

9. The method of claim 6 wherein said operator shifts said boundaries towards higher values.

10. The method of claim 6 wherein said operator shifts both of said boundaries further apart.

11. The method of claim 6 wherein said operator shifts both of said boundaries closer together.

12. The method of claim 5 wherein said operator comprises an elitist operator which stores in said computer information about a token representing a favorable possible solution in one said iteration, and reimparts said information to a population of tokens in a later said iteration.

13. The method of claim 12 wherein said operator comprises an ultra elitist operator which stores information about the current most favorable trial solution in one said iteration, allowing the population of said tokens or said trial solutions to "forget" (not contain) said most favorable solution for a specified number of iterations after which said operator reimparts said information to the population of said tokens or said trial solutions

14. The method of claim 12 wherein said operator comprises a roving elitist operator which stores information concerning the most favorable trial solution in each said iteration and employs said information after each application of any other operator acting upon said adaptive translation mapping to assure that said mapping remains capable of representing said most favorable trial solution.

15. The method of claim 5 wherein said operator comprises a homotopy optimizer operator which adjusts trial solutions.

16. The method of claim 5 wherein said operator comprises a biased mutation operator which stochastically selects characters of said population of said tokens, mutates selected said characters evaluates said mutated tokens, and accepts or rejects said mutated characters dependent upon a stochastic sampling of a probability distribution dependent upon some function of the differences in the evaluations of said mutated tokens before versus after said mutations.

17. The method of claim 14 wherein said characters are mutated one at a time and the acceptance or rejection is determined after each mutation.

18. The method of claim 5 wherein said operator comprises an annealing schedule operator that either raises or lowers the rate at which mutations are accepted based on measurements of convergence and/or characteristics of said trial solutions.

19. The method of claim 5 wherein said operator comprises a splitting operator that splits the tokens into species and splits the trial solution space into domains specific to the species to permit searches to proceed simultaneously with respect to the different species.

20. The method of claim 5 wherein said operator comprises a joining operator that recombines two species of tokens into a single species for subsequent iterations of the solution method.

21. The method of claim 19 or 20 wherein said operator is triggered based on a measurement of the fourth moment of said trial solutions.

22. The method of claim 3 or 5 further comprising

specifying threshold values for defining a range within which said operator is not invoked, and

maintaining said threshold values in computer memory.

23. The method of claim 3 or 5 further comprising

providing factors that define the magnitude of the effect of invoking said operator.

24. The method of claim 3 or 5 wherein

said tokens comprise subtokens, and

said operator is applied selectively to one or more of said subtokens.

25. The method of claim 1 wherein said step of analyzing characteristics of said tokens includes applying a statistical measurement across a population of trial solutions or a population of tokens.

26. The method of claim 25 wherein said measurement is a measurement of the convergence of said tokens.

27. The method of claim 26 wherein said operator comprises a dither operator, a homotopy optimizer operator, or an annealing schedule operator.

28. The method of claim 25 wherein said measurement is a measurement of the first moment of said trial solutions.

29. The method of claim 28 wherein said operator comprises a shift left operator or a shift right operator.

30. The method of claim 25 wherein said measurement is a measurement of the second moment of said trial solutions.

31. The method of claim 30 wherein said operator comprises an expansion operator, a contraction operator, a homptopy optimizer, or an annealing schedule operator.

32. The method of claim 25 wherein said measurement is a measurement of the fourth moment of said trial solutions.

33. The method of claim 32 wherein said operator comprises a splitting operator or a rejoining operator.

36. The method of claim 1 or 34 wherein said problem comprises a combinatorial optimization problem.

37. The method of claim 1 or 34 wherein said problem comprises a function optimization problem.

34. A computer method for finding the best solution to a problem of the kind for which there are a number of possible solutions, comprising

providing by computer a representational scheme for representing trial solutions as values of tokens, said representational scheme defining characteristics of said tokens,

using said representational scheme to represent by computer a population of chromosomes made up of genes whose values correspond to parameters of said possible solutions and are represented in accordance with said representational scheme,

maintaining said genes in computer memory,

computer processing said genes iteratively to produce successive generations of the chromosome population in order to cause the values of the genes to converge on the best solution,

in at least some generations, performing a computer measurement of convergences of the genes in the chromosome population, and the first and second moments of the parameter values of the possible solutions, and

computer modifying the representational scheme based on the measurements using computer-invoked operators which increase or decrease the resolution of the genes as stored in computer memory, and shift left or right and expand or contract the upper or lower boundaries of the parameters of the possible solutions.

35. The method of claim 34 wherein said operators include ultra elitism and roving elitism.

38. A computer method for finding the best solution to a problem of the kind having possible solutions within a solution space, comprising

providing a representational scheme for representing trial solutions as values of tokens in said solution space, said representational scheme defining characteristics of said tokens,

using said representational scheme to represent by computer, trial solutions in said solution space as values of tokens in accordance with said representational scheme,

maintaining said tokens in computer memory,

computer processing said tokens to change the token values and to thereby explore said solution space,

taking computer measurements of the tokens maintained in computer memory and corresponding possible solutions which reflect the nature of said problem, and

adjusting the computer representational scheme based on said measurements to enable said tokens to explore successive portions of said solution space at possibly changing resolutions in order to reach said best solution.