Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint

Frank Neumann, Mojgan Pourhassan, Carsten Witt

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

90 Downloads (Pure)

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 Θ(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.

Original languageEnglish
Title of host publicationProceedings of the 2019 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery
Publication date13 Jul 2019
Pages1506-1514
ISBN (Electronic)9781450361118
DOIs
Publication statusPublished - 13 Jul 2019
Event2019 Genetic and Evolutionary Computation Conference - Prague, Czech Republic
Duration: 13 Jul 201917 Jul 2019

Conference

Conference2019 Genetic and Evolutionary Computation Conference
CountryCzech Republic
CityPrague
Period13/07/201917/07/2019
SponsorAssociation for Computing Machinery
SeriesGECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference

Keywords

  • (1+1) EA
  • Constraints
  • Linear functions
  • Randomised search heuristics
  • Runtime analysis

Fingerprint Dive into the research topics of 'Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint'. Together they form a unique fingerprint.

Cite this