nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Lifelong Learning Selection Hyper-heuristics for Constraint Satisfaction Problems

verfasst von : José Carlos Ortiz-Bayliss, Hugo Terashima-Marín, Santiago Enrique Conant-Pablos

Erschienen in: Advances in Artificial Intelligence and Soft Computing

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Selection hyper-heuristics are methods that manage the use of different heuristics and recommend one of them that is suitable for the current problem space under exploration. In this paper we describe a hyper-heuristic model for constraint satisfaction that is inspired in the idea of a lifelong learning process that allows the hyper-heuristic to continually improve the quality of its decisions by incorporating information from every instance it solves. The learning takes place in a transparent way because the learning process is executed in parallel in a different thread than the one that deals with the user’s requests. We tested the model on various constraint satisfaction problem instances and obtained promising results, specially when tested on unseen instances from different classes.

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 On the Model Checking of the Graded -calculus on Trees

Nächstes Kapitel A Parametric Polynomial Deterministic Algorithm for #2SAT

Bitner, J.R., Reingold, E.M.: Backtrack programming techniques. Commun. ACM 18, 651–656 (1975)MATHCrossRef

Bittle, S.A., Fox, M.S.: Learning and using hyper-heuristics for variable and value ordering in constraint satisfaction problems. In: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers, pp. 2209–2212. ACM (2009)

Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting systematic search by weighting constraints. In: European Conference on Artificial Intelligence (ECAI 2004), pp. 146–150 (2004)

Brelaz, D.: New methods to colour the vertices of a graph. Commun. ACM 22, 251–256 (1979)MATHMathSciNetCrossRef

Burke, E., Hart, E., Kendall, G., Newall, J., Ross, P., Shulenburg, S.: Hyper-heuristics: an emerging direction in modern research technology. In: Handbook of metaheuristics, pp. 457–474. Kluwer Academic Publishers (2003)

Capodieci, N., Hart, E., Cabri, G.: Artificial immune systems in the context of autonomic computing: integrating design paradigms. In: Proceedings of the 2014 Conference Companion on Genetic and Evolutionary Computation Companion, GECCO Comp 2014, pp. 21–22. ACM, New York (2014)

Dechter, R., Meiri, I.: Experimental evaluation of preprocessing algorithms for constraint satisfaction problems. Artif. Intell. 38(2), 211–242 (1994)MathSciNetCrossRef

Gagliolo, M., Schmidhuber, J.: Dynamic algorithm portfolios. Ann. Math. Artif. Intell. 47, 3–4 (2006)MathSciNetCrossRef

Gent, I., MacIntyre, E., Prosser, P., Smith, B., T.Walsh: An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem. In: Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP 1996), pp. 179–193 (1996)

10.

Haralick, R.M., Elliott, G.L.: Increasing tree search efficiency for constraint satisfaction problems. Artif. Intell. 14, 263–313 (1980)CrossRef

11.

Hart, E., Sim, K.: On the life-long learning capabilities of a NELLI*: a hyper-heuristic optimisation system. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 282–291. Springer, Heidelberg (2014)

12.

Huberman, B.A., Lukose, R.M., Hogg, T.: An economics approach to hard computational problems. Science 27, 51–53 (1997)CrossRef

13.

Sim, K.E.H., Paechter, B.: A lifelong learning hyper-heuristic method for bin packing. Evol. Comput. 23(1), 37–67 (2015)CrossRef

14.

Minton, S., Johnston, M.D., Phillips, A., Laird, P.: Minimizing conflicts: a heuristic repair method for CSP and scheduling problems. Artif. Intell. 58, 161–205 (1992)MATHCrossRef

15.

O’Mahony, E., Hebrard, E., Holland, A., Nugent, C., O’Sullivan, B.: Using case-based reasoning in an algorithm portfolio for constraint solving. In: Proceedings of the 19th Irish Conference on Artificial Intelligence and Cognitive Science (2008)

16.

Ortiz-Bayliss, J.C., Terashima-Marín, H., Conant-Pablos, S.E.: Learning vector quantization for variable ordering in constraint satisfaction problems. Pattern Recogn. Lett. 34(4), 423–432 (2013)CrossRef

17.

Petrovic, S., Epstein, S.L.: Random subsets support learning a mixture of heuristics. Int. J. Artif. Intell. Tools 17, 501–520 (2008)CrossRef

18.

Rice, J.R.: The algorithm selection problem. Adv. Comput. 15, 65–118 (1976)CrossRef

19.

Ross, P., Marín-Blázquez, J.: Constructive hyper-heuristics in class timetabling. In: Proceedings of the 2005 IEEE Congress on Evolutionary Computation (CEC 2005), vol. 2. IEEE Press (2005)

20.

Silver, D.L.: Machine lifelong learning: challenges and benefits for artificial general intelligence. In: Schmidhuber, J., Thórisson, K.R., Looks, M. (eds.) AGI 2011. LNCS, vol. 6830, pp. 370–375. Springer, Heidelberg (2011) CrossRef

21.

Silver, D.L., Yang, Q., Li, L.: Lifelong machine learning systems: beyond learning algorithms. In: Lifelong Machine Learning, Papers from the 2013 AAAI Spring Symposium, Palo Alto, California, USA, 25–27 March 2013

22.

Sim, K., Hart, E.: An improved immune inspired hyper-heuristic for combinatorial optimisation problems. In: Proceedings of the 2014 Conference on Genetic and Evolutionary Computation, GECCO 2014, pp. 121–128. ACM, New York (2014)

23.

Soto, R., Crawford, B., Monfroy, E., Bustos, V.: Using autonomous search for generating good enumeration strategy blends in constraint programming. In: Murgante, B., Gervasi, O., Misra, S., Nedjah, N., Rocha, A.M.A.C., Taniar, D., Apduhan, B.O. (eds.) ICCSA 2012, Part III. LNCS, vol. 7335, pp. 607–617. Springer, Heidelberg (2012) CrossRef

Titel: Lifelong Learning Selection Hyper-heuristics for Constraint Satisfaction Problems
verfasst von: José Carlos Ortiz-Bayliss
Hugo Terashima-Marín
Santiago Enrique Conant-Pablos
Verlag: Springer International Publishing
Buch: Advances in Artificial Intelligence and Soft Computing
Print ISBN: 978-3-319-27059-3

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

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-27060-9_15

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner