@article{ShiSchirneckFriedrichetal.2018,
  author    = {Shi, Feng and Schirneck, Friedrich Martin and Friedrich, Tobias and K{\"o}tzing, Timo and Neumann, Frank},
  title     = {Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints},
  series = {Algorithmica : an international journal in computer science},
  volume    = {82},
  journal   = {Algorithmica : an international journal in computer science},
  number    = {10},
  publisher = {Springer},
  address   = {New York},
  issn      = {0178-4617},
  doi       = {10.1007/s00453-020-00739-x},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-605295},
  pages     = {3117 -- 3123},
  year      = {2018},
  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.},
  language  = {en}
}