Automatic Tuning of GRASP with Path-Relinking in data clustering with F-Race and iterated F-Race
Abstract
In studies that use metaheuristics although the input parameters directly influence the performance of the algorithm its definition is mostly done manually raising questions about the quality of the results. This paper aims to apply the F/I-Race in the self parameterization of GRASP with Path-Relinking in the data clustering in order to obtain better results than the manually tuned algorithms. Experiments performed with five data sets showed that the use of I/F-race contributed to achievement best results than manual tuning.
Keywords:
Auto-parametrização, I/F-Race, GRASP, Path-Relinking, Agrupamento de Dados
References
Aiex, R. M.; Resende, M. G. & Ribeiro, C. C. (2007). “TTT plots: a perl program to create time-to-target plots”. Optimization Letters 1.4, pp. 355-366.
Binato, S.; de Oliveira, G. & de Araujo, J. (2002). A greedy randomized adaptive search procedure for transmission expansion planning. IEEE Transactions on Power Systems, 16(2) pp. 247-253.
Birattari, M. & Dorigo, M. (2004). "The problem of tuning metaheuristics as seen from a machine learning perspective." PhD thesis, Univerité Libre de Bruxelles, Brussels, Belgium.
Birattari, M.; Stützle, T; Paquete, L. & Varrentrapp, K. (2002). "A Racing Algorithm for Configuring Metaheuristics." GECCO. Vol. 2.
Birattari, M.; Stützle, T; Paquete, L. & Varrentrapp, K. (2009) “Tuning metaheuristics: a machine learning perspective”. Springer, Vol. 197.
Birattari, M.; Yuan, Z; Balaprakash, P. & Stützle, T. (2010). "F-Race and iterated F-Race: An overview." Experimental methods for the analysis of optimization algorithms, pp. 311- 336, Springer Berlin Heidelberg.
Botelho, A. L. V.; Semaan, G. S. & Ochi, L. S. (2011) "Agrupamento de Sistemas Orientados a Objetos com Metaheurísticas Evolutivas" Anais do VII Simpósio Brasileiro de Sistemas de Informação. págs. 153 – 165.
Brown, D. E. & Huntley, C. L. (1992). A practical application of simulated annealing to clustering. In Pattern Recognition, pp. 401–412.
Christopher, J., Function to sample according to a truncated normal distribution. 2011. https://github.com/cran/Irace/blob/master/R/tnorm.R. Acessado em 22/10/2014.
CIRG - Computational Intelligence Research Group (CIRG@UP) Department of Computer Science University of Pretoria South Africa. Biblioteca CILIB. 2010. http://www.cilib.net/. Acessado em 22/10/2014.
Conover, W. J. (1999). Practical Nonparametric Statistics, 3rd Edition, New York: John Wiley & Sons.
Dobslaw, F. (2010). A parameter tuning framework for metaheuristics based on design of experiments and artificial neural networks. In Proceeding of the International Conference on Computer Mathematics and Natural Computing 2010. WASET.
Du , K.-L. (2010). Clustering: A neural network approach, Neural Networks, Volume 23, Issue 1, pp. 89- 107.
Evett, I. W., & Spiehler, E. J. (1987). “Rule induction in forensic science”. KBS in Goverment, Online Publications, páginas 107-118.
Feo, T. A. & Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of global optimization, 6(2), pp 109-133.
Festa, P.; Gonçalves, J. F.; Resende, M. G. & Silva, R. M. (2010). “Automatic tuning of GRASP with path-relinking heuristics with a biased random-key genetic algorithm”. In Experimental Algorithms, pp. 338-349. Springer Berlin Heidelberg.
Frinhani, R. M. D.; Silva, R. M. A. & Mateus, G. R. (2011). “GRASP com Path-Relinking para agrupamento de dados biológicos”. Dissertação de Mestrado. Universidade Federal de Minas Gerais, Departamento de Ciência da Computação.
FSF - Free Software Foundation. Biblioteca Renjin, 2007. http://www.renjin.org/. Acessado em 22/10/2014.
Glover, F. & Marti, R. (2006). “Tabu search”. In Metaheuristic procedures for training neutral networks, pp. 53-69.
Glover, F. (1997). “Tabu search and adaptive memory programming: advances, applications and challenges. In Interfaces in computer science and operations research” pp. 1-75. Springer US.
Glover, F.; Laguna, M. & Martı, R. (2000). Fundamentals of scatter search and Path-Relinking. In Control and Cybernetics, pp. 653–684.
Gonçalves, J. F. & Resende, M. G. (2011). Biased randomkey genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5), 487-525.
Google Inc. Biblioteca Google-Collections .2007. http:// code.google.com/p/google-collections/. Acessado em 22/10/2014.
Hall, L.; Ozyurt, B. & Bezdek, J. (1999). Clustering with a genetically optmized aproach. In Evolutionary Computation, pp 103–112.
Hamadi, Y.; Monfroy, E. & Saubion, F. (2012) “Autonomous Search” XVI, 308 p., ISBN: 978-3-642-21433-2, Springer.
Hartigan, J. A. & Wong, M. A. (1979). “Algorithm AS 136: A k-means clustering algorithm.” Applied statistics, pp 100- 108.
Hubert, L. & Arabie, P. (1985). Comparing partitions. Journal of Classification, 2(1):193-218.
Jain, A. K. & Dubes, R. C. (1988). “Algorithms for clustering data.”. Englewood Cliffs. Prentice-Hall.
Kaufman, L. & Rousseeuw, P. J. (1990). “Partitioning around medoids (program pam).” Finding groups in data: an introduction to cluster analysis, pp 68-125.
Lee, D.; Chen, J. & Cao, J. (2010). “The continuous berth allocation problem: A greedy randomized adaptive search solution”. Transportation Research Part E: Logistics and Transportation Review, 46(6):1017-1029.
Lopes, M. C. S. (2004). Mineração de dados textuais utilizando técnicas de clustering para o idioma português.
Doctoral dissertation, Departamento de Engenharia Civil. Universidade Federal do Rio de Janeiro.
López-Ibánez, M.; Dubois-Lacoste, J.; Stützle, T.; & Birattari, M. (2011). The irace package: Iterated racing for automatic algorithm configuration. Tech. Rep. TR/IRIDIA/2011-004, Université Libre de Bruxelles, Belgium.
Maron, O. & Moore, A.W. (1994). Hoeffding races: Accelerating model selection search for classification and function approximation. In: Cowan J. D., et al. (eds), Advances in Neural Information Processing Systems Morgan Kaufmann , San Francisco, CA, USA, vol 6, pp. 59–66.
Matsumoto, M. & Nishimura, T. (1998). Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation, 8:3-30.
Monti, S.; Savage, K.; Kutok, J.; Feuerhake, F.; Kurtin, P.; Mihm, M.; Wu, B.; Pasqualucci, L.; & Others. (2005) “Molecular profiling of difuse large B-cell lymphoma identifies robust subtypes including one characterized by host inflammatory response. Blood, 105(5):1851-1861.
Morán-Mirabal, L. F.; González-Velarde, J. L. & Resende, M. G. (2013). Automatic tuning of GRASP with evolutionary path-relinking. In Hybrid Metaheuristics (pp. 62-77). Springer Berlin Heidelberg.
Morris, T.; Bjarnason, R.; Adams, T; Clow, B; Clarkson, R; Partridge, N. & Zaugg, T. (2010) Biblioteca functionaljava. Regents of the University of California. Site: http://www.functionaljava.org/. Acessado em 22/10/2014.
Nascimento, M.; Toledo, F. & de Carvalho, A. (2010). Investigation of a new grasp based clustering algorithm applied to biological data. In Computers and Operations Research, pp 1381–1388.
Ohata, A. T.; & Quintanilha, J. A. (2005). O uso de algoritmos de clustering na mensuração da expansão urbana e detecção de alterações na Região Metropolitana de São Paulo. Anais do XII Simpósio Brasileiro de Sensoriamento Remoto, Goiânia, Brasil, 16–21 de Abril de 2005, 647-655.
Ozbay, Y.; Ceylan, R. & Karlik, B. (2006). A fuzzy clustering neural network architecture for classification of ecg arrhythmias. In Computers in Biology and Medicine, pp 376–388.
Papoulis, A. (1991) & Random Variable Probability. "Stochastic Processes. " McGraw-Hill.
Resende, M. G. & Ribeiro, C. C.(2005). GRASP with pathrelinking: Recent advances and applications. In Metaheuristics: progress as real problem solvers, pp. 29-63. Springer US.
Resende, M. G. C.; Ribeiro, C. C.; Glover, F. & Martí, R. (2010b). Scatter search and path-relinking: Fundamentals, advances and applications. Handbook of Metaheuristics, pp. 87-107.
Sirdey, R.; Carlier, J. & Nace, D. (2010). A GRASP for a resource-constrained scheduling problem. International Journal of Innovative Computing and Applications, 2(3):143- 149.
Spolaôr, N.; Lee, H. D.; Ferrero, C. A.; Coy, C. S. R., Fagundes; J. J., Wu; F. C.; ... & de Coloproctologia, S. (2008). Um Estudo da Aplicação de Clustering de Séries Temporais em Dados Médicos.
Su, A.; Cooke, M.; Ching, K.; Hakak, Y.; Walker, J.; Wiltshire, T.; Orth, A.; Vega, R.; Sapinoso, L.; Moqrich, A. & Others (2002). Large-scale analysis of the human and mouse transcriptomes. Proceedings of the National Academy of Sciences, 99(7):4465-4470.
Zlochin, M.; Birattari, M.; Meuleau, N. & Dorigo M. (2004) "Model-based search for combinatorial optimization: A critical survey." Annals of Operations Research, vol 131. pp 373-395.
Binato, S.; de Oliveira, G. & de Araujo, J. (2002). A greedy randomized adaptive search procedure for transmission expansion planning. IEEE Transactions on Power Systems, 16(2) pp. 247-253.
Birattari, M. & Dorigo, M. (2004). "The problem of tuning metaheuristics as seen from a machine learning perspective." PhD thesis, Univerité Libre de Bruxelles, Brussels, Belgium.
Birattari, M.; Stützle, T; Paquete, L. & Varrentrapp, K. (2002). "A Racing Algorithm for Configuring Metaheuristics." GECCO. Vol. 2.
Birattari, M.; Stützle, T; Paquete, L. & Varrentrapp, K. (2009) “Tuning metaheuristics: a machine learning perspective”. Springer, Vol. 197.
Birattari, M.; Yuan, Z; Balaprakash, P. & Stützle, T. (2010). "F-Race and iterated F-Race: An overview." Experimental methods for the analysis of optimization algorithms, pp. 311- 336, Springer Berlin Heidelberg.
Botelho, A. L. V.; Semaan, G. S. & Ochi, L. S. (2011) "Agrupamento de Sistemas Orientados a Objetos com Metaheurísticas Evolutivas" Anais do VII Simpósio Brasileiro de Sistemas de Informação. págs. 153 – 165.
Brown, D. E. & Huntley, C. L. (1992). A practical application of simulated annealing to clustering. In Pattern Recognition, pp. 401–412.
Christopher, J., Function to sample according to a truncated normal distribution. 2011. https://github.com/cran/Irace/blob/master/R/tnorm.R. Acessado em 22/10/2014.
CIRG - Computational Intelligence Research Group (CIRG@UP) Department of Computer Science University of Pretoria South Africa. Biblioteca CILIB. 2010. http://www.cilib.net/. Acessado em 22/10/2014.
Conover, W. J. (1999). Practical Nonparametric Statistics, 3rd Edition, New York: John Wiley & Sons.
Dobslaw, F. (2010). A parameter tuning framework for metaheuristics based on design of experiments and artificial neural networks. In Proceeding of the International Conference on Computer Mathematics and Natural Computing 2010. WASET.
Du , K.-L. (2010). Clustering: A neural network approach, Neural Networks, Volume 23, Issue 1, pp. 89- 107.
Evett, I. W., & Spiehler, E. J. (1987). “Rule induction in forensic science”. KBS in Goverment, Online Publications, páginas 107-118.
Feo, T. A. & Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of global optimization, 6(2), pp 109-133.
Festa, P.; Gonçalves, J. F.; Resende, M. G. & Silva, R. M. (2010). “Automatic tuning of GRASP with path-relinking heuristics with a biased random-key genetic algorithm”. In Experimental Algorithms, pp. 338-349. Springer Berlin Heidelberg.
Frinhani, R. M. D.; Silva, R. M. A. & Mateus, G. R. (2011). “GRASP com Path-Relinking para agrupamento de dados biológicos”. Dissertação de Mestrado. Universidade Federal de Minas Gerais, Departamento de Ciência da Computação.
FSF - Free Software Foundation. Biblioteca Renjin, 2007. http://www.renjin.org/. Acessado em 22/10/2014.
Glover, F. & Marti, R. (2006). “Tabu search”. In Metaheuristic procedures for training neutral networks, pp. 53-69.
Glover, F. (1997). “Tabu search and adaptive memory programming: advances, applications and challenges. In Interfaces in computer science and operations research” pp. 1-75. Springer US.
Glover, F.; Laguna, M. & Martı, R. (2000). Fundamentals of scatter search and Path-Relinking. In Control and Cybernetics, pp. 653–684.
Gonçalves, J. F. & Resende, M. G. (2011). Biased randomkey genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5), 487-525.
Google Inc. Biblioteca Google-Collections .2007. http:// code.google.com/p/google-collections/. Acessado em 22/10/2014.
Hall, L.; Ozyurt, B. & Bezdek, J. (1999). Clustering with a genetically optmized aproach. In Evolutionary Computation, pp 103–112.
Hamadi, Y.; Monfroy, E. & Saubion, F. (2012) “Autonomous Search” XVI, 308 p., ISBN: 978-3-642-21433-2, Springer.
Hartigan, J. A. & Wong, M. A. (1979). “Algorithm AS 136: A k-means clustering algorithm.” Applied statistics, pp 100- 108.
Hubert, L. & Arabie, P. (1985). Comparing partitions. Journal of Classification, 2(1):193-218.
Jain, A. K. & Dubes, R. C. (1988). “Algorithms for clustering data.”. Englewood Cliffs. Prentice-Hall.
Kaufman, L. & Rousseeuw, P. J. (1990). “Partitioning around medoids (program pam).” Finding groups in data: an introduction to cluster analysis, pp 68-125.
Lee, D.; Chen, J. & Cao, J. (2010). “The continuous berth allocation problem: A greedy randomized adaptive search solution”. Transportation Research Part E: Logistics and Transportation Review, 46(6):1017-1029.
Lopes, M. C. S. (2004). Mineração de dados textuais utilizando técnicas de clustering para o idioma português.
Doctoral dissertation, Departamento de Engenharia Civil. Universidade Federal do Rio de Janeiro.
López-Ibánez, M.; Dubois-Lacoste, J.; Stützle, T.; & Birattari, M. (2011). The irace package: Iterated racing for automatic algorithm configuration. Tech. Rep. TR/IRIDIA/2011-004, Université Libre de Bruxelles, Belgium.
Maron, O. & Moore, A.W. (1994). Hoeffding races: Accelerating model selection search for classification and function approximation. In: Cowan J. D., et al. (eds), Advances in Neural Information Processing Systems Morgan Kaufmann , San Francisco, CA, USA, vol 6, pp. 59–66.
Matsumoto, M. & Nishimura, T. (1998). Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation, 8:3-30.
Monti, S.; Savage, K.; Kutok, J.; Feuerhake, F.; Kurtin, P.; Mihm, M.; Wu, B.; Pasqualucci, L.; & Others. (2005) “Molecular profiling of difuse large B-cell lymphoma identifies robust subtypes including one characterized by host inflammatory response. Blood, 105(5):1851-1861.
Morán-Mirabal, L. F.; González-Velarde, J. L. & Resende, M. G. (2013). Automatic tuning of GRASP with evolutionary path-relinking. In Hybrid Metaheuristics (pp. 62-77). Springer Berlin Heidelberg.
Morris, T.; Bjarnason, R.; Adams, T; Clow, B; Clarkson, R; Partridge, N. & Zaugg, T. (2010) Biblioteca functionaljava. Regents of the University of California. Site: http://www.functionaljava.org/. Acessado em 22/10/2014.
Nascimento, M.; Toledo, F. & de Carvalho, A. (2010). Investigation of a new grasp based clustering algorithm applied to biological data. In Computers and Operations Research, pp 1381–1388.
Ohata, A. T.; & Quintanilha, J. A. (2005). O uso de algoritmos de clustering na mensuração da expansão urbana e detecção de alterações na Região Metropolitana de São Paulo. Anais do XII Simpósio Brasileiro de Sensoriamento Remoto, Goiânia, Brasil, 16–21 de Abril de 2005, 647-655.
Ozbay, Y.; Ceylan, R. & Karlik, B. (2006). A fuzzy clustering neural network architecture for classification of ecg arrhythmias. In Computers in Biology and Medicine, pp 376–388.
Papoulis, A. (1991) & Random Variable Probability. "Stochastic Processes. " McGraw-Hill.
Resende, M. G. & Ribeiro, C. C.(2005). GRASP with pathrelinking: Recent advances and applications. In Metaheuristics: progress as real problem solvers, pp. 29-63. Springer US.
Resende, M. G. C.; Ribeiro, C. C.; Glover, F. & Martí, R. (2010b). Scatter search and path-relinking: Fundamentals, advances and applications. Handbook of Metaheuristics, pp. 87-107.
Sirdey, R.; Carlier, J. & Nace, D. (2010). A GRASP for a resource-constrained scheduling problem. International Journal of Innovative Computing and Applications, 2(3):143- 149.
Spolaôr, N.; Lee, H. D.; Ferrero, C. A.; Coy, C. S. R., Fagundes; J. J., Wu; F. C.; ... & de Coloproctologia, S. (2008). Um Estudo da Aplicação de Clustering de Séries Temporais em Dados Médicos.
Su, A.; Cooke, M.; Ching, K.; Hakak, Y.; Walker, J.; Wiltshire, T.; Orth, A.; Vega, R.; Sapinoso, L.; Moqrich, A. & Others (2002). Large-scale analysis of the human and mouse transcriptomes. Proceedings of the National Academy of Sciences, 99(7):4465-4470.
Zlochin, M.; Birattari, M.; Meuleau, N. & Dorigo M. (2004) "Model-based search for combinatorial optimization: A critical survey." Annals of Operations Research, vol 131. pp 373-395.
Published
2015-05-26
How to Cite
SILVA, Júlio; FRINHANI, Rafael; SILVA, Ricardo; MATEUS, Geraldo.
Automatic Tuning of GRASP with Path-Relinking in data clustering with F-Race and iterated F-Race. In: BRAZILIAN SYMPOSIUM ON INFORMATION SYSTEMS (SBSI), 11. , 2015, Goiânia.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2015
.
p. 47-54.
DOI: https://doi.org/10.5753/sbsi.2015.5800.
