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:
- Computational Intractability: Metrics like Hypervolume become mathematically impossible to calculate as the number of objectives increases.
- Reference Dependency: Tools like Inverted Generational Distance (IGD) require a known "perfect" reference set, which is rarely available in real-world scenarios.
- Uniformity vs. Diversity: Most metrics conflate "uniformity" (even spacing) with "diversity" (broad coverage).
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.
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