Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/136266
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Single- and multi-objective evolutionary algorithms for the knapsack problem with dynamically changing constraints |
Author: | Roostapour, V. Neumann, A. Neumann, F. |
Citation: | Theoretical Computer Science, 2022; 924:129-147 |
Publisher: | Elsevier |
Issue Date: | 2022 |
ISSN: | 0304-3975 1879-2294 |
Statement of Responsibility: | Vahid Roostapour, Aneta Neumann, Frank Neumann |
Abstract: | Evolutionary algorithms are bio-inspired algorithms that can easily adapt to changing environments. Recent results in the area of runtime analysis have pointed out that algorithms such as the (1+1) EA and Global SEMO can efficiently reoptimize linear functions under a dynamic uniform constraint. Motivated by this study, we investigate single- and multi-objective baseline evolutionary algorithms for the classical knapsack problem where the capacity of the knapsack varies over time. We establish different benchmark scenarios where the capacity changes every τ iterations according to a uniform or normal distribution. Our experimental investigations analyze the behavior of our algorithms in terms of the magnitude of changes determined by parameters of the chosen distribution, the frequency determined by τ, and the class of knapsack instance under consideration. Our results show that the multi-objective approaches using a population that caters for dynamic changes have a clear advantage on many benchmarks scenarios when the frequency of changes is not too high. Furthermore, we demonstrate that the diversity mechanisms used in popular evolutionary multi-objective algorithms such as NSGA-II and SPEA2 do not necessarily result in better performance and even lead to inferior results compared to our simple multi-objective approaches. |
Keywords: | Combinatorial optimization; Dynamic constraints; Knapsack problem |
Rights: | © 2022 Elsevier B.V. All rights reserved. |
DOI: | 10.1016/j.tcs.2022.05.008 |
Grant ID: | http://purl.org/au-research/grants/arc/DP160102401 |
Published version: | https://doi.org/10.1016/j.tcs.2022.05.008 |
Appears in Collections: | Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.