Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Interleaving Innovization with Evolutionary Multi-Objective Optimization in Production System Simulation for Faster Convergence Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

Algorithm Selection for the Graph Coloring Problem

verfasst von : Nysret Musliu, Martin Schwengerer

Erschienen in: Learning and Intelligent Optimization

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We present an automated algorithm selection method based on machine learning for the graph coloring problem (GCP). For this purpose, we identify \(78\) features for this problem and evaluate the performance of six state-of-the-art (meta) heuristics for the GCP. We use the obtained data to train several classification algorithms that are applied to predict on a new instance the algorithm with the highest expected performance. To achieve better performance for the machine learning algorithms, we investigate the impact of parameters, and evaluate different data discretization and feature selection methods. Finally, we evaluate our approach, which exploits the existing GCP techniques and the automated algorithm selection, and compare it with existing heuristic algorithms. Experimental results show that the GCP solver based on machine learning outperforms previous methods on benchmark instances.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Using Racing to Automatically Configure Algorithms for Scaling Performance
Nächstes Kapitel Batched Mode Hyper-heuristics
Fußnoten
1
Available at http://​mat.​gsia.​cmu.​edu/​COLOR04/​, last visited on 22.10.2012
 
2
Available at www.​imada.​sdu.​dk/​~marco/​gcp-study/​, last visited on 28.10.2012
 
Literatur
1.
Blöchliger, I., Zufferey, N.: A graph coloring heuristic using partial solutions and a reactive tabu scheme. Comput. Oper. Res. 35(3), 960–975 (2008)MathSciNetCrossRefMATH
2.
Bouckaert, R.R., Frank, E., Hall, M., Kirkby, R., Reutemann, P., Seewald, A., Scuse, D.: Weka manual (3.6.6), October 2011
3.
Brélaz, D.: New methods to color the vertices of a graph. Commun. ACM 22, 251–256 (1979)CrossRefMATH
4.
Brown, K.L., Nudelman, E., Shoham, Y.: Empirical hardness models: methodology and a case study on combinatorial auctions. J. ACM 56(4), 1–52 (2009)MathSciNetCrossRef
5.
6.
Chiarandini, M.: Stochastic local search methods for highly constrained combinatorial optimisation problems. Ph.D. thesis, TU Darmstadt, August 2005
7.
Chiarandini, M., Dumitrescu, I., Stützle, T.: Stochastic local search algorithms for the graph colouring problem. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall/CRC, Boca Raton (2007)
8.
Chiarandini, M., Stützle, T.: An application of iterated local search to graph coloring. In: Johnson, D.S., Mehrotra, A., Trick, M.A. (eds.) Proceedings of the Computational Symposium on Graph Coloring and its Generalizations (2002)
9.
Chiarandini, M., Stützle, T.: An analysis of heuristics for vertex colouring. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 326–337. Springer, Heidelberg (2010)
10.
Culberson, J.C., Luo, F.: Exploring the k-colorable landscape with iterated greedy. In: Dimacs Series in Discrete Mathematics and Theoretical Computer Science, pp. 245–284. American Mathematical Society, Providence (1995)
11.
Dougherty, J., Kohavi, R., Sahami, M.: Supervised and unsupervised discretization of continuous features. In: Machine Learning: Proceedings of the Twelfth International Conference, pp. 194–202. Morgan Kaufmann, San Francisco (1995)
12.
Ewald, R.: Experimentation methodology. In: Ewald, R. (ed.) In: Automatic Algorithm Selection for Complex Simulation Problems, pp. 203–246. Vieweg+Teubner Verlag, Wiesbaden (2012)CrossRef
13.
Fayyad, U.M., Irani, K.B.: Multi-interval discretization of continuous-valued attributes for classification learning. In: Bajcsy, R. (ed.) IJCAI. Morgan Kaufmann, San Mateo (1993)
14.
15.
Freeman, L.C.: A set of measures of centrality based on betweenness. Sociometry 40(1), 35–41 (1977)CrossRef
16.
17.
Garey, M.R., Johnson, D.S., Hing, S.C.: An application of graph coloring to printed circuit testing. IEEE Trans. Circ. Syst. (1976)
18.
Guerri, A., Milano, M.: Learning techniques for automatic algorithm portfolio selection. In: de Mántaras, R.L., Saitta, L. (eds.) In: Conference on Artificial Intelligence, ECAI’2004, pp. 475–479. IOS Press, Amsterdam (2004)
19.
Guo, H., Hsu, W.H.: A machine learning approach to algorithm selection for NP-hard optimization problems: a case study on the MPE problem. Ann. Oper. Res. 156, 61–82 (2007)MathSciNetCrossRefMATH
20.
Hage, P., Harary, F.: Eccentricity and centrality in networks. Soc. Netw. 17(1), 57–63 (1995)CrossRef
21.
22.
Johnson, D.J., Trick, M.A. (eds) Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 11–13 October 1993. American Mathematical Society (1996)
23.
Kanda, J., de Carvalho, A.C.P.L.F., Hruschka, E.R., Soares, C.: Selection of algorithms to solve traveling salesman problems using meta-learning. Int. J. Hybrid Intell. Syst. 8(3), 117–128 (2011)
24.
Kononenko, I.: On biases in estimating multi-valued attributes. In: IJCAI. Morgan Kaufmann, San Francisco (1995)
25.
26.
Lewis, R., Thompson, J., Mumford, C.L., Gillard, J.W.: A wide-ranging computational comparison of high-performance graph colouring algorithms. Comput. Oper. Res. 39(9), 1933–1950 (2012)MathSciNetCrossRefMATH
27.
28.
Malaguti, E., Monaci, M., Toth, P.: A metaheuristic approach for the vertex coloring problem. INFORMS J. Comput. 20(2), 302–316 (2008)MathSciNetCrossRefMATH
29.
30.
Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Non-model-based algorithm portfolios for SAT. In: Sakallah, K.A., Simon, L. (eds.) SAT 2011. LNCS, vol. 6695, pp. 369–370. Springer, Heidelberg (2011)
31.
Messelis, T., De Causmaecker, P.: An algorithm selection approach for nurse rostering. In: Proceedings of BNAIC 2011, Nevelland, pp. 160–166, November (2011)
32.
Morak, M., Musliu, N., Pichler, R., Rümmele, S., Woltran, S.: Evaluating tree-decomposition based algorithms for answer set programming. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, vol. 7219, pp. 130–144. Springer, Heidelberg (2012)
33.
Nadeau, C., Bengio, Y.: Inference for the generalization error. Mach. Learn. 52(3), 239–281 (2003)CrossRefMATH
34.
Nudelman, E.: Empirical approach to the complexity of hard problems. Ph.D. thesis, Stanford University, Stanford, CA, USA (2006)
35.
Pardalos, P., Mavridou, T., Xue, J.: The Graph Coloring Problem: A Bibliographic Survey, pp. 331–395. Kluwer Academic Publishers, Boston (1998)
36.
37.
Rice, J.R.: The algorithm selection problem. Adv. Comput. 15, 65–118 (1976)CrossRef
38.
Schwengerer, M.: Algorithm selection for the graph coloring problem. Vienna University of Technology, Master’s thesis, October 2012
39.
Smith-Miles, K.: Towards insightful algorithm selection for optimisation using meta-learning concepts. In: IEEE International Joint Conference on Neural Networks. IEEE, New York (2008)
40.
Smith-Miles, K., Lopes, L.: Measuring instance difficulty for combinatorial optimization problems. Comput. OR 39(5), 875–889 (2012)MathSciNetCrossRefMATH
41.
Smith-Miles, K., van Hemert, J., Lim, X.Y.: Understanding TSP difficulty by learning from evolved instances. In: Blum, C., Battiti, R. (eds.) LION 2010. LNCS, vol. 6073, pp. 266–280. Springer, Heidelberg (2010)
42.
Smith-Miles, K., Wreford, B., Lopes, L., Insani, N.: Predicting metaheuristic performance on graph coloring problems using data mining. In: El Talbi, G. (ed.) Hybrid Metaheuristics. SCI, pp. 3–76. Springer, Heidelberg (2013)
43.
Venkatesan, R., Levin, L.: Random instances of a graph coloring problem are hard. Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, pp. 217–222. ACM, New York (1988)CrossRef
44.
Watts, D.J., Strogatz, S.M.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440–442 (1998)CrossRef
45.
Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1(1), 67–82 (1997)CrossRef
46.
47.
Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla: portfolio-based algorithm selection for sat. J. Artif. IntelL. Res. 32, 565–606 (2008)MATH
48.
Zufferey, N., Giaccari, P.: Graph colouring approaches for a satellite range scheduling problem. J. Schedul. 11(4), 263–277 (2008)MathSciNetCrossRefMATH
Metadaten
Titel
Algorithm Selection for the Graph Coloring Problem
verfasst von
Nysret Musliu
Martin Schwengerer
Copyright-Jahr
2013
Verlag
Springer Berlin Heidelberg
Buch
Learning and Intelligent Optimization

Print ISBN: 978-3-642-44972-7

Electronic ISBN: 978-3-642-44973-4

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-3-642-44973-4_42