Evolution is Still Good: Theoretical Analysis of Evolutionary Algorithms on General Cover Problems

• URL: http://arxiv.org/abs/2210.00672v1
• Date: Mon, 3 Oct 2022 01:25:53 GMT
• Title: Evolution is Still Good: Theoretical Analysis of Evolutionary Algorithms on General Cover Problems
• Authors: Yaoyao Zhang, Chaojie Zhu, Shaojie Tang, Ringli Ran, Ding-Zhu Du, Zhao Zhang
• Abstract summary: Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. We identify such a relation by proposing a unified analysis framework for a generalized simple multi-objective evolutionary algorithm.
• Score: 16.98107289469868
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. In this paper, we identify such a relation by proposing a unified analysis framework for a generalized simple multi-objective evolutionary algorithm (GSEMO), and apply it on a minimum weight general cover problem. For a wide range of problems (including the the minimum submodular cover problem in which the submodular function is real-valued, and the minimum connected dominating set problem for which the potential function is non-submodular), GSEMO yields asymptotically tight approximation ratios in expected polynomial time.

Related papers

• A Generalized Evolutionary Metaheuristic (GEM) Algorithm for Engineering Optimization [1.6589012298747952]
  A major trend in recent years is the use of nature-inspired metaheustic algorithms (NIMA) There are over 540 algorithms in the literature, and there is no unified framework to understand the search mechanisms of different algorithms. We propose a generalized evolutionary metaheuristic algorithm to unify more than 20 different algorithms.
  arXiv  Detail & Related papers  (2024-07-02T09:55:15Z)
• Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm [80.94861441583275]
  We investigate the complexity of the generalization bound of the decentralized gradient descent (D-SGDA) algorithm. Our results analyze the impact of different top factors on the generalization of D-SGDA. We also balance it with the generalization to obtain the optimal convex-concave setting.
  arXiv  Detail & Related papers  (2023-10-31T11:27:01Z)
• Runtime Analysis of Competitive co-Evolutionary Algorithms for Maximin Optimisation of a Bilinear Function [1.3053649021965603]
  Co-evolutionary algorithms have a wide range of applications, such as in hardware design, evolution of strategies for board games, and patching software bugs. It is an open challenge to develop a theory that can predict when co-evolutionary algorithms find solutions efficiently and reliable. This paper provides a first step in developing runtime analysis for population-based competitive co-evolutionary algorithms.
  arXiv  Detail & Related papers  (2022-06-30T12:35:36Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  We propose a family of Riemannian algorithms generalizing and extending the seminal approximation framework of Robbins and Monro. Compared to their Euclidean counterparts, Riemannian algorithms are much less understood due to lack of a global linear structure on the manifold. We provide a general template of almost sure convergence results that mirrors and extends the existing theory for Euclidean Robbins-Monro schemes.
  arXiv  Detail & Related papers  (2022-06-14T12:30:11Z)
• Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory [61.12008553173672]
  We address the minimization problem of the Bregman divergence between an exponential subfamily and a mixture subfamily in a Bregman divergence system. We apply this algorithm to rate distortion and its variants including the quantum setting.
  arXiv  Detail & Related papers  (2022-01-07T13:33:28Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA) We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$. When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
  arXiv  Detail & Related papers  (2021-10-18T14:00:22Z)
• Evolving Evolutionary Algorithms with Patterns [0.0]
  The model is based on the Multi Expression Programming (MEP) technique. Several evolutionary algorithms for function optimization are evolved by using the considered model.
  arXiv  Detail & Related papers  (2021-10-10T16:26:20Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms [16.691265882753346]
  A simple evolutionary algorithm called GSEMO has been shown to achieve good approximation for submodular functions efficiently. We extend theoretical results to partition matroid constraints which generalize cardinality constraints.
  arXiv  Detail & Related papers  (2020-06-23T05:37:29Z)
• Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem [0.0]
  This paper characterizes and discusses devolutionary genetic algorithms and evaluates their performances in solving the minimum labeling Steiner tree (MLST) problem. We define devolutionary algorithms as the process of reaching a feasible solution by devolving a population of super-optimal unfeasible solutions over time. We show how classical evolutionary concepts, such as crossing, mutation and fitness can be adapted to aim at reaching an optimal or close-to-optimal solution.
  arXiv  Detail & Related papers  (2020-04-18T13:27:28Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  Adaptivity is an important yet under-studied property in modern optimization theory. Our algorithm is proved to achieve the best-available convergence for non-PL objectives simultaneously while outperforming existing algorithms for PL objectives.
  arXiv  Detail & Related papers  (2020-02-13T05:42:27Z)

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.