Abstract
Characterization of optimization problems with respect to their solvability is one of the focal points of many research projects in the field of global optimization. Our study contributes to these efforts with the usage of the computational and mathematical tools of network science. Given an optimization problem, a network formed by all the minima found by an optimization method can be constructed. In this paper we use the Basin Hopping method on well-known benchmarking problems and investigate the resulting networks using several measures.
Similar content being viewed by others
References
Ackley D (2012) A connectionist machine for genetic hillclimbing, vol 28. Springer, Berlin
Albert R, Barabási A-L (2002) Statistical mechanics of complex networks. Rev Mod Phys 74:47–97
Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 10:P10008
Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Comput Netw 30:107–117
Cho H, Olivera F, Guikema SD (2008) A derivation of the number of minima of the Griewank function. Appl Math Comput 204:694–701
Daolio F, Tomassini M, Vérel S, Ochoa G (2011) Communities of minima in local optima networks of combinatorial spaces. Phys A Stat Mech Appl 390:1684–1694
Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91:201–213
Doye JPK (2002) The network topology of a potential energy landscape: a static scale-free network. Phys Rev Lett 88:238701
Erdős P, Rényi A (1959) On random graphs. Publ Math 6:290–297
Fourer R, Kernighan BW (2002) AMPL: a modeling language for mathematical programming. Duxbury Press, North Scituate
Freeman L (1977) A set of measures of centrality based on betweenness. Sociometry 40:35–41
Griewank AO (1981) Generalized descent for global optimization. J Optim Theory Appl 34:11–39
Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680
Leary RH (2000) Global optimization on funneling landscapes. J Glob Optim 18:367–383
Levy AV, Montalvo A, Gomez S, Calderon A (1981) Topics in global optimization, Lecture Notes in Mathematics, No. 909, Springer-Verlag, Berlin
Locatelli M (2003) A note on the Griewank Test Function. J Glob Optim 25:169–174
Locatelli M (2005) On the multilevel structure of global optimization problems. Comput Optim Appl 30:5–22
Locatelli M, Schoen F (2013) Global optimization: theory. Algorithms and applications. SIAM-MOS, Philadelphia
Locatelli M, Maischberger M, Schoen F (2014) Differential evolution methods based on local searches. Comput Oper Res 43:169–180
Mittelmann H (2017) Benchmarks for optimization software. http://plato.asu.edu/bench.html. Accessed 17 Jan 2017
More JJ, Munson TS (2002) Computing mountain passes, Preprint ANL/MCS-P957- 0502
Murtagh BA, Saunders MA (2003) MINOS 5.51 user’s guide, Technical Report SOL 83-20R
Neumaier A (2004) Complete search in continuous global optimization and constraint satisfaction. Acta Numer 13:271–369
Neumaier A, Shcherbina O, Huyer W, Vinkó T (2005) A comparison of complete global optimization solvers. Math Program 103:335–356
Newman MEJ (2010) Networks: an introduction. Oxford University Press, Oxford
Newman MEJ (2005) A measure of betweenness centrality based on random walks. Soc Netw 27:39–54
Newman MEJ (2006) Modularity and community structure in networks. PNAS 103:8577–8696
Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D (2004) Defining and identifying communities in networks. PNAS 101(9):2658–2663
Rios LM, Sahinidis NV (2013) Derivative-free optimization: a review of algorithms and comparison of software implementations. J Glob Optim 56:1247–1293
Scala A, Amaral L, Barthélémy M (2001) Small-world networks and the conformation space of lattice polymer chains. Europhys Lett 55:594–600
Stillinger FH, Weber TA (1984) Packing structures and transitions in liquids and solids. Science 225:983–989
Storn R, Price K (1997) Differential evolution—a simple and efficient heuristic for global optimisation over continuous spaces. J Glob Optim 11:341–359
Suganthan PN, Hansen N, Liang JJ, Deb K, Chen YP, Auger A, Tiwari S (2005) Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. KanGAL report, 2005005:
Tomassini M, Verel S, Ochoa G (2008) Complex-network analysis of combinatorial spaces: the NK landscape case. Phys Rev E 78(6):066114
Torn A, Zilinskas A (1989) Global optimization. Springer, New York
Wales DJ, Doye JPK (1997) Global optimization by basin-hopping and the lowest energy structures of Lennard-Jones clusters containing up to 110 atoms. J Phys Chem A 101:5111–5116
Zabinsky ZB, Smith RL (1992) Pure adaptive search in global optimization. Math Program 53:323–338
Acknowledgements
The authors would like o thank the anonymous reviewers for their valuable comments and suggestions to improve the quality of the paper. T. Vinkó was supported by the Bolyai Scholarship of the Hungarian Academy of Sciences.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Vinkó, T., Gelle, K. Basin Hopping Networks of continuous global optimization problems. Cent Eur J Oper Res 25, 985–1006 (2017). https://doi.org/10.1007/s10100-017-0480-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10100-017-0480-0