Analyzing the Runtime of the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) on the Concatenated Trap Function

• URL: http://arxiv.org/abs/2407.08335v1
• Date: Thu, 11 Jul 2024 09:37:21 GMT
• Title: Analyzing the Runtime of the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) on the Concatenated Trap Function
• Authors: Yukai Qiao, Marcus Gallagher,
• Abstract summary: GOMEA is an evolutionary algorithm that leverages linkage learning to efficiently exploit problem structure. We show that GOMEA can solve the problem in $O(m32k)$ with high probability, where $m$ is the number of subfunctions and $k$ is the subfunction length. This is a significant speedup compared to the (1+1) Evolutionary EA, which requires $O(ln(m)(mk)k)$ expected evaluations.
• Score: 2.038038953957366
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) is a state of the art evolutionary algorithm that leverages linkage learning to efficiently exploit problem structure. By identifying and preserving important building blocks during variation, GOMEA has shown promising performance on various optimization problems. In this paper, we provide the first runtime analysis of GOMEA on the concatenated trap function, a challenging benchmark problem that consists of multiple deceptive subfunctions. We derived an upper bound on the expected runtime of GOMEA with a truthful linkage model, showing that it can solve the problem in $O(m^{3}2^k)$ with high probability, where $m$ is the number of subfunctions and $k$ is the subfunction length. This is a significant speedup compared to the (1+1) EA, which requires $O(ln{(m)}(mk)^{k})$ expected evaluations.

Related papers

• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization. We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution. Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Multiple-gain Estimation for Running Time of Evolutionary Combinatorial Optimization [12.810490884742784]
  This paper proposes a multiple-gain model to estimate the fitness trend of population during iterations. The proposed model is an improved version of the average gain model, which is the approach to estimate the running time of evolutionary algorithms for numerical optimization.
  arXiv  Detail & Related papers  (2025-01-13T01:24:36Z)
• Benchmarking of GPU-optimized Quantum-Inspired Evolutionary Optimization Algorithm using Functional Analysis [0.0]
  This article presents a comparative analysis of GPU-parallelized implementations of evolutionary optimization (QIEO) The results demonstrate that QIEO performs better for these functions than GA.
  arXiv  Detail & Related papers  (2024-12-12T06:47:23Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  We propose two variance reduced ZO estimators for complex gradient problems. We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
  arXiv  Detail & Related papers  (2024-10-03T15:04:01Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  We study the power of query access for the task of agnostic learning under the Gaussian distribution. We show that query access gives significant runtime improvements over random examples for agnostically learning MIMs.
  arXiv  Detail & Related papers  (2023-12-27T15:50:47Z)
• The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem [6.793248433673384]
  The Non-dominated Sorting Genetic Algorithm-II (NSGA-II) is one of the most prominent algorithms to solve multi-objective optimization problems. We give the first proven performance guarantees for a classic optimization problem, the NP-complete bi-objective minimum spanning tree problem.
  arXiv  Detail & Related papers  (2023-05-22T19:59:19Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• Focused Jump-and-Repair Constraint Handling for Fixed-Parameter Tractable Graph Problems Closed Under Induced Subgraphs [3.495114525631289]
  We investigate a (1+1)EA equipped with a tailored jump-and-repair operation that can be used to probabilistically repair infeasible offspring in graph problems.
  arXiv  Detail & Related papers  (2022-03-25T19:36:02Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Analysis of Evolutionary Algorithms on Fitness Function with Time-linkage Property [27.660240128423176]
  In real-world applications, many optimization problems have the time-linkage property, that is, the objective function value relies on the current solution as well as the historical solutions. This paper takes the first step to rigorously analyze evolutionary algorithms for time-linkage functions.
  arXiv  Detail & Related papers  (2020-04-26T07:56:40Z)
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity [109.54166127479093]
  Zeroth-order (a.k.a, derivative-free) methods are a class of effective optimization methods for solving machine learning problems. In this paper, we propose a class faster faster zerothorder alternating gradient method multipliers (MMADMM) to solve the non finitesum problems. We show that ZOMMAD methods can achieve a lower function $O(frac13nfrac1)$ for finding an $epsilon$-stationary point. At the same time, we propose a class faster zerothorder online ADM methods (M
  arXiv  Detail & Related papers  (2019-07-30T02:21:43Z)

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.