Explanipedia

Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer Open

Martin S. Krejca, Miloš S. Stanković · 2025

Together with the NSGA-II, the SPEA2 is one of the most widely used domination-based multi-objective evolutionary algorithms. For both algorithms, the known runtime guarantees are linear in the population size; for the NSGA-II, matching lo…

Towards the genome-scale discovery of bivariate monotonic classifiers Open

Océane Fourquet, Martin S. Krejca, Carola Doerr, Benno Schwikowski · 2025

We provide the first open-source implementation for learning BMCs, a Python implementation of fastBMC in particular, and Python code to reproduce the fastBMC results on real and simulated data in this paper, at https://github.com/oceanefrq…

Speeding Up the NSGA-II via Dynamic Population Sizes Open

Martin S. Krejca, Simon Wietheger · 2025

Multi-objective evolutionary algorithms (MOEAs) are among the most widely and successfully applied optimizers for multi-objective problems. However, to store many optimal trade-offs (the Pareto optima) at once, MOEAs are typically run with…

Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm Open

Benjamin Doerr, Martin S. Krejca, Andre Opris · 2025

The global simple evolutionary multi-objective optimizer (GSEMO) is a simple, yet often effective multi-objective evolutionary algorithm (MOEA). By only maintaining non-dominated solutions, it has a variable population size that automatica…

Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II Open

Yasser Alghouass, Benjamin Doerr, Martin S. Krejca, Mohammed Lagmah · 2025

Together with the NSGA-II and SMS-EMOA, the strength Pareto evolutionary algorithm 2 (SPEA2) is one of the most prominent dominance-based multi-objective evolutionary algorithms (MOEAs). Different from the NSGA-II, it does not employ the c…

Population Dynamics and Improved Runtime Guarantees for the (μ+1) EA on BinVal Open

Martin S. Krejca, Frank Neumann, Carsten Witt · 2025

Hot off the Press: Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark Open

Marcel Chwiałkowski, Benjamin Doerr, Martin S. Krejca · 2025

International audience

Hot off the Press: Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem Solutions Open

Benjamin Doerr, Martin S. Krejca, Noé Weeks · 2025

International audience

Hot off the Press: Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces Open

Benjamin Doerr, Martin S. Krejca, Günter Rudolph · 2025

International audience

Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm Open

Benjamin Doerr, Martin S. Krejca, Andre Opris · 2025

The global simple evolutionary multi-objective optimizer (GSEMO) is a simple, yet often effective multi-objective evolutionary algorithm (MOEA). By only maintaining non-dominated solutions, it has a variable population size that automatica…

Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II Open

Yasser Alghouass, Benjamin Doerr, Martin S. Krejca, Mohammed Lagmah · 2025

Together with the NSGA-II and SMS-EMOA, the strength Pareto evolutionary algorithm 2 (SPEA2) is one of the most prominent dominance-based multi-objective evolutionary algorithms (MOEAs). Different from the NSGA-II, it does not employ the c…

Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces Open

Benjamin Doerr, Martin S. Krejca, Günter Rudolph · 2025

Randomized search heuristics have been applied successfully to a plethora of problems. This success is complemented by a large body of theoretical results. Unfortunately, the vast majority of these results regard problems with binary or co…

Speeding Up the NSGA-II with a Simple Tie-Breaking Rule Open

Benjamin Doerr, Tudor Ivan, Martin S. Krejca · 2025

The non-dominated sorting genetic algorithm II (NSGA-II) is the most popular multi-objective optimization heuristic. Recent mathematical runtime analyses have detected two shortcomings in discrete search spaces, namely, that the NSGA-II ha…

Identification of Monotonically Classifying Pairs of Genes for Ordinal Disease Outcomes Open

Océane Fourquet, Daria Afenteva, Kaiyang Zhang, Sampsa Hautaniemi, Martin S. Krejca , et al. · 2025

In this study, we extend an existing classification method for identifying pairs of genes whose joint expression is associated with binary outcomes to ordinal multi-class outcomes, such as overall survival or disease progression. Our appro…

Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark Open

Marcel Chwiałkowski, Benjamin Doerr, Martin S. Krejca · 2025

The compact genetic algorithm (cGA) is one of the simplest estimation-of-distribution algorithms (EDAs). Next to the univariate marginal distribution algorithm (UMDA) -- another simple EDA -- , the cGA has been subject to extensive mathema…

Gradually Declining Immunity Retains the Exponential Duration of Immunity-Free Diffusion Open

Andreas Göbel, Nicolas Klodt, Martin S. Krejca, Marcus Pappik · 2025

Diffusion processes pervade numerous areas of AI, abstractly modeling the dynamics of exchanging, oftentimes volatile, information in networks. A central question is how long the information remains in the network, known as survival time. …

Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces Open

Benjamin Doerr, Martin S. Krejca, Günter Rudolph · 2024

Randomized search heuristics have been applied successfully to a plethora of problems. This success is complemented by a large body of theoretical results. Unfortunately, the vast majority of these results regard problems with binary or co…

Speeding Up the NSGA-II With a Simple Tie-Breaking Rule Open

Benjamin Doerr, Tudor Ivan, Martin S. Krejca · 2024

The non-dominated sorting genetic algorithm~II (NSGA-II) is the most popular multi-objective optimization heuristic. Recent mathematical runtime analyses have detected two shortcomings in discrete search spaces, namely, that the NSGA-II ha…

Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem Open

Benjamin Doerr, Dimitri Korkotashvili, Martin S. Krejca · 2024

The NSGA-II is the most prominent multi-objective evolutionary algorithm (cited more than 50,000 times). Very recently, a mathematical runtime analysis has proven that this algorithm can have enormous difficulties when the number of object…

Sampling repulsive Gibbs point processes using random graphs Open

Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, Martin S. Krejca, Marcus Pappik · 2024

We study computational aspects of repulsive Gibbs point processes, which are probabilistic models of interacting particles in a finite-volume region of space. We introduce an approach for reducing a Gibbs point process to the hard-core mod…

Runtime Analysis of the (μ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations Open

Benjamin Doerr, Aymen Echarghaoui, Mohammed Jamal, Martin S. Krejca · 2024

International audience

Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy Heuristics Open

Benjamin Doerr, Martin S. Krejca, Hoang Nguyen Vu · 2024

The target set selection problem (TSS) asks for a set of vertices such that an influence spreading process started in these vertices reaches the whole graph. The current state of the art for this NP-hard problem are three recently proposed…

A Flexible Evolutionary Algorithm with Dynamic Mutation Rate Archive Open

Martin S. Krejca, Carsten Witt · 2024

We propose a new, flexible approach for dynamically maintaining successful\nmutation rates in evolutionary algorithms using $k$-bit flip mutations. The\nalgorithm adds successful mutation rates to an archive of promising rates that\nare fa…

Estimation-of-distribution algorithms for multi-valued decision variables Open

Firas Ben Jedidia, Benjamin Doerr, Martin S. Krejca · 2024

International audience

Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem Solutions Open

Benjamin Doerr, Martin S. Krejca, Noé Weeks · 2024

The decomposition-based multi-objective evolutionary algorithm (MOEA/D) does not directly optimize a given multi-objective function $f$, but instead optimizes $N + 1$ single-objective subproblems of $f$ in a co-evolutionary manner. It main…

The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network Models Open

Tobias Friedrich, Andreas Göbel, Nicolas Klodt, Martin S. Krejca, Marcus Pappik · 2024

Information diffusion models on networks are at the forefront of AI research. The dynamics of such models typically follow stochastic models from epidemiology, used to model not only infections but various phenomena, including the behavior…

Runtime Analysis of the (μ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations Open

Benjamin Doerr, Aymen Echarghaoui, Jamal Mohammed, Martin S. Krejca · 2024

Most evolutionary algorithms used in practice heavily employ crossover. In contrast, the rigorous understanding of how crossover is beneficial is largely lagging behind. In this work, we make a considerable step forward by analyzing the po…

Runtime Analysis of the (µ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations Open

Benjamin Doerr, Aymen Echarghaoui, Jamal Mohammed, Martin S. Krejca · 2024

International audience

Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic Approximation Open

Thomas Bläsius, Sarel Cohen, Philipp Fischbeck, Tobias Friedrich, Martin S. Krejca · 2024

Random graph models are widely used to understand network properties and graph algorithms. Key to such analyses are the different parameters of each model, which affect various network features, such as its size, clustering, or degree dist…

From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion Models Open

Tobias Friedrich, Andreas Göbel, Nicolas Klodt, Martin S. Krejca, Marcus Pappik · 2024

Diffusion of information in networks is at the core of many problems in AI. Common examples include the spread of ideas and rumors as well as marketing campaigns. Typically, information diffuses at a non-linear rate, for example, if market…

Martin S. Krejca YOU? Author Swipe