Genetic optimization computer system

• US 20060224536A1
• Filed: 03/02/2006
• Published: 10/05/2006
• Est. Priority Date: 03/02/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Todd, Stephen, Todd, Peter James
• Granted Patent: US 7,302,416 B2
• Time in Patent Office: Days
• US Class Current: 706/16
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A genetic optimization computer system comprises a model and an optimizer. The model defines the structure of a candidate solution to a problem as a plurality of objects in combination (A,B,C). The objects consist of defined parameters (x,y). The model also runs potential solutions to the problem and generates an output. The optimizer stores potential solution candidates and crosses pairs of them to produce new child solution candidates which are run by the model. The child solutions are evaluated on the basis of the model output and their fitness for purpose indicated, and identified to the optimizer. The model also defines at least one group of objects which are identically structured and equivalent to each other. By associating each object of the defined group from one solution candidate with an object of the defined group from another solution candidate so as to minimize the difference between the respective groups prior to crossing the candidates, a faster convergence towards an optimum solution is achieved.

Claims

1. A genetic optimization computer system comprising:

a model defining the structure of a candidate solution to a problem as a plurality of objects in combination, the objects consisting of defined parameters, the model further including means to run potential solutions to the problem and to generate an output;

an optimizer including a store for storing a plurality of potential solution candidates to the problem, which solution candidates are combinations of object instances having specific values substituted for parameters;

means for crossing a parent pair of solution candidates to produce a new child solution candidate; and

means for inputting the new child solution candidate to the model in order for the model to run the child solution candidate and generate said model output;

the system further including fitness indicating means for indicating on the basis of the model output the relative fitness for purpose of the child solution candidate and means responsive thereto for identifying relatively fitter child solution to the optimizer;

wherein the model further defines at least one group of objects to be identically structured and equivalent to each other and the optimizer further includes means for associating each object of the defined group from one solution candidate with an object of the defined group from another solution candidate so as to minimize the difference between the objects of the respective groups prior to crossing of the solution candidates.

2. A system as claimed in claim 1 in which the defined parameters of the defined group are numeric and the means for associating objects is arranged to calculate a defined representation of said difference between each possible combination of parameters of the objects of the respective groups in order to select the association having the minimum difference.

3. A system as claimed in claim 2 in which the means for associating objects is arranged to select pairs of objects for association iteratively in order of their calculated closeness.

4. A system as claimed in claim 2 wherein the calculation involves determining the squares of the difference in value of like parameters.

5. A system as claimed in claim 1 in which the fitness indicating means is part of a fitness evaluation means arranged to calculate the fitness indication quantitatively from the model output.

6. A system as claimed in claim 5 in which the fitness evaluation means is part of the model.

7. A system as claimed in claim 1 in which the fitness indicating means includes interactive input means for receiving a user generated indication of fitness in response to the model output.

8. A system as claimed in claim 1 in which the means for identifying relatively fitter child solutions to the optimizer is part of an optimizer control means which is effective in response to the fitness indication to cause promotion of fitter solutions and deletion of inferior solutions in the optimizer store.

9. A method of genetic optimization for implementation in a computer system, which system comprises a stored model defining the structure of a candidate solution to a problem as a plurality of objects in combination, the objects consisting of defined parameters, the model further including means to run potential solutions to the problem and to generate an output;

and a solution store for storing a plurality of potential solution candidates, which solution candidates are combinations of object instances having specific values substituted for parameters;

the method comprising the steps of;

crossing a parent pair of solution candidates to produce a new child solution candidate;

running the child solution candidate in the model to generate said model output;

indicating on the basis of the model output the relative fitness for purpose of the child solution candidate; and

identifying relatively fitter child solution candidates for storage in the solution store;

wherein the model further defines at least one group of objects to be identically structured and equivalent to each other and the method includes the further step of;

prior to the crossing of the parent pair of solution candidates, associating each object of the defined group from one solution candidate with an object of the defined group from another solution candidate so as to minimize the difference between the objects of the respective groups.

10. A method as claimed in claim 9 in which the defined parameters of the defined group are numeric and in which the step of associating objects includes calculating a defined representation of said difference between each possible combination of parameters of the objects of the respective groups and using the calculated differences to select the association having the minimum difference.

11. A method as claimed in claim 10 including the step of selecting pairs of objects for association iteratively in order of their calculated closeness.

12. A method as claimed in claim 10 wherein the calculating step involves determining the squares of the difference in value of like parameters.

13. A method as claimed in claim 9 including the step of receiving an interactive user generated indication of fitness in response to the model output.

14. A method as claimed in claim 9 including the step of calculating the fitness indication quantitatively from the model output.

15. A method as claimed in claim 9 including the step of promoting fitter solutions to and deleting inferior solutions from the solution store in dependence on the relative fitness indication.

16. A computer program comprising instructions which, when executed by a computer, cause the computer to carry out the steps of a method as claimed in claim 9.