Comparative Analysis of Indicators for Multi-objective Diversity Optimization
Lecture notes in computer science, pp. 58–71
Abstract
Abstract Indicator-based (multi-objective) diversity optimization aims at finding a set of near (Pareto)optimal solutions that maximizes a diversity indicator, where diversity is typically interpreted as the number of essentially different solutions. Whereas, in the first diversity-oriented evolutionary multi-objective optimization algorithm, the NOAH algorithm by Ulrich and Thiele, the Solow Polasky Diversity (SP Diversity, also known as Magnitude [1]) served as a metric, other diversity indicators could be considered. We examine the parameter-free Max-Min Diversity and the Riesz $$s$$ s -Energy, which features uniformly distributed solution sets. Focusing on multi-objective diversity optimization, we discuss different diversity indicators from the perspective of indicator-based evolutionary algorithms with multiple objectives. We examine theoretical, computational, and practical properties of these indicators, such as monotonicity in species, twinning, monotonicity in distance, strict monotonicity in distance, uniformity of maximizing point sets, computational effort for a set of size $$n$$ n , single-point contributions, subset selection, and submodularity. We present new theorems—including a proof of the NP-hardness of the Riesz $$s$$ s -Energy Subset Selection Problem—and consolidate existing results from the literature. In the experiments, we apply these indicators in the NOAH algorithm to analyze search dynamics via an example. We study how optimizing one indicator impacts others and propose NOAH-specific modifications for the Max-Min indicator.
Authors 6
-
Affiliation as printed
Leiden Institute of Advanced Computer Science, Leiden University, Leiden, The Netherlands
-
Affiliation as printed
Leiden Institute of Advanced Computer Science, Leiden University, Leiden, The Netherlands
-
Eindhoven University of Technology
Affiliation as printed
Eindhoven University of Technology, Eindhoven, The Netherlands
-
Affiliation as printed
Leiden Institute of Advanced Computer Science, Leiden University, Leiden, The Netherlands
-
Eindhoven University of Technology
Affiliation as printed
Eindhoven University of Technology, Eindhoven, The Netherlands
-
Leiden University · University of Jyväskylä
Affiliation as printed
Faculty of Information Technology, University of Jyvaskyla, Jyvaskyla, Finland
Leiden Institute of Advanced Computer Science, Leiden University, Leiden, The Netherlands
Cited by 4 stored of 4
4 results
No patents citing this paper on Lens.org (checked 2026-10-11).