EUVIMEDEUVIMED entdecken
Crossref

Runtime Analysis of Single- and Multiobjective Evolutionary Algorithms for Chance-Constrained Optimization Problems with Normally Distributed Random Variables*

Frank Neumann iD, Carsten Witt iD

Evolutionary Computation · 2025

DOI: 10.1162/evco_a_00355 ↗

Kurz gefasst

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

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Chance-constrained optimization problems allow us to model problems where constraints involving stochastic components should be violated only with a small probability. Evolutionary algorithms have been applied to this scenario and shown to achieve high-quality results. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for chance-constrained optimization. We study the scenario of stochastic components that are independent and normally distributed. Considering the simple single-objective (1+1) EA, we show that imposing an additional uniform constraint already leads to local optima for very restricted scenarios and an exponential optimization time. We therefore introduce a multiobjective formulation of the problem which trades off the expected cost and its variance. We show that multiobjective evolutionary algorithms are highly effective when using this formulation and obtain a set of solutions that contains an optimal solution for any possible confidence level imposed on the constraint. Furthermore, we prove that this approach can also be used to compute a set of optimal solutions for the chance-constrained minimum spanning tree problem. In order to deal with potentially exponentially many trade-offs in the multiobjective formulation, we propose and analyze improved convex multiobjective approaches. Experimental investigations on instances of the NP-hard stochastic minimum weight dominating set problem confirm the benefit of the multiobjective and the improved convex multiobjective approach in practice.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsBiological EvolutionStochastic ProcessesComputer SimulationNormal DistributionModels, Theoretical

Stichwörter der Autor:innen

Chance constraintsPareto optimizationevolutionary multiobjective algorithmsruntime analysis.

Autor:innen und Institutionen

  • Optimisation and Logistics, The University of Adelaide, Adelaide, Australia frank.neumann@adelaide.edu.au.
  • DTU Compute, Technical University of Denmark, Kgs. Lyngby, Denmark cawi@dtu.dk.

ORCID-Profile: Frank Neumann, Carsten Witt

Zitieren

APA

Neumann, F., & Witt, C. (2025). Runtime Analysis of Single- and Multiobjective Evolutionary Algorithms for Chance-Constrained Optimization Problems with Normally Distributed Random Variables*. Evolutionary Computation. https://doi.org/10.1162/evco_a_00355

Vancouver

Neumann F, Witt C. Runtime Analysis of Single- and Multiobjective Evolutionary Algorithms for Chance-Constrained Optimization Problems with Normally Distributed Random Variables*. Evolutionary Computation. 2025. doi:10.1162/evco_a_00355

BibTeX
@article{Neumann2025,
  author = {Neumann, Frank and Witt, Carsten},
  title = {Runtime Analysis of Single- and Multiobjective Evolutionary Algorithms for Chance-Constrained Optimization Problems with Normally Distributed Random Variables*},
  journal = {Evolutionary Computation},
  year = {2025},
  doi = {10.1162/evco_a_00355}
}
Kostenlos starten →