Paper Info
Title
Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint
Abstract
ABSTRACTIn 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 Θ(n2) for RLS and improve the previously best known bound of (1+1) EA from O(n2 log(Bwmax)) to O(n2 log B) in expectation and to O(n2 log n) with high probability, where wmax and B are the maximum weight of the linear objective function and the bound of the uniform constraint, respectively.
Year
DOI
Venue
2019
10.1145/3321707.3321722
Genetic and Evolutionary Computation Conference
Keywords
Field
DocType
randomised search heuristics, (1+1) EA, linear functions, constraints, runtime analysis
Mathematical optimization,Computer science,Heuristics,Linear function
Conference
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Frank Neumann11727124.28
Mojgan Pourhassan294.92
Carsten Witt398759.83