On Non-Elitist Evolutionary Algorithms Optimizing Fitness Functions with a Plateau

• URL: http://arxiv.org/abs/2004.09491v1
• Date: Sat, 18 Apr 2020 03:20:14 GMT
• Title: On Non-Elitist Evolutionary Algorithms Optimizing Fitness Functions with a Plateau
• Authors: Anton V. Eremeev
• Abstract summary: We consider the expected runtime of non-elitist evolutionary algorithms (EAs) We show that the EA with fitness selection is inefficient if the bitwise mutation is used with the standard settings of mutation probability.
• Score: 2.28438857884398
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 global optimum. On one hand, using the level-based theorems, we obtain polynomial upper bounds on the expected runtime for some modes of non-elitist EA based on unbiased mutation and the bitwise mutation in particular. On the other hand, we show that the EA with fitness proportionate selection is inefficient if the bitwise mutation is used with the standard settings of mutation probability.

Related papers

• Covariance-Adaptive Sequential Black-box Optimization for Diffusion Targeted Generation [60.41803046775034]
  We show how to perform user-preferred targeted generation via diffusion models with only black-box target scores of users. Experiments on both numerical test problems and target-guided 3D-molecule generation tasks show the superior performance of our method in achieving better target scores.
  arXiv  Detail & Related papers  (2024-06-02T17:26: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)
• 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)
• Effective Mutation Rate Adaptation through Group Elite Selection [50.88204196504888]
  This paper introduces the Group Elite Selection of Mutation Rates (GESMR) algorithm. GESMR co-evolves a population of solutions and a population of MRs, such that each MR is assigned to a group of solutions. With the same number of function evaluations and with almost no overhead, GESMR converges faster and to better solutions than previous approaches.
  arXiv  Detail & Related papers  (2022-04-11T01:08:26Z)
• Evolving Evolutionary Algorithms using Multi Expression Programming [0.0]
  Instead of evolving only the parameters of the algorithm we will evolve an entire EA capable of solving a particular problem. An nongenerational EA for function optimization is evolved in this paper. Numerical experiments show the effectiveness of this approach.
  arXiv  Detail & Related papers  (2021-08-22T09:30:57Z)
• Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms [13.026567958569965]
  We study evolutionary diversity optimization for the knapsack problem (KP) Our goal is to evolve a population of solutions that all have a profit of at least $(mu+1)$-EA with initial approximate solutions calculated by a well-known FPTAS for the KP.
  arXiv  Detail & Related papers  (2021-04-27T12:26:18Z)
• 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)
• The Variational Method of Moments [65.91730154730905]
  conditional moment problem is a powerful formulation for describing structural causal parameters in terms of observables. Motivated by a variational minimax reformulation of OWGMM, we define a very general class of estimators for the conditional moment problem. We provide algorithms for valid statistical inference based on the same kind of variational reformulations.
  arXiv  Detail & Related papers  (2020-12-17T07:21:06Z)
• AdaLead: A simple and robust adaptive greedy search algorithm for sequence design [55.41644538483948]
  We develop an easy-to-directed, scalable, and robust evolutionary greedy algorithm (AdaLead) AdaLead is a remarkably strong benchmark that out-competes more complex state of the art approaches in a variety of biologically motivated sequence design challenges.
  arXiv  Detail & Related papers  (2020-10-05T16:40:38Z)
• 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)
• 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)

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.