Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Maximum Likelihood Estimation Based on Random Subspace EDA: Application to Extrasolar Planet Detection Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Matrix Factorization Based Benchmark Set Analysis: A Case Study on HyFlex

Author : Mustafa Mısır

Published in: Simulated Evolution and Learning

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The present paper offers an analysis strategy to examine benchmark sets of combinatorial search problems. Experimental analysis has been widely used to compare a set of algorithms on a group of instances from such problem domains. These studies mostly focus on the algorithms’ performance rather than the quality of the target benchmark set. In relation to that, the insights about the algorithms’ varying performance happen to be highly limited. The goal here is to introduce a benchmark set analysis strategy that can tell the quality of a benchmark set while allowing to retrieve some insights regarding the algorithms’ performance. A matrix factorization based strategy is utilized for this purpose. A Hyper-heuristic framework, i.e. HyFlex, involving 6 problem domains is accommodated as the testbed to perform the analysis on.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter GP-Based Approach to Comprehensive Quality-Aware Automated Semantic Web Service Composition
next chapter Learning to Describe Collective Search Behavior of Evolutionary Algorithms in Solution Space
Footnotes
1
The scikit-learn library is used with default values.
 
Literature
1.
Koren, Y., Bell, R., Volinsky, C., et al.: Matrix factorization techniques for recommender systems. Computer 42(8), 30–37 (2009)CrossRef
2.
Su, X., Khoshgoftaar, T.M.: A survey of collaborative filtering techniques. Adv. Artif. Intell. 2009, 4 (2009)CrossRef
3.
4.
Rice, J.: The algorithm selection problem. Adv. Comput. 15, 65–118 (1976)CrossRef
5.
6.
7.
Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., Woodward, J.R.: A classification of hyper-heuristic approaches. In: Gendreau, M., Potvin, J.Y. (eds.) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol. 146, pp. 449–468. Springer, Boston (2010)CrossRef
8.
Burke, E.K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., Qu, R.: Hyper-heuristics: a survey of the state of the art. J. Oper. Res. Soc. 64(12), 1695–1724 (2013)CrossRef
9.
Chen, S., Li, Z., Yang, B., Rudolph, G.: Quantum-inspired hyper-heuristics for energy-aware scheduling on heterogeneous computing systems. IEEE Trans. Parallel Distrib. Syst. 27(6), 1796–1810 (2016)CrossRef
10.
11.
Terashima-Marin, H., Morán-Saavedra, A., Ross, P.: Forming hyper-heuristics with gas when solving 2D-regular cutting stock problems. In: IEEE Congress on Evolutionary Computation (CEC), vol. 2, pp. 1104–1110. IEEE (2005)
12.
Sotelo-Figueroa, M.A., Soberanes, H.J.P., Carpio, J.M., Huacuja, H.J.F., Reyes, L.C., Alcaraz, J.A.S., Espinal, A.: Generating bin packing heuristic through grammatical evolution based on bee swarm optimization. In: Melin, P., Castillo, O., Kacprzyk, J. (eds.) Nature-Inspired Design of Hybrid Intelligent Systems. SCI, vol. 667, pp. 655–671. Springer, Cham (2017). doi:10.​1007/​978-3-319-47054-2_​43 CrossRef
13.
Bader-El-Den, M., Poli, R.: Generating SAT local-search heuristics using a GP hyper-heuristic framework. In: Monmarché, N., Talbi, E.-G., Collet, P., Schoenauer, M., Lutton, E. (eds.) EA 2007. LNCS, vol. 4926, pp. 37–49. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-79305-2_​4 CrossRef
14.
Burke, E.K., Hyde, M.R., Kendall, G., Ochoa, G., Ozcan, E., Woodward, J.R.: Exploring hyper-heuristic methodologies with genetic programming. In: Mumford, C.L., Jain, L.C. (eds.) Computational Intelligence. Intelligent Systems Reference Library, vol. 1, pp. 177–201. Springer, Heidelberg (2009)CrossRef
15.
Burke, E.K., MacCarthy, B.L., Petrovic, S., Qu, R.: Knowledge discovery in a hyper-heuristic for course timetabling using case-based reasoning. In: Burke, E., De Causmaecker, P. (eds.) Practice and Theory of Automated Timetabling IV. LNCS, vol. 2740, pp. 276–287. Springer, Heidelberg (2003). doi:10.​1007/​978-3-540-45157-0_​18 CrossRef
16.
Maashi, M., Kendall, G., Özcan, E.: Choice function based hyper-heuristics for multi-objective optimization. Appl. Soft Comput. 28, 312–326 (2015)CrossRef
17.
Marín-Blázquez, J.G., Schulenburg, S.: A hyper-heuristic framework with XCS: learning to create novel problem-solving algorithms constructed from simpler algorithmic ingredients. In: Kovacs, T., Llorà, X., Takadama, K., Lanzi, P.L., Stolzmann, W., Wilson, S.W. (eds.) IWLCS 2003-2005. LNCS, vol. 4399, pp. 193–218. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-71231-2_​14 CrossRef
18.
Cowling, P., Kendall, G., Soubeiga, E.: A hyperheuristic approach to scheduling a sales summit. In: Burke, E., Erben, W. (eds.) PATAT 2000. LNCS, vol. 2079, pp. 176–190. Springer, Heidelberg (2001). doi:10.​1007/​3-540-44629-X_​11 CrossRef
19.
Da Costa, L., Fialho, A., Schoenauer, M., Sebag, M.: Adaptive operator selection with dynamic multi-armed bandits. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO), PP. 913–920. Atlanta, Georgia, USA (2008)
20.
Epitropakis, M.G., Caraffini, F., Neri, F., Burke, E.K.: A separability prototype for automatic memes with adaptive operator selection. In: IEEE Symposium on Foundations of Computational Intelligence (FOCI), PP. 70–77. IEEE (2014)
21.
Kotthoff, L.: Algorithm selection for combinatorial search problems: a survey. AI Mag. 35(3), 48–60 (2014)CrossRef
22.
Park, J., Mei, Y., Nguyen, S., Chen, G., Johnston, M., Zhang, M.: Genetic programming based hyper-heuristics for dynamic job shop scheduling: cooperative coevolutionary approaches. In: Heywood, M.I., McDermott, J., Castelli, M., Costa, E., Sim, K. (eds.) EuroGP 2016. LNCS, vol. 9594, pp. 115–132. Springer, Cham (2016). doi:10.​1007/​978-3-319-30668-1_​8 CrossRef
23.
Sotelo-Figueroa, M., Soberanes, H., Carpio, J., Fraire Huacuja, H., Reyes, L., Soria Alcaraz, J.: Evolving bin packing heuristic using micro-differential evolution with indirect representation. In: Castillo, O., Melin, P., Kacprzyk, J. (eds.) Recent Advances on Hybrid Intelligent Systems, vol. 451, pp. 349–359. Studies in Computational Intelligence. Springer, Heidelberg (2013)CrossRef
24.
Cheeseman, P., Kanefsky, B., Taylor, W.M.: Where the really hard problems are. In: IJCAI, vol. 91, pp. 331–337 (1991)
25.
Jones, T., Forrest, S., et al.: Fitness distance correlation as a measure of problem difficulty for genetic algorithms. ICGA 95, 184–192 (1995)
26.
Ruan, Y., Kautz, H.A., Horvitz, E.: The backdoor key: a path to understanding problem hardness. In: AAAI, vol. 4, pp. 118–123 (2004)
27.
Smith-Miles, K., Lopes, L.: Measuring instance difficulty for combinatorial optimization problems. Comput. Oper. Res. 39(5), 875–889 (2012)MathSciNetCrossRefMATH
28.
Leyton-Brown, K., Hoos, H.H., Hutter, F., Xu, L.: Understanding the empirical hardness of NP-complete problems. Commun. ACM 57(5), 98–107 (2014)CrossRef
29.
van Hemert, J.I.: Evolving combinatorial problem instances that are difficult to solve. Evol. Comput. 14(4), 433–462 (2006)CrossRef
30.
Smith-Miles, K., van Hemert, J.I.: Discovering the suitability of optimisation algorithms by learning from evolved instances. Ann. Math. Artif. Intell. 61(2), 87 (2011)MathSciNetCrossRefMATH
31.
Lopes, L., Smith-Miles, K.: Generating applicable synthetic instances for branch problems. Oper. Res. 61(3), 563–577 (2013)CrossRefMATH
32.
33.
Malitsky, Y., Merschformann, M., O’Sullivan, B., Tierney, K.: Structure-preserving instance generation. In: Festa, P., Sellmann, M., Vanschoren, J. (eds.) LION 2016. LNCS, vol. 10079, pp. 123–140. Springer, Cham (2016). doi:10.​1007/​978-3-319-50349-3_​9 CrossRef
34.
Smith-Miles, K., Tan, T.T.: Measuring algorithm footprints in instance space. In: IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE (2012)
35.
Jolliffe, I.: Principal Component Analysis. Wiley Online Library, Hoboken (2002)MATH
36.
Saul, L.K., Roweis, S.T.: Think globally, fit locally: unsupervised learning of low dimensional manifolds. J. Mach. Learn. Res. 4, 119–155 (2003)MathSciNetMATH
37.
Kaufman, L., Rousseeuw, P.J.: Finding Groups in Data: an Introduction to Cluster Analysis, vol. 344. John Wiley & Sons, Hoboken (2009)MATH
38.
Rousseeuw, P.J.: Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. J. Comput. Appl. Math. 20, 53–65 (1987)CrossRefMATH
39.
40.
Mısır, M.: Intelligent hyper-heuristics: a tool for solving generic optimisation problems. Ph.D. thesis, Department of Computer Science, KU Leuven (2012)
41.
Mısır, M., Handoko, S.D., Lau, H.C.: OSCAR: online selection of algorithm portfolios with case study on memetic algorithms. In: Dhaenens, C., Jourdan, L., Marmion, M.-E. (eds.) LION 2015. LNCS, vol. 8994, pp. 59–73. Springer, Cham (2015). doi:10.​1007/​978-3-319-19084-6_​6 CrossRef
Metadata
Title
Matrix Factorization Based Benchmark Set Analysis: A Case Study on HyFlex
Author
Mustafa Mısır
Copyright Year
2017
Book
Simulated Evolution and Learning

Print ISBN: 978-3-319-68758-2

Electronic ISBN: 978-3-319-68759-9

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-68759-9_16

Premium Partner

    Image Credits