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.<n>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: http://creativecommons.org/publicdomain/zero/1.0/
• 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

• A Preprocessing Framework for Efficient Approximate Bi-Objective Shortest-Path Computation in the Presence of Correlated Objectives [21.108406629056173]
  We consider the bi-objective shortest-path (BOSP) problem in the presence of correlated objectives.<n>BOSP is generally computationally challenging as the size of the search space is exponential in the number of objective functions and the graph size.<n>We propose an efficient algorithm that reduces the search effort in the presence of correlated objectives.
  arXiv  Detail & Related papers  (2025-05-28T11:26:14Z)
• Multi-granularity Interest Retrieval and Refinement Network for Long-Term User Behavior Modeling in CTR Prediction [68.90783662117936]
  Click-through Rate (CTR) prediction is crucial for online personalization platforms.<n>Recent advancements have shown that modeling rich user behaviors can significantly improve the performance of CTR prediction.<n>We propose Multi-granularity Interest Retrieval and Refinement Network (MIRRN)
  arXiv  Detail & Related papers  (2024-11-22T15:29:05Z)
• Interpetable Target-Feature Aggregation for Multi-Task Learning based on Bias-Variance Analysis [53.38518232934096]
  Multi-task learning (MTL) is a powerful machine learning paradigm designed to leverage shared knowledge across tasks to improve generalization and performance. We propose an MTL approach at the intersection between task clustering and feature transformation based on a two-phase iterative aggregation of targets and features. In both phases, a key aspect is to preserve the interpretability of the reduced targets and features through the aggregation with the mean, which is motivated by applications to Earth science.
  arXiv  Detail & Related papers  (2024-06-12T08:30:16Z)
• 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)
• Real-Time Image Segmentation via Hybrid Convolutional-Transformer Architecture Search [51.89707241449435]
  In this paper, we address the challenge of integrating multi-head self-attention into high-resolution representation CNNs efficiently. We develop a multi-target multi-branch supernet method, which fully utilizes the advantages of high-resolution features. We present a series of models via the Hybrid Convolutional-Transformer Architecture Search (HyCTAS) method that searches for the best hybrid combination of light-weight convolution layers and memory-efficient self-attention layers.
  arXiv  Detail & Related papers  (2024-03-15T15:47:54Z)
• 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)
• BOtied: Multi-objective Bayesian optimization with tied multivariate ranks [33.414682601242006]
  In this paper, we show a natural connection between non-dominated solutions and the extreme quantile of the joint cumulative distribution function. Motivated by this link, we propose the Pareto-compliant CDF indicator and the associated acquisition function, BOtied. Our experiments on a variety of synthetic and real-world problems demonstrate that BOtied outperforms state-of-the-art MOBO acquisition functions.
  arXiv  Detail & Related papers  (2023-06-01T04:50:06Z)
• 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)
• 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)
• A New Lagrangian Problem Crossover: A Systematic Review and Meta-Analysis of Crossover Standerds [1.1802674324027231]
  This paper presents an overview of crossover standards classification. The significance of novel standard crossover is proposed depending on Lagrangian Dual Function (LDF) The accuracy and performance of the proposed standard have evaluated by three unimodal test functions.
  arXiv  Detail & Related papers  (2022-04-21T15:50:02Z)
• 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)
• Multi-task Supervised Learning via Cross-learning [102.64082402388192]
  We consider a problem known as multi-task learning, consisting of fitting a set of regression functions intended for solving different tasks. In our novel formulation, we couple the parameters of these functions, so that they learn in their task specific domains while staying close to each other. This facilitates cross-fertilization in which data collected across different domains help improving the learning performance at each other task.
  arXiv  Detail & Related papers  (2020-10-24T21:35:57Z)
• 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)
• Benchmarking a $(\mu+\lambda)$ Genetic Algorithm with Configurable Crossover Probability [4.33419118449588]
  We investigate a family of $(mu+lambda)$ Genetic Algorithms (GAs) which creates offspring either from mutation or by recombining two randomly chosen parents. By scaling the crossover probability, we can thus interpolate from a fully mutation-only algorithm towards a fully crossover-based GA.
  arXiv  Detail & Related papers  (2020-06-10T15:22:44Z)

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.