Runtime Analysis of Evolutionary Algorithms for Multiparty Multiobjective Optimization

• URL: http://arxiv.org/abs/2501.16336v1
• Date: Thu, 09 Jan 2025 13:16:08 GMT
• Title: Runtime Analysis of Evolutionary Algorithms for Multiparty Multiobjective Optimization
• Authors: Yuetong Sun, Peilan Xu, Wenjian Luo,
• Abstract summary: This paper presents the first theoretical analysis of the expected runtime of evolutionary algorithms on bi-party multi-objective optimization problems (BPMOPs) Our findings demonstrate that employing traditional multi-objective optimization algorithms to solve MPMOPs is both time-consuming and inefficient. We propose co-evolutionary multi-party multi-objectives (CoEMPMO) for pseudo-Boolean optimization and shortest path problems within a multi-party multi-objective context.
• Score: 0.8520624117635325
• License:
• Abstract: In scenarios where multiple decision-makers operate within a common decision space, each focusing on their own multi-objective optimization problem (e.g., bargaining games), the problem can be modeled as a multi-party multi-objective optimization problem (MPMOP). While numerous evolutionary algorithms have been proposed to solve MPMOPs, most results remain empirical. This paper presents the first theoretical analysis of the expected runtime of evolutionary algorithms on bi-party multi-objective optimization problems (BPMOPs). Our findings demonstrate that employing traditional multi-objective optimization algorithms to solve MPMOPs is both time-consuming and inefficient, as the resulting population contains many solutions that fail to achieve consensus among decision-makers. An alternative approach involves decision-makers individually solving their respective optimization problems and seeking consensus only in the final stage. While feasible for pseudo-Boolean optimization problems, this method may fail to guarantee approximate performance for one party in NP-hard problems. Finally, We propose coevolutionary multi-party multi-objective optimizers (CoEMPMO) for pseudo-Boolean optimization and shortest path problems within a multi-party multi-objective context, which maintains a common solution set among all parties through coevolution. Theoretical and experimental results demonstrate that the proposed \( \text{CoEMPMO}_{\text{random}} \) outperforms previous algorithms in terms of the expected lower bound on runtime for pseudo-Boolean optimization problems. Additionally, \( \text{CoEMPMO}_{\text{cons}}^{\text{SP}} \) achieves better efficiency and precision in solving shortest path problems compared to existing algorithms.

Related papers

• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications. We propose learning to predict emphmultiple diverse initial solutions given parameters that define the problem instance. We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required.
  arXiv  Detail & Related papers  (2024-11-04T15:17:19Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Combining Kernelized Autoencoding and Centroid Prediction for Dynamic Multi-objective Optimization [3.431120541553662]
  This paper proposes a unified paradigm, which combines the kernelized autoncoding evolutionary search and the centriod-based prediction. The proposed method is compared with five state-of-the-art algorithms on a number of complex benchmark problems.
  arXiv  Detail & Related papers  (2023-12-02T00:24:22Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Socio-cognitive Optimization of Time-delay Control Problems using Evolutionary Metaheuristics [89.24951036534168]
  Metaheuristics are universal optimization algorithms which should be used for solving difficult problems, unsolvable by classic approaches. In this paper we aim at constructing novel socio-cognitive metaheuristic based on castes, and apply several versions of this algorithm to optimization of time-delay system model.
  arXiv  Detail & Related papers  (2022-10-23T22:21:10Z)
• Enhanced Opposition Differential Evolution Algorithm for Multimodal Optimization [0.2538209532048866]
  Most of the real-world problems are multimodal in nature that consists of multiple optimum values. Classical gradient-based methods fail for optimization problems in which the objective functions are either discontinuous or non-differentiable. We have proposed an algorithm known as Enhanced Opposition Differential Evolution (EODE) algorithm to solve the MMOPs.
  arXiv  Detail & Related papers  (2022-08-23T16:18:27Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• A survey on multi-objective hyperparameter optimization algorithms for Machine Learning [62.997667081978825]
  This article presents a systematic survey of the literature published between 2014 and 2020 on multi-objective HPO algorithms. We distinguish between metaheuristic-based algorithms, metamodel-based algorithms, and approaches using a mixture of both. We also discuss the quality metrics used to compare multi-objective HPO procedures and present future research directions.
  arXiv  Detail & Related papers  (2021-11-23T10:22:30Z)
• A novel multiobjective evolutionary algorithm based on decomposition and multi-reference points strategy [14.102326122777475]
  Multiobjective evolutionary algorithm based on decomposition (MOEA/D) has been regarded as a significantly promising approach for solving multiobjective optimization problems (MOPs) We propose an improved MOEA/D algorithm by virtue of the well-known Pascoletti-Serafini scalarization method and a new strategy of multi-reference points.
  arXiv  Detail & Related papers  (2021-10-27T02:07:08Z)
• Batched Data-Driven Evolutionary Multi-Objective Optimization Based on Manifold Interpolation [6.560512252982714]
  We propose a framework for implementing batched data-driven evolutionary multi-objective optimization. It is so general that any off-the-shelf evolutionary multi-objective optimization algorithms can be applied in a plug-in manner. Our proposed framework is featured with a faster convergence and a stronger resilience to various PF shapes.
  arXiv  Detail & Related papers  (2021-09-12T23:54:26Z)
• A Decomposition-based Large-scale Multi-modal Multi-objective Optimization Algorithm [9.584279193016522]
  We propose an efficient multi-modal multi-objective optimization algorithm based on the widely used MOEA/D algorithm. Experimental results show that our proposed algorithm can effectively preserve the diversity of solutions in the decision space.
  arXiv  Detail & Related papers  (2020-04-21T09:18:54Z)

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.