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.
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.