Thee 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+(łambda, łambda))\) GA can recompute the optimal solution more efficiently in some cases.
%0 Conference Paper
%1 shi2017reoptimization
%A Shi, Feng
%A Schirneck, Martin
%A Friedrich, Tobias
%A Kötzing, Timo
%A Neumann, Frank
%B Genetic and Evolutionary Computation Conference (GECCO)
%D 2017
%K testing typo3
%P 1407-1414
%T Reoptimization Times of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints
%X Thee 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+(łambda, łambda))\) GA can recompute the optimal solution more efficiently in some cases.
@inproceedings{shi2017reoptimization,
abstract = {Thee 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+(\lambda, \lambda))\) GA can recompute the optimal solution more efficiently in some cases.},
added-at = {2017-09-19T19:29:58.000+0200},
author = {Shi, Feng and Schirneck, Martin and Friedrich, Tobias and Kötzing, Timo and Neumann, Frank},
biburl = {https://www.bibsonomy.org/bibtex/2f42004e08f8bcb1e0380f5ab71170670/typo3tester},
booktitle = {Genetic and Evolutionary Computation Conference (GECCO)},
interhash = {0384586ae3ecdab9cc9fafd5568a46b1},
intrahash = {f42004e08f8bcb1e0380f5ab71170670},
keywords = {testing typo3},
pages = {1407-1414},
timestamp = {2017-09-19T19:29:58.000+0200},
title = {Reoptimization Times of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints},
year = 2017
}