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
Start single access now
Request access for companies
EXTENDED SEARCH
Log in
Top

Hint

Swipe to navigate through the chapters of this book

Published in:
Adaptive and Multilevel Metaheuristics Read chapter Read first chapter

2018 | OriginalPaper | Chapter

3. Data Mining in Stochastic Local Search

Authors : Simone de Lima Martins, Isabel Rosseti, Alexandre Plastino

Published in: Handbook of Heuristics

Publisher: Springer International Publishing

Log in

Abstract

This chapter explores some stochastic local search heuristics that incorporate a data mining procedure. The basic idea of using data mining inside a heuristic is to obtain knowledge from previous iterations performed by a heuristic to guide the search in next iterations. Patterns extracted from good quality solutions can be used to guide the search, leading to a more effective exploration of the solution space. This survey shows that memoryless heuristics may benefit from the use of data mining by obtaining better solutions in smaller computational times. Also, some results are revisited to demonstrate that even memory-based heuristics can benefit from using data mining by reducing the computational time to achieve good quality solutions.

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 Biased Random-Key Genetic Progamming
next chapter Evolution Strategies
Literature
1.
Agrawal R, Imielinski T, Swami A (1993) Mining association rules between sets of items in large databases. In: Proceedings of the ACM SIGMOD international conference on management of data, Washington, DC, pp 207–216
2.
Agrawal R, Srikant R (1994) Fast algorithms for mining association rules in large databases. In: Proceedings of the 20th international conference on very large data bases, Santiago, pp 487–499
3.
Aiex R, Resende MGC, Ribeiro CC (2007) TTTplots: a perl program to create time-to-target plots. Optim Lett 1:355–366
4.
Aloise D, Ribeiro CC (2011) Adaptive memory in multistart heuristics for multicommodity network design. J Heuristics 17:153–179
5.
Barbalho H, Rosseti I, Martins SL, Plastino A (2013) A hybrid data mining GRASP with path-relinking. Comput Oper Res 40:3159–3173
6.
Beasley JE (1985) A note on solving large p-median problems. Eur J Oper Res 21:270–273
7.
Breslau L, Diakonikolas I, Duffield N, Gu Y, Hajiaghayi M, Johnson DS, Karloff H, Resende MGC, Sen S (2011) Disjoint-path facility location: theory and practice. In: Proceedings of the thirteenth workshop of algorithm engineering and experiments (ALENEX11). SIAM, Philadelphia, pp 60–74
8.
Campos V, Piñana E, Martí R (2011) Adaptive memory programming for matrix bandwidth minimization. Ann Oper Res 183:7–23
9.
Chaovalitwongse W, Oliveira C, Chiarini B, Pardalos P, Resende MGC (2011) Revised GRASP with path-relinking for the linear ordering problem. J Comb Optim 22:1–22
10.
Dahl G, Johannessen B (2004) The 2-path network problem. Networks 43:190–199
11.
Eiben A, Smith J (2007) Introduction to evolutionary computing. Springer-Verlag, Berlin
12.
Feo TA, Resende MGC (1995) Greedy randomized adaptive search procedures. J Glob Optim 6:109–133
13.
Fleurent C, Glover F (1999) Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory. INFORMS J Comput 2:198–204
14.
García-Martínez C, Rodriguez F, Lozano M (2012) Arbitrary function optimisation with metaheuristics. Soft Comput 16:2115–2133
15.
Glover F, Laguna M, Martí R (2000) Fundamentals of scatter search and path relinking. Control Cybern 39:653–684
16.
Glover F, Laguna M, Martí R (2003) Scatter search and path relinking: advances and applications. In: Glover F, Kochenberger GA (eds) Handbook of metaheuristics. International series in operations research & management science, vol 57. Springer, Boston, pp 1–35
17.
Goethals B, Zaki MJ (2004) Advances in frequent itemset mining implementations: report on fimi’03. SIGKDD Explor Newsl 6:109–117
18.
Gonçalves LB, Martins SL, Ochi LS (2010) Effective heuristics for the set covering with pairs problem. Int Trans Oper Res 17:739–751
19.
Grahne G, Zhu J (2003) Efficiently using prefix-trees in mining frequent itemsets. In: Proceedings of the IEEE ICDM workshop on frequent itemset mining implementations, Melbourne, Florida, USA
20.
Guerine M, Rosseti I, Plastino A (2014) Extending the hybridization of metaheuristics with data mining to a broader domain. In: Proceedings of the 16th international conference on enterprise systems, Lisboa, pp 395–406
21.
Han J, Kamber M (2011) Data mining: concepts and techniques, 3rd edn. Morgan Kaufmann, San Francisco
22.
Han J, Pei J, Yin Y (2000) Mining frequent patterns without candidate generation. In: Proceedings of the ACM SIGMOD international conference on management of data, Washington, DC, pp 1–12
23.
Hansen P, Mladenović N (1997) Variable neighborhood search for the p-median. Locat Sci 5:207–226 CrossRef
24.
Hansen P, Mladenović N, Perez-Brito D (2001) Variable neighborhood decomposition search. J Heuristics 7:335–350 CrossRef
25.
Hassin R, Segev D (2005) The set cover with pairs problem. In: Sarukkai S, Sen S (eds) FSTTCS 2005: foundations of software technology and theoretical computer science. Lecture notes in computer science, vol 3821. Springer, Berlin/Heidelberg, pp 164–176 CrossRef
26.
Hernández-Pérez H, Salazar-González JJ (2004) A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discret Appl Math 145:453–459 MathSciNetCrossRef
27.
28.
29.
Hoos HH, Stützle T (2005) Stochastic local search: foundations and applications. Elsevier, San Francisco MATH
30.
Igel C, Toussaint M (2003) On classes of functions for which no free lunch results hold. Inf Process Lett IPL 86:317–321 MathSciNetCrossRef
31.
Jourdan L, Dhaenens C, Talbi EG (2006) Using datamining techniques to help metaheuristics: a short survey. In: Almeida F, Blesa Aguilera M, Blum C, Moreno Vega JM, Pérez Pérez M, Roli A, Sampels M (eds) Hybrid metaheuristics. Lecture notes in computer science, vol 4030. Springer, Berlin/Heidelberg, pp 57–69 CrossRef
32.
Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems. II: the p-medians. SIAM J Appl Math 37:513–538 MathSciNetCrossRef
33.
Laguna M, Martí R (1999) GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS J Comput 11:44–52 CrossRef
34.
Li B, Chen F, Yin L (2000) Server replication and its placement for reliable multicast. In: Proceedings of the 9th international conference on computer communication and networks, Las Vegas, pp 396–401
35.
Lin S, Kernighan B (1973) An effective heuristic algorithm for the traveling salesman problem. Oper Res 21:498–516 MathSciNetCrossRef
36.
Lodi A, Allemand K, Liebling TM (1999) An evolutionary heuristic for quadratic 01 programming. Eur J Oper Res 119:662–670 CrossRef
37.
Lourenço HR, Martin OC, Stützle T (2003) Iterated local search. In: Glover F, Kochenberger GA (eds) Handbook of metaheuristics, vol. 57. Springer, Boston, pp 320–353 CrossRef
38.
39.
Plastino A, Barbalho H, Santos LFM, Fuchshuber R, Martins SL (2014) Adaptive and multi-mining versions of the DM-GRASP hybrid metaheuristic. J. Heuristics 20:39–74 CrossRef
40.
Plastino A, Fuchshuber R, Martins SL, Freitas AA, Salhi S (2011) A hybrid data mining metaheuristic for the p-median problem. Stat Anal Data Min 4:313–335 MathSciNetCrossRef
41.
42.
Resende MGC, Ribeiro CC (2005) GRASP with path-relinking: recent advances and applications. In: Ibaraki T, Nonobe K, Yagiura M (eds) Metaheuristics: progress as real problem solvers. Operations research/computer science interfaces series, vol 32. Springer, New York, pp 29–63 CrossRef
43.
Resende MGC, Werneck RF (2003) On the implementation of a swap-based local search procedure for the p-median problem. In: Proceedings of the thirteenth workshop of algorithm engineering and experiments (ALENEX03). SIAM, Baltimore, Maryland, USA, pp 119–127
44.
Resende MGC, Werneck RF (2004) A hybrid heuristic for the p-median problem. J Heuristics 10:59–88 CrossRef
45.
Ribeiro CC, Resende MGC (2012) Path-relinking intensification methods for stochastic local search algorithms. J Heuristics 18:193–214 CrossRef
46.
Ribeiro CC, Rosseti I (2007) Efficient parallel cooperative implementations of GRASP heuristics. Parallel Comput 33:21–35 MathSciNetCrossRef
47.
Ribeiro MH, Plastino A, Martins SL (2006) Hybridization of grasp metaheuristic with data mining techniques. J Math Model Algorithms 5:23–41 MathSciNetCrossRef
48.
Santos HG, Ochi LS, Marinho EH, Drummond LM (2006) Combining an evolutionary algorithm with data mining to solve a single-vehicle routing problem. Neurocomputing 70: 70–77 CrossRef
49.
Santos LF, Martins SL, Plastino A (2008) Applications of the DM-GRASP heuristic: a survey. Int Trans Oper Res 15:387–416 MathSciNetCrossRef
50.
Senne ELF, Lorena LAN (2000) Langrangean/surrogate heuristics for p-median problems. In: Laguna M, González-Velarde JL (eds) Computing tools for modeling, optimization and simulation: interfaces in computer science and operations research. Operations research/computer science interfaces series, vol 32. Kluwer, Boston, pp 115–130 CrossRef
51.
Taillard ED (2003) Heuristic methods for large centroid clustering problems. J Heuristics 9: 51–74 CrossRef
52.
Tan PN, Steinback M, Kumar V (2015) Introduction to data mining, 2nd edn. Addison-Wesley, Boston, MA, USA
53.
Tansel BC, Francis RL, Lowe TJ (1983) A hybrid heuristic for the p-median problem. J Heuristics 29:482–511 MATH
54.
Witten IH, Frank E (2011) Data mining: practical machine learning tools and techniques with java implementations, 3rd edn. Morgan Kaufmann, Burlington
55.
Wolpert DH, Macread WG (1997) No free lunch theorems for optimization. IEEE Trans Evolut Comput 1:67–82 CrossRef
56.
Zaki MJ, Wagner Meira J (2014) Data mining and analysis: fundamental concepts and algorithms. Cambridge University Press, New York CrossRef
Metadata
Title
Data Mining in Stochastic Local Search
Authors
Simone de Lima Martins
Isabel Rosseti
Alexandre Plastino
Copyright Year
2018
Book
Handbook of Heuristics

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

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

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-07124-4_11

Premium Partner

    Image Credits