Avaliação das Técnicas Gulosa e Probabilística no Desempenho do Algoritmo de Otimização de Colônia de Formigas
Resumo
O Big Data Analytics e os algoritmos de Aprendizado de Máquina enfrentam desafios significativos ao lidar com grandes volumes de dados, tornando as técnicas de pré-processamento essenciais nesse contexto. Uma dessas técnicas é a Seleção de Instâncias, que identifica as instâncias mais relevantes em uma base de dados. Este estudo compara duas abordagens do algoritmo de Otimização por Colônia de Formigas (ACO) para a seleção de instâncias: a heurística gulosa e a abordagem probabilística. Em 16 bases de dados, a abordagem gulosa reduziu o tamanho das bases em média 50% e apresentou um tempo de execução quase pela metade em relação à abordagem probabilística.
Referências
A. A. Akinyelu. Bio-inspired technique for improving machine learning speed and big data processing. In 2020 International Joint Conference on Neural Networks (IJCNN), pages 1–8, 2020. DOI: 10.1109/IJCNN48605.2020.9206762.
I. M. Anwar, K. M. Salama, e A. M. Abdelbar. Instance selection with ant colony optimization. Procedia Computer Science, 53:248–256, 2015. ISSN 1877-0509. DOI: 10.1016/j.procs.2015.07.301. INNS Conference on Big Data 2015 Program San Francisco, CA, USA 8-10 August 2015.
A. C. Barus, T. Y. Chen, D. Grant, F. C. Kuo, e M. F. Lau. Testing of heuristic methods: A case study of greedy algorithm. In Z. Huzar, R. Koci, B. Meyer, B. Walter, e J. Zendulka, editors, Software Engineering Techniques, pages 246–260, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-22386-0_19.
L. Breiman. Random forests. Machine learning, 45(1):5–32, 2001. DOI: 10.1023/A:1010950718922.
J. L. Carbonera e M. Abel. An attraction-based approach for instance selection. In 2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI), pages 1053–1058, 2020. DOI: 10.1109/ICTAI50040.2020.00161.
F. Cheng, F. Chu, e L. Zhang. A multi-objective evolutionary algorithm based on length reduction for large-scale instance selection. Information Sciences, 576, 06 2021. DOI: 10.1016/j.ins.2021.06.052.
G. da Silva Fonseca. Heurística gulosa para o problema dinâmico de coleta e entrega de pacientes. Galoá Proceedings, 54:152846, 2022.
M. Dorigo e G. Di Caro. Ant colony optimization: a new meta-heuristic. In Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), volume 2, pages 1470–1477 Vol. 2, 1999. DOI: 10.1109/CEC.1999.782657.
A. C. M. Gonçalves. Análise de desempenho do algoritmo colônia de formigas para seleção de instâncias. Trabalho de conclusão de graduação, Pontifícia Universidade Católica de Minas Gerais, Belo Horizonte, 2022.
H. Hott., C. Jandre., P. Xavier., A. Miloud-Aouidate., D. Miranda., M. Song., L. Zárate., e C. Nobre. Selection of representative instances using ant colony: A case study in a data-base of children and adolescents with attention-deficit/hyperactivity disorder. In Proceedings of the 15th International Joint Conference on Biomedical Engineering Systems and Technologies - HEALTHINF,, pages 103–110. INSTICC, SciTePress, 2022. ISBN 978-989-758-552-4. DOI: 10.5220/0010843000003123.
Y. Jia, S. Zhou, Q. Zeng, C. Li, D. Chen, K. Zhang, L. Liu, e Z. Chen. The uav path coverage algorithm based on the greedy strategy and ant colony optimization. Electronics, 11(17), 2022. ISSN 2079-9292. DOI: 10.3390/electronics11172667.
E. Maggio. Uma Heurística para a Programação da Produção de FMS usando Modelagem em Redes de Petri. Editora XYZ, 2004. Busca heurística - Estratégias de Busca para Solução de Problemas.
M. Morin, I. Abi-Zeid, e C.-G. Quimper. Ant colony optimization for path planning in search and rescue operations. European Journal of Operational Research, 305(1): 53–63, 2023. ISSN 0377-2217. DOI: 10.1016/j.ejor.2022.06.019.
K. Salama, A. Abdelbar, e I. Anwar. Data reduction for classification with ant colony algorithms. Intelligent Data Analysis, 20:1021–1059, 09 2016. DOI: 10.3233/IDA-160855.
K. M. Salama e A. A. Freitas. Learning bayesian network classifiers using ant colony optimization. Swarm Intelligence, 7(2):229–254, 2013. DOI: 10.1007/s11721-013-0087-6.
J. Silva e M. Pereira. Heurísticas e algoritmos de busca em problemas de otimização. Revista de Computação e Matemática, 15(2):123–134, 2020. Discussão sobre a irreversibilidade das decisões na heurística gulosa.
S. O. Tovias-Alanis, W. Gómez-Flores, e G. Toscano-Pulido. Instance selection based on linkage trees. In 2021 18th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE), pages 1–6, 2021. DOI: 10.1109/CCE53527.2021.9633116.
C.-F. Tsai, K.-L. Sue, Y.-H. Hu, e A. Chiu. Combining feature selection, instance selection, and ensemble classification techniques for improved financial distress prediction. Journal of Business Research, 130:200–209, 06 2021. DOI: 10.1016/j.jbusres.2021.03.018.
A. C. B. K. Vendramin, A. Munaretto, M. R. Delgado, e A. C. Viana. A greedy ant colony optimization for routing in delay tolerant networks. In 2011 IEEE GLOBECOM Workshops (GC Wkshps), pages 1127–1132, 2011. DOI: 10.1109/GLOCOMW.2011.6162354.
C. M. Wilt e W. Ruml. Building a heuristic for greedy search. In International Symposium on Combinatorial Search, pages 131–139, 2015. DOI: 10.1609/socs.v6i1.18352.
I. M. Anwar, K. M. Salama, e A. M. Abdelbar. Instance selection with ant colony optimization. Procedia Computer Science, 53:248–256, 2015. ISSN 1877-0509. DOI: 10.1016/j.procs.2015.07.301. INNS Conference on Big Data 2015 Program San Francisco, CA, USA 8-10 August 2015.
A. C. Barus, T. Y. Chen, D. Grant, F. C. Kuo, e M. F. Lau. Testing of heuristic methods: A case study of greedy algorithm. In Z. Huzar, R. Koci, B. Meyer, B. Walter, e J. Zendulka, editors, Software Engineering Techniques, pages 246–260, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-22386-0_19.
L. Breiman. Random forests. Machine learning, 45(1):5–32, 2001. DOI: 10.1023/A:1010950718922.
J. L. Carbonera e M. Abel. An attraction-based approach for instance selection. In 2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI), pages 1053–1058, 2020. DOI: 10.1109/ICTAI50040.2020.00161.
F. Cheng, F. Chu, e L. Zhang. A multi-objective evolutionary algorithm based on length reduction for large-scale instance selection. Information Sciences, 576, 06 2021. DOI: 10.1016/j.ins.2021.06.052.
G. da Silva Fonseca. Heurística gulosa para o problema dinâmico de coleta e entrega de pacientes. Galoá Proceedings, 54:152846, 2022.
M. Dorigo e G. Di Caro. Ant colony optimization: a new meta-heuristic. In Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), volume 2, pages 1470–1477 Vol. 2, 1999. DOI: 10.1109/CEC.1999.782657.
A. C. M. Gonçalves. Análise de desempenho do algoritmo colônia de formigas para seleção de instâncias. Trabalho de conclusão de graduação, Pontifícia Universidade Católica de Minas Gerais, Belo Horizonte, 2022.
H. Hott., C. Jandre., P. Xavier., A. Miloud-Aouidate., D. Miranda., M. Song., L. Zárate., e C. Nobre. Selection of representative instances using ant colony: A case study in a data-base of children and adolescents with attention-deficit/hyperactivity disorder. In Proceedings of the 15th International Joint Conference on Biomedical Engineering Systems and Technologies - HEALTHINF,, pages 103–110. INSTICC, SciTePress, 2022. ISBN 978-989-758-552-4. DOI: 10.5220/0010843000003123.
Y. Jia, S. Zhou, Q. Zeng, C. Li, D. Chen, K. Zhang, L. Liu, e Z. Chen. The uav path coverage algorithm based on the greedy strategy and ant colony optimization. Electronics, 11(17), 2022. ISSN 2079-9292. DOI: 10.3390/electronics11172667.
E. Maggio. Uma Heurística para a Programação da Produção de FMS usando Modelagem em Redes de Petri. Editora XYZ, 2004. Busca heurística - Estratégias de Busca para Solução de Problemas.
M. Morin, I. Abi-Zeid, e C.-G. Quimper. Ant colony optimization for path planning in search and rescue operations. European Journal of Operational Research, 305(1): 53–63, 2023. ISSN 0377-2217. DOI: 10.1016/j.ejor.2022.06.019.
K. Salama, A. Abdelbar, e I. Anwar. Data reduction for classification with ant colony algorithms. Intelligent Data Analysis, 20:1021–1059, 09 2016. DOI: 10.3233/IDA-160855.
K. M. Salama e A. A. Freitas. Learning bayesian network classifiers using ant colony optimization. Swarm Intelligence, 7(2):229–254, 2013. DOI: 10.1007/s11721-013-0087-6.
J. Silva e M. Pereira. Heurísticas e algoritmos de busca em problemas de otimização. Revista de Computação e Matemática, 15(2):123–134, 2020. Discussão sobre a irreversibilidade das decisões na heurística gulosa.
S. O. Tovias-Alanis, W. Gómez-Flores, e G. Toscano-Pulido. Instance selection based on linkage trees. In 2021 18th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE), pages 1–6, 2021. DOI: 10.1109/CCE53527.2021.9633116.
C.-F. Tsai, K.-L. Sue, Y.-H. Hu, e A. Chiu. Combining feature selection, instance selection, and ensemble classification techniques for improved financial distress prediction. Journal of Business Research, 130:200–209, 06 2021. DOI: 10.1016/j.jbusres.2021.03.018.
A. C. B. K. Vendramin, A. Munaretto, M. R. Delgado, e A. C. Viana. A greedy ant colony optimization for routing in delay tolerant networks. In 2011 IEEE GLOBECOM Workshops (GC Wkshps), pages 1127–1132, 2011. DOI: 10.1109/GLOCOMW.2011.6162354.
C. M. Wilt e W. Ruml. Building a heuristic for greedy search. In International Symposium on Combinatorial Search, pages 131–139, 2015. DOI: 10.1609/socs.v6i1.18352.
Publicado
23/10/2024
Como Citar
GONÇALVES, Ana Carolina Medeiros; BRITO, Maria Eduarda Oliveira; FREITAS, Henrique Cota de; NOBRE, Cristiane Neri.
Avaliação das Técnicas Gulosa e Probabilística no Desempenho do Algoritmo de Otimização de Colônia de Formigas. 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. 1-12.
DOI: https://doi.org/10.5753/sscad.2024.244773.
