Method and system for conditioning of numerical algorithms for solving optimization problems within a genetic framework

• US 20070005521A1
• Filed: 06/03/2005
• Published: 01/04/2007
• Est. Priority Date: 06/03/2005
• Status: Active Grant

• Current Assignee: Simtone Corporation
• Original Assignee: Aspeed Software
• Inventors: Gulko, Abraham, Ziegler, Kurt, Dalessio, Michael, Dimitriou, Labro
• Granted Patent: US 7,328,194 B2
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A system for conditioning algorithms to achieve optimum execution time is disclosed. The system defines a computer programmable framework that can be used to efficiently find a global optimization vector. The system provides a precise execution sequencing of operations in order to achieve a speedy conclusion and a genetic receipt for finding the optimal number of siblings (cluster nodes) for the algorithm. The system defines the genetic function for generating an initial population of solution vectors, a condition number for optimal searching of a single vector, a best fit off-springs selection method, and a diversification function.

Claims

1. A system for conditioning an algorithm to achieve optimum execution time, the system comprising:

a master controller configured to control operations of the system to manage a life cycle of a genetic process;

a diversification module configured to generate a plurality of sibling vectors based on an input seed vector;

a plurality of genetic modules, each genetic module configured to perform a computational process and generate an off-spring vector based on a corresponding sibling vector received from the diversification module, wherein the plurality of genetic modules perform their respective computational processes independently in a parallel manner;

a generation depth manager configured to determine a generation depth for each of the plurality of genetic modules, wherein the generation depth is used by the corresponding genetic module to perform its computational process;

a best fit evaluator configured to evaluate an objective function for the off-spring vector generated by each genetic module and generate an objective value; and

a convergence manager configured to evaluate the objective value to determine if one or more terminal conditions associated with the objective function have been reached.

2. The system of claim 1 further comprising:

a pool manager configured to manage the plurality of genetic modules and instantiate additional genetic modules, where appropriate.

3. The system of claim 2 wherein, for an off-spring vector associated with a corresponding genetic module, in response to the determination that none of the terminal conditions associated with the objective function has not been reached, the master controller is further configured to direct the diversification module to use the off-spring vector as the input seed vector to generate a new plurality of sibling vectors.

4. The system of claim 3 wherein the pool manager instantiates a new plurality of genetic modules for the new plurality of sibling vectors.

5. The system of claim 4 wherein the generation depth manager defmes a new plurality of generation depths for the new plurality of genetic modules.

6. The system of claim 1 further comprising:

a communication manager configured to facilitate communications between the master controller and the plurality of genetic modules.

7. The system of claim 1 wherein the one or more terminal conditions associated with the objective function include a condition under which the objective value reaches a predetermined value or falls within an acceptable range.

8. The system of claim 1 wherein the convergence manager is further configured to keep a running tally of generation levels associated with each of the plurality of genetic modules.

9. The system of claim 1 wherein the generation depth manager is further configured to determine the generation depth for each of the plurality of genetic module based on the sibling vector associated with the corresponding genetic module.

10. The system of claim 1 wherein the generation depths for the plurality of genetic modules may vary from one another.

11. The system of claim 1 wherein if one or more terminal conditions associated with the objective function have been reached, the master controller is configured to terminate the genetic process by terminating all the computational processes associated with the plurality of genetic modules.

12. The system of claim 1 wherein, for an off-spring vector associated with a corresponding genetic module, in response to the determination that none of the terminal conditions associated with the objective function has not been reached, the best fit evaluator is further configured to determine if the objective value is better than a previously calculated value;

and

wherein in response to the determination that the objective value is not better than the previously calculated value, the master controller is further configured to direct the diversification module to use a new seed vector as the input seed vector to generate a new plurality of sibling vectors, wherein the new seed vector is obtained from an external process or computation.

13. A method for conditioning an algorithm to achieve optimum execution time, the method comprising:

directing a master controller to provide an initial seed vector and an optimal pool size;

directing a diversification module to generate a plurality of sibling vectors based on an input seed vector, wherein the initial seed vector is initially used as the input seed vector;

instantiating a plurality of genetic modules using the optima pool size, wherein each genetic module is configured to perform a computational process and generate an off-spring vector based on a corresponding sibling vector received from the diversification module, and wherein the plurality of genetic modules perform their respective computational processes independently in a parallel manner;

directing a generation depth manager to determine a generation depth for each of the plurality of genetic modules, wherein the generation depth is used by the corresponding genetic module to perform its computation process;

directing a best fit evaluator to evaluate an objective function for the off-spring vector generated by each genetic module and generate an objective value; and

directing a convergence manager to evaluate the objective value to determine if one or more terminal conditions associated with the objective function have been reached.

14. The method of claim 13 further comprising:

directing a pool manager to manage the plurality of genetic modules and instantiate additional genetic modules, where appropriate.

15. The method of claim 13 further comprising:

for an off-spring vector associated with a corresponding genetic module, in response to the determination that none of the terminal conditions associated with the objective function has not been reached, directing the master controller to cause the diversification module to use the off-spring vector as the input seed vector to generate a new plurality of sibling vectors.

16. The method of claim 15 further comprising:

directing the pool manager to instantiate a new plurality of genetic modules for the new plurality of sibling vectors.

17. The method of claim 16 further comprising:

directing the generation depth manager to define a new plurality of generation depths for the new plurality of genetic modules.

18. The method of claim 13 further comprising:

directing a communication manager to facilitate communications between the master controller and the plurality of genetic modules.

19. The method of claim 13 wherein the one or more terminal conditions associated with the objective function include a condition under which the objective value reaches a predetermined value or falls within an acceptable range.

20. The method of claim 13 further comprising:

directing the convergence manager to keep a running tally of generation levels associated with each of the plurality of genetic modules.

21. The method of claim 13 further comprising:

directing the generation depth manager to determine the generation depth for each of the plurality of genetic module based on the sibling vector associated with the corresponding genetic module.

22. The method of claim 13 wherein the generation depths for the plurality of genetic modules may vary from one another.

23. The method of claim 13 further comprising:

if one or more terminal conditions associated with the objective function have been reached, directing the master controller to terminate the genetic process by terminating all the computational processes associated with the plurality of genetic modules.

24. The method of claim 13 further comprising:

for an off-spring vector associated with a corresponding genetic module, in response to the determination that none of the terminal conditions associated with the objective function has not been reached, directing the best fit evaluator to determine if the objective value is better than a previously calculated value; and

in response to the determination that the objective value is not better than the previously calculated value, directing the master controller to cause the diversification module to use the a new seed vector as the input seed vector to generate a new plurality of sibling vectors, wherein the new seed vector is obtained from an external process or computation.