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

Yue Xie; Aneta Neumann; Frank Neumann; Andrew M. Sutton

doi:10.1145/3449639.3459381

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

Yue Xie, Aneta Neumann, Frank Neumann, Andrew M. Sutton

Computer Science (Duluth)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

11 Scopus citations

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.

Original language	English (US)
Title of host publication	GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference
Publisher	Association for Computing Machinery, Inc
Pages	1187-1194
Number of pages	8
ISBN (Electronic)	9781450383509
DOIs	https://doi.org/10.1145/3449639.3459381
State	Published - Jun 26 2021
Event	2021 Genetic and Evolutionary Computation Conference, GECCO 2021 - Virtual, Online, France Duration: Jul 10 2021 → Jul 14 2021

Publication series

Name	GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference

Conference

Conference	2021 Genetic and Evolutionary Computation Conference, GECCO 2021
Country/Territory	France
City	Virtual, Online
Period	7/10/21 → 7/14/21

Bibliographical note

Funding Information:
This research has been supported by the SA Government through the PRIF RCP Industry Consortium.

Publisher Copyright:
© 2021 ACM.

Keywords

Chance-constrained knapsack problem
Evolutionary algorithms
Run-time analysis

Access

10.1145/3449639.3459381

OpenUrl availability

Full text

Cite this

Xie, Y., Neumann, A., Neumann, F., & Sutton, A. M. (2021). Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights. In GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference (pp. 1187-1194). (GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference). Association for Computing Machinery, Inc. https://doi.org/10.1145/3449639.3459381

Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights. / Xie, Yue; Neumann, Aneta; Neumann, Frank et al.
GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, Inc, 2021. p. 1187-1194 (GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Xie, Y, Neumann, A, Neumann, F & Sutton, AM 2021, Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights. in GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference. GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference, Association for Computing Machinery, Inc, pp. 1187-1194, 2021 Genetic and Evolutionary Computation Conference, GECCO 2021, Virtual, Online, France, 7/10/21. https://doi.org/10.1145/3449639.3459381

Xie Y, Neumann A, Neumann F, Sutton AM. Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights. In GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, Inc. 2021. p. 1187-1194. (GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference). doi: 10.1145/3449639.3459381

Xie, Yue ; Neumann, Aneta ; Neumann, Frank et al. / Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights. GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, Inc, 2021. pp. 1187-1194 (GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference).

@inproceedings{5b7227a67d23482d8ede4a685acaf453,

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

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.",

keywords = "Chance-constrained knapsack problem, Evolutionary algorithms, Run-time analysis",

author = "Yue Xie and Aneta Neumann and Frank Neumann and Sutton, {Andrew M.}",

note = "Funding Information: This research has been supported by the SA Government through the PRIF RCP Industry Consortium. Publisher Copyright: {\textcopyright} 2021 ACM.; 2021 Genetic and Evolutionary Computation Conference, GECCO 2021 ; Conference date: 10-07-2021 Through 14-07-2021",

year = "2021",

month = jun,

day = "26",

doi = "10.1145/3449639.3459381",

language = "English (US)",

series = "GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference",

publisher = "Association for Computing Machinery, Inc",

pages = "1187--1194",

booktitle = "GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference",

}

TY - GEN

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

AU - Xie, Yue

AU - Neumann, Aneta

AU - Neumann, Frank

AU - Sutton, Andrew M.

PY - 2021/6/26

Y1 - 2021/6/26

N2 - 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.

AB - 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.

KW - Chance-constrained knapsack problem

KW - Evolutionary algorithms

KW - Run-time analysis

UR - http://www.scopus.com/inward/record.url?scp=85110198781&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85110198781&partnerID=8YFLogxK

U2 - 10.1145/3449639.3459381

DO - 10.1145/3449639.3459381

M3 - Conference contribution

AN - SCOPUS:85110198781

T3 - GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference

SP - 1187

EP - 1194

BT - GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery, Inc

T2 - 2021 Genetic and Evolutionary Computation Conference, GECCO 2021

Y2 - 10 July 2021 through 14 July 2021

ER -

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

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this