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

• URL: http://arxiv.org/abs/2412.11684v2
• Date: Tue, 17 Dec 2024 12:52:14 GMT
• Title: Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces
• Authors: Benjamin Doerr, Martin S. Krejca, Günter Rudolph,
• Abstract summary: We analyze multi-objective evolutionary algorithms for integer search spaces. We find that power-law mutation outperforms the one with exponential tails. We suggest to favor power-law mutation for unknown problems in integer spaces.
• Score: 9.591164070876687
• License:
• Abstract: 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 continuous decision variables -- the theoretical analysis of randomized search heuristics for unbounded integer domains is almost nonexistent. To resolve this shortcoming, we start the runtime analysis of multi-objective evolutionary algorithms, which are among the most successful randomized search heuristics, for unbounded integer search spaces. We analyze single- and full-dimensional mutation operators with three different mutation strengths, namely changes by plus/minus one (unit strength), random changes following a law with exponential tails, and random changes following a power-law. The performance guarantees we prove on a recently proposed natural benchmark problem suggest that unit mutation strengths can be slow when the initial solutions are far from the Pareto front. When setting the expected change right (depending on the benchmark parameter and the distance of the initial solutions), the mutation strength with exponential tails yields the best runtime guarantees in our results -- however, with a wrong choice of this expectation, the performance guarantees quickly become highly uninteresting. With power-law mutation, which is an essentially parameter-less mutation operator, we obtain good results uniformly over all problem parameters and starting points. 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 near-optimal parametrization. Hence, we suggest to favor power-law mutation for unknown problems in integer spaces.

Related papers

• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. We show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks.
  arXiv  Detail & Related papers  (2024-10-22T10:19:27Z)
• A Flexible Evolutionary Algorithm With Dynamic Mutation Rate Archive [2.07180164747172]
  We propose a new, flexible approach for dynamically maintaining successful mutation rates in evolutionary algorithms using $k$-bit flip mutations. Rates expire when their number of unsuccessful trials has exceeded a threshold, while rates currently not present in the archive can enter it in two ways. For the minimum selection probabilities, we suggest different options, including heavy-tailed distributions.
  arXiv  Detail & Related papers  (2024-04-05T10:51:40Z)
• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  We show that two evolutionary algorithms can tolerate constant noise probabilities without increasing the runtime on the OneMax benchmark. Our results are based on a novel proof argument that the noiseless offspring can be seen as a biased uniform crossover between the parent and the noisy offspring.
  arXiv  Detail & Related papers  (2024-04-02T16:35:52Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  We prove the first high-probability results with logarithmic dependence on the confidence level for methods for solving monotone and structured non-monotone VIPs. Our results match the best-known ones in the light-tails case and are novel for structured non-monotone problems. In addition, we numerically validate that the gradient noise of many practical formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.
  arXiv  Detail & Related papers  (2022-06-02T15:21:55Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  gradient Langevin Dynamics is one of the most fundamental algorithms to solve non-eps optimization problems. In this paper, we show two variants of this kind, namely the Variance Reduced Langevin Dynamics and the Recursive Gradient Langevin Dynamics.
  arXiv  Detail & Related papers  (2022-03-30T11:39:00Z)
• E-detectors: a nonparametric framework for sequential change detection [86.15115654324488]
  We develop a fundamentally new and general framework for sequential change detection. Our procedures come with clean, nonasymptotic bounds on the average run length. We show how to design their mixtures in order to achieve both statistical and computational efficiency.
  arXiv  Detail & Related papers  (2022-03-07T17:25:02Z)
• Analysis of Evolutionary Diversity Optimisation for Permutation Problems [17.268191781480745]
  Investigation on evolutionary diversity optimization for three of the most well-studied permutation problems. Results show many mutation operators for these problems guarantee convergence to maximally diverse populations. Experiments are carried out on QAPLIB and synthetic instances in unconstrained and constrained settings.
  arXiv  Detail & Related papers  (2021-02-23T03:13:26Z)
• Optimal Static Mutation Strength Distributions for the $(1+\lambda)$ Evolutionary Algorithm on OneMax [1.0965065178451106]
  We show that, for large enough population sizes, such optimal distributions may be surprisingly complicated and counter-intuitive. We show that, for large enough population sizes, such optimal distributions may be surprisingly complicated and counter-intuitive.
  arXiv  Detail & Related papers  (2021-02-09T16:56:25Z)
• Total Deep Variation: A Stable Regularizer for Inverse Problems [71.90933869570914]
  We introduce the data-driven general-purpose total deep variation regularizer. In its core, a convolutional neural network extracts local features on multiple scales and in successive blocks. We achieve state-of-the-art results for numerous imaging tasks.
  arXiv  Detail & Related papers  (2020-06-15T21:54:15Z)
• Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem [12.098400820502635]
  We consider the Spanning Tree (MST) problem in a single- and multi-objective version. We introduce a biased mutation, which puts more emphasis on the selection of edges of low rank in terms of low domination number. We show that a combined mutation operator which decides for unbiased or biased edge selection exhibits an upper bound -- as unbiased mutation -- in the worst case.
  arXiv  Detail & Related papers  (2020-04-22T07:47:00Z)
• Fast Mutation in Crossover-based Algorithms [8.34061303235504]
  Heavy-tailed mutation operator proposed in Doerr, Le, Makhmara and Nguyen (GECCO) A heavy-tailed mutation operator proposed in Doerr, Le, Makhmara and Nguyen (GECCO) An empirical study shows the effectiveness of the fast mutation also on random satisfiable Max-3SAT instances.
  arXiv  Detail & Related papers  (2020-04-14T14:16:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.