TY  - JOUR
A1  - Shi, Feng
A1  - Schirneck, Friedrich Martin
A1  - Friedrich, Tobias
A1  - Kötzing, Timo
A1  - Neumann, Frank
T1  - Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints
JF  - Algorithmica : an international journal in computer science
N2  - 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.
Y1  - 2018
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-605295
SN  - 0178-4617
SN  - 1432-0541
VL  - 82
IS  - 10
SP  - 3117
EP  - 3123
PB  - Springer
CY  - New York
ER  -