System and method for estimation of a distribution algorithm

• US 20050256684A1
• Filed: 01/11/2005
• Published: 11/17/2005
• Est. Priority Date: 01/12/2004
• Status: Active Grant

• Current Assignee: Honda Research Institute Europe GmbH (Honda Motor Company)
• Original Assignee: Honda Research Institute Europe GmbH (Honda Motor Company)
• Inventors: Okabe, Tatsuya, Sendhoff, Bernhard, Olhofer, Markus, Jin, Yaochu
• Granted Patent: US 7,428,514 B2
• Time in Patent Office: Days
• US Class Current: 703/2
• 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 optimization, comprising the steps of:

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

(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, and

(f) repeating steps (c) through (e) until the quality reaches a threshold value.

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 a Voronoi-mesh is applied in step (c) to build a stochastic model for generating offspring.

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. The computer software program product, implementing a method of claim 1 when executing on a computing device.

9. A system for optimization, 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; and

means for comparing the quality to a threshold value.