Methods for multi-objective optimization using evolutionary algorithms

• US 7,363,280 B2
• Filed: 11/09/2001
• Issued: 04/22/2008
• Est. Priority Date: 11/14/2000
• 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
• Primary Examiner(s): Vincent; David
• Assistant Examiner(s): Buss; Benjamin
• Application Number:
  US10/007,906
• Publication Number:
  US 20020099929A1
• Time in Patent Office: 2,356 Days
• Field of Search: 706/45, 706/13, 706/37, 706/39, 706/19, 706/932
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

In the field of multi-objective optimization using evolutionary algorithms conventionally different objectives are aggregated and combined into one objective function using a fixed weight when more than one objective needs to be optimized. With such a weighted aggregation, only one solution can be obtained in one run. Therefore, according to the present invention two methods to change the weights systematically and dynamically during the evolutionary optimization are proposed. One method is to assign uniformly distributed weight to each individual in the population of the evolutionary algorithm. The other method is to change the weight periodically when the evolution proceeds. In this way a full set of Pareto solutions can be obtained in one single run.

Claims

1. A computer-implemented method for optimizing multi-objective engineering or design problems using evolutionary algorithms, the method comprising the steps of:

(a) setting up an initial population of individuals as parents, the individuals encoding object parameters to be optimized wherein said object parameters represent engineering or design characteristics including physical characteristics;

(b) reproducing the parents to create a plurality of offspring individuals;

(c) evaluating a quality of the offspring individuals by means of a fitness function;

(d) wherein the fitness function includes a sum of weighted sub-functions that represent an objective, said weights for the sub-functions are changed dynamically during the optimization of the multi-objective engineering or design problems;

(e) selecting one or more offspring having a highest evaluated quality value as parents for a next generation corresponding to a next evolution cycle, wherein said weights for the sub-functions are changed according to a periodic function during the optimization wherein a value of said weights repeats periodically according to said periodic function;

(f) repeating steps (a)-(e) until a termination condition for the optimization is satisfied; and

(g) outputting said weight values to a computer readable medium for use in the design of at least one of an aerodynamic body, a physical object, or a heat exchange wall.

2. The method of claim 1, wherein each offspring has a same weight in a same generation.

3. The method of claim 1, wherein the weights for the sub-functions are changed gradually between 0 and 1 with the process of optimization of multi-objective problems.

4. The method of claim 3, wherein the periodic change has a shape of a sine function applied on a generation number representing a number of the generation.

5. The method of claim 1 further comprising the step of:

recording, in a computer readable archive, Pareto solutions found as optimal solutions for a multi-objective problem.

6. The method of claim 1, wherein a pressure loss and an outlet angle calculated by a Navier-Stokes-solver and geometric constraints are objectives in the multi-objective problems that are used to optimize an aerodynamic body, wherein said aerodynamic body is the engineering or design problem that is optimized.

7. A computer program stored in a computer readable medium for performing the method of:

setting up an initial population of individuals as parents, the individuals encoding object parameters to be optimized wherein said object parameters represent engineering or design characteristics including physical characteristics;

(a) reproducing the parents to create a plurality of offspring individuals;

(b) evaluating a quality of the offspring individuals by means of a fitness function;

(c) wherein the fitness function includes a sum of weighted sub-functions that represent an objective, said weights for the sub-functions are changed dynamically during the optimization of multi-objective problems;

(d) selecting one or more offspring having a highest evaluated quality value as parents for a next generation corresponding to a next evolution cycle, wherein said weights for the sub-functions are changed according to a periodic function during the optimization wherein a value of said weights repeats periodically according to said periodic function;

(e) selecting one or more offspring having a highest evaluated quality value as parents for a next generation corresponding to a next evolution cycle, wherein said weights for the sub-functions are changed according to a periodic function during the optimization wherein a value of said weights repeats periodically according to said periodic function;

wherein a pressure loss and an outlet angle calculated by a Navier-Stokes-solver and geometric constraints are objectives in the multi-objective problems that are used to optimize an aerodynamic body;

(f) repeating steps (a)-(e) until a termination condition for the optimization is satisfied; and

(g) outputting said weight values to a computer readable medium for use in the design of at least one of an aerodynamic body, a physical object, or a heat exchange wall.

8. A computer-implemented method for optimizing an aerodynamic body represented by multi-objective problems using evolutionary algorithms, the method comprising the steps of:

(a) setting up an initial population of individuals as parents, the individuals encoding object parameters to be optimized wherein said object parameters represent characteristics of the aerodynamic body;

(b) reproducing the parents to create a plurality of offspring individuals;

(c) evaluating a quality of the offspring individuals by means of a fitness function;

(d) wherein the fitness function includes a sum of weighted sub-functions that represent an objective, said weights for the sub-functions are changed dynamically during the optimization of multi-objective engineering or design problems;

(e) selecting one or more offspring having a highest evaluated quality value as parents for a next generation corresponding to a next evolution cycle, wherein said weights for the sub-functions are changed according to a periodic function during the optimization wherein a value of said weights repeats periodically according to said periodic function;

(f) repeating steps (a)-(e) until a termination condition for the optimization is satisfied; and

(g) outputting said weight values to a computer readable medium for use in the design of at least one of an aerodynamic body, a physical object, or a heat exchange wall.

9. The method of claim 8, wherein each offspring has a same weight in a same generation.

10. The method of claim 8, wherein the weights for the sub-functions are changed gradually between 0 and 1 with the process of optimization of multi-objective problems.

11. The method of claim 8, wherein the periodic change has a shape of a sine function applied on a generation number representing a number of the generation.

12. The method of claim 8, further comprising the step of:

recording, in a computer readable archive, Pareto solutions found as optimal solutions for a multi-objective problem.

13. The method of claim 8, wherein a pressure loss and an outlet angle calculated by a Navier-Stokes-solver and geometric constraints are objectives in the multi-objective problems that are used to optimize the aerodynamic body.

14. A computer-implemented method for optimizing multi-objective engineering or design problems using evolutionary algorithms, the method comprising the steps of:

(a) setting up an initial population of individuals as parents, the individuals encoding object parameters to be optimized wherein said object parameters represent engineering or design characteristics including physical characteristics;

(b) reproducing the parents to create a plurality of offspring individuals;

(c) evaluating a quality of the offspring individuals by means of a fitness function;

(d) wherein the fitness function includes a sum of weighted sub-functions that represent an objective, said weights for the sub-functions are changed dynamically during the optimization of the multi-objective engineering or design problems;

(e) selecting one or more offspring having a highest evaluated quality value as parents for a next generation corresponding to a next evolution cycle, wherein said weights for the sub-functions are changed according to a periodic function during the optimization wherein a value of said weights repeats periodically according to said periodic function;

(f) repeating steps (a)-(e) until a termination condition for the optimization is satisfied; and

(g) recording, in a computer readable medium, Pareto solutions found as optimal solutions for a multi-objective problem.

15. The method of claim 14, wherein each offspring has a same weight in a same generation.

16. The method of claim 14, wherein the weights for the sub-functions are changed gradually between 0 and 1 with the process of optimization of multi-objective problems.

17. The method of claim 14, wherein the periodic function has a shape of a sine function applied on a generation number representing a number of the generation.