Genetic optimization computer system

• US 7,302,416 B2
• Filed: 03/02/2006
• Issued: 11/27/2007
• Est. Priority Date: 03/02/2005
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Todd, Stephen, Todd, Peter James
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US11/366,698
• Publication Number:
  US 20060224536A1
• Time in Patent Office: 635 Days
• Field of Search: 706/13, 706/12, 706/45
• US Class Current: 706/13
• 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 apparatus for enabling computerized generation of an optimum solution to a problem, the computer system apparatus 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 data store means for storing a plurality of potential solution candidates to the problem, wherein 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 computer system apparatus 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 means for identifying relatively fitter child solutions to the optimizer is part of an optimizer control means which, responsive to the fitness indication, updates the optimizer data store means by promoting fitter solutions and deleting inferior solutions that are stored in the optimizer data store means;

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 to minimize the difference between the objects of the respective groups prior to crossing of the solution candidates.

2. A computer system apparatus as claimed in claim 1 wherein 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 computer system apparatus as claimed in claim 2 wherein the means for associating objects is arranged to select pairs of objects for association iteratively in order of their calculated closeness.

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

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

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

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

8. A computer system implemented method of genetic optimization for enabling computerized generation of an optimum solution to a problem, where the computer system comprises a stored model stored in a data storage of the computer system that defines a structure of a candidate solution to the problem as a plurality of objects in combination, the objects comprising defined parameters, the model further including means to run potential solutions to the problem and to generate an output;

and a solution data store of the computer system for storing a plurality of potential solution candidates, where the solution candidates are combinations of object instances having specific values substituted for parameters;

the computer system implemented 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;

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

promoting fitter solutions stored in the solution data store, and deleting inferior solutions from the solution data store, in dependence on the relative fitness indication;

manifesting the model output directly to a human user; and

receiving, from the human user, an interactive user generated indication of fitness in response to the model output;

wherein the model further defines at least one group of objects to be identically structured and equivalent to each other and the computer system implemented 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 to minimize the difference between the objects of the respective groups.

9. A method as claimed in claim 8 wherein the defined parameters of the defined group are numeric and wherein 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.

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

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

12. A method as claimed in claim 8 including the step of receiving an interactive user generated indication of fitness in response to the model output that is directly manifested to the human user.

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

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