Please use this identifier to cite or link to this item:
|Scopus||Web of Science®||Altmetric|
|Title:||Reoptimization times of evolutionary algorithms on linear functions under dynamic uniform constraints|
|Citation:||GECCO '17: Proceedings of the 2017 Genetic and Evolutionary Computation Conference, 2017 / Bosman, P.A.N. (ed./s), pp.1407-1414|
|Publisher:||Association for Computing Machinery (ACM)|
|Publisher Place:||New York, NY|
|Conference Name:||Genetic and Evolutionary Computation Conference (GECCO) (15 Jul 2017 - 19 Jul 2017 : Berlin, Germany)|
|Feng Shi, Martin Schirneck, Tobias Friedrich, Timo Kötzing, Frank Neumann|
|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.|
|Keywords:||Runtime analysis, reoptimization time, dynamic constraint, uniform constraint, evolutionary algorithm|
|Rights:||© 2017 Copyright held by the owner/author(s). Publication rights licensed to ACM.|
|Appears in Collections:||Aurora harvest 8|
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.