An Archive Can Bring Provable Speed-ups in Multi-Objective Evolutionary Algorithms

• URL: http://arxiv.org/abs/2406.02118v1
• Date: Tue, 4 Jun 2024 08:59:16 GMT
• Title: An Archive Can Bring Provable Speed-ups in Multi-Objective Evolutionary Algorithms
• Authors: Chao Bian, Shengjie Ren, Miqing Li, Chao Qian,
• Abstract summary: We show for the first time, that using an archive can guarantee speed-ups for MOEAs. We prove that for two well-established MOEAs, using an archive brings a acceleration on the expected running time.
• Score: 22.123838452178585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the area of multi-objective evolutionary algorithms (MOEAs), there is a trend of using an archive to store non-dominated solutions generated during the search. This is because 1) MOEAs may easily end up with the final population containing inferior solutions that are dominated by other solutions discarded during the search process and 2) the population that has a commensurable size of the problem's Pareto front is often not practical. In this paper, we theoretically show, for the first time, that using an archive can guarantee speed-ups for MOEAs. Specifically, we prove that for two well-established MOEAs (NSGA-II and SMS-EMOA) on two commonly studied problems (OneMinMax and LeadingOnesTrailingZeroes), using an archive brings a polynomial acceleration on the expected running time. The reason is that with an archive, the size of the population can reduce to a small constant; there is no need for the population to keep all the Pareto optimal solutions found. This contrasts existing theoretical studies for MOEAs where a population with a commensurable size of the problem's Pareto front is needed. The findings in this paper not only provide a theoretical confirmation for an increasingly popular practice in the design of MOEAs, but can also be beneficial to the theory community towards studying more practical MOEAs.

Related papers

• Stochastic Population Update Provably Needs An Archive in Evolutionary Multi-objective Optimization [20.883780207120783]
  We show that using an archive can allow a small population and accelerate the search of SPU-based MOEAs substantially. Specifically, we analyze the expected running time of two well-established MOEAs, SMS-EMOA and NSGA-II for solving a commonly studied bi-objective problem OneJumpZero.
  arXiv  Detail & Related papers  (2025-01-28T06:21:38Z)
• Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs [76.43407125275202]
  o1-like models can emulate human-like long-time thinking during inference. This paper presents the first comprehensive study on the prevalent issue of overthinking in these models. We propose strategies to mitigate overthinking, streamlining reasoning processes without compromising accuracy.
  arXiv  Detail & Related papers  (2024-12-30T18:55:12Z)
• Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem [9.044970217182117]
  NSGA-II is the most prominent multi-objective evolutionary algorithm. We show that the NSGA-II cannot compute the Pareto front in less than exponential time.
  arXiv  Detail & Related papers  (2024-11-15T07:50:40Z)
• Towards Running Time Analysis of Interactive Multi-objective Evolutionary Algorithms [23.815981112784552]
  This paper provides the first running time analysis (the essential theoretical aspect of EAs) for practical iMOEAs. We prove that the expected running time of the well-developed interactive NSGA-II for solving the OneMinMax and OneJumpZeroJump problems is $O(n log n)$ and $O(nk)$, respectively.
  arXiv  Detail & Related papers  (2023-10-12T14:57:47Z)
• Endogenous Macrodynamics in Algorithmic Recourse [52.87956177581998]
  Existing work on Counterfactual Explanations (CE) and Algorithmic Recourse (AR) has largely focused on single individuals in a static environment. We show that many of the existing methodologies can be collectively described by a generalized framework. We then argue that the existing framework does not account for a hidden external cost of recourse, that only reveals itself when studying the endogenous dynamics of recourse at the group level.
  arXiv  Detail & Related papers  (2023-08-16T07:36:58Z)
• Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms [23.248796792928204]
  Population update is a key component in multi-objective Evolutionary algorithms (MOEAs) In this paper, we analytically present that population update can be beneficial for the search of MOEAs. Specifically, we prove that the expected running time of two well-established MOEAs, SMS-EMOA and NSGA-II, for solving two bi-objective problems, OneJumpZero and bi-RoyalRoad, can be exponentially decreased if replacing its deterministic population update mechanism with a randomness one.
  arXiv  Detail & Related papers  (2023-06-05T05:54:56Z)
• MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with Known Pareto Front [71.19090689055054]
  Multi-objective AI planning suffers from a lack of benchmarks exhibiting known Pareto Fronts. We propose a tunable benchmark generator, together with a dedicated solver that provably computes the true Pareto front of the resulting instances. We show how to characterize the optimal plans for a constrained version of the problem, and then show how to reduce the general problem to the constrained one.
  arXiv  Detail & Related papers  (2023-04-28T07:09:23Z)
• Multi-objective Conflict-based Search for Multi-agent Path Finding [10.354181009277623]
  Multi-objective path planners typically compute an ensemble of paths while optimizing a single objective, such as path length. This article presents an approach named Multi-objective Conflict-based Search (MO-CBS) that bypasses this so-called curse of dimensionality.
  arXiv  Detail & Related papers  (2021-01-11T10:42:38Z)
• Geometric Entropic Exploration [52.67987687712534]
  We introduce a new algorithm that maximises the geometry-aware Shannon entropy of state-visits in both discrete and continuous domains. Our key theoretical contribution is casting geometry-aware MSVE exploration as a tractable problem of optimising a simple and novel noise-contrastive objective function. In our experiments, we show the efficiency of GEM in solving several RL problems with sparse rewards, compared against other deep RL exploration approaches.
  arXiv  Detail & Related papers  (2021-01-06T14:15:07Z)
• Theory-Inspired Path-Regularized Differential Network Architecture Search [206.93821077400733]
  We study the impact of skip connections to fast network optimization and its competitive advantage over other types of operations in differential architecture search (DARTS) We propose a theory-inspired path-regularized DARTS that consists of two key modules: (i) a differential group-structured sparse binary gate introduced for each operation to avoid unfair competition among operations, and (ii) a path-depth-wise regularization used to incite search exploration for deep architectures that converge slower than shallow ones.
  arXiv  Detail & Related papers  (2020-06-30T05:28:23Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

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.