Methods for efficient solution set optimization

• US 20060212279A1
• Filed: 01/30/2006
• Published: 09/21/2006
• Est. Priority Date: 01/31/2005
• Status: Abandoned Application

• Current Assignee: Board of Trustees of The University of Illinois, Curators of the University of Missouri (University of Missouri)
• Original Assignee: Board of Trustees of The University of Illinois, Curators of the University of Missouri (University of Missouri)
• Inventors: Pelikan, Martin, Goldberg, David E., Sastry, Kumara
• Application Number:
  US11/343,195
• Publication Number:
  US 20060212279A1
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A method for optimizing a solution set comprises the steps of generating an initial solution set, identifying a desirable portion of the initial solution set using a fitness calculator, using the desirable portion to create a surrogate fitness model that is computationally less expensive than the fitness calculator, generating new solutions, replacing at least a portion of the initial solution set with the new solutions to create a second solution set, and evaluating at least a portion of the second solution set with the fitness surrogate model to identify a second desirable portion.

Claims

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

a) creating an initial solution set;

b) identifying a desirable portion of said initial solution set using a fitness calculator;

c) creating a model that is representative of said desirable portion;

d) using said model to create a surrogate fitness estimator that is computationally less expensive than said fitness calculator;

e) generating new solutions;

f) replacing at least a portion of said initial solution set with said new solutions to create a new solution set; and

g) evaluating at least a portion of said new solution set with said fitness surrogate estimator to identify a new desirable portion.

2. A method for optimizing a solution set as defined by claim 1 and further including the step of determining whether completion criteria are satisfied and if not repeating steps c)-g) until said completion criteria are completed, said step of repeating including replacing said desirable portion in step c) with said new desirable portion and replacing said initial solution set in step f) with said new solution set.

3. A method as defined by claim 1 wherein said model includes a plurality of variables, at least some of which interact with one another, and wherein the step of using said model to create said surrogate fitness estimator includes using knowledge of said variable interaction to create said surrogate fitness estimator.

4. A method as defined by claim 1 wherein said model comprises a first model, and wherein the step of using said model to create said surrogate fitness estimator comprises the steps of creating a structural fitness model that represents variable interaction in said first model, and calibrating said structural fitness model.

5. A method as defined by claim 1 wherein the step of identifying a desirable portion of said initial solution set using said fitness calculator produces resulting fitness calculation data points, and wherein the method further includes the step of using said fitness calculation data points to create said fitness surrogate estimator.

6. A method as defined by claim 5 wherein the step of using said fitness calculation data points to create said fitness surrogate estimator comprises using said fitness calculation data points to calibrate said fitness surrogate estimator.

7. A method as defined by claim 5 wherein the method is performed over multiple iterations, wherein the fitness calculator is used to evaluate fitness in at least a plurality of the iterations, and wherein the step of using said fitness calculation data points to create said fitness surrogate estimator comprises using a selected portion of said fitness calculation data points that favors later calculated fitness calculation data points over earlier calculated fitness calculation data points.

8. A method as defined by claim 5 wherein said fitness surrogate estimator includes coefficients, wherein the step of using said data points comprises using said data points to solve for said coefficients through one or more steps of:

curve fitting, linear regression, least squares fitting, a heuristic search, a tabu search, and simulated annealing.

9. A method as defined by claim 1 wherein the step of generating said new solutions comprises using said model to create said new solutions.

10. A method as defined by claim 1 wherein the step of creating a model includes creating a probabilistic model that is configured to predict promising solutions, and wherein the step of generating new solutions comprises using said probabilistic model to create said new solutions.

11. A method as defined by claim 1 wherein the step of creating said model comprises creating a first model, and wherein the step of generating new solutions comprises using a second model that is different than said first model to generate said new solutions.

12. A method as defined by claim 1 wherein the step of creating said model includes building one or more of a Bayesian optimization algorithm, an extended compact genetic algorithm, decision trees, probability tables, and a marginal product model.

13. A method for optimizing a solution set as defined by claim 1 wherein said model is a probabilistic model that utilizes local structures to represent conditional probabilities between variables, and wherein the step of creating said fitness surrogate estimator using said model includes using said conditional probabilities between variables to create said fitness surrogate estimator.

14. A method for optimizing a solution set as defined by claim 1 and further including a step of applying decision criteria to determine what portion of said new solution set to evaluate with said fitness surrogate estimator.

15. A method for optimizing a solution set as defined by claim 14 wherein steps of the method are repeated over multiple iterations, and wherein said decision criteria change between said iterations.

16. A method for optimizing a solution set as defined by claim 1 wherein the step of evaluating at least a portion of said new solution set with said fitness surrogate estimator comprises evaluating X % of said new solution set using said fitness surrogate estimator and evaluating the remaining (100-X) % of said new solution set using said fitness calculator to identify said new desirable portion, where X % is at between about 75% and about 99%.

17. A method for optimizing a solution set as defined by claim 1 wherein the step of replacing at least a portion of said initial solution set with said new solutions comprises replacing all of said initial solution set with said new solutions to create said new solution set.

18. A computer program product useful to optimize a solution set, the computer program product comprising computer readable instructions stored on a computer readable memory that when executed by one or more computers cause the one or more computers to perform the following steps, not necessarily in the sequence listed:

a) generate an initial solution set;

b) identify a desirable portion of said initial solution set using a fitness calculator;

c) use said desirable portion to create a model configured to predict other promising solutions, said probabilistic model including a plurality of variables at least some of which interact with one another;

d) use said interactions between said variables to create a surrogate fitness estimator that is computationally less expensive than said fitness calculator;

e) generate new solutions using said probabilistic model;

f) replace at least a portion of said initial solution set with said new solutions to create a new solution set; and

g) evaluate X % of said new solution set using said fitness surrogate estimator and evaluate (100-X) % of said new solution set using said fitness calculator to identify a new desirable portion, where X is between about 75 and 100.

19. A computer program product as defined by claim 18 wherein the program instructions when executed by the one or more computers further cause the one or more computers to perform the step of:

h) determine whether completion criteria are satisfied and if not repeating steps c)-g) until said completion criteria are completed, said step of repeating including replacing said desirable portion in step c) with said new desirable portion and replacing said initial solution set in step f) with said new solution set

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

a) creating an initial solution set;

b) identifying a desirable portion of said initial solution set using a fitness calculator, use of said fitness calculator resulting in fitness calculation data points;

c) storing said fitness calculation data points;

d) using said desirable portion to create a model configured to predict other desirable solutions, said probabilistic model including a plurality of variables at least some of which interact with one another;

e) using said interaction of said variables in said model and said fitness calculation data points to create a surrogate fitness estimator that is computationally less expensive than said fitness calculator;

f) generating new solutions;

g) replacing at least a portion of said initial solution set with said new solutions to create a new solution set; and

h) evaluating X % of said new solution set with said fitness surrogate estimator and the remaining (100-X) % of said second solution set using said fitness calculator to identify a new desirable portion, where X is between about 75 and about 100; and

,

i) determining whether completion criteria are satisfied and if not repeating steps d)-h) until said completion criteria are completed, the step of repeating including replacing said desirable portion in step d) with said new desirable portion and replacing said initial solution set in step g) with said new solution set