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\) -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\) , single-point contributions, subset selection, and submodularity. We present new theorems—including a proof of the NP-hardness of the Riesz \(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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Comparative Analysis of Indicators for Multi-objective Diversity Optimization

  • Ksenia Pereverdieva,
  • André Deutz,
  • Tessa Ezendam,
  • Thomas Bäck,
  • Hèrm Hofmeyer,
  • Michael Emmerich

摘要

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\) -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\) , single-point contributions, subset selection, and submodularity. We present new theorems—including a proof of the NP-hardness of the Riesz \(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.