9813

Evolutionary Multiobjective Optimization

Optimization problems with multiple, often conflicting, objectives arise in a natural fashion in most real-world applications, such as aerodynamic design, financial decision making, and electronic circuit development. An important task in multiobjective optimization is to identify a set of optimal trade-off solutions (called a Pareto set) between the conflicting objectives, which helps gain a better understanding of the problem structure and supports the decision-maker in choosing the best compromise solution for the considered problem.
Evolutionary algorithms are particular suited for approximating the entire Pareto set because they work with a population of solutions rather than a single solution candidate. This enables approximating several members of the Pareto set simultaneously in a single algorithm run.
This Demonstration shows how an evolutionary multiobjective optimization algorithm (NSGA-II) approximates the Pareto set of Kursawe's two-objective optimization problem, which has a nonconvex, disconnected two-dimensional Pareto front and a disconnected three-dimensional Pareto set.
In each generation, all solution candidates are represented as decision vector in decision space (where the evolutionary search takes place) and as objective vector in objective space. Since the quality of a candidate solution is evaluated as a vector rather than a scalar, the concept of Pareto dominance is used to compare the quality of the solutions: The solution is said to dominate another solution if is not worse than in all objectives, and is strictly better than in at least one objective.
In each generation, all solutions that are not dominated by any other are called nondominated solutions. These solutions form the current approximation of the Pareto set and are marked green. In objective space, the image of the nondominated solutions is called the Pareto front approximation.
  • Contributed by: Robin Gruna
  • After work by: Kalyanmoy Deb, et. al.

THINGS TO TRY

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

The Nondominated Sorting Genetic Algorithm II (NSGA-II) by Kalyanmoy Deb et al. is an elitist multiobjective evolutionary algorithm with time complexity of in generating nondominated fronts in one generation for population size and objective functions. For more details see K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, "A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II," IEEE Transactions on Evolutionary Computation, 6(2), 2002 pp. 181–197.
For more details on Kursawe's multiobjective test problem see F. Kursawe, "A Variant of Evolution Strategies for Vector Optimization," in Parallel Problem Solving for Nature I (PPSN-I), 1990 pp. 193–197.
Snapshot 1: randomly initialized population; nondominated solutions are marked green
Snapshot 2: the attainments surface represents the family of tightest objective vectors that are known to be attainable as a result of the current approximation of the Pareto front
Snapshot 3: approximated Pareto set and front of the Kursawe test function after 100 generations. The approximated Pareto set consists of several disconnected and asymmetric areas in decision space. The corresponding Pareto front is non-connected as well and has a partial convex and concave shape.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+