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