Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
A Many-Objective Problem Where Crossover Is Provably Indispensable
Authors: Andre Opris
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present a many-objective problem class together with a theoretical runtime analysis of the widely used NSGA-III to demonstrate that crossover can yield an exponential speedup on the runtime. In particular, this algorithm can find the Pareto set in expected polynomial time when using crossover while without crossover it requires exponential time to even find a single Pareto-optimal point. To our knowledge, this is the first rigorous runtime analysis in many-objective optimisation demonstrating an exponential performance gap when using crossover for more than two objectives. |
| Researcher Affiliation | Academia | Andre Opris Chair of Algorithms for Intelligent Systems, University of Passau, Passau, Germany EMAIL |
| Pseudocode | Yes | Algorithm 1: NSGA-III on an m-objective function f with population size µ and crossover probability pc (Deb and Jain 2014) and Algorithm 2: Selection procedure based on a set Rp of reference points for maximising a function |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of its own open-source code for the methodology described. |
| Open Datasets | No | In this section, we define the many-objective REALROYALROAD function which we denote by m-RRMO. |
| Dataset Splits | No | The paper defines a theoretical problem class (m-RRMO) and conducts runtime analysis, therefore, it does not involve empirical evaluation with dataset splits. |
| Hardware Specification | No | The paper presents a theoretical runtime analysis and does not describe experiments run on specific hardware. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers for experimental replication. |
| Experiment Setup | No | The paper provides a theoretical runtime analysis and does not describe an experimental setup, hyperparameters, or training configurations. |