Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem

• URL: http://arxiv.org/abs/2004.10424v1
• Date: Wed, 22 Apr 2020 07:47:00 GMT
• Title: Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem
• Authors: Vahid Roostapour, Jakob Bossek, Frank Neumann
• Abstract summary: 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.
• Score: 12.098400820502635
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evolutionary algorithms (EAs) are general-purpose problem solvers that usually perform an unbiased search. This is reasonable and desirable in a black-box scenario. For combinatorial optimization problems, often more knowledge about the structure of optimal solutions is given, which can be leveraged by means of biased search operators. We consider the Minimum Spanning Tree (MST) problem in a single- and multi-objective version, and introduce a biased mutation, which puts more emphasis on the selection of edges of low rank in terms of low domination number. We present example graphs where the biased mutation can significantly speed up the expected runtime until (Pareto-)optimal solutions are found. On the other hand, we demonstrate that bias can lead to exponential runtime if heavy edges are necessarily part of an optimal solution. However, on general graphs in the single-objective setting, we show that a combined mutation operator which decides for unbiased or biased edge selection in each step with equal probability exhibits a polynomial upper bound -- as unbiased mutation -- in the worst case and benefits from bias if the circumstances are favorable.

Related papers

• Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
  In this paper, we analyze the usefulness of using genetic algorithms depending on the approximation class the problem belongs to. In particular, we use the standard approximability hierarchy, showing that genetic algorithms are especially useful for the most pessimistic classes of the hierarchy.
  arXiv  Detail & Related papers  (2024-02-01T09:18:34Z)
• Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima [12.009357100208353]
  We propose the test function EqualBlocksOneMax (EBOM) to support the study of how optimization algorithms handle large sets of optima. We show that EBOM behaves very similarly to a theoretically ideal model for EBOM, which samples each of the exponentially many optima with the same maximal probability.
  arXiv  Detail & Related papers  (2023-10-06T06:32:07Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  We consider monotone variational inequality (VI) problems in multi-GPU settings where multiple processors/workers/clients have access to local dual vectors. Extra-gradient, which is a de facto algorithm for monotone VI problems, has not been designed to be communication-efficient. We propose a quantized generalized extra-gradient (Q-GenX), which is an unbiased and adaptive compression method tailored to solve VIs.
  arXiv  Detail & Related papers  (2023-08-17T21:15:04Z)
• Run Time Analysis for Random Local Search on Generalized Majority Functions [1.0965065178451106]
  We study how one of its properties -- neutrality -- influences the run time of random local search. We provide a theorem, applicable to many optimization algorithms, that links the run time of MAJORITY with its symmetric version HASMAJORITY.
  arXiv  Detail & Related papers  (2022-04-27T08:40:33Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• A Rank based Adaptive Mutation in Genetic Algorithm [0.0]
  This paper presents an alternate approach of mutation probability generation using chromosome rank to avoid any susceptibility to fitness distribution. Experiments are done to compare results of simple genetic algorithm (SGA) with constant mutation probability and adaptive approaches within a limited resource constraint.
  arXiv  Detail & Related papers  (2021-04-18T12:41:33Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
  arXiv  Detail & Related papers  (2020-12-11T08:28:51Z)
• Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem [13.264683014487376]
  We study the well-known Minimum Spanning Tree problem (MST) in the context of diversity optimization. We show that a simple $(mu+1)$-EA can effectively compute a diversified population of spanning trees of high quality.
  arXiv  Detail & Related papers  (2020-10-21T11:50:49Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)

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.