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:
Algorithm Portfolios for Noisy Optimization: Compare Solvers Early Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

An Empirical Study of Off-Line Configuration and On-Line Adaptation in Operator Selection

verfasst von : Zhi Yuan, Stephanus Daniel Handoko, Duc Thien Nguyen, Hoong Chuin Lau

Erschienen in: Learning and Intelligent Optimization

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Automating the process of finding good parameter settings is important in the design of high-performing algorithms. These automatic processes can generally be categorized into off-line and on-line methods. Off-line configuration consists in learning and selecting the best setting in a training phase, and usually fixes it while solving an instance. On-line adaptation methods on the contrary vary the parameter setting adaptively during each algorithm run. In this work, we provide an empirical study of both approaches on the operator selection problem, explore the possibility of varying parameter value by a non-adaptive distribution tuned off-line, and incorporate the off-line with on-line approaches. In particular, using an off-line tuned distribution to vary parameter values at runtime appears to be a promising idea for automatic configuration.

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 Evaluating Instance Generators by Configuration
Nächstes Kapitel A Continuous Refinement Strategy for the Multilevel Computation of Vertex Separators
Fußnoten
1
There exist off-line configuration approaches called portfolio-based algorithm selection [5], which returns a portfolio of configurations instead of one fixed configuration, then select a configuration from the portfolio based on the feature of the future instance. However, each of its configurations remains fixed when solving an instance.
 
2
The term is syntactically and semantically analogous to the term mixed strategy widely used in game theory.
 
3
One can even regard the static operator strategy as a degenerate case of a mixed strategy, in which one operator is selected with probability 1, and each of the others with probability 0.
 
4
There are in total 33 instances found in the QAPLIB with size from 50 to 100. We further exclude one of them, esc64a, which is too simple and each algorithm considered in this work will solve it to optimum. Then it results in a total number of 32 instances in the heterogeneous set.
 
5
Comparing with the non-adaptive operator strategy (fixed or mixed strategy), the computational overhead of the on-line adaptation mechanisms in our implementation is around 1 % on instances of size 100, and around 3 % on instances of size 50.
 
6
More sophisticated techniques such as don’t look bit or neighborhood candidate list may speed up local search. However, the development of these techniques is out of the scope of this study.
 
7
However, mutation will be used in restart when the population converges.
 
8
We further generated the box-plot of the median ranks across 10 trials of each instance, and the performance comparison in this median-rank box-plot and the presented confidence-interval plots are almost identical. The confidence-interval plot is shown here instead of median-rank box-plot since it displays additional information of statistical significance by the Friedman test.
 
Literatur
1.
Hamadi, Y., Monfroy, E., Saubion, F. (eds.): Autonomous Search. Springer, Heidelberg (2007)
2.
Hoos, H.H.: Programming by optimization. Commun. ACM 55(2), 70–80 (2012)CrossRef
3.
Battiti, R., Brunato, M., Mascia, F.: Reactive Search and Intelligent Optimization. Springer, New York (2008)MATH
4.
Birattari, M.: Tuning Metaheuristics: A Machine Learning Perspective. Studies in Computational Intelligence, vol. 197. Springer, Heidelberg (2009)
5.
Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla: portfolio-based algorithm selection for SAT. J. Artif. Intell. Res. (JAIR) 32, 565–606 (2008)MATH
6.
Birattari, M., Stützle, T., Paquete, L., Varrentrapp, K.: A racing algorithm for configuring metaheuristics. In: Langdon, W.B., et al. (eds.) Proceedings of GECCO, pp. 11–18. Morgan Kaufmann, San Francisco (2002)
7.
Birattari, M., Yuan, Z., Balaprakash, P., Stützle, T.: F-Race and iterated F-Race: an overview. In: Bartz-Beielstein, T., et al. (eds.) Experimental Methods for the Analysis of Optimization Algorithms, pp. 311–336. Springer, Heidelberg (2010)CrossRef
8.
Hutter, F., Hoos, H.H., Leyton-Brown, K., Stützle, T.: ParamILS: an automatic algorithm configuration framework. J. Artif. Intell. Res. 36, 267–306 (2009)MATH
9.
Ansótegui, C., Sellmann, M., Tierney, K.: A gender-based genetic algorithm for the automatic configuration of algorithms. In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 142–157. Springer, Heidelberg (2009) CrossRef
10.
Hutter, F., Bartz-Beielstein, T., Hoos, H.H., Leyton-Brown, K., Murphy, K.: Sequential model-based parameter optimisation: an experimental investigation of automated and interactive approaches. In: Bartz-Beielstein, T., et al. (eds.) Empirical Methods for the Analysis of Optimization Algorithms, pp. 363–414. Springer, Heidelberg (2010)CrossRef
11.
Yuan, Z., Montes de Oca, M., Birattari, M., Stützle, T.: Continuous optimization algorithms for tuning real and integer parameters of swarm intelligence algorithms. Swarm Intell. 6(1), 49–75 (2012)CrossRef
12.
Angeline, P.J.: Adaptive and self-adaptive evolutionary computations. In: Palaniswami, M., et al. (eds.) Computational Intelligence: A Dynamic Systems Perspective. IEEE Press, New York (1995)
13.
Eiben, A.E., Michalewicz, Z., Schoenauer, M., Smith, J.E.: Parameter control in evolutionary algorithms. In: Lobo, F.G., et al. (eds.) Parameter Setting in Evolutionary Algorithms. SCI, vol. 54, pp. 19–46. Springer, Heidelberg (2007)CrossRef
14.
Lobo, F., Lima, C.F., Michalewicz, Z. (eds.): Parameter Setting in Evolutionary Algorithms. SCI, vol. 54. Springer, Heidelberg (2007)MATH
15.
Fialho, Á., Schoenauer, M., Sebag, M.: Toward comparison-based adaptive operator selection. In: Proceedings of GECCO, pp. 767–774. ACM (2010)
16.
Pellegrini, P., Stützle, T., Birattari, M.: A critical analysis of parameter adaptation in ant colony optimization. Swarm Intell. 6(1), 23–48 (2012)CrossRef
17.
Francesca, G., Pellegrini, P., Stützle, T., Birattari, M.: Off-line and on-line tuning: a study on operator selection for a memetic algorithm applied to the QAP. In: Merz, P., Hao, J.-K. (eds.) EvoCOP 2011. LNCS, vol. 6622, pp. 203–214. Springer, Heidelberg (2011) CrossRef
18.
Mascia, F., Pellegrini, P., Birattari, M., Stützle, T.: An analysis of parameter adaptation in reactive tabu search. Int. Trans. Oper. Res. 21(1), 127–152 (2014)CrossRefMATH
19.
20.
Pardalos, P.M., Wolkowicz, H. (eds.): Quadratic Assignment and Related Problems. DIMACS Series. American Mathematical Society, Providence (1994)MATH
21.
Merz, P., Freisleben, B.: Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans. Evol. Comput. 4(4), 337–352 (2000)CrossRef
22.
Krempser, E., Fialho, Á., Barbosa, H.J.C.: Adaptive operator selection at the hyper-level. In: Coello, C.A.C., Cutello, V., Deb, K., Forrest, S., Nicosia, G., Pavone, M. (eds.) PPSN 2012, Part II. LNCS, vol. 7492, pp. 378–387. Springer, Heidelberg (2012) CrossRef
23.
Fialho, Á., Da Costa, L., Schoenauer, M., Sebag, M.: Extreme value based adaptive operator selection. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 175–184. Springer, Heidelberg (2008) CrossRef
24.
Corne, D.W., Oates, M.J., Kell, D.B.: On fitness distributions and expected fitness gain of mutation rates in parallel evolutionary algorithms. In: Guervós, J.J.M., Adamidis, P.A., Beyer, H.-G., Fernández-Villacañas, J.-L., Schwefel, H.-P. (eds.) PPSN 2002. LNCS, vol. 2439, p. 132. Springer, Heidelberg (2002) CrossRef
25.
Thierens, D.: An adaptive pursuit strategy for allocating operator probabilities. In: Proceedings of IEEE CEC, pp. 1539–1546. IEEE (2005)
26.
Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-time analysis of the multiarmed bandit problem. Mach. Learn. 47(2), 235–256 (2002)CrossRefMATH
27.
Burkard, R.E., Karisch, S.E., Rendl, F.: QAPLIB - a quadratic assignment problem library. J. Global Optim. 10(4), 391–403 (1997)CrossRefMATHMathSciNet
28.
Stützle, T., Fernandes, S.: New benchmark instances for the QAP and the experimental analysis of algorithms. In: Gottlieb, J., Raidl, G.R. (eds.) EvoCOP 2004. LNCS, vol. 3004, pp. 199–209. Springer, Heidelberg (2004) CrossRef
29.
McGeoch, C.: Analyzing algorithms by simulation: variance reduction techniques and simulation speedups. ACM Comput. Surv. (CSUR) 24(2), 195–212 (1992)CrossRef
30.
Yuan, Z., Stützle, T., Montes de Oca, M.A., Lau, H.C., Birattari, M.: An analysis of post-selection in automatic configuration. In: Proceeding of GECCO, pp. 1557–1564. ACM (2013)
31.
Lindawati, Yuan, Z., Lau, H.C., Zhu, F.: Automated parameter tuning framework for heterogeneous and large instances: case study in quadratic assignment problem. In: Nicosia, G., Pardalos, P. (eds.) LION 7. LNCS, vol. 7997, pp. 423–437. Springer, Heidelberg (2013) CrossRef
32.
Taillard, E.: Robust taboo search for the quadratic assignment problem. Parallel Comput. 17(4), 443–455 (1991)CrossRefMathSciNet
33.
Fialho, Á., Da Costa, L., Schoenauer, M., Sebag, M.: Dynamic multi-armed bandits and extreme value-based rewards for adaptive operator selection in evolutionary algorithms. In: Stützle, T. (ed.) LION 3. LNCS, vol. 5851, pp. 176–190. Springer, Heidelberg (2009) CrossRef
34.
Handoko, S.D., Nguyen, D.T., Yuan, Z., Lau, H.C.: Reinforcement learning for adaptive operator selection in memetic search applied to quadratic assignment problem. In: Proceedings of GECCO (2014, to appear)
Metadaten
Titel
An Empirical Study of Off-Line Configuration and On-Line Adaptation in Operator Selection
verfasst von
Zhi Yuan
Stephanus Daniel Handoko
Duc Thien Nguyen
Hoong Chuin Lau
Copyright-Jahr
2014
Buch
Learning and Intelligent Optimization

Print ISBN: 978-3-319-09583-7

Electronic ISBN: 978-3-319-09584-4

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-319-09584-4_7