Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark

• URL: http://arxiv.org/abs/2501.16250v1
• Date: Mon, 27 Jan 2025 17:51:51 GMT
• Title: Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark
• Authors: Marcel Chwiałkowski, Benjamin Doerr, Martin S. Krejca,
• Abstract summary: We conduct a formal runtime analysis of the cGA on LeadingOnes. For the cGA's single parameter -- called the hypothetical population size -- at least polylogarithmically larger than the problem size, we prove that the cGA samples the optimum of LeadingOnes.
• Score: 9.044970217182117
• License:
• Abstract: The compact genetic algorithm (cGA) is one of the simplest estimation-of-distribution algorithms (EDAs). Next to the univariate marginal distribution algorithm (UMDA) -- another simple EDA -- , the cGA has been subject to extensive mathematical runtime analyses, often showcasing a similar or even superior performance to competing approaches. Surprisingly though, up to date and in contrast to the UMDA and many other heuristics, we lack a rigorous runtime analysis of the cGA on the LeadingOnes benchmark -- one of the most studied theory benchmarks in the domain of evolutionary computation. We fill this gap in the literature by conducting a formal runtime analysis of the cGA on LeadingOnes. For the cGA's single parameter -- called the hypothetical population size -- at least polylogarithmically larger than the problem size, we prove that the cGA samples the optimum of LeadingOnes with high probability within a number of function evaluations quasi-linear in the problem size and linear in the hypothetical population size. For the best hypothetical population size, our result matches, up to polylogarithmic factors, the typical quadratic runtime that many randomized search heuristics exhibit on LeadingOnes. Our analysis exhibits some noteworthy differences in the working principles of the two algorithms which were not visible in previous works.

Related papers

• A Runtime Analysis of the Multi-Valued Compact Genetic Algorithm on Generalized LeadingOnes [2.07180164747172]
  We analyze the runtime analysis of the multi-valued cGA on the r-valued LeadingOnes function. We show that the runtime of the r-cGA on r-LeadingOnes is O(n2r2 log3 n log2 r) with high probability.
  arXiv  Detail & Related papers  (2025-01-16T12:59:07Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC. It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters. GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Generalized OneMax [2.07180164747172]
  We provide a first runtime analysis of a generalized OneMax function. We show that the r-cGA solves this r-valued OneMax problem efficiently. At the end of experiments, we state one conjecture related to the expected runtime of another variant of multi-valued OneMax function.
  arXiv  Detail & Related papers  (2024-04-17T10:40:12Z)
• AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
  We show that by efficiently parallelizing existing causal discovery methods, we can scale them to thousands of dimensions. Specifically, we focus on the causal ordering subprocedure in DirectLiNGAM and implement GPU kernels to accelerate it. This allows us to apply DirectLiNGAM to causal inference on large-scale gene expression data with genetic interventions yielding competitive results.
  arXiv  Detail & Related papers  (2024-03-06T15:06:11Z)
• An Application of a Multivariate Estimation of Distribution Algorithm to Cancer Chemotherapy [59.40521061783166]
  Chemotherapy treatment for cancer is a complex optimisation problem with a large number of interacting variables and constraints. We show that the more sophisticated algorithm would yield better performance on a complex problem like this. We hypothesise that this is caused by the more sophisticated algorithm being impeded by the large number of interactions in the problem.
  arXiv  Detail & Related papers  (2022-05-17T15:28:46Z)
• Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) [16.904475483445452]
  We show that runtime analyses are feasible also for the NSGA-II. We prove that with a population size four times larger than the size of the Pareto front, the NSGA-II satisfies the same runtime guarantees as the SEMO and GSEMO algorithms.
  arXiv  Detail & Related papers  (2021-12-16T03:00: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)
• Quantum Algorithms for Data Representation and Analysis [68.754953879193]
  We provide quantum procedures that speed-up the solution of eigenproblems for data representation in machine learning. The power and practical use of these subroutines is shown through new quantum algorithms, sublinear in the input matrix's size, for principal component analysis, correspondence analysis, and latent semantic analysis. Results show that the run-time parameters that do not depend on the input's size are reasonable and that the error on the computed model is small, allowing for competitive classification performances.
  arXiv  Detail & Related papers  (2021-04-19T00:41:43Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics. Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis. We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
  arXiv  Detail & Related papers  (2020-06-23T04:25:36Z)
• From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm [15.56430085052365]
  In the regime with no genetic drift, the runtime is roughly proportional to the population size. We propose a parameter-less version of the compact genetic algorithm that automatically finds a suitable population size.
  arXiv  Detail & Related papers  (2020-04-15T15:12:01Z)
• A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes [9.853329403413701]
  We prove a stronger run time guarantee for the univariate distribution algorithm (UMDA) We show further run time gains from small selection rates. Under similar assumptions, we prove that a bound that matches our upper bound up to constant factors holds with high probability.
  arXiv  Detail & Related papers  (2020-04-10T10:20:05Z)

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.