B - Non-dominated solutions and the Pareto frontier


Generally, in multi-objective optimization there is a single best solution for each objective value. However, in all the other objective values this solution might not fare that well. Therefore, in multi-objective optimization, the non-dominated solutions are the ones that form the set of most interesting solutions. Each solution will exhibit some type of trade-off, which cannot be decided a priori (i.e. combined into a single fitness value) but needs to be explored a posteori. 

For multi-objective optimizations with m as number of objectives, each solution can be located based on its objective values in an m-dimensional space. 

A solution S1 dominates a solution S2 if all of S1’s objective values are better than the corresponding objective values of solution S2.

A solution S1 is dominated by a solution S3 if all of S3’s objective values are better than the corresponding objective values of S1.

A non-dominated solution S3 is a solution that is not dominated by any other solution SN. Note that this does not mean that a non-dominated solution S3 performs better in all objectives than all other solutions. It only means that there is no other solution SN that performs better in all objectives than the non-dominated solution S3. Another solution S4, that performs better in at least one objective is neither dominated by nor does it dominate solution S3. However, we cannot know whether S4 itself is non-dominated, or whether there are other solutions that dominate S4. For that we have to perform a Pareto-dominance check for S4, effectively  comparing S4’s fitness values with the fitness values of all other solutions. 

Note that this other solution (e.g. S4 in relation to S3) and all other solutions for which some objective values are better and some worse fall out of both areas of Pareto-dominance (i.e. dominated by S3 or dominating S3). These other solutions are in an indifferent Pareto-dominance state to the solution with which they are compared.

Figure based on: Pareto-, Aggregation-, and Indicator-based Methods in Many-objective Optimization; Tobias Wagner, Nicola Beume and Boris Naujoks; No. CI-217/06: Technical Report ISSN 1433-3325 September 2006, UNIVERSITY OF DORTMUND.

In a dual-objective result, the two objectives can be used as coordinate axes for a scatter plot, with the solutions located at their coordinates based on the value pairs for the respective solution’s objective values.

Multi-objective optimization result representation is customarily limited to two dimensional scatter plots, too. Matching objectives pairwise allows for exploration of design trade-offs and learning about the design.

When the same parameter is plotted on the x-axis and the y-axis, the solutions are aligned diagonally, with the best performer found by the genetic algorithm in that category as the dot nearest to the plot origin (for maximization using the option to Invert maximization(s) will align minimization and maximization to display in the same way), or for negative fitness values the dot furthest to the bottom left. Other pairings show a more characteristic Pareto frontier, or other dependencies, including some that appear more aligned with each other in specific areas of the plot.

outOfPlaneTotalheightCriterionComputedVentArea
outOfPlaneTotal
heightCriterion
ComputedVentArea
outOfPlaneTotalheightCriterionComputedVentArea

In the case shown above, ComputedVentArea and heightCriterion are not conflicting. Therefore, the scatterplots for the results showing those two objectives do not show the characteristic Pareto frontier. In contrast, ComputedVentArea and outOfPlaneTotal are conflicting objectives and form very characteristic Pareto frontiers in their plots.