Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces
Authors: Benjamin Doerr, Martin S. Krejca, Günter Rudolph
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We complement our mathematical findings with experimental results that suggest that our bounds are not always tight. Most prominently, our experiments indicate that power-law mutation outperforms the one with exponential tails even when the latter uses a nearoptimal parametrization. Hence, we suggest to favor powerlaw mutation for unknown problems in integer spaces. Empirical Analysis We aim to assess how far our theoretical upper bounds are from actual, empirical values. We also aim to understand whether the exponential-tail law actually has a parametrization that is favorable to the power-law mutation, as suggested by our theoretical results. |
| Researcher Affiliation | Academia | Benjamin Doerr1, Martin S. Krejca1, G unter Rudolph2 1Laboratoire d Informatique (LIX), CNRS, Ecole Polytechnique, Institut Polytechnique de Paris, Palaiseau, France 2Department of Computer Science, TU Dortmund University, Dortmund, Germany |
| Pseudocode | Yes | Algorithm 1: Algorithmic framework for evolutionary multi-objective minimization of a given dobjective function f : Zn Rd. |
| Open Source Code | Yes | Our code is publicly available (Doerr, Krejca, and Rudolph 2024b). Zenodo. https://zenodo.org/records/14506854. |
| Open Datasets | No | Benchmark Problem We consider the following bi-objective benchmark function, introduced by Rudolph (2023). Given a parameter a N, the function f : Zn N2 is defined as... Explanation for no: The paper analyzes a benchmark function, which is a theoretical problem definition, not an empirical dataset that would require specific access information. |
| Dataset Splits | No | Benchmark Problem We consider the following bi-objective benchmark function, introduced by Rudolph (2023). Explanation for no: The paper analyzes a theoretical benchmark function, not an empirical dataset that would typically involve training/test/validation splits. |
| Hardware Specification | No | Our choice for n is based on all of our results holding for any value of n N 2, and a smaller choice of n lets us run more experiments. Nonetheless, we note that we consider larger values of n in the full version, and the observations are qualitatively the same as they are for n = 2, just with an even clearer distinction between the different mutation operators. Explanation for no: The paper does not provide specific hardware details (e.g., CPU/GPU models, memory) used for running the experiments. |
| Software Dependencies | No | The paper does not mention any specific software dependencies with version numbers. Explanation for no: The paper does not provide specific software dependencies or version numbers for any libraries, frameworks, or tools used in the experimental implementation. |
| Experiment Setup | Yes | We choose n = 2 and x(0) = (0, 100a) =: (0, y0). Furthermore, we choose β = 3/2, which is generally a good choice (Doerr et al. 2017). Our choice for n is based on all of our results holding for any value of n N 2, and a smaller choice of n lets us run more experiments. The first scenario aims to determine a good value q for the exponential-tail mutation. To this end, we choose a = 200 as well as 1/q {5, 10, 20, 50, 100, 200, 500}, which covers a broad, quickly increasing, thus diverse, range of values for 1/q. |