Adaptive optimization methods

• US 8,131,656 B2
• Filed: 01/31/2007
• Issued: 03/06/2012
• 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 E., Sastry, Kumara, Lobo, Fenando G., Lima, Claudio F.
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): Kim, David H
• Application Number:
  US11/701,066
• Publication Number:
  US 20070208677A1
• Time in Patent Office: 1,861 Days
• Field of Search: 706/13
• 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 in one or more computers, the solution set comprising members representing individual solutions to a problem, the method comprising, not necessarily in the sequence listed:

generating a solution set;

evaluating solutions in said solution set in the one or more computers;

selecting desirable solutions from the solution set and saving said selected desirable solutions in the one or more computers;

creating a structural model in the one or more computers using said desirable solutions;

creating a surrogate fitness model in the one or more computers 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 a method 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, wherein 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 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.

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

12. The method of claim 1, wherein said determining a method changes the method for generating a new solution set from a method used to generate a new solution set in a previous iteration.

13. A method for optimizing a solution set in one or more computers, the solution set comprising members representing individual solutions to a problem, the method comprising, not necessarily in the sequence listed:

generating a solution set;

evaluating solutions in said solution set in the one or more computers;

selecting desirable solutions from the solution set and saving said selected desirable solutions in the one or more computers;

creating a structural model in the one or more computers using said desirable solutions;

creating a surrogate fitness model in the one or more computers based on said structural model and said desirable solutions;

generating a new solution set at least partly based on said created structural model;

determining if completion criteria are satisfied;

if completion criteria are not satisfied, evaluating solutions in said new solution set in the one or more computers;

wherein said evaluating solutions in said new solution set comprises;

analyzing at least one of said structural model and said surrogate fitness model in the one or more computers;

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

evaluating solutions in said new solution set in the one or more computers based on said determined method;

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

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

15. A method for optimizing a solution set in one or more computers, the solution set comprising members representing individual solutions to a problem, the method comprising, not necessarily in the sequence listed:

generating a solution set;

evaluating solutions in said solution set in the one or more computers;

selecting desirable solutions from the solution set and saving said desirable solutions in the one or more computers;

creating a structural model in the one or more computers using said desirable solutions;

creating a surrogate fitness model in the one or more computers based on said structural model and said desirable solutions;

analyzing at least one of said structural model and said surrogate fitness model in the one or more computers;

generating a new solution set in the one or more computers;

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 on 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.

16. The method of claim 15, 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.

17. The method of claim 15, 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.

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

19. A method for optimizing a solution set in one or more computers, the solution set comprising members representing individual solutions to a problem, the method comprising, not necessarily in the sequence listed:

a) generating an initial solution set;

b) evaluating solutions in said generated solution set in the one or more computers;

c) selecting desirable solutions from said generated solution set and saving said selected desirable solutions in the one or more computers;

d) creating a model in the one or more computers 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 in the one or more computers using said updated model;

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).

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

21. The method of claim 19, 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.

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

23. A method for optimizing a solution set in one or more computers, the solution set comprising members representing individual solutions to a problem, the method comprising, not necessarily in the sequence listed:

a) generating an initial solution set;

b) evaluating solutions in said generated solution set in the one or more computers;

c) selecting desirable solutions from said generated solution set and saving said selected desirable solutions in the one or more computers;

d) creating a model in the one or more computers 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 in the one or more computers using said updated model;

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);

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;

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.