Simple Random Sampling Estimation of the Number of Local Optima

Khulood Alyahya; Jonathan E. Rowe

doi:10.1007/978-3-319-45823-6_87

Simple Random Sampling Estimation of the Number of Local Optima

Khulood Alyahya, Jonathan E. Rowe

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Citations (Scopus)

342 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 language	English
Title of host publication	Parallel Problem Solving from Nature -- PPSN XIV
Subtitle of host publication	14th International Conference, September 17-21,2016, Proceedings
Publisher	Springer
Pages	932-941
Number of pages	10
Volume	9921
ISBN (Electronic)	978-3-319-45823-6
ISBN (Print)	978-3-319-45822-9
DOIs	https://doi.org/10.1007/978-3-319-45823-6_87
Publication status	Published - 2016
Event	14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 - Edinburgh, United Kingdom Duration: 17 Sept 2016 → 21 Sept 2016

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9921
ISSN (Print)	0302-9743
ISSN (Electronic)	0302-9743

Conference

Conference	14th International Conference on Parallel Problem Solving from Nature, PPSN 2016
Country/Territory	United Kingdom
City	Edinburgh
Period	17/09/16 → 21/09/16

Access to Document

10.1007/978-3-319-45823-6_87

Alyahya_Rowe_Simple_Random_Sampling_LNCS
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-45823-6_87
Accepted author manuscript, 493 KBLicence: Other (please specify with Rights Statement)

Cite this

@inproceedings{c8c78b9dee5a43929045e6037d321ec7,

title = "Simple Random Sampling Estimation of the Number of Local Optima",

abstract = "We evaluate the performance of estimating the number oflocal 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.",

author = "Khulood Alyahya and Rowe, {Jonathan E.}",

year = "2016",

doi = "10.1007/978-3-319-45823-6_87",

language = "English",

isbn = "978-3-319-45822-9",

volume = "9921",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "932--941",

booktitle = "Parallel Problem Solving from Nature -- PPSN XIV",

note = "14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 ; Conference date: 17-09-2016 Through 21-09-2016",

}

Alyahya, K & Rowe, JE 2016, Simple Random Sampling Estimation of the Number of Local Optima. in Parallel Problem Solving from Nature -- PPSN XIV: 14th International Conference, September 17-21,2016, Proceedings. vol. 9921, Lecture Notes in Computer Science, vol. 9921, Springer, pp. 932-941, 14th International Conference on Parallel Problem Solving from Nature, PPSN 2016, Edinburgh, United Kingdom, 17/09/16. https://doi.org/10.1007/978-3-319-45823-6_87

Simple Random Sampling Estimation of the Number of Local Optima. / Alyahya, Khulood; Rowe, Jonathan E.
Parallel Problem Solving from Nature -- PPSN XIV: 14th International Conference, September 17-21,2016, Proceedings. Vol. 9921 Springer, 2016. p. 932-941 (Lecture Notes in Computer Science; Vol. 9921).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Simple Random Sampling Estimation of the Number of Local Optima

AU - Alyahya, Khulood

AU - Rowe, Jonathan E.

PY - 2016

Y1 - 2016

N2 - We evaluate the performance of estimating the number oflocal 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.

AB - We evaluate the performance of estimating the number oflocal 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.

U2 - 10.1007/978-3-319-45823-6_87

DO - 10.1007/978-3-319-45823-6_87

M3 - Conference contribution

SN - 978-3-319-45822-9

VL - 9921

T3 - Lecture Notes in Computer Science

SP - 932

EP - 941

BT - Parallel Problem Solving from Nature -- PPSN XIV

PB - Springer

T2 - 14th International Conference on Parallel Problem Solving from Nature, PPSN 2016

Y2 - 17 September 2016 through 21 September 2016

ER -

Simple Random Sampling Estimation of the Number of Local Optima

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this