Adaptive optimization methods

• US 20070208677A1
• Filed: 01/31/2007
• Published: 09/06/2007
• Est. Priority Date: 01/31/2006
• Status: Active Grant

• Current Assignee: Board of Trustees of The University of Illinois
• Original Assignee: Board of Trustees of The University of Illinois
• Inventors: Goldberg, David, Sastry, Kumara, Lima, Claudio, Lobo, Fernando
• Granted Patent: US 8,131,656 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
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

Methods and systems for optimizing a solution set. A solution set is generated, and solutions in the solution set are evaluated. Desirable solutions from the solution set are selected. A structural model is created using the desirable solutions, and a surrogate fitness model is created based on the structural model and the desirable solutions. A new solution set may be generated and/or evaluated, based on analyzing at least one of the structural model and the surrogate fitness model, and determining a method for generating a new solution set and/or evaluating the new solution set based at least in part on the analyzing.

Claims

1. A method for optimizing a solution set comprising, not necessarily in the sequence listed:

generating a solution set;

evaluating solutions in said solution set;

selecting desirable solutions from the solution set;

creating a structural model using said desirable solutions;

creating a surrogate fitness model based on said structural model and said desirable solutions;

generating a new solution set;

wherein said generating a new solution set comprises;

analyzing at least one of said structural model and said surrogate fitness model;

determining a method for generating a new solution set based at least in part on said analyzing;

generating a new solution set based on said determined method.

2. The method of claim 1, wherein said analyzing comprises analyzing said surrogate fitness model, and said determining comprises determining a proportion of model sampling versus mutation.

3. The method of claim 2, wherein said analyzing said surrogate fitness model comprises inferring at least one of scaling between variables, scaling between linked groups of variables, and a signal-to-noise ratio of said surrogate fitness model.

4. The method of claim 3, said analyzing said surrogate fitness model further comprises comparing said surrogate fitness model to a surrogate fitness model in a previous generation.

5. The method of claim 2, wherein said determining a proportion of model sampling versus mutation comprises at least one of emphasizing, de-emphasizing, and removing one or more sampling and mutation operators in said generating a new solution set.

6. The method of claim 1, wherein said analyzing comprises inferring at least one neighborhood for a local search using said structural model, and said determining comprises determining a local search within said inferred neighborhoods.

7. The method of claim 1, wherein said analyzing comprises analyzing said surrogate fitness model, and wherein said determining comprises determining a proportion of global and local search.

8. The method of claim 1, wherein said analyzing comprises analyzing said surrogate fitness model, and wherein said determining comprises selecting a local search method among a plurality of available local search methods.

9. The method of claim 1, further comprising:

determining if completion criteria is satisfied;

if completion criteria is not satisfied, evaluating at least a portion of the solutions in said new solution set using said surrogate fitness model.

10. The method of claim 9, wherein said analyzing comprises analyzing said surrogate fitness model, and further comprising:

determining the portion of the solutions in said new solution set to be evaluated using said surrogate fitness model based on said analyzing said surrogate fitness model;

evaluating said determined portion of the solutions in said new solution set using said surrogate fitness model;

evaluating other of the solutions in said new solution set using a fitness calculation other than said surrogate fitness model.

21. A computer program product useful to optimize a solution set, the computer program product comprising computer readable instructions stored on a computer readable memory or medium that when executed by one or more computers cause one or more computers to perform the steps in the method of claim 1.

11. A method for optimizing a solution set comprising, not necessarily in the sequence listed:

generating a solution set;

evaluating solutions in said solution set;

selecting desirable solutions from the solution set;

creating a structural model using said desirable solutions;

creating a surrogate fitness model based on said structural model and said desirable solutions;

generating a new solution set;

determining if completion criteria are satisfied;

if completion criteria are not satisfied, evaluating solutions in said new solution set;

wherein said evaluating solutions in said new solution set comprises;

analyzing at least one of said structural model and said surrogate fitness model;

determining a method for evaluating solutions based at least in part on said analyzing;

evaluating solutions in said new solution set based on said determined method.

12. The method of claim 11, wherein said analyzing comprises analyzing said structural model to infer a topology of a parallel function evaluation, and wherein said determining comprises determining an evaluation method using said inferred topology.

13. The method of claim 11, wherein said analyzing comprises analyzing said surrogate fitness model, and wherein said determining comprises determining a parallel function evaluation method.

22. A computer program product useful to optimize a solution set, the computer program product comprising computer readable instructions stored on a computer readable memory or medium that when executed by one or more computers cause one or more computers to perform the steps in the method of claim 11.

14. A method for optimizing a solution set comprising, not necessarily in the sequence listed:

generating a solution set;

evaluating solutions in said solution set;

selecting desirable solutions from the solution set;

creating a structural model using said desirable solutions;

creating a surrogate fitness model based on said structural model and said desirable solutions;

analyzing at least one of said structural model and said surrogate fitness model;

generating a new solution set;

determining if completion criteria are satisfied;

if completion criteria are not satisfied, evaluating solutions in said new solution set;

wherein said generating a new solution set comprises;

determining a method for generating a new solution set based at least in part of said analyzing;

generating a new solution set based on said determined method;

wherein said evaluating solutions in said new solution set comprises;

determining a method for evaluating solutions based at least in part of said analyzing;

evaluating solutions in said new solution set based on said determined method.

15. The method of claim 14, wherein the structural model comprises at least one of a Bayesian optimization, an extended compact genetic algorithm, a decision tree, a probability table, and a marginal product model.

16. The method of claim 14, wherein said creating a surrogate fitness model comprises:

inferring a form of said surrogate fitness model from said structural model to provide a structure;

calibrating said structure using results from said evaluating solutions.

23. A computer program product useful to optimize a solution set, the computer program product comprising computer readable instructions stored on a computer readable memory or medium that when executed by one or more computers cause one or more computers to perform the steps in the method of claim 14.

17. A method for optimizing a solution set comprising, not necessarily in the sequence listed:

a) generating an initial solution set;

b) evaluating solutions in said generated solution set;

c) selecting desirable solutions from said generated solution set;

d) creating a model of said selected desirable solutions;

e) mutating a best individual in said generated solution set;

f) updating said created model using said mutated best individual;

g) generating a new solution set;

h) determining if stopping criteria is satisfied;

i) if stopping criteria is not satisfied, repeating steps b)-g), wherein said generated new solution set replaces said generated new solution set in step b).

18. The method of claim 17, wherein said updating said created model comprises updating, by building block, said created model based on said mutated best individual.

19. The method of claim 17, wherein said created model comprises a marginal product model (MPM) and wherein said updating said created model comprises updating instance frequencies of the MPM according to building block instances present on said mutated best individual.

20. The method of claim 19, wherein said updating instance frequencies of the MPM comprises:

increasing BB instances frequencies of the mutated individual by s;

decreasing the BB instances frequencies of a previous best individual by s;

wherein said evaluating solutions uses an s-wise selection.

24. A computer program product useful to optimize a solution set, the computer program product comprising computer readable instructions stored on a computer readable memory or medium that when executed by one or more computers cause one or more computers to perform the steps in the method of claim 17.