Top

Published in:

2019 | OriginalPaper | Chapter

13. Algorithm Selector and Prescheduler in the ICON Challenge

Authors : François Gonard, Marc Schoenauer, Michèle Sebag

Published in: Bioinspired Heuristics for Optimization

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Algorithm portfolios are known to offer robust performances, efficiently overcoming the weakness of every single algorithm on some particular problem instances. Two complementary approaches to get the best out of an algorithm portfolio are to achieve algorithm selection (AS), and to define a scheduler, sequentially launching a few algorithms on a limited computational budget each. The presented system relies on the joint optimization of a pre-scheduler and a per-instance AS, selecting an algorithm well-suited to the problem instance at hand. ASAP has been thoroughly evaluated against the state-of-the-art during the ICON challenge for algorithm selection, receiving an honorable mention. Its evaluation on several combinatorial optimization benchmarks exposes surprisingly good results of the simple heuristics used; some extensions thereof are presented and discussed in the paper.

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 A Probabilistic Finite State Machine Design of Particle Swarm Optimization

next chapter A Metaheuristic Approach to Compute Pure Nash Equilibria

The increase in the overall number of features is handled by an embedded feature selection mechanism, removing all features with negligible importance criterion (<10\(^{-5}\) in the experiments) in a independently learned 10-trees random forest regression model.

The codes of all submitted systems and the results are publicly available, http://challenge.icon-fet.eu/challengeas.

For CSP-2010 dataset, only two algorithms are available: the pre-scheduler thus consists of a single algorithm, and all ASAP_RF.V2 variants with the same selector hyperparameter are identical.

Remind that these instances are not actually passed to the AS in the challenge evaluation setup

Bischl, B., Kerschke, P., Kotthoff, L., Lindauer, M., Malitsky, Y., Fréchette, A., et al. (2016). Aslib: a benchmark library for algorithm selection. Artificial Intelligence, 237, 41–58.

Branke, J., Deb, K., Dierolf, H., & Osswald, M. (2004). Finding knees in multi-objective optimization. Parallel problem solving from nature-PPSN VIII (pp. 722–731). Berlin: Springer.

Cauwet, M., Liu, J., Rozière, B., & Teytaud, O. (2016). Algorithm portfolios for noisy optimization. Annals of Mathematics and Artificial Intelligence, 76(1–2), 143–172.

Deb, K. (2003). Multi-objective evolutionary algorithms: introducing bias among pareto-optimal solutions. Advances in evolutionary computing (pp. 263–292). Berlin: Springer.

Gagliolo, M., & Schmidhuber, J. (2011). Algorithm portfolio selection as a bandit problem with unbounded losses. Annals of Mathematics and Artificial Intelligence, 61(2), 49–86.

Gomes, C. P., & Selman, B. (2001). Algorithm portfolios. Artificial Intelligence, 126(1), 43–62.

Hansen, N., Müller, S. D., & Koumoutsakos, P. (2003). Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation. Evolutionary Computation, 11(1), 1–18.

Huberman, B. A., Lukose, R. M., & Hogg, T. (1997). An economics approach to hard computational problems. Science, 275(5296), 51–54.CrossRef

Kadioglu, S., Malitsky, Y., Sabharwal, A., Samulowitz, H., & Sellmann, M. (2011). Algorithm selection and scheduling. In Proceedings of the 17th CP (pp. 454–469). LNCS. Berlin: Springer.

10.

Kotthoff, L. (2015). ICON challenge on algorithm selection. CoRR arXiv:abs/1511.04326.

11.

Kotthoff, L. (2016). Algorithm selection for combinatorial search problems: a survey (pp. 149–190). Berlin: Springer International Publishing.

12.

Leyton-Brown, K., Nudelman, E., Andrew, G., McFadden, J., & Shoham, Y. (2003). A portfolio approach to algorithm selection. In Proceedings of the IJCAI (pp. 1542–1543).

13.

Lindauer, M., Bergdoll, R. D., & Hutter, F. (2016). An empirical study of per-instance algorithm scheduling. In Proceedings of the LION10 (pp. 253–259). Berlin: Springer.

14.

Malitsky, Y., Sabharwal, A., & Samulowitz, H. (2013). Algorithm portfolios based on cost-sensitive hierarchical clustering. In Proceedings of the 23rd IJCAI (pp. 608–614). California: AAAI Press.

15.

Mısır, M., & Sebag, M. (2017). Alors: an algorithm recommender system. Artificial Intelligence, 244, 291–314. Published on-line Dec. 2016.

16.

O’Mahony, E., Hebrard, E., Holland, A., Nugent, C., & O’Sullivan, B. (2008). Using case-based reasoning in an algorithm portfolio for constraint solving. In Proceedings of the ICAICS (pp. 210–216).

17.

Oentaryo, R. J., Handoko, S. D., & Lau, H. C. (2015). Algorithm selection via ranking. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI).

18.

Pedregosa, F., et al. (2011). Scikit-learn: machine learning in python. Journal of Machine Learning Research, 12, 2825–2830.

19.

Rice, J. R. (1976). The algorithm selection problem. Advances in Computers, 15, 65–118.

20.

Stern, D., Herbrich, R., Graepel, T., Samulowitz, H., Pulina, L., & Tacchella, A. (2010). Collaborative expert portfolio management. In Proceedings of the 24th AAAI (pp. 179–184).

21.

Wolpert, D., & Macready, W. (1997). No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1), 67–82.

22.

Xu, L., Hutter, F., Hoos, H., & Leyton-Brown, K. (2012). Features for SAT. University of British Columbia.

23.

Xu, L., Hutter, F., & Hoos, H. H. (2008). Satzilla: portfolio-based algorithm selection for sat. Journal of Artificial Intelligence Research, pp. 565–606.

24.

Xu, L., Hutter, F., Shen, J., Hoos, H. H., & Leyton-Brown, K. (2012). Satzilla2012: improved algorithm selection based on cost-sensitive classification models. In Proceedings of the SAT Challenge (pp. 57–58).

25.

Yun, X., & Epstein, S. L. (2012). Learning algorithm portfolios for parallel execution. In Y. Hamadi & M. Schoenauer (Eds.), In Proceedings of the LION 6 (Vol. 7219, pp. 323–338). LNCS. Berlin: Springer.

Title: Algorithm Selector and Prescheduler in the ICON Challenge
Authors: François Gonard
Marc Schoenauer
Michèle Sebag
Publisher: Springer International Publishing
Book: Bioinspired Heuristics for Optimization
Print ISBN: 978-3-319-95103-4

Electronic ISBN: 978-3-319-95104-1

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-319-95104-1_13

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner