System and method for estimation of a distribution algorithm

• US 7,428,514 B2
• Filed: 01/11/2005
• Issued: 09/23/2008
• Est. Priority Date: 01/12/2004
• Status: Expired due to Fees

• Current Assignee: Honda Research Institute Europe GmbH (Honda Motor Company)
• Original Assignee: Honda Research Institute Europe GmbH (Honda Motor Company)
• Inventors: Sendhoff, Bernhard, Jin, Yaochu, Okabe, Tatsuya, Olhofer, Markus
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US11/033,767
• Publication Number:
  US 20050256684A1
• Time in Patent Office: 1,351 Days
• Field of Search: 706/13, 706/45, 706/47, 707/101, 702/19, 716/9, 703/2
• US Class Current: 706/13
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

The underlying invention generally relates to the field of Estimation of Distribution Algorithm, especially to optimization problems, including single-objective optimization and Multi-Objective Optimization.

The proposed method for optimization comprises six steps. In a first step it provides an initial population or a data set with a plurality of members respectively represented by parameter sets. Then one or a plurality of fitness functions are applied to evaluate the quality of the members of the population. In a third step offspring of the population is generated by means of a stochastic model using information from all members of the population. One or a plurality of fitness functions are applied to evaluate the quality of the offspring with respect to the underlying problem of the optimization. In a fifth step offspring is selected. Lastly the method goes back to the third step until the quality reaches a threshold value.

Claims

1. A method for optimizing a design representing a physical object, wherein said physical object is an aerodynamic or hydrodynamic structure, comprising the steps of:

(a) providing an initial population or a data set with a plurality of members respectively represented by parameter sets representing the design;

(b) applying one or a plurality of fitness functions to evaluate the quality of the members of the population;

(c) generating offspring of the population by means of a stochastic model using information from all members of the population;

(d) applying one or a plurality of fitness functions to evaluate the quality of the offspring with respect to the underlying problem of the optimization;

(e) selecting offspring,

(f) repeating steps (c) through (e) until the quality reaches a threshold value representing the optimized design, and

(g) storing said optimized design in a computer storage capable of being executed by a computing device;

wherein a Voronoi-mesh is applied in step (c) to build a stochastic model for generating offspring.

2. The method of claim 1, wherein in step (d) the members are ranked according to their quality, and wherein in step (e) all members are stored and members of a higher respectively lower rank have a higher respectively lower selection probability.

3. The method of claim 1, wherein each cell in the Voronoi-mesh is assigned a selection probability based on a rank of the cell.

4. The method of claim 1, wherein the stochastic model is perturbed to avoid local optima.

5. The method of claim 1, wherein the data in the space of the parameter sets are clustered in generating stochastic model in step (c).

6. The method of claim 1, wherein at least one of the principal component analysis and the independent component analysis are used in generating a stochastic model in step (c).

7. The method of claim 1, wherein at least one of a function approximation of the solution space and the fitness space is generated.

8. A computer software program product, implementing a method of claim 1 when executing when running on a computing device.

9. A system for optimizing a design representing a physical object, wherein said physical object is an aerodynamic or hydrodynamic structure, comprising:

means for providing an initial population or a data set with a plurality of members respectively represented by parameter sets;

means for applying one or a plurality of fitness functions to evaluate the quality of the members of the population;

means for generating offspring of the population by means of a stochastic model using information from all members of the population;

means for applying one or a plurality of fitness functions to evaluate the quality of the offspring with respect to the underlying problem of the optimization;

means for selecting offspring;

means for comparing the quality to a threshold value; and

means for storing said optimized design in a computer storage capable of being executed by a computing device;

wherein a Voronoi-mesh is applied in the means for generating offspring to build a stochastic model for generating offspring.