Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Reoptimization times of evolutionary algorithms on linear functions under dynamic uniform constraints
Author: Shi, F.
Schirneck, M.
Friedrich, T.
Kotzing, T.
Neumann, F.
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
Issue Date: 2017
ISBN: 9781450349208
Conference Name: Genetic and Evolutionary Computation Conference (GECCO) (15 Jul 2017 - 19 Jul 2017 : Berlin, Germany)
Editor: Bosman, P.A.N.
Statement of
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.
DOI: 10.1145/3071178.3071270
Grant ID:
Published version:
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.