Source-linked AI summary
Techniques for Highly Multiobjective Optimisation: Some Nondominated Points are Better than Others
David Corne, Joshua Knowles
TL;DR
Many-objective EMO algorithms scale poorly, partly because populations contain many nondominated solutions that common algorithms cannot distinguish for selection. This paper investigates preference orderings for nondominated points and finds that average-ranking variants are highly effective across many-objective problems.
Problem
EMO algorithms scale poorly on problems with five or more objectives, while many-objective populations are likely to contain nondominated solutions that common algorithms cannot distinguish selectively.
Method
The paper compares methods for inducing preference orderings over nondominated points without using domain-dependent objective preferences.
Results
Average ranking (ARF) is highly effective compared with the other tested methods and usually outperforms them across problems with 5–20 objectives and differing inter-objective correlations.
Takeaways & Limitations
ARF is a strong candidate for many-objective search because it is computationally simple and efficient, while k-optimality is generally the next-best method.
Takeaways & Limitations
The paper's notion of the best possible Pareto-front approximation depends on the selected metric, because no fully accepted definition exists.
Abstract
from arXiv · showhide
The research area of evolutionary multiobjective optimization (EMO) is reaching better understandings of the properties and capabilities of EMO algorithms, and accumulating much evidence of their worth in practical scenarios. An urgent emerging issue is that the favoured EMO algorithms scale poorly when problems have many (e.g. five or more) objectives. One of the chief reasons for this is believed to be that, in many-objective EMO search, populations are likely to be largely composed of nondominated solutions. In turn, this means that the commonly-used algorithms cannot distinguish between these for selective purposes. However, there are methods that can be used validly to rank points in a nondominated set, and may therefore usefully underpin selection in EMO search. Here we discuss and compare several such methods. Our main finding is that simple variants of the often-overlooked Average Ranking strategy usually outperform other methods tested, covering problems with 5-20 objectives and differing amounts of inter-objective correlation.
1. INTRODUCTION & BACKGROUND
Many-objective EMO scales poorly partly because populations contain many nondominated points, weakening selection based on dominance. This paper investigates nondominated-point ranking methods without objective preferences, while acknowledging metric and method-coverage limitations.
- Motivation: As the number of objectives increases, populations are more likely to consist largely of nondominated points, limiting selective discrimination by dominance-based algorithms.This affects algorithms whose selective fitness assignment depends on populations containing substantial numbers of dominated points.
- Motivation: Fitness deterioration can arise when size-restricted archives discard points that would later dominate points retained in subsequent generations.The study uses a simple random archiver so tested-method biases arise from parental selection rather than archiving.
- Approach: The paper compares preference-ordering methods for nondominated sets while treating all objectives equally and avoiding domain-dependent objective priorities.Earlier work includes the favour relation and k-optimality, while winning_score is shown to be equivalent to one tested method.
- Scope: The paper notes that there is no fully accepted definition of the best possible Pareto-front approximation because interpretations depend on the chosen metric.The authors explicitly subsume their meaning of best possible approximation in the selected metric.
- Scope: The investigation covers selected nondominated-point ranking techniques, omits density-based methods, and includes methods whose rankings may or may not depend on the current population.The authors state that the study does not cover the full range of available techniques.
2.1 Preliminaries
The preliminaries formalize multiobjective optimization through objective vectors, dominance, coverage, and nondominated sets. They then treat candidate structures by their objective values when assigning selective fitness.
- Problem formulation: A multiobjective problem seeks structures that simultaneously minimize k objective functions, with maximization handled by conversion to minimization.The search space is represented by structures mapped to objective values.
- Problem formulation: For a population subset P, each objective has one or more best solutions, while a single solution may occasionally be best across all objectives.The preliminaries use objective-wise comparisons among individuals in P.
- Core relations: Coverage means one solution is no worse than another on any objective, including cases where it dominates or equals the other in objective space.The relation is defined by objective-wise non-worseness.
- Core relations: The nondominated set contains members of P that are not dominated by any other member of P.Nondominance is defined relative to the specified population subset.
- Fitness assignment: When assigning selective fitness, the paper represents structures by the vectors of objective values produced by their objective functions.This objective-space treatment applies to structures such as graphs or neural networks.
2.2 Ranking Nondominated Points
The paper reviews methods for imposing preference orderings on nondominated points without domain-dependent objective preferences. It focuses on average ranking, ratios, favour, k-optimality, and winning score, including their mechanics and limitations.
- Motivation: The methods are presented as alternatives to domain-specific objective priorities and as approaches distinct from MCDM, which emphasizes compromise points rather than the full Pareto set.The paper considers all objectives equally while seeking approximations to the Pareto front.
- Objective Ranking and Ratios: Average Ranking (AR) scores each point by summing its ranks across objectives, so lower total scores indicate better points.For example, ranks 2, 2, and 5 produce an AR score of 9.
- Objective Ranking and Ratios: The related Sum of Ratios (SR) method replaces each objective rank with its normalized objective value.SR assumes minimization and evaluates normalized objective values across a set of k-objective points.
- The Favour Relation: The favour relation prefers one point when it is better on more objectives than its competitor, but cycles can prevent a complete ordering.Its procedure builds a favour graph, collapses strongly connected components, and derives a partial ordering from the resulting directed acyclic graph.
- K-Optimality: k-optimality ranks a point by the lowest subset size for which it remains nondominated across every subset of that many objectives.Although every point is efficient of order k, determining k-optimality becomes unusable beyond around 20 objectives because no efficient procedure was available.
- Equivalence of Winning Score and AR: Winning score sums pairwise margins across objectives, and its ordering is equivalent to AR up to a positive constant transformation.A margin is positive when a point wins on more objectives, negative when it loses, and the induced order matches AR.
2.3 Metrics and Test Problems
The paper evaluates rank-distribution richness using relative entropy and defines test problems based on multiobjective TSPs and single-machine job-shop problems. Performance comparisons use the standard cover metric, while acknowledging that no metric is fully authoritative.
- Metrics: A ranking with more varied rank frequencies gives selection more opportunity to distinguish among nondominated points.The paper illustrates this by contrasting one point at rank 1 with a distribution spread across three ranks.
- Metrics: Relative entropy measures how richly a ranking method orders a nondominated set, with higher values indicating more selection-relevant discrimination.It approaches 1 when points occupy distinct ranks and is zero when every point receives the same rank.
- Test Problems: The test problems include k-objective traveling salesperson problems generated from correlated distance matrices and multiobjective single-machine job-shop problems.TSP instances use 30 cities; job-shop objectives sum lateness across jobs assigned to each customer.
- Metrics: The standard cover metric compares two archived solution sets by measuring the percentage of one set covered by the other.A statistically significant series of pairwise wins identifies the better-performing algorithm in the reported comparisons.
3. RANK DISTRIBUTIONS
The experiments examine rank distributions produced by favour and k-optimality across many-objective random populations. Favour produces little discrimination as objectives increase, whereas k-optimality yields more consistently distributed ranks.
- Experiments: 1,000 random populations are generated for each objective count k in {5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20}.Each population contains 50 k-objective MOTSP individuals, and relative entropy is calculated for both ranking methods.
- Figure 1: Figure 1 compares the relative-entropy distributions for populations ranked by favour and k-optimality across objective counts.The figure shows favour on the left and k-optimality on the right, with bars representing relative-entropy intervals.
- Findings: Favour induces very low relative-entropy distributions, especially as the number of objectives increases.Low relative entropy indicates that favour rarely creates much discrimination among nondominated points.
- Findings: k-optimality produces reliably above-zero relative-entropy values that improve with increasing objective count.The paper expects this steadier rank distribution to support better performance than favour.
4. COMPARATIVE EXPERIMENTS
The experiments compare four nondominated-point ranking methods with three baselines across many-objective TSP and JSP settings. ARF performs best in most cases, while performance differences weaken under very many objectives and high conflict.
- Methods: Seven methods were compared: ARF, SRF, favour, k-optimality, random Pareto-front selection, summed-objective selection, and random selection.ARF, SRF, favour, and k-optimality ranked nondominated points; the remaining methods served as baselines.
- Evaluation: 17 or more of 20 paired cover-metric wins indicated statistical significance before the stated Bonferroni correction.Each method pair produced 20 paired Cov(A,B) and Cov(B,A) values for each experimental setting.
- Results: JSP findings were broadly similar to TSP findings, but stronger negative correlation produced less clear discrimination as objective count increased.Some JSP columns contained more statistically inconclusive comparisons than their TSP counterparts.
- Results: ARF outperformed the other algorithms in most cases, except under very many objectives and high conflict.The exceptions were k=20 with TSPcp = -40 and k=15,20 with JSPcp = 10,20; in those cases, no method exceeded random selection.
- Results: K-optimality was usually second to ARF, while favour and random Pareto-front selection performed relatively well at lower and higher objective counts, respectively.Summed-objective selection, summed ratio, and favour for 10 or more objectives could perform consistently worse than random selection.
5. CONCLUDING DISCUSSION
The paper concludes that average ranking is a strong candidate for many-objective search, especially when objectives lack significant inter-correlation. It also identifies limited generalizability and metric choice as important qualifications.
- Conclusions: ARF was highly effective compared with the other tested methods when objectives did not exhibit significant inter-correlation.K-optimality was generally next best; favour and random Pareto-front selection tended to perform well with fewer and more objectives, respectively.
- Implications: ARF is computationally simple and efficient and outperformed two methods proposed specifically for many-objective problems.The authors recommend further testing ARF and revisiting both ARF and AR for standard two-to-five-objective problems.
- Limitations: The authors generalize only tentatively from the MOTSP and SMJSP test problems.They explicitly identify the use of a single comparative performance metric as another limitation.
- Future work: Alternative favour and k-optimality variants could provide less collapsed or finer-grained rankings, motivating further study.The proposed variants adjust the favour threshold or account for the proportion of efficient z-objective subsets.