Auto-parametrização do GRASP com Path-Relinking no agrupamento de dados com F-Race e iterated F-Race
Resumo
Em estudos que utilizam metaheurísticas embora os parâmetros de entrada influenciem diretamente o desempenho do algoritmo sua definição na maioria das vezes é feita manualmente levantando questões sobre a qualidade dos resultados. Este artigo se propõe a aplicar o I/F-Race na auto-parametrização do GRASP com PathRelinking no agrupamento de dados visando obter melhores resultados em relação aos parametrizados manualmente. Experimentos realizados com cinco conjuntos de dados demostraram que a utilização do I/F-Race contribui para obtenção de melhores resultados que a parametrização manual.
Palavras-chave:
Auto-parametrização, I/F-Race, GRASP, Path-Relinking, Agrupamento de Dados
Referências
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.
Publicado
26/05/2015
Como Citar
SILVA, Júlio; FRINHANI, Rafael; SILVA, Ricardo; MATEUS, Geraldo.
Auto-parametrização do GRASP com Path-Relinking no agrupamento de dados com F-Race e iterated F-Race. In: SIMPÓSIO BRASILEIRO DE SISTEMAS DE INFORMAÇÃO (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.
