[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

PageRank centrality for performance prediction: the impact of the local optima network model

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

A local optima network (LON) compresses relevant features of fitness landscapes in a complex network, where nodes are local optima and edges represent transition probabilities between different basins of attraction. Previous work has found that the PageRank centrality of local optima can be used to predict the success rate and average fitness achieved by local search based metaheuristics. Results are available for LONs where edges describe either basin transition probabilities or escape edges. This paper studies the interplay between the type of LON edges and the ability of the PageRank centrality for the resulting LON to predict the performance of local search based metaheuristics. It finds that LONs are stochastic models of the search heuristic. Thus, to achieve an accurate prediction, the definition of the LON edges must properly reflect the type of diversification steps used in the metaheuristic. LONs with edges representing basin transition probabilities capture well the diversification mechanism of simulated annealing which sometimes also accepts worse solutions that allow the search process to pass between basins. In contrast, LONs with escape edges capture well the diversification step of iterated local search, which escapes from local optima by applying a larger perturbation step.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. The edges in a directed graph are usually denoted as arcs. However, to be consistent with the current terminology in the LON literature, we use the term edge instead of arc throughout the paper.

  2. We follow the standard LON terminology and denote A as the set of directed edges.

References

  • Applegate, D., Cook, W., Rohe, A.: Chained Lin–Kernighan for large traveling salesman problems. INFORMS J. Comput. 15(1), 82–92 (2003). doi:10.1287/ijoc.15.1.82.15157

    Article  MathSciNet  MATH  Google Scholar 

  • Borgatti, S.P.: Centrality and network flow. Soc. Netw. 27(1), 55–71 (2005). doi:10.1016/j.socnet.2004.11.008

    Article  MathSciNet  Google Scholar 

  • Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. Comput. Netw. ISDN Syst. 30(1–7), 107–117 (1998). doi:10.1016/S0169-7552(98)00110-X

    Article  Google Scholar 

  • Chicano, F., Daolio, F., Ochoa, G., Vérel, S., Tomassini, M., Alba, E.: Local optima networks, landscape autocorrelation and heuristic search performance. In: Coello, C.A.C., Cutello, V., Deb, K., Forrest, S., Nicosia, G., Pavone, M. (eds.) Parallel Problem Solving from Nature—PPSN XII: 12th International Conference, vol. 7492 LNCS, pp. 337–347. Springer, Berlin (2012). doi:10.1007/978-3-642-32964-7_34

  • Daolio, F., Verel, S., Ochoa, G., Tomassini, M.: Local optima networks and the performance of iterated local search. In: Soule, T. (ed.) Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation Conference—GECCO ’12, p. 369. ACM Press, Philadelphia (2012). doi:10.1145/2330163.2330217

  • Franceschet, M.: PageRank: standing on the shoulders of giants. Commun. ACM 54(6), 92–101 (2011). doi:10.1145/1953122.1953146

    Article  Google Scholar 

  • Frobenius, F.G.: Ueber Matrizen aus nicht negativen Elementen, pp. 456–477. Sitzungsberichte Preussische Akademie der Wissenschaft, Berlin (1912)

  • Hagberg, A.A., Schult, D.A., Swart, P.J.: Exploring network structure, dynamics, and function using NetworkX. In: Proceedings of the 7th Python in Science Conference (SciPy 2008), pp. 11–15 (2008)

  • Herrmann, S.: Determining the difficulty of landscapes by PageRank centrality in local optima networks. In: Chicano, F., Hu, B., García-Sánchez, P. (eds.) Evolutionary Computation in Combinatorial Optimization: 16th European Conference, EvoCOP 2016, Porto, Portugal, March 30–April 1, 2016, Proceedings, pp. 74–87. Springer International Publishing, Cham (2016). doi:10.1007/978-3-319-30698-8_6

  • Herrmann, S., Rothlauf, F.: Predicting heuristic search performance with PageRank centrality in local optima networks. In: Silva, S. (ed.) Proceedings of the 2015 Genetic and Evolutionary Computation Conference—GECCO ’15, pp. 401–408. ACM Press, Madrid (2015). doi:10.1145/2739480.2754691

  • Jones, T., Forrest, S.: Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In: Proceedings of the Sixth International Conference on Genetic Algorithms, pp. 184–192. Morgan Kaufmann Publishers Inc., San Francisco, CA (1995)

  • Kallel, L., Naudts, B., Reeves, C.R.: Properties of fitness functions and search landscapes. In: Kallel, L., Naudts, B., Rogers, A. (eds.) Theoretical Aspects of Evolutionary Computing, Natural Computing Series, pp. 175–206. Springer, Berlin (2001). doi:10.1007/978-3-662-04448-3_8

    Chapter  Google Scholar 

  • Kauffman, S.A., Weinberger, E.D.: The NK model of rugged fitness landscapes and its application to maturation of the immune response. J. Theor. Biol. 141(2), 211–245 (1989). doi:10.1016/S0022-5193(89)80019-0

    Article  Google Scholar 

  • Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–80 (1983). doi:10.1126/science.220.4598.671

    Article  MathSciNet  MATH  Google Scholar 

  • Laarhoven, P.J.M., Aarts, E.H.L.: Simulated Annealing: Theory and Applications. Kluwer Academic Publishers, Norwell, MA (1988)

    MATH  Google Scholar 

  • Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2), 498–516 (1973). doi:10.1287/opre.21.2.498

    Article  MathSciNet  MATH  Google Scholar 

  • Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search. In: Glover, F., Kochenberger, G.A. (eds.) Handbook of Metaheuristics, pp. 320–353. Kluwer Academic Publishers, Boston (2003). doi:10.1007/0-306-48056-5_11.

  • Lu, G., Li, J., Yao, X.: Fitness landscapes and problem difficulty in evolutionary algorithms: from theory to applications. In: Richter, H., Engelbrecht, A. (eds.) Recent Advances in the Theory and Application of Fitness Landscapes, Emergence, Complexity and Computation, pp. 133–152. Springer, Berlin (2014). doi:10.1007/978-3-642-41888-4

    Google Scholar 

  • Malan, K.M., Engelbrecht, A.P.: Fitness landscape analysis for metaheuristic performance prediction. In: Richter, H., Engelbrecht, A. (eds.) Recent Advances in the Theory and Application of Fitness Landscapes, pp. 103–129. Springer, Berlin (2014). doi:10.1007/978-3-642-41888-4_9

    Chapter  Google Scholar 

  • Ochoa, G., Tomassini, M., Vérel, S., Darabos, C.: A study of NK landscapes’ basins and local optima networks. In: Keijzer, M. (ed) Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation—GECCO ’08, pp. 555–562. ACM Press, Atlanta, GA (2008). doi:10.1145/1389095.1389204

  • Ochoa, G., Verel, S., Tomassini, M.: First-improvement vs. best-improvement local optima networks of NK landscapes. In: Schaefer, R., Cotta, C., Kolodziej, J., Rudolph, G. (eds.) PPSN’10: Proceedings of the 11th International Conference on Parallel Problem Solving from Nature, vol. I, pp. 104–113. Springer, Kraków (2010)

  • Ochoa, G., Verel, S., Daolio, F., Tomassini, M.: Local optima networks: a new model of combinatorial fitness landscapes. In: Richter, H., Engelbrecht, A. (eds.) Recent Advances in the Theory and Application of Fitness Landscapes, Emergence, Complexity and Computation, vol. 6, pp. 233–262. Springer, Berlin. (2014). doi:10.1007/978-3-642-41888-4_9

    Google Scholar 

  • Ochoa, G., Chicano, F., Tinós, R., Whitley, D.: Tunnelling crossover networks. In: Silva, S. (ed) Proceedings of the 2015 Genetic and Evolutionary Computation Conference—GECCO ’15, pp. 449–456. ACM Press, Madrid (2015). doi:10.1145/2739480.2754657

  • Ochoa, G., Veerapen, N., Whitley, D., Burke, E.K.: The multi-funnel structure of TSP fitness landscapes: a visual exploration. In: Artificial Evolution: 12th International Conference, Evolution Artificielle, EA 2015, pp. 1–13. Springer International Publishing, Lyon (2016). doi:10.1007/978-3-319-31471-6_1

  • Perron, O.: Zur Theorie der Matrices. Mathematische Annalen 1 64(1), 248–263 (1907)

    Article  MathSciNet  MATH  Google Scholar 

  • Pitzer, E., Affenzeller, M.: A Comprehensive survey on fitness landscape analysis. In: Fodor, J., Klempous, R., Suárez Araujo, C.P. (eds.) Recent Advances in Intelligent Engineering Systems, Studies in Computational Intelligence, vol. 378, pp. 161–191 (2012). Springer, Berlin. doi:10.1007/978-3-642-23229-9

  • R Core Team: R: a language and environment for statistical computing. R Foundation for Statistical Computing, Vienna. http://www.R-project.org/ (2014)

  • Reidys, C.M., Stadler, P.F.: Combinatorial landscapes. SIAM Rev. 44(1), 3–54 (2002). doi:10.1137/S0036144501395952

    Article  MathSciNet  MATH  Google Scholar 

  • Rothlauf, F.: Design of Modern Heuristics: Principles and Application. Springer, Berlin (2011)

    Book  MATH  Google Scholar 

  • Stadler, P.F.: Fitness landscapes. Appl. Math. Comput. 117, 187–207 (2002)

    MathSciNet  Google Scholar 

  • Stillinger, F.H.: A topographic view of supercooled liquids and glass formation. Science 267(5206), 1935–1939 (1995). doi:10.1126/science.267.5206.1935

    Article  Google Scholar 

  • Vérel, S., Daolio, F., Ochoa, G., Tomassini, M.: Local optima networks with escape edges. In: Hao, J.K., Legrand, P., Collet, P., Monmarché, N., Lutton, E., Schoenauer, M. (eds.) Artificial Evolution, EA 2011. Lecture Notes in Computer Science, vol. 7401, pp. 49–60. Springer, Berlin, Heidelberg (2012)

    Google Scholar 

  • Weinberger, E.D.: Correlated and uncorrelated fitness landscapes and how to tell the difference. Biol. Cybern. 336, 325–336 (1990)

    Article  MATH  Google Scholar 

  • Wright, S.: The roles of mutation, inbreeding, crossbreeding, and selection in evolution. In: Jones, D.F. (ed.) Proceedings of the 6th International Congress of Genetics, Morgan Kaufmann Publishers Inc, pp. 356–366. Ithaca, New York (1932)

Download references

Acknowledgements

G. Ochoa acknowledges support from the Leverhulme Trust (Award No. RPG-2015-395).

Author information

Authors and Affiliations

  1. Johannes Gutenberg-Universität, Mainz, Germany

    Sebastian Herrmann & Franz Rothlauf

  2. University of Stirling, Stirling, Scotland, UK

    Gabriela Ochoa

Authors
  1. Sebastian Herrmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gabriela Ochoa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Franz Rothlauf
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sebastian Herrmann.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Herrmann, S., Ochoa, G. & Rothlauf, F. PageRank centrality for performance prediction: the impact of the local optima network model. J Heuristics 24, 243–264 (2018). https://doi.org/10.1007/s10732-017-9333-1

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-017-9333-1

Keywords