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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agresti, A., Coull, B.A.: Approximate is better than “exact” for interval estimation of binomial proportions. Am. Statistician 52(2), 119–126 (1998)
Brown, L.D., Cai, T.T., DasGupta, A.: Interval estimation for a binomial proportion. Stat. Sci. 16(2), 101–117 (2001)
Burnham, K.P., Overton, W.S.: Estimation of the size of a closed population when capture probabilities vary among animals. Biometrika 65(3), 625–633 (1978)
Caruana, R., Mullin, M.: Estimating the number of local minima in big, nasty search spaces. In: Proceedings of IJCAI-1999 Workshop on Statistical Machine Learning for Large-Scale Optimization (1999)
Englert, M., Röglin, H., Vöcking, B.: Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. Algorithmica 68(1), 190–264 (2013)
Eremeev, A.V., Reeves, C.R.: Non-parametric estimation of properties of combinatorial landscapes. In: Cagnoni, S., Gottlieb, J., Hart, E., Middendorf, M., Raidl, G.R. (eds.) EvoIASP 2002, EvoWorkshops 2002, EvoSTIM 2002, EvoCOP 2002, and EvoPlan 2002. LNCS, vol. 2279, pp. 31–40. Springer, Heidelberg (2002)
Ferreira, F.F., Fontanari, J.F.: Probabilistic analysis of the number partitioning problem. J. Phys. A: Math. Gen. 31(15), 3417 (1998)
Garnier, J., Kallel, L.: How to detect all maxima of a function. In: Kallel, L., Naudts, B., Rogers, A. (eds.) Theoretical Aspects of Evolutionary Computing, pp. 343–370. Springer, Heidelberg (2001)
Garnier, J., Kallel, L.: Efficiency of local search with multiple local optima. SIAM J. Discret. Math. 15(1), 122–141 (2002)
Goldman, B.W., Punch, W.F.: Hyperplane elimination for quickly enumerating local optima. In: Chicano, F., et al. (eds.) EvoCOP 2016. LNCS, vol. 9595, pp. 154–169. Springer, Heidelberg (2016)
Grundel, D.A., Krokhmal, P.A., Oliveira, C.A.S., Pardalos, P.M.: On the number of local minima for the multidimensional assignment problem. J. Comb. Optim. 13(1), 1–18 (2007)
Hernando, L., Mendiburu, A., Lozano, J.A.: An evaluation of methods for estimating the number of local optima in combinatorial optimization problems. Evol. Comput. 21(4), 625–658 (2013)
Mathias, K.E., Whitley, L.D.: Transforming the search space with gray coding. In: IEEE WCCI, pp. 513–518, vol. 1 (1994)
Pires, A.M., Amado, C.: Interval estimators for a binomial proportion: comparison of twenty methods. REVSTAT-Stat. J. 6(2), 165–197 (2008)
Prügel-Bennett, A., Tayarani-N, M.-H.: Maximum satisfiability: anatomy of the fitness landscape for a hard combinatorial optimization problem. IEEE Trans. Evol. Comput. 16(3), 319–338 (2012)
Reeves, C.R.: Direct statistical estimation of GA landscape properties. Found. Genet. Algorithms 6, 91–107 (2001)
Reeves, C.R., Eremeev, A.V.: Statistical analysis of local search landscapes. J. Oper. Res. Soc. 55(7), 687–693 (2004)
Stadler, P.F., Stephens, C.R.: Landscapes and effective fitness. Comments Theor. Biol. 8(4–5), 389–431 (2002)
Tayarani-N, M.-H., Prügel-Bennett, A.: On the landscape of combinatorial optimization problems. IEEE Trans. Evol. Comput. 18(3), 420–434 (2014)
Tayarani-N, M.-H., Prügel-Bennett, A.: Quadratic assignment problem: a landscape analysis. Evol. Intell. 8(4), 165–184 (2015)
Tovey, C.A.: Hill climbing with multiple local optima. SIAM J. Algebraic Discrete Methods 6(3), 384–393 (1985)
Triola, M.F.: Elementary Statistics, 12th edn. Pearson, Upper Saddle River (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Alyahya, K., Rowe, J.E. (2016). Simple Random Sampling Estimation of the Number of Local Optima. In: Handl, J., Hart, E., Lewis, P., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds) Parallel Problem Solving from Nature – PPSN XIV. PPSN 2016. Lecture Notes in Computer Science(), vol 9921. Springer, Cham. https://doi.org/10.1007/978-3-319-45823-6_87
Download citation
DOI: https://doi.org/10.1007/978-3-319-45823-6_87
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-45822-9
Online ISBN: 978-3-319-45823-6
eBook Packages: Computer ScienceComputer Science (R0)