Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: Analysis of the (1 + 1) EA on subclasses of linear functions under uniform and linear constraints
Author: Friedrich, T.
Kötzing, T.
Lagodzinski, J.A.G.
Neumann, F.
Schirneck, M.
Citation: Theoretical Computer Science, 2020; 832:3-19
Publisher: Elsevier BV
Issue Date: 2020
ISSN: 0304-3975
Statement of
Tobias Friedrich, Timo Kötzing, J.A. Gregor Lagodzinski, Frank Neumann, Martin Schirneck
Abstract: Linear functions have gained great attention in the run time analysis of evolutionary computation methods. The corresponding investigations have provided many effective tools for analyzing more complex problems. So far, the runtime analysis of evolutionary algorithms has mainly focused on unconstrained problems, but problems occurring in applications frequently involve constraints. Therefore, there is a strong need to extend the current analyses and used methods for analyzing unconstrained problems to a setting involving constraints. In this paper, we consider the behavior of the classical Evolutionary Algorithm on linear functions under linear constraint. We show tight bounds in the case where the constraint is given by the OneMax function and the objective function is given by either the OneMax or the BinVal function. For the general case we present upper and lower bounds.
Keywords: Run time analysis; Evolutionary algorithm; Knapsack; Constraints
Rights: © 2018 Published by Elsevier B.V.
DOI: 10.1016/j.tcs.2018.04.051
Grant ID:
Appears in Collections:Aurora harvest 4
Computer Science publications

Files in This Item:
File Description SizeFormat 
hdl_124600.pdfAccepted version783.06 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.