Sliding Window Bi-Objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone Submodular Functions

• URL: http://arxiv.org/abs/2407.09731v2
• Date: Wed, 7 Aug 2024 05:13:09 GMT
• Title: Sliding Window Bi-Objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone Submodular Functions
• Authors: Xiankun Yan, Aneta Neumann, Frank Neumann,
• Abstract summary: In this paper, we apply the sliding-selection approach introduced in [21] to the optimization of chance-constrained monotone submodular functions. We show that the SW-GSEMO algorithm successfully limits the population size as a key factor that impacts the runtime.
• Score: 10.506038775815094
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Variants of the GSEMO algorithm using multi-objective formulations have been successfully analyzed and applied to optimize chance-constrained submodular functions. However, due to the effect of the increasing population size of the GSEMO algorithm considered in these studies from the algorithms, the approach becomes ineffective if the number of trade-offs obtained grows quickly during the optimization run. In this paper, we apply the sliding-selection approach introduced in [21] to the optimization of chance-constrained monotone submodular functions. We theoretically analyze the resulting SW-GSEMO algorithm which successfully limits the population size as a key factor that impacts the runtime and show that this allows it to obtain better runtime guarantees than the best ones currently known for the GSEMO. In our experimental study, we compare the performance of the SW-GSEMO to the GSEMO and NSGA-II on the maximum coverage problem under the chance constraint and show that the SW-GSEMO outperforms the other two approaches in most cases. In order to get additional insights into the optimization behavior of SW-GSEMO, we visualize the selection behavior of SW-GSEMO during its optimization process and show it beats other algorithms to obtain the highest quality of solution in variable instances.

Related papers

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  gradient-based algorithms are widely used in bilevel optimization. We introduce a without-replacement sampling based algorithm which achieves a faster convergence rate. We validate our algorithms over both synthetic and real-world applications.
  arXiv  Detail & Related papers  (2024-11-07T17:05:31Z)
• Sampling-based Pareto Optimization for Chance-constrained Monotone Submodular Problems [10.506038775815094]
  In this paper, a sampling-based method is proposed to directly evaluate the chance constraint. To address the problems with more challenging settings, an enhanced GSEMO algorithm is introduced. The ASW-GSEMO with the sampling-based evaluation approach outperforms other algorithms.
  arXiv  Detail & Related papers  (2024-04-18T05:15:20Z)
• Evolutionary Solution Adaption for Multi-Objective Metal Cutting Process Optimization [59.45414406974091]
  We introduce a framework for system flexibility that allows us to study the ability of an algorithm to transfer solutions from previous optimization tasks. We study the flexibility of NSGA-II, which we extend by two variants: 1) varying goals, that optimize solutions for two tasks simultaneously to obtain in-between source solutions expected to be more adaptable, and 2) active-inactive genotype, that accommodates different possibilities that can be activated or deactivated. Results show that adaption with standard NSGA-II greatly reduces the number of evaluations required for optimization to a target goal, while the proposed variants further improve the adaption costs.
  arXiv  Detail & Related papers  (2023-05-31T12:07:50Z)
• Towards Self-adaptive Mutation in Evolutionary Multi-Objective Algorithms [10.609857097723266]
  We study how self-adaptation influences multi-objective evolutionary algorithms. We show that adapting the mutation rate based on single-objective optimization and hypervolume can speed up the convergence of GSEMO. We propose a GSEMO with self-adaptive mutation, which considers optimizing for single objectives and adjusts the mutation rate for each solution individually.
  arXiv  Detail & Related papers  (2023-03-08T14:26:46Z)
• An Empirical Evaluation of Zeroth-Order Optimization Methods on AI-driven Molecule Optimization [78.36413169647408]
  We study the effectiveness of various ZO optimization methods for optimizing molecular objectives. We show the advantages of ZO sign-based gradient descent (ZO-signGD) We demonstrate the potential effectiveness of ZO optimization methods on widely used benchmark tasks from the Guacamol suite.
  arXiv  Detail & Related papers  (2022-10-27T01:58:10Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA) We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$. When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
  arXiv  Detail & Related papers  (2021-10-18T14:00:22Z)
• EOS: a Parallel, Self-Adaptive, Multi-Population Evolutionary Algorithm for Constrained Global Optimization [68.8204255655161]
  EOS is a global optimization algorithm for constrained and unconstrained problems of real-valued variables. It implements a number of improvements to the well-known Differential Evolution (DE) algorithm. Results prove that EOSis capable of achieving increased performance compared to state-of-the-art single-population self-adaptive DE algorithms.
  arXiv  Detail & Related papers  (2020-07-09T10:19:22Z)
• Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms [16.691265882753346]
  A simple evolutionary algorithm called GSEMO has been shown to achieve good approximation for submodular functions efficiently. We extend theoretical results to partition matroid constraints which generalize cardinality constraints.
  arXiv  Detail & Related papers  (2020-06-23T05:37:29Z)
• Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms [11.807734722701786]
  Here the constraint involves components and the constraint can only be violated with a small probability of alpha. We show that the algorithm GSEMO obtains the same worst case performance guarantees for monotone submodular functions. Our experimental results show that the use of evolutionary multi-objective algorithms leads to significant performance improvements.
  arXiv  Detail & Related papers  (2020-06-20T00:17:44Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  Adaptivity is an important yet under-studied property in modern optimization theory. Our algorithm is proved to achieve the best-available convergence for non-PL objectives simultaneously while outperforming existing algorithms for PL objectives.
  arXiv  Detail & Related papers  (2020-02-13T05:42:27Z)

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.