Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint
Author: Neumann, F.
Pourhassan, M.
Witt, C.
Citation: Algorithmica: an international journal in computer science, 2021; 83(10):3209-3237
Publisher: Springer
Issue Date: 2021
ISSN: 0178-4617
Statement of
Frank Neumann, Mojgan Pourhassan, Carsten Witt
Abstract: In the last decade remarkable progress has been made in development of suitable proof techniques for analysing randomised search heuristics. The theoretical investigation of these algorithms on classes of functions is essential to the understanding of the underlying stochastic process. Linear functions have been traditionally studied in this area resulting in tight bounds on the expected optimisation time of simple randomised search algorithms for this class of problems. Recently, the constrained version of this problem has gained attention and some theoretical results have also been obtained on this class of problems. In this paper we study the class of linear functions under uniform constraint and investigate the expected optimisation time of Randomised Local Search (RLS) and a simple evolutionary algorithm called (1+1) EA. We prove a tight bound of Θ(n²) for RLS and improve the previously best known upper bound of (1+1) EA from O(n²log(Bw(max))) to O(n²logB) in expectation and to O(n²logn) with high probability, where w(max) and B are the maximum weight of the linear objective function and the bound of the uniform constraint, respectively. Also, we obtain a tight bound of O(n²) for the (1+1) EA on a special class of instances. We complement our theoretical studies by experimental investigations that consider different values of B and also higher mutation rates that reflect the fact that 2-bit flips are crucial for dealing with the uniform constraint.
Keywords: Randomised search heuristics; (1+1) EA; linear functions; constraints; runtime analysis
Rights: © Springer Science+Business Media, LLC, part of Springer Nature 2020
DOI: 10.1007/s00453-020-00779-3
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.