Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationEvolutionary AlgorithmsMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
On Non-Elitist Evolutionary Algorithms Optimizing Fitness Functions with a Plateau
We consider the expected runtime of non-elitist evolutionary algorithms (EAs), when they are applied to a family of fitness functions with a plateau of second-best fitness in a Hamming ball of radius r around a unique gl…
Evolutionary AlgorithmsRuntime Analysis for Self-adaptive Mutation Rates
We propose and analyze a self-adaptive version of the $(1,\lambda)$ evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis on th…
Precise Runtime Analysis for Plateau Functions
To gain a better theoretical understanding of how evolutionary algorithms (EAs) cope with plateaus of constant fitness, we propose the $n$-dimensional Plateau$_k$ function as natural benchmark and analyze how different v…
Evolutionary AlgorithmsEvolutionary Algorithms with Self-adjusting Asymmetric Mutation
Evolutionary Algorithms (EAs) and other randomized search heuristics are often considered as unbiased algorithms that are invariant with respect to different transformations of the underlying search space. However, if a …
Evolutionary AlgorithmsA First Step Towards Runtime Analysis of Evolutionary Neural Architecture Search
Evolutionary neural architecture search (ENAS) employs evolutionary algorithms to find high-performing neural architectures automatically, and has achieved great success. However, compared to the empirical success, its r…
Binary ClassificationEvolutionary AlgorithmsNeural Architecture Search