Simple Random Sampling Estimation of the Number of Local Optima

Khulood Alyahya, Jonathan E. Rowe

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)
257 Downloads (Pure)

Abstract

We evaluate the performance of estimating the number of
local optima by estimating their proportion in the search space using simple random sampling (SRS). The performance of this method is compared against that of the jackknife method. The methods are used to estimate the number of optima in two landscapes of random instances of some combinatorial optimisation problems. SRS provides a cheap, unbiased and accurate estimate when the proportion is not exceedingly small. We discuss choices of confidence interval in the case of extremely small proportion. In such cases, the method more likely provides an upper bound to the number of optima and can be combined with other methods to obtain a better lower bound. We suggest that SRS should be the first choice for estimating the number of optima when no prior information is available about the landscape under study.
Original languageEnglish
Title of host publicationParallel Problem Solving from Nature -- PPSN XIV
Subtitle of host publication14th International Conference, September 17-21,2016, Proceedings
PublisherSpringer
Pages932-941
Number of pages10
Volume9921
ISBN (Electronic)978-3-319-45823-6
ISBN (Print)978-3-319-45822-9
DOIs
Publication statusPublished - 2016
Event14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 - Edinburgh, United Kingdom
Duration: 17 Sep 201621 Sep 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9921
ISSN (Print)0302-9743
ISSN (Electronic)0302-9743

Conference

Conference14th International Conference on Parallel Problem Solving from Nature, PPSN 2016
Country/TerritoryUnited Kingdom
CityEdinburgh
Period17/09/1621/09/16

Fingerprint

Dive into the research topics of 'Simple Random Sampling Estimation of the Number of Local Optima'. Together they form a unique fingerprint.

Cite this