Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/113404
Citations
Scopus Web of Science® Altmetric
?
?
Type: Journal article
Title: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints
Author: Shi, F.
Schirneck, M.
Friedrich, T.
Kötzing, T.
Neumann, F.
Citation: Algorithmica, 2018; :1-30
Publisher: Springer
Issue Date: 2018
ISSN: 0178-4617
1432-0541
Statement of
Responsibility: 
Feng Shi, Martin Schirneck, Tobias Friedrich, Timo Kötzing, Frank Neumann
Abstract: Rigorous runtime analysis is a major approach towards understanding evolutionary computing techniques, and in this area linear pseudo-Boolean objective functions play a central role. Having an additional linear constraint is then equivalent to the NP-hard Knapsack problem, certain classes thereof have been studied in recent works. In this article, we present a dynamic model of optimizing linear functions under uniform constraints. Starting from an optimal solution with respect to a given constraint bound, we investigate the runtimes that different evolutionary algorithms need to recompute an optimal solution when the constraint bound changes by a certain amount. The classical (1+1) EA and several population-based algorithms are designed for that purpose, and are shown to recompute efficiently. Furthermore, a variant of the (1+(λ,λ)) GA for the dynamic optimization problem is studied, whose performance is better when the change of the constraint bound is small.
Keywords: Evolutionary algorithm; Runtime analysis; Reoptimization time; Dynamic constraint; Uniform constraint
Rights: © Springer Science+Business Media, LLC, part of Springer Nature 2018
RMID: 0030088745
DOI: 10.1007/s00453-018-0451-4
Grant ID: http://purl.org/au-research/grants/arc/DP140103400
http://purl.org/au-research/grants/arc/DP160102401
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.