Runtime Analysis of Single- and Multiobjective Evolutionary Algorithms for Chance-Constrained Optimization Problems with Normally Distributed Random Variables*.
Saved in:
| Title: | Runtime Analysis of Single- and Multiobjective Evolutionary Algorithms for Chance-Constrained Optimization Problems with Normally Distributed Random Variables*. |
|---|---|
| Authors: | Neumann, Frank1 (AUTHOR) frank.neumann@adelaide.edu.au, Witt, Carsten2 (AUTHOR) cawi@dtu.dk |
| Source: | Evolutionary Computation. Summer2025, Vol. 33 Issue 2, p191-214. 24p. |
| Subjects: | Multi-objective optimization, Dominating set, Probability theory, Spanning trees |
| Abstract: | 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Evolutionary Computation is the property of MIT Press and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 185630749 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Runtime Analysis of Single- and Multiobjective Evolutionary Algorithms for Chance-Constrained Optimization Problems with Normally Distributed Random Variables<superscript>*</superscript>. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Neumann%2C+Frank%22">Neumann, Frank</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> frank.neumann@adelaide.edu.au</i><br /><searchLink fieldCode="AR" term="%22Witt%2C+Carsten%22">Witt, Carsten</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> cawi@dtu.dk</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Evolutionary+Computation%22">Evolutionary Computation</searchLink>. Summer2025, Vol. 33 Issue 2, p191-214. 24p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Multi-objective+optimization%22">Multi-objective optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Dominating+set%22">Dominating set</searchLink><br /><searchLink fieldCode="DE" term="%22Probability+theory%22">Probability theory</searchLink><br /><searchLink fieldCode="DE" term="%22Spanning+trees%22">Spanning trees</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Evolutionary Computation is the property of MIT Press and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=185630749 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1162/evco_a_00355 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 24 StartPage: 191 Subjects: – SubjectFull: Multi-objective optimization Type: general – SubjectFull: Dominating set Type: general – SubjectFull: Probability theory Type: general – SubjectFull: Spanning trees Type: general Titles: – TitleFull: Runtime Analysis of Single- and Multiobjective Evolutionary Algorithms for Chance-Constrained Optimization Problems with Normally Distributed Random Variables*. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Neumann, Frank – PersonEntity: Name: NameFull: Witt, Carsten IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 06 Text: Summer2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 10636560 Numbering: – Type: volume Value: 33 – Type: issue Value: 2 Titles: – TitleFull: Evolutionary Computation Type: main |
| ResultId | 1 |
