Reoptimization times of evolutionary algorithms on linear functions under dynamic uniform constraints

Abstract

The investigations of linear pseudo-Boolean functions play a central role in the area of runtime analysis of evolutionary computing techniques. Having an additional linear constraint on a linear function is equivalent to the NP-hard knapsack problem and special problem classes thereof have been investigated in recent works. In this paper, we extend these studies to problems with dynamic constraints and investigate the runtime of different evolutionary algorithms to recompute an optimal solution when the constraint bound changes by a certain amount. We study the classical (1+1) EA and population-based algorithms and show that they recompute an optimal solution very efficiently. Furthermore, we show that a variant of the (1+(λ, λ)) GA can recompute the optimal solution more efficiently in some cases.