Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
An Importance Sampling Approach to the Estimation of Algorithm Performance in Automated Algorithm Design Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Learning a Reactive Restart Strategy to Improve Stochastic Search

Authors : Serdar Kadioglu, Meinolf Sellmann, Markus Wagner

Published in: Learning and Intelligent Optimization

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Building on the recent success of bet-and-run approaches for restarted local search solvers, we introduce the idea of learning online adaptive restart strategies. Universal restart strategies deploy a fixed schedule that runs with utter disregard of the characteristics that each individual run exhibits. Whether a run looks promising or abysmal, it gets run exactly until the predetermined limit is reached. Bet-and-run strategies are at least slightly less ignorant as they decide which trial to use for a long run based on the performance achieved so far. We introduce the idea of learning fully adaptive restart strategies for black-box solvers, whereby the learning is performed by a parameter tuner. Numerical results show that adaptive strategies can be learned effectively and that these significantly outperform bet-and-run strategies.

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 An Iterated Local Search Framework with Adaptive Operator Selection for Nurse Rostering
next chapter Efficient Adaptive Implementation of the Serial Schedule Generation Scheme Using Preprocessing and Bloom Filters
Footnotes
1
We say black-box because we do not need to know anything about the inner workings of the solver. However, we make two assumptions. First, that we can set a time limit to the solver where it stops, and that we can add more time and continue the interrupted computation later. Second, that whenever the solver stops it returns information when it found the first solution, when it found the best solution so far, and what the quality of the best solution found so far is.
 
2
This best possible solution is the best solution provided within the given time limit by any of the 10,000 runs we conducted.
 
Literature
1.
Gomes, C.P., Selman, B., Crato, N., Kautz, H.A.: Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. J. Autom. Reason. 24(1), 67–100 (2000)CrossRefMATHMathSciNet
2.
Hoos, H.H.: Stochastic local search - methods, models, applications. Ph.D. thesis, TU Darmstadt (1998)
3.
4.
5.
6.
Marti, R.: Multi-start methods. In: Glover, F., Kochenberger, G.A. (eds.) Handbook of Metaheuristics, pp. 355–368 (2003)
7.
Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search: framework and applications. In: Gendreau, M., Potvin, J.Y. (eds.) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol. 146, pp. 363–397. Springer, Boston (2010). doi:10.​1007/​978-1-4419-1665-5_​12 CrossRef
8.
Schoenauer, M., Teytaud, F., Teytaud, O.: A rigorous runtime analysis for quasi-random restarts and decreasing stepsize. In: Hao, J.-K., Legrand, P., Collet, P., Monmarché, N., Lutton, E., Schoenauer, M. (eds.) EA 2011. LNCS, vol. 7401, pp. 37–48. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-35533-2_​4 CrossRef
9.
10.
Huang, J.: The effect of restarts on the efficiency of clause learning. In: International Joint Conference on Artificial Intelligence (IJCAI), pp. 2318–2323 (2007)
11.
Lalla-Ruiz, E., Voß, S.: Improving solver performance through redundancy. Syst. Sci. Syst. Eng. 25(3), 303–325 (2016)CrossRef
12.
13.
Friedrich, T., Kötzing, T., Wagner, M.: A generic bet-and-run strategy for speeding up stochastic local search. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pp. 801–807 (2017)
14.
Lissovoi, A., Sudholt, D., Wagner, M., Zarges, C.: Theoretical results on bet-and-run as an initialisation strategy. In: Genetic and Evolutionary Computation Conference (GECCO) (2017, accepted for publication)
15.
Stützle, T., López-Ibáñez, M.: Automatic (offline) configuration of algorithms. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 795–818 (2016)
16.
Bezerra, L.C.T., López-Ibáñez, M., Stützle, T.: Automatic component-wise design of multiobjective evolutionary algorithms. IEEE Trans. Evol. Comput. 20(3), 403–417 (2016)CrossRef
17.
Ansótegui, C., Pon, J., Tierney, K., Sellmann., M.: Reactive dialectic search portfolios for MaxSAT. In: AAAI Conference on Artificial Intelligence (2017, accepted for publication)
18.
19.
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). doi:10.​1007/​978-3-642-04244-7_​14 CrossRef
20.
21.
Polacek, M., Doerner, K.F., Hartl, R.F., Kiechle, G., Reimann, M.: Scheduling periodic customer visits for a traveling salesperson. Eur. J. Oper. Res. 179, 823–837 (2007)CrossRefMATH
22.
Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2011)MATH
23.
Applegate, D.L., Cook, W.J., Rohe, A.: Chained Lin-Kernighan for large traveling salesman problems. INFORMS J. Comput. 15(1), 82–92 (2003)CrossRefMATHMathSciNet
24.
25.
26.
Gomes, F.C., Meneses, C.N., Pardalos, P.M., Viana, G.V.R.: Experimental analysis of approximation algorithms for the vertex cover and set covering problems. Comput. Oper. Res. 33(12), 3520–3534 (2006)CrossRefMATH
27.
Abu-Khzam, F.N., Langston, M.A., Shanbhag, P., Symons, C.T.: Scalable parallel algorithms for FPT problems. Algorithmica 45(3), 269–284 (2006)CrossRefMATHMathSciNet
28.
Cai, S.: Balance between complexity and quality: local search for minimum vertex cover in massive graphs. In: International Joint Conference on Artificial Intelligence (IJCAI), pp. 747–753 (2015). Code: http://​lcs.​ios.​ac.​cn/​caisw/​MVC.​html. Accessed 21 Dec 2016
29.
Cai, S., Su, K., Luo, C., Sattar, A.: NuMVC: an efficient local search algorithm for minimum vertex cover. J. Artif. Intell. Res. 46(1), 687–716 (2013)MATHMathSciNet
30.
Ansótegui, C., Malitsky, Y., Samulowitz, H., Sellmann, M., Tierney, K.: Model-based genetic algorithms for algorithm configuration. In: International Joint Conference on Artificial Intelligence (IJCAI), pp. 733–739 (2015)
Metadata
Title
Learning a Reactive Restart Strategy to Improve Stochastic Search
Authors
Serdar Kadioglu
Meinolf Sellmann
Markus Wagner
Copyright Year
2017
Book
Learning and Intelligent Optimization

Print ISBN: 978-3-319-69403-0

Electronic ISBN: 978-3-319-69404-7

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-69404-7_8

Premium Partner

    Image Credits