Optimization techniques using genetic algorithms

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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

Claim 6

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.

Claim 7

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.

Claim 8

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

Claim 9

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

Claim 10

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

Claim 11

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

Claim 12

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

Claim 13

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.

Claim 14

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

Claim 15

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.

Claim 16

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

Claim 17

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.

Claim 18

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

Claim 19

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.

Claim 20

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.

Claim 21

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.

Claim 22

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

Claim 23

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.

Claim 24

The method of claim 3 or 5 further comprising providing factors that define the magnitude of the effect of invoking said operator.

Claim 25

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.

Claim 26

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.

Claim 27

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

Claim 28

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

Claim 29

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

Claim 30

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

Claim 31

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

Claim 32

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

Claim 33

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

Claim 34

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

Claim 35

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.

Claim 36

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.

Claim 37

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

Claim 38

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

Claim 39

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

Claim 40

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.

Claim 41

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.