Diversity Assessment in Many-Objective Optimization

Handing Wang, Yaochu Jin, Xin Yao

Abstract

In many-objective optimization (MaOP), traditional metrics for assessing solution diversity often fail due to the "curse of dimensionality." This paper proposes Pure Diversity (PD), a novel metric inspired by biological biodiversity measures. Unlike existing tools, PD accurately evaluates spatial coverage without requiring a pre-defined reference set or incurring prohibitive computational costs. By employing fractional $L_p$-norm distances, PD effectively distinguishes between solution uniformity and true diversity, providing a robust diagnostic tool for high-dimensional search spaces.

Introduction: The Challenge of High-Dimensional Diversity

Designing complex systems—such as an automobile that must be simultaneously cost-effective, safe, and fuel-efficient—requires balancing numerous competing goals. As the number of objectives grows beyond three, visualizing the "trade-off surface" (Pareto front) becomes impossible. In these high-dimensional spaces, traditional metrics encounter several critical issues:

  1. Computational Intractability: Metrics like Hypervolume become mathematically impossible to calculate as the number of objectives increases.
  2. Reference Dependency: Tools like Inverted Generational Distance (IGD) require a known "perfect" reference set, which is rarely available in real-world scenarios.
  3. Uniformity vs. Diversity: Most metrics conflate "uniformity" (even spacing) with "diversity" (broad coverage).
Comparison of uniformity versus diversity across different solution distributions.

As illustrated above, a set of solutions can be perfectly evenly spaced (high uniformity) while occupying only a small fraction of the available space (low diversity). PD is specifically designed to prioritize the latter.

Methods: A Biological Approach to Dissimilarity

The authors introduce Pure Diversity (PD) by adapting biological principles where ecosystem diversity is measured by the degree of difference between species rather than just their count.

Fractional $L_p$-norm Distance

A key innovation in PD is the use of the $L_p$-norm with $p < 1$ (specifically $p=0.1$). In high-dimensional spaces, standard Euclidean distance ($p=2$) often fails because the distance between the nearest and farthest points becomes nearly identical.

The effect of varying the p-parameter in the Lp-norm on distance sensitivity.

By using a fractional power, the metric "stretches" the space, enhancing the sensitivity to differences between solutions across many dimensions.

Recursive Greedy Accumulation

The PD algorithm calculates diversity through a recursive process that identifies the most dissimilar neighbors and adds their dissimilarity values to a running total. This reference-free approach allows PD to evaluate a population's health based solely on the solutions themselves.

Evaluation and Results

The metric was rigorously tested using the DTLZ and WFG benchmark suites across 2 to 10 objectives. PD successfully identified diversity loss in synthetic datasets where traditional metrics like Spacing or Maximum Spread provided misleading results. It revealed that some popular algorithms, such as IBEA, suffer from "collapsing" diversity in high dimensions—a flaw previously undetected by older tools.

To demonstrate practical utility, the researchers developed NSGA-III-PD, a variant of the standard NSGA-III algorithm that utilizes PD for reference point selection. In 10-objective tests, NSGA-III-PD significantly outperformed the baseline in maintaining a diverse solution set.

Conclusion

Pure Diversity offers a specialized tool for measuring the "unmeasurable" in high-dimensional optimization. While it is a diversity metric rather than a comprehensive performance metric—meaning it must be paired with convergence measures to assess overall solution quality—it provides a critical diagnostic capability. Future work will focus on optimizing the $O(n^2)$ computational complexity and exploring PD's performance on degenerate Pareto fronts.

Summary updated

Abstract

Maintaining diversity is one important aim of multiobjective optimization. However, diversity for manyobjective optimization problems is less straightforward to define than for multiobjective optimization problems. Inspired by measures for biodiversity, we propose a new diversity metric for many-objective optimization, which is an accumulation of the dissimilarity in the population, where an Lp-norm-based (p<;1) distance is adopted to measure the dissimilarity of solutions. Empirical results demonstrate our proposed metric can more accurately assess the diversity of solutions in various situations. We compare the diversity of the solutions obtained by four popular many-objective evolutionary algorithms using the proposed diversity metric on a large number of benchmark problems with two to ten objectives. The behaviors of different diversity maintenance methodologies in those algorithms are discussed in depth based on the experimental results. Finally, we show that the proposed diversity measure can also be employed for enhancing diversity maintenance or reference set generation in many-objective optimization.
BibTeX
@article{wang2017diversity,
  author = {Handing Wang and Yaochu Jin and Xin Yao},
  title = {{Diversity Assessment in Many-Objective Optimization}},
  journal = {IEEE Trans. Cybernetics},
  year = {2017},
  doi = {10.1109/tcyb.2016.2550502},
}
Figure