Crowding Distance

Crowding distance is a defining component of the Non-dominated Sorting Genetic Algorithm II (NSGA-II). After the population is sorted into non-dominated fronts, crowding distance is assigned within each front. The algorithm uses a crowded-comparison operator (<n) that first prefers a lower (better) non-domination rank, and if ranks are equal, prefers a larger crowding distance.

• Truncation Mechanism: When reducing a population to a fixed size, NSGA-II fills slots from the best fronts first, using crowding distance as a tie-breaker to trim the most crowded regions of the last accepted front.
• Runtime Complexity: The non-dominated sorting and crowding distance assignment in NSGA-II have a computational complexity of O(MN²), where M is the number of objectives and N is the population size.

Solutions that define the extremes of a non-dominated front are assigned an infinite crowding distance (or a very large value in practice). This guarantees their automatic survival during selection, which is critical for capturing the full range of possible compromises between objectives.

• Ideal and Nadir Points: These boundary points help approximate the ideal point (best theoretically achievable values) and the nadir point (worst values among Pareto optimal solutions).
• Visualization: In a 2-objective plot, the solutions with the smallest f1 and the smallest f2 are the boundaries and receive infinite crowding distance.

Crowding distance's effectiveness diminishes as the number of objectives increases, a scenario known as many-objective optimization (MaOO). In high-dimensional objective spaces, most solutions become non-dominated, reducing the discriminatory power of Pareto ranking. Furthermore, the concept of "nearest neighbors" becomes less meaningful, and the population tends to be sparse, making crowding distance comparisons less effective for guiding selection.

• Curse of Dimensionality: The volume of the objective space grows exponentially, making it difficult to maintain a representative, well-distributed front with a finite population.
• Alternative Metrics: Algorithms for MaOO often replace or augment crowding distance with other indicators, such as the Hypervolume indicator or grid-based density estimators.

While crowding distance is a local, perimeter-based measure, the Hypervolume indicator measures the global dominated volume. A solution's hypervolume contribution is the volume of space exclusively dominated by it. Both metrics aim to reward diversity, but hypervolume is a Pareto-compliant indicator with stronger theoretical properties.

• Contrast: Crowding distance is fast to compute (O(MN log N)) but is a heuristic. Hypervolume calculation is computationally expensive (O(N^(M/2)) but provides a direct quality measure.
• Usage: Advanced MOEAs like SMS-EMOA use hypervolume contribution directly for selection, while NSGA-II uses the faster crowding distance approximation.

NSGA-II is the canonical multi-objective evolutionary algorithm (MOEA) that popularized the use of crowding distance. It operates by:

1. Non-Dominated Sorting: Ranking the population into fronts based on Pareto dominance.
2. Crowding Distance Assignment: Calculating density within each front.
3. Selection: Using rank and crowding distance to select parents and survivors, favoring solutions in better fronts and, within a front, those in less crowded regions.

The hypervolume indicator (or S-metric) is a Pareto-compliant quality measure for a set of solutions. It calculates the volume of the objective space dominated by the set, bounded by a reference point. While crowding distance is a diversity-preserving selection criterion, hypervolume is an offline performance metric used to evaluate and compare the output of different MOEAs.

• Comprehensiveness: Captures both convergence (closeness to the true Pareto front) and diversity (spread of solutions).

Scalarization is an alternative approach to multi-objective optimization that transforms the vector of objectives into a single scalar objective, typically using a weighted sum or the epsilon-constraint method. This contrasts with Pareto-based methods like NSGA-II that use crowding distance to maintain a diverse set of solutions. Scalarization requires pre-defining preferences (e.g., weights), while Pareto methods first discover the trade-off surface.

MOBO is a sample-efficient framework for optimizing expensive black-box functions with multiple objectives. It uses a probabilistic surrogate model (like a Gaussian Process) and an acquisition function to guide the search. While MOBO does not use crowding distance directly, it addresses the same core challenge: effectively exploring the trade-off surface. Advanced MOBO methods use hypervolume-based acquisition or other techniques to manage the diversity of suggested points.