Skip to main content

2015 | OriginalPaper | Buchkapitel

OSCAR: Online Selection of Algorithm Portfolios with Case Study on Memetic Algorithms

verfasst von : Mustafa Mısır, Stephanus Daniel Handoko, Hoong Chuin Lau

Erschienen in: Learning and Intelligent Optimization

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

This paper introduces an automated approach called OSCAR that combines algorithm portfolios and online algorithm selection. The goal of algorithm portfolios is to construct a subset of algorithms with diverse problem solving capabilities. The portfolio is then used to select algorithms from for solving a particular (set of) instance(s). Traditionally, algorithm selection is usually performed in an offline manner and requires the need of domain knowledge about the target problem; while online algorithm selection techniques tend not to pay much attention to a careful construction of algorithm portfolios. By combining algorithm portfolios and online selection, our hope is to design a problem-independent hybrid strategy with diverse problem solving capability. We apply OSCAR to design a portfolio of memetic operator combinations, each including one crossover, one mutation and one local search rather than single operator selection. An empirical analysis is performed on the Quadratic Assignment and Flowshop Scheduling problems to verify the feasibility, efficacy, and robustness of our proposed approach.

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!

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!

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!

Literatur
1.
Zurück zum Zitat Rice, J.: The algorithm selection problem. Adv. comput. 15, 65–118 (1976) Rice, J.: The algorithm selection problem. Adv. comput. 15, 65–118 (1976)
2.
Zurück zum Zitat Gomes, C., Selman, B.: Algorithm portfolio design: theory vs. practice. In: Proceedings of the 13th Conference on Uncertainty in Artificial Intelligence (UAI 1997), Providence/Rhode Island, USA, pp. 190–197 (1997) Gomes, C., Selman, B.: Algorithm portfolio design: theory vs. practice. In: Proceedings of the 13th Conference on Uncertainty in Artificial Intelligence (UAI 1997), Providence/Rhode Island, USA, pp. 190–197 (1997)
3.
Zurück zum Zitat Huberman, B., Lukose, R., Hogg, T.: An economics approach to hard computational problems. Science 275, 51 (1997)CrossRef Huberman, B., Lukose, R., Hogg, T.: An economics approach to hard computational problems. Science 275, 51 (1997)CrossRef
4.
Zurück zum Zitat Da Costa, L., Fialho, A., Schoenauer, M., Sebag, M., et al.: Adaptive operator selection with dynamic multi-armed bandits. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2008), Atlanta, Georgia, USA, pp. 913–920 (2008) Da Costa, L., Fialho, A., Schoenauer, M., Sebag, M., et al.: Adaptive operator selection with dynamic multi-armed bandits. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2008), Atlanta, Georgia, USA, pp. 913–920 (2008)
5.
Zurück zum Zitat Burke, E., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., Qu, R.: Hyper-heuristics: a survey of the state of the art. J. Oper. Res. Soc. 64, 1695–1724 (2013)CrossRef Burke, E., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., Qu, R.: Hyper-heuristics: a survey of the state of the art. J. Oper. Res. Soc. 64, 1695–1724 (2013)CrossRef
6.
Zurück zum Zitat Moscato, P., Cotta, C., Mendes, A.: Memetic algorithms. In: Moscato, P., Cotta, C., Mendes, A. (eds.) New Optimization Techniques in Engineering, pp. 53–85. Springer, Heidelberg (2004)CrossRef Moscato, P., Cotta, C., Mendes, A.: Memetic algorithms. In: Moscato, P., Cotta, C., Mendes, A. (eds.) New Optimization Techniques in Engineering, pp. 53–85. Springer, Heidelberg (2004)CrossRef
7.
Zurück zum Zitat Krasnogor, N., Smith, J.: A memetic algorithm with self-adaptive local search: TSP as a case study. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2000), Las Vegas/Nevada, USA, pp. 987–994 (2000) Krasnogor, N., Smith, J.: A memetic algorithm with self-adaptive local search: TSP as a case study. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2000), Las Vegas/Nevada, USA, pp. 987–994 (2000)
8.
Zurück zum Zitat Yuan, Z., Handoko, S.D., Nguyen, D.T., Lau, H.C.: An empirical study of off-line configuration and on-line adaptation in operator selection. In: Pardalos, P.M., Resende, M.G.C., Vogiatzis, C., Walteros, J.L. (eds.) LION 2014. LNCS, vol. 8426, pp. 62–76. Springer International Publishing, Switzerland (2014)CrossRef Yuan, Z., Handoko, S.D., Nguyen, D.T., Lau, H.C.: An empirical study of off-line configuration and on-line adaptation in operator selection. In: Pardalos, P.M., Resende, M.G.C., Vogiatzis, C., Walteros, J.L. (eds.) LION 2014. LNCS, vol. 8426, pp. 62–76. Springer International Publishing, Switzerland (2014)CrossRef
9.
Zurück zum Zitat Runarsson, T.P., Yao, X.: Stochastic ranking for constrained evolutionary optimization. IEEE Trans. Evol. Comput. 4, 284–294 (2000)CrossRef Runarsson, T.P., Yao, X.: Stochastic ranking for constrained evolutionary optimization. IEEE Trans. Evol. Comput. 4, 284–294 (2000)CrossRef
10.
Zurück zum Zitat Handoko, S.D., Kwoh, C.K., Ong, Y.S.: Feasibility structure modeling: an effective chaperone for constrained memetic algorithms. IEEE Trans. Evol. Comput. 14, 740–758 (2010)CrossRef Handoko, S.D., Kwoh, C.K., Ong, Y.S.: Feasibility structure modeling: an effective chaperone for constrained memetic algorithms. IEEE Trans. Evol. Comput. 14, 740–758 (2010)CrossRef
11.
Zurück zum Zitat Xu, L., Hutter, F., Hoos, H., Leyton-Brown, K.: SATzilla: portfolio-based algorithm selection for SAT. J. Artif. Intell. Res. 32, 565–606 (2008)MATH Xu, L., Hutter, F., Hoos, H., Leyton-Brown, K.: SATzilla: portfolio-based algorithm selection for SAT. J. Artif. Intell. Res. 32, 565–606 (2008)MATH
12.
Zurück zum Zitat Kadioglu, S., Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm selection and scheduling. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 454–469. Springer, Heidelberg (2011) CrossRef Kadioglu, S., Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm selection and scheduling. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 454–469. Springer, Heidelberg (2011) CrossRef
13.
Zurück zum Zitat Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm portfolios based on cost-sensitive hierarchical clustering. In: Proceedings of the 23rd International Joint Conference on Artifical Intelligence (IJCAI 2013), pp. 608–614 (2013) Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm portfolios based on cost-sensitive hierarchical clustering. In: Proceedings of the 23rd International Joint Conference on Artifical Intelligence (IJCAI 2013), pp. 608–614 (2013)
14.
Zurück zum Zitat Stern, D., Herbrich, R., Graepel, T., Samulowitz, H., Pulina, L., Tacchella, A.: Collaborative expert portfolio management. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI 2010), Atlanta/Georgia, USA, pp. 179–184 (2010) Stern, D., Herbrich, R., Graepel, T., Samulowitz, H., Pulina, L., Tacchella, A.: Collaborative expert portfolio management. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI 2010), Atlanta/Georgia, USA, pp. 179–184 (2010)
15.
Zurück zum Zitat Xu, L., Hoos, H., Leyton-Brown, K.: Hydra: automatically configuring algorithms for portfolio-based selection. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI 2010), pp. 210–216 (2010) Xu, L., Hoos, H., Leyton-Brown, K.: Hydra: automatically configuring algorithms for portfolio-based selection. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI 2010), pp. 210–216 (2010)
16.
Zurück zum Zitat Hutter, F., Hoos, H., Leyton-Brown, K., Stützle, T.: ParamILS: an automatic algorithm configuration framework. J. Artif. Intell. Res. 36, 267–306 (2009)MATH Hutter, F., Hoos, H., Leyton-Brown, K., Stützle, T.: ParamILS: an automatic algorithm configuration framework. J. Artif. Intell. Res. 36, 267–306 (2009)MATH
17.
Zurück zum Zitat KhudaBukhsh, A.R., Xu, L., Hoos, H.H., Leyton-Brown, K.: Satenstein: automatically building local search sat solvers from components. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), vol. 9, pp. 517–524 (2009) KhudaBukhsh, A.R., Xu, L., Hoos, H.H., Leyton-Brown, K.: Satenstein: automatically building local search sat solvers from components. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), vol. 9, pp. 517–524 (2009)
18.
Zurück zum Zitat O’Mahony, E., Hebrard, E., Holland, A., Nugent, C., O’Sullivan, B.: Using case-based reasoning in an algorithm portfolio for constraint solving. In: Irish Conference on Artificial Intelligence and Cognitive Science (2008) O’Mahony, E., Hebrard, E., Holland, A., Nugent, C., O’Sullivan, B.: Using case-based reasoning in an algorithm portfolio for constraint solving. In: Irish Conference on Artificial Intelligence and Cognitive Science (2008)
19.
Zurück zum Zitat Thierens, D.: An adaptive pursuit strategy for allocating operator probabilities. In: Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO 2005), pp. 1539–1546. ACM (2005) Thierens, D.: An adaptive pursuit strategy for allocating operator probabilities. In: Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO 2005), pp. 1539–1546. ACM (2005)
20.
Zurück zum Zitat Nareyek, A.: Choosing search heuristics by non-stationary reinforcement learning. In: Resende, M., de Sousa, J. (eds.) Metaheuristics: Computer Decision-Making, pp. 523–544. Kluwer Academic Publishers, Dordrecht (2003) CrossRef Nareyek, A.: Choosing search heuristics by non-stationary reinforcement learning. In: Resende, M., de Sousa, J. (eds.) Metaheuristics: Computer Decision-Making, pp. 523–544. Kluwer Academic Publishers, Dordrecht (2003) CrossRef
21.
Zurück zum Zitat Mısır, M.: Intelligent hyper-heuristics: a tool for solving generic optimisation problems. Ph.D. thesis, Department of Computer Science, KU Leuven (2012) Mısır, M.: Intelligent hyper-heuristics: a tool for solving generic optimisation problems. Ph.D. thesis, Department of Computer Science, KU Leuven (2012)
22.
Zurück zum Zitat Guyon, I., Elisseeff, A.: An introduction to variable and feature selection. J. Mach. Learn. Res. 3, 1157–1182 (2003)MATH Guyon, I., Elisseeff, A.: An introduction to variable and feature selection. J. Mach. Learn. Res. 3, 1157–1182 (2003)MATH
24.
Zurück zum Zitat Quinlan, J.R.: C4.5. Programs for Machine Learning. Morgan Kaufmann, San Francisco (1993) Quinlan, J.R.: C4.5. Programs for Machine Learning. Morgan Kaufmann, San Francisco (1993)
26.
Zurück zum Zitat Burkard, R.E., Karisch, S.E., Rendl, F.: Qaplib-a quadratic assignment problem library. J. Global Optim. 10, 391–403 (1997)CrossRefMATHMathSciNet Burkard, R.E., Karisch, S.E., Rendl, F.: Qaplib-a quadratic assignment problem library. J. Global Optim. 10, 391–403 (1997)CrossRefMATHMathSciNet
27.
Zurück zum Zitat Borg, I., Groenen, P.J.: Modern Multidimensional Scaling: Theory and Applications. Springer, New York (2005) Borg, I., Groenen, P.J.: Modern Multidimensional Scaling: Theory and Applications. Springer, New York (2005)
28.
Zurück zum Zitat Taillard, E.: Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64, 278–285 (1993)CrossRefMATH Taillard, E.: Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64, 278–285 (1993)CrossRefMATH
29.
Zurück zum Zitat Mersmann, O., Bischl, B., Trautmann, H., Preuss, M., Weihs, C., Rudolph, G.: Exploratory landscape analysis. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, pp. 829–836. ACM (2011) Mersmann, O., Bischl, B., Trautmann, H., Preuss, M., Weihs, C., Rudolph, G.: Exploratory landscape analysis. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, pp. 829–836. ACM (2011)
Metadaten
Titel
OSCAR: Online Selection of Algorithm Portfolios with Case Study on Memetic Algorithms
verfasst von
Mustafa Mısır
Stephanus Daniel Handoko
Hoong Chuin Lau
Copyright-Jahr
2015
DOI
https://doi.org/10.1007/978-3-319-19084-6_6