Avaliação de Desempenho e Escalabilidade do Algoritmo de Otimização de Colônia de Formigas em C++ e Python
Resumo
O algoritmo de Otimização de Colônia de Formigas, do inglês Ant Colony Optimization (ACO), é um algoritmo inspirado no comportamento das formigas em busca de alimento. Implementado originalmente em Python para seleção de instâncias, o código desenvolvido apresenta desempenho lento em grandes bases de dados. Este artigo apresenta a avaliação da conversão do ACO desenvolvido em Python para C++, visando comparar o desempenho das duas versões. A hipótese está fundamentada na melhoria do tempo de execução em C++, mantendo a qualidade na seleção de instâncias. Os objetivos incluem converter o código ACO em Python para C++, comparar o desempenho entre as duas versões, e identificar razões para as diferenças. Os resultados mostram que o ACO em C++ possui maior desempenho e escalabilidade com qualidade na redução de instâncias, principalmente, para grandes bases de dados.
Referências
D. F. Bacon, S. L. Graham, e O. J. Sharp. Compiler transformations for high-performance computing. ACM Comput. Surv., 26(4):345–420, 1994. DOI: 10.1145/197405.197406.
G. Barany. Python interpreter performance deconstructed. In Proceedings of the Workshop on Dynamic Languages and Applications, Dyla’14, page 1–9, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450329163.
F. Bertoni e M. Pires. Aplicação de algoritmos evolutivos multiobjetivo na seleção de instâncias. In Anais do XIII Simpósio Brasileiro de Sistemas de Informação, pages 261–268, Porto Alegre, RS, Brasil, 2017. SBC. DOI: 10.5753/sbsi.2017.6051.
T. Borovicka, M. J. Jr., P. Kordik, e M. Jirina. Selecting representative data sets. In A. Karahoca, editor, Advances in Data Mining Knowledge Discovery and Applications, chapter 2. IntechOpen, Rijeka, 2012. DOI: 10.5772/50787.
M. Dorigo, M. Birattari, e T. Stutzle. Ant colony optimization. IEEE Computational Intelligence Magazine, 1(4):28–39, 2006. DOI: 10.1109/MCI.2006.329691.
C. Gong, Z. gang Su, P. hong Wang, Q. Wang, e Y. You. Evidential instance selection for k-nearest neighbor classification of big data. International Journal of Approximate Reasoning, 138:123–144, 2021. DOI: 10.1016/j.ijar.2021.08.006.
M. Ismail e G. E. Suh. Quantitative overhead analysis for python. In 2018 IEEE International Symposium on Workload Characterization (IISWC), pages 36–47, 2018. DOI: 10.1109/IISWC.2018.8573512.
X. Leroy. An overview of Types in Compilation. In TIC 1998: workshop Types in Compilation, volume 1473 of LNCS, pages 1–8. Springer, Kyoto, Japan, Mar. 1998. DOI: 10.1007/BFb0055509.
A. C. Medeiros. Análise de desempenho do algoritmo colônia de formigas para seleção de instâncias. Trabalho de conclusão de graduação, PUC Minas, 2022.
S. Nanz e C. A. Furia. A comparative study of programming languages in rosetta code. In 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering, volume 1, pages 778–788, 2015. DOI: 10.1109/ICSE.2015.90.
J. A. Olvera-López, J. A. Carrasco-Ochoa, J. F. Martínez-Trinidad, e J. Kittler. A review of instance selection methods. Artificial Intelligence Review, 34(2):133–143, 2010. DOI: 10.1007/s10462-010-9165-y.
S. Saha, P. S. Sarker, A. A. Saud, S. Shatabda, e M. Hakim Newton. Cluster-oriented instance selection for classification problems. Information Sciences, 602:143–158, 2022. ISSN 0020-0255. DOI: 10.1016/j.ins.2022.04.036.
N. Spolaôr, E. A. Cherman, M. C. Monard, e H. D. Lee. Relieff for multi-label feature selection. In 2013 Brazilian Conference on Intelligent Systems, pages 6–11, 2013. DOI: 10.1109/BRACIS.2013.10.
B. Stroustrup. An overview of c++. ACM SIGPLAN Notices, 21(10):7–18, jun 1986. DOI: 10.1145/323648.323736.
Y. Ueda e M. Ohara. Performance competitiveness of a statically compiled language for server-side web applications. In 2017 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 13–22, 2017. DOI: 10.1109/ISPASS.2017.7975266.
G. Barany. Python interpreter performance deconstructed. In Proceedings of the Workshop on Dynamic Languages and Applications, Dyla’14, page 1–9, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450329163.
F. Bertoni e M. Pires. Aplicação de algoritmos evolutivos multiobjetivo na seleção de instâncias. In Anais do XIII Simpósio Brasileiro de Sistemas de Informação, pages 261–268, Porto Alegre, RS, Brasil, 2017. SBC. DOI: 10.5753/sbsi.2017.6051.
T. Borovicka, M. J. Jr., P. Kordik, e M. Jirina. Selecting representative data sets. In A. Karahoca, editor, Advances in Data Mining Knowledge Discovery and Applications, chapter 2. IntechOpen, Rijeka, 2012. DOI: 10.5772/50787.
M. Dorigo, M. Birattari, e T. Stutzle. Ant colony optimization. IEEE Computational Intelligence Magazine, 1(4):28–39, 2006. DOI: 10.1109/MCI.2006.329691.
C. Gong, Z. gang Su, P. hong Wang, Q. Wang, e Y. You. Evidential instance selection for k-nearest neighbor classification of big data. International Journal of Approximate Reasoning, 138:123–144, 2021. DOI: 10.1016/j.ijar.2021.08.006.
M. Ismail e G. E. Suh. Quantitative overhead analysis for python. In 2018 IEEE International Symposium on Workload Characterization (IISWC), pages 36–47, 2018. DOI: 10.1109/IISWC.2018.8573512.
X. Leroy. An overview of Types in Compilation. In TIC 1998: workshop Types in Compilation, volume 1473 of LNCS, pages 1–8. Springer, Kyoto, Japan, Mar. 1998. DOI: 10.1007/BFb0055509.
A. C. Medeiros. Análise de desempenho do algoritmo colônia de formigas para seleção de instâncias. Trabalho de conclusão de graduação, PUC Minas, 2022.
S. Nanz e C. A. Furia. A comparative study of programming languages in rosetta code. In 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering, volume 1, pages 778–788, 2015. DOI: 10.1109/ICSE.2015.90.
J. A. Olvera-López, J. A. Carrasco-Ochoa, J. F. Martínez-Trinidad, e J. Kittler. A review of instance selection methods. Artificial Intelligence Review, 34(2):133–143, 2010. DOI: 10.1007/s10462-010-9165-y.
S. Saha, P. S. Sarker, A. A. Saud, S. Shatabda, e M. Hakim Newton. Cluster-oriented instance selection for classification problems. Information Sciences, 602:143–158, 2022. ISSN 0020-0255. DOI: 10.1016/j.ins.2022.04.036.
N. Spolaôr, E. A. Cherman, M. C. Monard, e H. D. Lee. Relieff for multi-label feature selection. In 2013 Brazilian Conference on Intelligent Systems, pages 6–11, 2013. DOI: 10.1109/BRACIS.2013.10.
B. Stroustrup. An overview of c++. ACM SIGPLAN Notices, 21(10):7–18, jun 1986. DOI: 10.1145/323648.323736.
Y. Ueda e M. Ohara. Performance competitiveness of a statically compiled language for server-side web applications. In 2017 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 13–22, 2017. DOI: 10.1109/ISPASS.2017.7975266.
Publicado
23/10/2024
Como Citar
MAGALHÃES, João Marcos de Oliveira; GONÇALVES, Ana Carolina Medeiros; NOBRE, Cristiane Neri; FREITAS, Henrique Cota de.
Avaliação de Desempenho e Escalabilidade do Algoritmo de Otimização de Colônia de Formigas em C++ e Python. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 25. , 2024, São Carlos/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 97-108.
DOI: https://doi.org/10.5753/sscad.2024.244375.
