research-article

Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights

Authors:

Andrew M. SuttonAuthors Info & Claims

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 1187 - 1194

https://doi.org/10.1145/3449639.3459381

Published: 26 June 2021 Publication History

Abstract

Addressing a complex real-world optimization problem is a challenging task. The chance-constrained knapsack problem with correlated uniform weights plays an important role in the case where dependent stochastic components are considered. We perform runtime analysis of a randomized search algorithm (RSA) and a basic evolutionary algorithm (EA) for the chance-constrained knapsack problem with correlated uniform weights. We prove bounds for both algorithms for producing a feasible solution. Furthermore, we investigate the behaviour of the algorithms and carry out analyses on two settings: uniform profit value and the setting in which every group shares an arbitrary profit profile. We provide insight into the structure of these problems and show how the weight correlations and the different profit profiles influence the runtime behavior of both algorithms in the chance-constrained setting.

References

[1]

Hirad Assimi, Oscar Harper, Yue Xie, Aneta Neumann, and Frank Neumann. 2020. Evolutionary Bi-Objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives. In ECAI 2020 - 24th European Conference on Artificial Intelligence, Vol. 325. IOS Press, 307--314.

[2]

Anne Auger and Benjamin Doerr. 2011. Theory of Randomized Search Heuristics. World Scientific.

[3]

A. Charnes and W. W. Cooper. 1959. Chance-Constrained Programming. Management Science 6, 1 (1959), 73--79.

Digital Library

[4]

Janiele Custodio, Miguel A. Lejeune, and Antonio Zavaleta. 2019. Note on "A chance-constrained programming framework to handle uncertainties in radiation therapy treatment planning". Eur. J. Oper. Res. 275, 2 (2019), 793--794.

[5]

Benjamin Doerr, Carola Doerr, Aneta Neumann, Frank Neumann, and Andrew M. Sutton. 2020. Optimization of Chance-Constrained Submodular Functions. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020. AAAI Press, 1460--1467.

[6]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the analysis of the (1 + 1) evolutionary algorithm. Theor. Comput. Sci. 276, 1-2 (2002), 51--81.

Digital Library

[7]

Tobias Friedrich, Timo Kötzing, J. A. Gregor Lagodzinski, Frank Neumann, and Martin Schirneck. 2020. Analysis of the (1+1) EA on subclasses of linear functions under uniform and linear constraints. Theor. Comput. Sci. 832 (2020), 3--19.

[8]

Grani Adiwena Hanasusanto, Vladimir Roitch, Daniel Kuhn, and Wolfram Wiesemann. 2015. A distributionally robust perspective on uncertainty quantification and chance constrained programming. Math. Program. 151, 1 (2015), 35--62.

Digital Library

[9]

Grani Adiwena Hanasusanto, Vladimir Roitch, Daniel Kuhn, and Wolfram Wiesemann. 2017. Ambiguous Joint Chance Constraints Under Mean and Dispersion Information. Oper. Res. 65, 3 (2017), 751--767.

Digital Library

[10]

Jun He, Boris Mitavskiy, and Yuren Zhou. 2014. A theoretical assessment of solution quality in evolutionary algorithms for the knapsack problem. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2014, Beijing, China, July 6-11, 2014. IEEE, 141--148.

[11]

Shih-Cheng Horng, Shieh-Shing Lin, and Feng-Yi Yang. 2012. Evolutionary algorithm for stochastic job shop scheduling with random processing time. Expert Syst. Appl. 39, 3 (2012), 3603--3610.

Digital Library

[12]

Thomas Jansen. 2013. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer.

Digital Library

[13]

Per Kristian Lehre and Carsten Witt. 2013. General Drift Analysis with Tail Bounds. CoRR abs/1307.2559 (2013). arXiv:1307.2559 http://arxiv.org/abs/1307.2559

[14]

Pu Li, Harvey Arellano-Garcia, and Günter Wozny. 2008. Chance constrained programming approach to process optimization under uncertainty. Comput. Chem. Eng. 32, 1-2 (2008), 25--45.

[15]

Andrei Lissovoi and Carsten Witt. 2017. A Runtime Analysis of Parallel Evolutionary Algorithms in Dynamic Optimization. Algorithmica 78, 2 (2017), 641--659.

Digital Library

[16]

Bo Liu, Qingfu Zhang, Francisco V. Fernández, and Georges G. E. Gielen. 2013. An Efficient Evolutionary Algorithm for Chance-Constrained Bi-Objective Stochastic Optimization. IEEE Trans. Evol. Comput. 17, 6 (2013), 786--796.

Digital Library

[17]

Heinz Mühlenbein. 1992. How Genetic Algorithms Really Work: Mutation and Hillclimbing. 15--26.

[18]

Aneta Neumann and Frank Neumann. 2020. Optimising Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-objective Algorithms. In Parallel Problem Solving from Nature - PPSN XVI - 16th International Conference, PPSN 2020, Proceedings, Part I (Lecture Notes in Computer Science, Vol. 12269). Springer, 404--417.

[19]

Frank Neumann, Mojgan Pourhassan, and Vahid Roostapour. 2020. Analysis of Evolutionary Algorithms in Dynamic and Stochastic Environments. Springer International Publishing, Cham, 323--357.

[20]

Frank Neumann and Andrew M. Sutton. 2019. Runtime analysis of the (1 + 1) evolutionary algorithm for the chance-constrained knapsack problem. In FOGA. ACM, 147--153.

[21]

Frank Neumann and Carsten Witt. 2010. Bioinspired Computation in Combinatorial Optimization. Springer.

[22]

Babatunde Odetayo, Mostafa Kazemi, John MacCormack, William D Rosehart, Hamidreza Zareipour, and Ali Reza Seifi. 2018. A chance constrained programming approach to the integrated planning of electric power generation, natural gas network and storage. IEEE Transactions on Power Systems 33, 6 (2018), 6883--6893.

[23]

Chandra A. Poojari and Boby Varghese. 2008. Genetic Algorithm based technique for solving Chance Constrained Problems. Eur. J. Oper. Res. 185, 3 (2008), 1128--1154.

[24]

Pratyusha Rakshit, Amit Konar, and Swagatam Das. 2017. Noisy evolutionary optimization algorithms - A comprehensive survey. Swarm and Evolutionary Computation 33 (2017), 18--45.

[25]

Vahid Roostapour, Aneta Neumann, Frank Neumann, and Tobias Friedrich. 2019. Pareto Optimization for Subset Selection with Dynamic Cost Constraints. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019. AAAI Press, 2354--2361.

[26]

Jochen Till, Guido Sand, Maren Urselmann, and Sebastian Engell. 2007. A hybrid evolutionary algorithm for solving two-stage stochastic integer programs in chemical batch scheduling. Computers & Chemical Engineering 31, 5-6 (2007), 630--647.

[27]

Yue Xie, Oscar Harper, Hirad Assimi, Aneta Neumann, and Frank Neumann. 2019. Evolutionary algorithms for the chance-constrained knapsack problem. In GECCO. ACM, 338--346.

[28]

Yue Xie, Aneta Neumann, and Frank Neumann. 2020. Specific single- and multiobjective evolutionary algorithms for the chance-constrained knapsack problem. In GECCO. ACM, 271--279.

[29]

Maryam Zaghian, Gino J. Lim, and Azin Khabazian. 2018. A chance-constrained programming framework to handle uncertainties in radiation therapy treatment planning. Eur. J. Oper. Res. 266, 2 (2018), 736--745.

Cited By

Friedrich TKötzing TNeumann ANeumann FRadhakrishnan A(2025)Analysis of the (1+1) EA on LeadingOnes with ConstraintsAlgorithmica10.1007/s00453-025-01298-9Online publication date: 19-Feb-2025
https://doi.org/10.1007/s00453-025-01298-9
Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Hewa Pathiranage INeumann FAntipov DNeumann ALi XHandl J(2024)Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack ProblemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654067(520-528)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654067
Show More Cited By

Index Terms

Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Random search heuristics
  2. Theory and algorithms for application domains
    1. Theory of randomized search heuristics

Recommendations

Runtime analysis of the (1 + 1) evolutionary algorithm for the chance-constrained knapsack problem
FOGA '19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

The area of runtime analysis has made important contributions to the theoretical understanding of evolutionary algoirthms for stochastic problems in recent years. Important real-world applications involve chance constraints where the goal is to optimize ...
Analysis of the (1 + 1)-EA for finding approximate solutions to vertex cover problems

Vertex cover is one of the best known NP-Hard combinatorial optimization problems. Experimental work has claimed that evolutionary algorithms (EAs) perform fairly well for the problem and can compete with problem-specific ones. A theoretical analysis ...
The choice of the offspring population size in the (1,λ) EA
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,λ) EA. We establish a sharp threshold at λ = log{\frac{e}{e-1}} n ≈5 log₁₀ n between exponential and polynomial running times on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference

June 2021

1219 pages

ISBN:9781450383509

DOI:10.1145/3449639

Editor:
Francisco Chicano
University of Malaga
,
General Chair:
Krzysztof Krawiec
Poznan University of Technology

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

SA Government

Conference

GECCO '21

Sponsor:

SIGEVO

GECCO '21: Genetic and Evolutionary Computation Conference

July 10 - 14, 2021

Lille, France

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
117
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)3

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Friedrich TKötzing TNeumann ANeumann FRadhakrishnan A(2025)Analysis of the (1+1) EA on LeadingOnes with ConstraintsAlgorithmica10.1007/s00453-025-01298-9Online publication date: 19-Feb-2025
https://doi.org/10.1007/s00453-025-01298-9
Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Hewa Pathiranage INeumann FAntipov DNeumann ALi XHandl J(2024)Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack ProblemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654067(520-528)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654067
Pathirage Don TNeumann ANeumann FLi XHandl J(2024)The Chance Constrained Travelling Thief Problem: Problem Formulations and AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654014(214-222)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654014
Li XLiu SWang JChen XOng YTang K(2024)Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms, and ApplicationsIEEE Transactions on Cybernetics10.1109/TCYB.2024.340239554:12(7969-7980)Online publication date: Dec-2024
https://doi.org/10.1109/TCYB.2024.3402395
Perera KNeumann FNeumann A(2024)Multi-objective Evolutionary Approaches for the Knapsack Problem with Stochastic ProfitsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_8(116-132)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70055-2_8
Doerr BSilva SPaquete L(2023)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595042(946-975)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595042
Friedrich TKötzing TNeumann ANeumann FRadhakrishnan ASilva SPaquete L(2023)Analysis of (1+1) EA on LeadingOnes with ConstraintsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590453(1584-1592)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590453
Doerr BWagner M(2022)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533628(890-921)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533628
Xia XHuang ZPeng XChen ZXiang Y(2022)Performance analysis of evolutionary algorithm for the maximum internal spanning tree problemThe Journal of Supercomputing10.1007/s11227-022-04342-578:9(11949-11973)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s11227-022-04342-5
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten