×

zbMATH — the first resource for mathematics

Hybridization of GRASP metaheuristic with data mining techniques. (English) Zbl 1099.68741
Summary: In this work, we propose a hybridization of GRASP metaheuristic that incorporates a data mining process. We believe that patterns obtained from a set of sub-optimal solutions, by using data mining techniques, can be used to guide the search for better solutions in metaheuristics procedures. In this hybrid GRASP proposal, after executing a significant number of GRASP iterations, the data mining process extracts patterns from an elite set of solutions which will guide the following iterations. To validate this proposal we have worked on the Set Packing Problem as a case study. Computational experiments, comparing traditional GRASP and different hybrid approaches, show that employing frequent patterns mined from an elite set of solutions conducted to better results. Besides, additional performed experiments evidence that data mining strategies accelerate the process of finding good solutions.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
PDF BibTeX Cite
Full Text: DOI
References:
[1] Agrawal, R., Imielinski, T. and Srikant, R.: Mining association rules between sets of items in large databases, in ACM SIGMOD Intl. Conf. on Management of Data, 1993, pp. 207–216.
[2] Agrawal, R. and Srikant, R.: Fast algorithms for mining association rules, in 20th Very Large DataBase Conference, 1994, pp. 487–499.
[3] Bastide, Y., Taouil, R., Pasquier, N., Stumme, G. and Lakhal, L.: Mining frequent patterns with counting inference, ACM SIGKDD Explorations Newsletter 2 (2000), 66–75. · Zbl 0983.68511
[4] Berry, M. L. A. and Linoff, G.: Data Mining Techniques: for Marketing, Sales and Customer Support, Wiley Computer, 1997.
[5] Delorme, X., Gandibleux, X. and Rodriguez, J.: GRASP for set packing problems, Eur. J. Oper. Res. 153 (2003), 564–580. · Zbl 1099.90572
[6] Feo, T. A. and Resende, M. G. C.: Greedy randomized adaptive search procedures, J. Glob. Optim. 6 (1995), 109–133. · Zbl 0822.90110
[7] Gandibleux, X., Delorme, X. and T’Kindt, V.: An ant colony algorithm for the set packing problem, Note de Recherche, no 13, LAMIH-ROI, Université de Valeciennes et du Hainaut-Cambrésis, 2004.
[8] Garey, M. R. and Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, V. H. Freeman and Company, 1979. · Zbl 0411.68039
[9] Guo, Y., Lim, A., Rodrigues, B. and Zhu, Y.: Heuristics for a brokering set packing problem, in 8th Intl. Symposium on Artificial Intelligence and Mathematics, 2004.
[10] Goethals, B. and Zaki, M. J.: Advances in frequent itemset mining implementations: introduction to FIMI’03, in IEEE ICDM Workshop on Frequent Itemset Mining Implementations, 2003.
[11] Grahne, G. and Zhu, J.: Efficiently using prefix-trees in mining frequent itemsets, in IEEE ICDM Workshop on Frequent Itemset Mining Implementations, 2003.
[12] Han, J. and Kamber, M.: Data Mining: Concepts and Techniques, Morgan Kaufmann, 2000. · Zbl 1230.68018
[13] Han, J., Pei, J. and Yin, Y.: Mining frequent patterns without candidate generation, in ACM SIGMOD Intl. Conf. on Management of Data, 2000, pp. 1–12.
[14] Lodi, A., Allemand, K. and Liebling, T. M.: An evolutionary heuristic for quadratic 0-1 programming, Eur. J. Oper. Res. 119 (1999), 662–670. · Zbl 0938.90051
[15] Mingozzi, A., Maniezzo, V., Ricciardelli, S. and Bianco, L.: An exact algorithm for the project scheduling with resource constraints based on a new mathematical formulation, Manag. Sci. 44 (1998), 714–729. · Zbl 1004.90036
[16] Orlando, S., Palmerimi, P. and Perego, R.: Adaptive and resource-aware mining of frequent sets, in IEEE Intl. Conf. on Data Mining, 2002, pp. 338–345.
[17] Orlando, S., Palmerimi, P., Perego, R., Lucchese, C. and Silvestri, F.: kDCI++: A multi–strategy algorithm for discovering frequent sets in large databases, in IEEE ICDM Workshop on Frequent Itemset Mining Implementations, 2003.
[18] Padberg, M. W.: On the facial structure of set packing polyhedra, Math. Program. 5 (1973), 199–215. · Zbl 0272.90041
[19] Pardalos, P. M. and Rodgers, G. P.: Computational aspects of a branch and bound algorithm for quadratic zero-one programming, Computing 45 (1990), 131–144. · Zbl 0721.65034
[20] Park, J. S., Chen, M. and Yu, P. S.: An effective hash-based algorithm for mining association rules, in ACM SIGMOD Intl. Conf. on Management of Data, 1995, pp. 175–186.
[21] Savasere, A., Omiecinski, E. and Navathe, S.: An efficient algorithm for mining association rules in large databases, in 21st Very Large DataBase Conference, 1995, pp. 432–444.
[22] Talbi, E. G.: A taxonomy of hybrid metaheuristics, Journal of Heuristics 8 (2002), 541–564.
[23] Zwaneveld, P. J., Kroon, L. G., Romeijin, H. E., Salomon, M., Dauzères-Pérès, S., Van Hoesel, S. P. and Ambergen, H. W.: Routing trains through railway stations: model formulation and algorithms, Trans. Sci. 30 (1996), 181–194. · Zbl 0884.90079
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.