Skip to main content
main-content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2018 | OriginalPaper | Buchkapitel

3. Data Mining in Stochastic Local Search

verfasst von: Simone de Lima Martins, Isabel Rosseti, Alexandre Plastino

Erschienen in: Handbook of Heuristics

Verlag: Springer International Publishing

share
TEILEN

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.
Literatur
1.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Aiex R, Resende MGC, Ribeiro CC (2007) TTTplots: a perl program to create time-to-target plots. Optim Lett 1:355–366 Aiex R, Resende MGC, Ribeiro CC (2007) TTTplots: a perl program to create time-to-target plots. Optim Lett 1:355–366
4.
Zurück zum Zitat Aloise D, Ribeiro CC (2011) Adaptive memory in multistart heuristics for multicommodity network design. J Heuristics 17:153–179 Aloise D, Ribeiro CC (2011) Adaptive memory in multistart heuristics for multicommodity network design. J Heuristics 17:153–179
5.
Zurück zum Zitat Barbalho H, Rosseti I, Martins SL, Plastino A (2013) A hybrid data mining GRASP with path-relinking. Comput Oper Res 40:3159–3173 Barbalho H, Rosseti I, Martins SL, Plastino A (2013) A hybrid data mining GRASP with path-relinking. Comput Oper Res 40:3159–3173
6.
Zurück zum Zitat Beasley JE (1985) A note on solving large p-median problems. Eur J Oper Res 21:270–273 Beasley JE (1985) A note on solving large p-median problems. Eur J Oper Res 21:270–273
7.
Zurück zum Zitat 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 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.
Zurück zum Zitat Campos V, Piñana E, Martí R (2011) Adaptive memory programming for matrix bandwidth minimization. Ann Oper Res 183:7–23 Campos V, Piñana E, Martí R (2011) Adaptive memory programming for matrix bandwidth minimization. Ann Oper Res 183:7–23
9.
Zurück zum Zitat 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 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.
Zurück zum Zitat Dahl G, Johannessen B (2004) The 2-path network problem. Networks 43:190–199 Dahl G, Johannessen B (2004) The 2-path network problem. Networks 43:190–199
11.
Zurück zum Zitat Eiben A, Smith J (2007) Introduction to evolutionary computing. Springer-Verlag, Berlin Eiben A, Smith J (2007) Introduction to evolutionary computing. Springer-Verlag, Berlin
12.
Zurück zum Zitat Feo TA, Resende MGC (1995) Greedy randomized adaptive search procedures. J Glob Optim 6:109–133 Feo TA, Resende MGC (1995) Greedy randomized adaptive search procedures. J Glob Optim 6:109–133
13.
Zurück zum Zitat Fleurent C, Glover F (1999) Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory. INFORMS J Comput 2:198–204 Fleurent C, Glover F (1999) Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory. INFORMS J Comput 2:198–204
14.
Zurück zum Zitat García-Martínez C, Rodriguez F, Lozano M (2012) Arbitrary function optimisation with metaheuristics. Soft Comput 16:2115–2133 García-Martínez C, Rodriguez F, Lozano M (2012) Arbitrary function optimisation with metaheuristics. Soft Comput 16:2115–2133
15.
Zurück zum Zitat Glover F, Laguna M, Martí R (2000) Fundamentals of scatter search and path relinking. Control Cybern 39:653–684 Glover F, Laguna M, Martí R (2000) Fundamentals of scatter search and path relinking. Control Cybern 39:653–684
16.
Zurück zum Zitat 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 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.
Zurück zum Zitat Goethals B, Zaki MJ (2004) Advances in frequent itemset mining implementations: report on fimi’03. SIGKDD Explor Newsl 6:109–117 Goethals B, Zaki MJ (2004) Advances in frequent itemset mining implementations: report on fimi’03. SIGKDD Explor Newsl 6:109–117
18.
Zurück zum Zitat Gonçalves LB, Martins SL, Ochi LS (2010) Effective heuristics for the set covering with pairs problem. Int Trans Oper Res 17:739–751 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Han J, Kamber M (2011) Data mining: concepts and techniques, 3rd edn. Morgan Kaufmann, San Francisco Han J, Kamber M (2011) Data mining: concepts and techniques, 3rd edn. Morgan Kaufmann, San Francisco
22.
Zurück zum Zitat 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 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.
Zurück zum Zitat Hansen P, Mladenović N (1997) Variable neighborhood search for the p-median. Locat Sci 5:207–226 CrossRef Hansen P, Mladenović N (1997) Variable neighborhood search for the p-median. Locat Sci 5:207–226 CrossRef
24.
Zurück zum Zitat Hansen P, Mladenović N, Perez-Brito D (2001) Variable neighborhood decomposition search. J Heuristics 7:335–350 CrossRef Hansen P, Mladenović N, Perez-Brito D (2001) Variable neighborhood decomposition search. J Heuristics 7:335–350 CrossRef
25.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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
29.
Zurück zum Zitat Hoos HH, Stützle T (2005) Stochastic local search: foundations and applications. Elsevier, San Francisco MATH Hoos HH, Stützle T (2005) Stochastic local search: foundations and applications. Elsevier, San Francisco MATH
30.
Zurück zum Zitat Igel C, Toussaint M (2003) On classes of functions for which no free lunch results hold. Inf Process Lett IPL 86:317–321 MathSciNetCrossRef 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems. II: the p-medians. SIAM J Appl Math 37:513–538 MathSciNetCrossRef 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.
Zurück zum Zitat Laguna M, Martí R (1999) GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS J Comput 11:44–52 CrossRef Laguna M, Martí R (1999) GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS J Comput 11:44–52 CrossRef
34.
Zurück zum Zitat 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 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.
Zurück zum Zitat Lin S, Kernighan B (1973) An effective heuristic algorithm for the traveling salesman problem. Oper Res 21:498–516 MathSciNetCrossRef Lin S, Kernighan B (1973) An effective heuristic algorithm for the traveling salesman problem. Oper Res 21:498–516 MathSciNetCrossRef
36.
Zurück zum Zitat Lodi A, Allemand K, Liebling TM (1999) An evolutionary heuristic for quadratic 01 programming. Eur J Oper Res 119:662–670 CrossRef Lodi A, Allemand K, Liebling TM (1999) An evolutionary heuristic for quadratic 01 programming. Eur J Oper Res 119:662–670 CrossRef
37.
Zurück zum Zitat 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 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
39.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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
42.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Resende MGC, Werneck RF (2004) A hybrid heuristic for the p-median problem. J Heuristics 10:59–88 CrossRef Resende MGC, Werneck RF (2004) A hybrid heuristic for the p-median problem. J Heuristics 10:59–88 CrossRef
45.
Zurück zum Zitat Ribeiro CC, Resende MGC (2012) Path-relinking intensification methods for stochastic local search algorithms. J Heuristics 18:193–214 CrossRef Ribeiro CC, Resende MGC (2012) Path-relinking intensification methods for stochastic local search algorithms. J Heuristics 18:193–214 CrossRef
46.
Zurück zum Zitat Ribeiro CC, Rosseti I (2007) Efficient parallel cooperative implementations of GRASP heuristics. Parallel Comput 33:21–35 MathSciNetCrossRef Ribeiro CC, Rosseti I (2007) Efficient parallel cooperative implementations of GRASP heuristics. Parallel Comput 33:21–35 MathSciNetCrossRef
47.
Zurück zum Zitat Ribeiro MH, Plastino A, Martins SL (2006) Hybridization of grasp metaheuristic with data mining techniques. J Math Model Algorithms 5:23–41 MathSciNetCrossRef Ribeiro MH, Plastino A, Martins SL (2006) Hybridization of grasp metaheuristic with data mining techniques. J Math Model Algorithms 5:23–41 MathSciNetCrossRef
48.
Zurück zum Zitat 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 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.
Zurück zum Zitat Santos LF, Martins SL, Plastino A (2008) Applications of the DM-GRASP heuristic: a survey. Int Trans Oper Res 15:387–416 MathSciNetCrossRef Santos LF, Martins SL, Plastino A (2008) Applications of the DM-GRASP heuristic: a survey. Int Trans Oper Res 15:387–416 MathSciNetCrossRef
50.
Zurück zum Zitat 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 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.
Zurück zum Zitat Taillard ED (2003) Heuristic methods for large centroid clustering problems. J Heuristics 9: 51–74 CrossRef Taillard ED (2003) Heuristic methods for large centroid clustering problems. J Heuristics 9: 51–74 CrossRef
52.
Zurück zum Zitat Tan PN, Steinback M, Kumar V (2015) Introduction to data mining, 2nd edn. Addison-Wesley, Boston, MA, USA Tan PN, Steinback M, Kumar V (2015) Introduction to data mining, 2nd edn. Addison-Wesley, Boston, MA, USA
53.
Zurück zum Zitat Tansel BC, Francis RL, Lowe TJ (1983) A hybrid heuristic for the p-median problem. J Heuristics 29:482–511 MATH Tansel BC, Francis RL, Lowe TJ (1983) A hybrid heuristic for the p-median problem. J Heuristics 29:482–511 MATH
54.
Zurück zum Zitat Witten IH, Frank E (2011) Data mining: practical machine learning tools and techniques with java implementations, 3rd edn. Morgan Kaufmann, Burlington Witten IH, Frank E (2011) Data mining: practical machine learning tools and techniques with java implementations, 3rd edn. Morgan Kaufmann, Burlington
55.
Zurück zum Zitat Wolpert DH, Macread WG (1997) No free lunch theorems for optimization. IEEE Trans Evolut Comput 1:67–82 CrossRef Wolpert DH, Macread WG (1997) No free lunch theorems for optimization. IEEE Trans Evolut Comput 1:67–82 CrossRef
56.
Zurück zum Zitat Zaki MJ, Wagner Meira J (2014) Data mining and analysis: fundamental concepts and algorithms. Cambridge University Press, New York CrossRef Zaki MJ, Wagner Meira J (2014) Data mining and analysis: fundamental concepts and algorithms. Cambridge University Press, New York CrossRef
Metadaten
Titel
Data Mining in Stochastic Local Search
verfasst von
Simone de Lima Martins
Isabel Rosseti
Alexandre Plastino
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-07124-4_11

Premium Partner