Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multiobjective Algorithms.
Saved in:
| Title: | Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multiobjective Algorithms. |
|---|---|
| Authors: | Neumann, Aneta1 (AUTHOR) aneta.neumann@adelaide.edu.au, Neumann, Frank1 (AUTHOR) frank.neumann@adelaide.edu.au |
| Source: | Evolutionary Computation. Fall2025, Vol. 33 Issue 3, p363-393. 31p. |
| Subjects: | Submodular functions, Evolutionary algorithms, Mathematical optimization, Multi-objective optimization, Stochastic programming, Operations research |
| Abstract: | 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. [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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 187728434 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multiobjective Algorithms. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Neumann%2C+Aneta%22">Neumann, Aneta</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> aneta.neumann@adelaide.edu.au</i><br /><searchLink fieldCode="AR" term="%22Neumann%2C+Frank%22">Neumann, Frank</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> frank.neumann@adelaide.edu.au</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Evolutionary+Computation%22">Evolutionary Computation</searchLink>. Fall2025, Vol. 33 Issue 3, p363-393. 31p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Submodular+functions%22">Submodular functions</searchLink><br /><searchLink fieldCode="DE" term="%22Evolutionary+algorithms%22">Evolutionary algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Multi-objective+optimization%22">Multi-objective optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Stochastic+programming%22">Stochastic programming</searchLink><br /><searchLink fieldCode="DE" term="%22Operations+research%22">Operations research</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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. [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=187728434 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1162/evco_a_00360 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 31 StartPage: 363 Subjects: – SubjectFull: Submodular functions Type: general – SubjectFull: Evolutionary algorithms Type: general – SubjectFull: Mathematical optimization Type: general – SubjectFull: Multi-objective optimization Type: general – SubjectFull: Stochastic programming Type: general – SubjectFull: Operations research Type: general Titles: – TitleFull: Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multiobjective Algorithms. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Neumann, Aneta – PersonEntity: Name: NameFull: Neumann, Frank IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 09 Text: Fall2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 10636560 Numbering: – Type: volume Value: 33 – Type: issue Value: 3 Titles: – TitleFull: Evolutionary Computation Type: main |
| ResultId | 1 |
