research-article

Runtime analysis of the (1 + 1) evolutionary algorithm for the chance-constrained knapsack problem

Authors:

Andrew M. SuttonAuthors Info & Claims

FOGA '19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

Pages 147 - 153

https://doi.org/10.1145/3299904.3340315

Published: 27 August 2019 Publication History

Abstract

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 a function under the condition that constraints are only violated with a small probability. We rigorously analyze the runtime of the (1+1) EA for the chance-constrained knapsack problem. In this setting, the weights are stochastic, and the objective is to maximize a linear profit function while minimizing the probability of a constraint violation in the total weight. We investigate a number of special cases for this problem, paying attention to how the structure of the chance constraint influences the runtime behavior of the (1+1) EA. Our results reveal that small changes to the profit value can result in hard-to-escape local optima.

References

[1]

Anne Auger and Benjamin Doerr (Eds.). 2011. Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific, Singapore.

Digital Library

[2]

Xiaodi Bai, Xiaojin Zheng, and Xiaoling Sun. 2012. A survey on probabilistically constrained optimization problems. Numerical Algebra, Control & Optimization 2, 4 (2012), 767--778.

[3]

Abraham Charnes and William W Cooper. 1959. Chance-constrained programming. Management Science 6, 1 (1959), 73--79.

Digital Library

[4]

Tobias Friedrich, Timo Kötzing, Martin S. Krejca, and Andrew M. Sutton. 2016. Robustness of Ant Colony Optimization to Noise. Evolutionary Computation 24, 2 (2016), 237--254.

Digital Library

[5]

Tobias Friedrich, Timo Kötzing, J.A. Gregor Lagodzinski, Frank Neumann, and Martin Schirneck. 2018. Analysis of the (1+1) EA on subclasses of linear functions under uniform and linear constraints. Theoretical Computer Science (2018).

Digital Library

[6]

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

Digital Library

[7]

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

Digital Library

[8]

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). IEEE, 141--148.

[9]

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

Digital Library

[10]

Olivier Klopfenstein and Dritan Nace. 2008. A robust approach to the chance-constrained knapsack problem. Operations Research Letters 36, 5 (2008), 628 -- 632.

Digital Library

[11]

Rajeev Kumar and Nilanjan Banerjee. 2005. Running Time Analysis of a Multiobjective Evolutionary Algorithm on Simple and Hard Problems. In Proceedings of the Eighth Conference on Foundations of Genetic Algorithms (FOGA) (Lecture Notes in Computer Science), Vol. 3469. Springer, Berlin, 112--131.

Digital Library

[12]

Pu Li, Harvey Arellano-Garcia, and Günter Wozny. 2008. Chance constrained programming approach to process optimization under uncertainty. Computers & Chemical Engineering 32, 1 (2008), 25 -- 45.

[13]

Pu Li, Moritz Wendt, and Günter Wozny. 2000. Robust model predictive control under chance constraints. Computers & Chemical Engineering 24, 2 (2000), 829 -- 834.

[14]

Andrei Lissovoi and Carsten Witt. 2015. Runtime analysis of ant colony optimization on dynamic shortest path problems. Theoretical Computer Science 561 (2015), 73 -- 85.

Digital Library

[15]

Andrei Lissovoi and Carsten Witt. 2016. MMAS Versus Population-Based EA on a Family of Dynamic Fitness Functions. Algorithmica 75, 3 (01 Jul 2016), 554--576.

Digital Library

[16]

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

Digital Library

[17]

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. Evolutionary Computation 17, 6 (2013), 786--796.

Digital Library

[18]

Frank Neumann and Andrew M. Sutton. 2018. Runtime Analysis of Evolutionary Algorithms for the Knapsack Problem with Favorably Correlated Weights. In Proceedings of the Fifteenth International Conference on Parallel Problem Solving from Nature (Lecture Notes in Computer Science), Anne Auger, Carlos M. Fonseca, Nuno Lourenço, Penousal Machado, Luís Paquete, and Darrell Whitley (Eds.), Vol. 11102. Springer, 141--152.

[19]

Frank Neumann and Carsten Witt. 2010. Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity (1st ed.). Springer, Berlin.

Digital Library

[20]

Prabhakar Raghavan and Rajeev Motwani. 1995. Randomized algorithms. Cambridge University Press, Cambridge.

Digital Library

[21]

Vahid Roostapour, Aneta Neumann, and Frank Neumann. 2018. On the Performance of Baseline Evolutionary Algorithms on the Dynamic Knapsack Problem. In Proceedings of the Fifteenth International Conference on Parallel Problem Solving from Nature (Lecture Notes in Computer Science), Anne Auger, Carlos M. Fonseca, Nuno Lourenço, Penousal Machado, Luís Paquete, and Darrell Whitley (Eds.), Vol. 11101. Springer, Berlin, 158--169.

[22]

Vahid Roostapour, Aneta Neumann, Frank Neumann, and Tobias Friedrich. 2018. Pareto Optimization for Subset Selection with Dynamic Cost Constraints. CoRR abs/1811.07806 (2018). arXiv:1811.07806 http://arxiv.org/abs/1811.07806 Conference version appears at AAAI 2019.

[23]

Vahid Roostapour, Mojgan Pourhassan, and Frank Neumann. 2018. Analysis of Evolutionary Algorithms in Dynamic and Stochastic Environments. CoRR abs/1806.08547 (2018). arXiv:1806.08547 http://arxiv.org/abs/1806.08547

[24]

Abraham Wald. 1944. On Cumulative Sums of Random Variables. Ann. Math. Statist. 15, 3 (09 1944), 283--296.

[25]

Abraham Wald. 1945. Some Generalizations of the Theory of Cumulative Sums of Random Variables. Ann. Math. Statist. 16, 3 (09 1945), 287--293.

[26]

Yue Xie, Oscar Harper, Hirad Assimi, Aneta Neumann, and Frank Neumann. 2019. Evolutionary Algorithms for the Chance-Constrained Knapsack Problem. CoRR abs/1902.04767 (2019). arXiv:1902.04767 http://arxiv.org/abs/1902.04767 Conference version appears at GECCO 2019.

[27]

Yuren Zhou and Jun He. 2007. A Runtime Analysis of Evolutionary Algorithms for Constrained Optimization Problems. IEEE Transactions on Evolutionary Computation 11, 5 (2007), 608--619.

Digital Library

Cited By

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
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
Neumann FWitt C(2022)Runtime Analysis of the (1+1) EA on Weighted Sums of Transformed Linear FunctionsParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_38(542-554)Online publication date: 15-Aug-2022
https://doi.org/10.1007/978-3-031-14721-0_38
Show More Cited By

Index Terms

Runtime analysis of the (1 + 1) evolutionary algorithm for the chance-constrained knapsack problem
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Theory of randomized search heuristics

Recommendations

Specific single- and multi-objective evolutionary algorithms for the chance-constrained knapsack problem
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

The chance-constrained knapsack problem is a variant of the classical knapsack problem where each item has a weight distribution instead of a deterministic weight. The objective is to maximize the total profit of the selected items under the condition ...
Evolutionary algorithms for the chance-constrained knapsack problem
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference

Evolutionary algorithms have been widely used for a range of stochastic optimization problems. In most studies, the goal is to optimize the expected quality of the solution. Motivated by real-world problems where constraint violations have extremely ...
A novel quantum-inspired evolutionary algorithm for solving combinatorial optimization problems
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

In this paper, we propose a novel quantum-inspired evolutionary algorithm, called NQEA, for solving combinatorial optimization problems. NQEA uses a new Q-bit update operator to increase the balance between the exploration and exploitation of the search ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA '19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

August 2019

187 pages

ISBN:9781450362542

DOI:10.1145/3299904

General Chair:
Tobias Friedrich
Hasso Plattner Institute
,
Program Chairs:
Carola Doerr
Sorbonne University
,
Dirk Arnold
Dalhousie University

Copyright © 2019 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: 27 August 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '19

Sponsor:

SIGEVO

FOGA '19: Foundations of Genetic Algorithms XV

August 27 - 29, 2019

Potsdam, Germany

Acceptance Rates

FOGA '19 Paper Acceptance Rate 15 of 31 submissions, 48%;

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
136
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
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
Neumann FWitt C(2022)Runtime Analysis of the (1+1) EA on Weighted Sums of Transformed Linear FunctionsParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_38(542-554)Online publication date: 15-Aug-2022
https://doi.org/10.1007/978-3-031-14721-0_38
Shi FYan XNeumann F(2022)Runtime Analysis of Simple Evolutionary Algorithms for the Chance-Constrained Makespan Scheduling ProblemParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_37(526-541)Online publication date: 15-Aug-2022
https://doi.org/10.1007/978-3-031-14721-0_37
Neumann AXie YNeumann F(2022)Evolutionary Algorithms for Limiting the Effect of Uncertainty for the Knapsack Problem with Stochastic ProfitsParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14714-2_21(294-307)Online publication date: 14-Aug-2022
https://doi.org/10.1007/978-3-031-14714-2_21
Doerr BNeumann F(2021)A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete OptimizationACM Transactions on Evolutionary Learning and Optimization10.1145/34723041:4(1-43)Online publication date: 31-Dec-2021
https://doi.org/10.1145/3472304
Xie YNeumann ANeumann FCoello Coello C(2020)Specific single- and multi-objective evolutionary algorithms for the chance-constrained knapsack problemProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390162(271-279)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390162
Neumann ANeumann F(2020)Optimising Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-objective AlgorithmsParallel Problem Solving from Nature – PPSN XVI10.1007/978-3-030-58112-1_28(404-417)Online publication date: 31-Aug-2020
https://doi.org/10.1007/978-3-030-58112-1_28

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.

Media

Figures

Other

Tables

View Table of Contents