A Many Objective Problem Where Crossover is Provably Indispensable

• URL: http://arxiv.org/abs/2412.18375v1
• Date: Tue, 24 Dec 2024 12:00:37 GMT
• Title: A Many Objective Problem Where Crossover is Provably Indispensable
• Authors: Andre Opris,
• Abstract summary: This paper addresses theory in evolutionary multi-objective optimisation (EMO) and focuses on the role of crossover operators in many-objective optimisation. We present a many-objective problem class together with a theoretical analysis of the widely used NSGA-III to demonstrate that crossover can yield an exponential speedup on the runtime.
• Score: 1.223779595809275
• License:
• Abstract: This paper addresses theory in evolutionary multiobjective optimisation (EMO) and focuses on the role of crossover operators in many-objective optimisation. The advantages of using crossover are hardly understood and rigorous runtime analyses with crossover are lagging far behind its use in practice, specifically in the case of more than two objectives. We present a many-objective problem class together with a theoretical runtime analysis of the widely used NSGA-III to demonstrate that crossover can yield an exponential speedup on the runtime. In particular, this algorithm can find the Pareto set in expected polynomial time when using crossover while without crossover it requires exponential time to even find a single Pareto-optimal point. To our knowledge, this is the first rigorous runtime analysis in many-objective optimisation demonstrating an exponential performance gap when using crossover for more than two objectives.

Related papers

• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours. We focus on the case of linear utility functions parameterised by weight vectors w. We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• 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)
• CrossGET: Cross-Guided Ensemble of Tokens for Accelerating Vision-Language Transformers [53.224004166460254]
  This paper introduces Cross-Guided Ensemble of Tokens (CrossGET), a general acceleration framework for vision-language Transformers. CrossGET adaptively combines tokens in real-time during inference, significantly reducing computational costs. Experiments have been conducted on various vision-language tasks, such as image-text retrieval, visual reasoning, image captioning, and visual question answering.
  arXiv  Detail & Related papers  (2023-05-27T12:07:21Z)
• Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation [4.212663349859165]
  We provide a theoretical analysis of the well-known EMO algorithms GSEMO and NSGA-II. We show that immune-inspired hypermutations cannot avoid exponential optimisation times.
  arXiv  Detail & Related papers  (2023-01-31T15:03:34Z)
• Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives [16.904475483445452]
  The NSGA-II is one of the most prominent algorithms to solve multi-objective optimization problems. We show that the NSGA-II is less effective for larger numbers of objectives.
  arXiv  Detail & Related papers  (2022-11-23T16:15:26Z)
• Predicting the State of Synchronization of Financial Time Series using Cross Recurrence Plots [75.20174445166997]
  This study introduces a new method for predicting the future state of synchronization of the dynamics of two financial time series. We adopt a deep learning framework for methodologically addressing the prediction of the synchronization state. We find that the task of predicting the state of synchronization of two time series is in general rather difficult, but for certain pairs of stocks attainable with very satisfactory performance.
  arXiv  Detail & Related papers  (2022-10-26T10:22:28Z)
• Multi-Objective GFlowNets [59.16787189214784]
  We study the problem of generating diverse candidates in the context of Multi-Objective Optimization. In many applications of machine learning such as drug discovery and material design, the goal is to generate candidates which simultaneously optimize a set of potentially conflicting objectives. We propose Multi-Objective GFlowNets (MOGFNs), a novel method for generating diverse optimal solutions, based on GFlowNets.
  arXiv  Detail & Related papers  (2022-10-23T16:15:36Z)
• Pareto Driven Surrogate (ParDen-Sur) Assisted Optimisation of Multi-period Portfolio Backtest Simulations [0.0]
  This study presents the glsParDen-Sur modelling framework to efficiently perform the required hyper- parameter search. glsParDen-Sur extends previous surrogate frameworks by including a reservoir sampling-based look-ahead mechanism for offspring generation in glsplEA alongside the traditional acceptance sampling scheme.
  arXiv  Detail & Related papers  (2022-09-13T07:29:20Z)
• 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)
• An Empirical Study of Assumptions in Bayesian Optimisation [61.19427472792523]
  In this work we rigorously analyse conventional and non-conventional assumptions inherent to Bayesian optimisation. We conclude that the majority of hyper- parameter tuning tasks exhibit heteroscedasticity and non-stationarity. We hope these findings may serve as guiding principles, both for practitioners and for further research in the field.
  arXiv  Detail & Related papers  (2020-12-07T16:21:12Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)

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.