EUVIMEDEUVIMED entdecken
Crossref

Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multiobjective Algorithms

Aneta Neumann iD, Frank Neumann iD

Evolutionary Computation · 2025

DOI: 10.1162/evco_a_00360 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Evolutionary Computation, 2025. Verfasst von Aneta Neumann und 1 weiteren Autor:innen. Beteiligte Einrichtung: Optimisation and Logistics, The University of Adelaide, Adelaide, Australia aneta.neumann@adelaide.edu.au. Hauptthemen laut MEDLINE: Algorithms, Biological Evolution. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 100 Literaturangaben.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Many real-world optimization problems can be stated in terms of submodular functions. Furthermore, these real-world problems often involve uncertainties which may lead to the violation of given constraints. A lot of evolutionary multiobjective algorithms following the Pareto optimization approach have recently been analyzed and applied to submodular problems with different types of constraints. We present a first runtime analysis of evolutionary multiobjective algorithms based on Pareto optimization for chance-constrained submodular functions. Here the constraint involves stochastic components and the constraint can only be violated with a small probability of α. We investigate the classical GSEMO algorithm for two different bi-objective formulations using tail bounds to determine the feasibility of solutions. We show that the algorithm GSEMO obtains the same worst case performance guarantees for monotone submodular functions as recently analyzed greedy algorithms for the case of uniform IID weights and uniformly distributed weights with the same dispersion when using the appropriate bi-objective formulation. As part of our investigations, we also point out situations where the use of tail bounds in the first bi-objective formulation can prevent GSEMO from obtaining good solutions in the case of uniformly distributed weights with the same dispersion if the objective function is submodular but non-monotone due to a single element impacting monotonicity. Furthermore, we investigate the behavior of the evolutionary multiobjective algorithms GSEMO, NSGA-II, and SPEA2 on different submodular chance-constrained network problems. Our experimental results show that the use of evolutionary multiobjective algorithms leads to significant performance improvements compared to state-of-the-art greedy algorithms for submodular optimization.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsBiological EvolutionComputer SimulationProbability

Stichwörter der Autor:innen

Chance constraintsevolutionary multiobjective agorithmssubmodular functions.

Autor:innen und Institutionen

  • Optimisation and Logistics, The University of Adelaide, Adelaide, Australia aneta.neumann@adelaide.edu.au.
  • Optimisation and Logistics, The University of Adelaide, Adelaide, Australia frank.neumann@adelaide.edu.au.

ORCID-Profile: Aneta Neumann, Frank Neumann

Zitieren

APA

Neumann, A., & Neumann, F. (2025). Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multiobjective Algorithms. Evolutionary Computation. https://doi.org/10.1162/evco_a_00360

Vancouver

Neumann A, Neumann F. Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multiobjective Algorithms. Evolutionary Computation. 2025. doi:10.1162/evco_a_00360

BibTeX
@article{Neumann2025,
  author = {Neumann, Aneta and Neumann, Frank},
  title = {Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multiobjective Algorithms},
  journal = {Evolutionary Computation},
  year = {2025},
  doi = {10.1162/evco_a_00360}
}
Kostenlos starten →