Avaliação do desempenho de um algoritmo baseado no comportamento de formigas em problemas de caminho de mínimo custo em ambientes raster
Analogias baseadas na capacidade de algumas espécies de formigas de encontrar o caminho mais curto entre seu ninho e uma fonte de alimento deram origem a uma técnica heurística de otimização denominada Ant Colony Optimization. Essa técnica tem sido amplamente utilizada na resolução de problemas de c...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Artículo |
| Lenguaje: | Portugués |
| Publicado: |
Sociedade Brasileira de Cartografia
2025
|
| Materias: | |
| Acceso en línea: | http://repositorio.unne.edu.ar/handle/123456789/58659 |
| Aporte de: |
| id |
I48-R184-123456789-58659 |
|---|---|
| record_format |
dspace |
| spelling |
I48-R184-123456789-586592025-09-24T15:11:52Z Avaliação do desempenho de um algoritmo baseado no comportamento de formigas em problemas de caminho de mínimo custo em ambientes raster Ant colony algorithm performance assessment on solving least-cost-path problems in raster environments Bravo, Juan Martín Collischonn, Walter Pilar, Jorge Víctor Gonçalves, Alexandre Otimização por colônias de formigas Caminhos de mínimo custo Ambientes raster Ant colony optimization Least cost path Grid raster environments Analogias baseadas na capacidade de algumas espécies de formigas de encontrar o caminho mais curto entre seu ninho e uma fonte de alimento deram origem a uma técnica heurística de otimização denominada Ant Colony Optimization. Essa técnica tem sido amplamente utilizada na resolução de problemas de caminho de mínimo custo em ambientes vetoriais. Neste trabalho é apresentada uma versão do algoritmo Max-Min Ant System adaptada para a resolução de problemas de caminho de mínimo custo em ambientes raster. O algoritmo encontra, muito provavelmente, o caminho ótimo dado o ponto de início do caminho, o ponto final, um campo de atrito em formato raster e uma função que define os custos incrementais de passagem entre duas celas vizinhas. Essa função depende do valor do atrito nessas celas. Foram realizados cinco testes hipotéticos com níveis crescentes de complexidade, incluindo dois sobre o traçado de obras de engenharia. Embora não foram utilizadas funções de custo reais os resultados obtidos são coerentes e mostram as vantagens do algoritmo. O algoritmo foi capaz de encontrar múltiplas soluções num problema com múltiplos caminhos ótimos. Ainda em outros testes o algoritmo conseguiu identificar caminhos complexos e sinuosos como os que definem o traçado de canais de irrigação ou estradas em zonas de montanha. O algoritmo foi implementado num programa na linguagem Visual Fortran permitindo o seguimento dos resultados parciais na tela do computador. Ant colony optimization is a set of heuristic optimization techniques that emulate real ant’s colony foraging behavior to find the shortest path between its nest and a food source. Those techniques have been widely used in order to solve least-cost-path problems based on vector’s representations. This study presents an adaptation of the traditional Max-Min Ant System algorithm to solve least-cost-path problems on the grid or raster structure, usually used in Geographical Information Systems. The algorithm finds, generally, the optimal path given a cost-of-passage surface in raster format, the path start and end points and a function that defines the incremental cost-of-passages between two neighboring cells. Five hypothetical tests with increasing complexity are made aiming to assess the model performance, including two of optimal routes identification for linear engineering structures, like canals or roads. Although real cost functions were not used, the results were coherent and showed the algorithm’s capabilities. The algorithm was able to find multiple solutions in a problem with multiple optimal paths. In other tests the algorithm was also able to identify complex paths that would define, for example, trajectories of irrigation channels or roads in mountainous zones. The algorithm was programmed in Visual Fortran language allowing partial results presentation on the computer screen. 2025-09-24T10:41:13Z 2025-09-24T10:41:13Z 2008 Artículo Bravo, Juan Martín, et. al., 2008. Avaliação do desempenho de um algoritmo baseado no comportamento de formigas em problemas de caminho de mínimo custo em ambientes raster. Revista brasileira de cartografía. Uberlândia: Sociedade Brasileira de Cartografia, 2008, vol. 60, no. 1, p. 31-41. 1808-0936 http://repositorio.unne.edu.ar/handle/123456789/58659 por https://seer.ufu.br/index.php/revistabrasileiracartografia/article/view/44881/23891 openAccess http://creativecommons.org/licenses/by-nc-nd/2.5/ar/ application/pdf p. 31-41 application/pdf Sociedade Brasileira de Cartografia Revista brasileira de cartografia, 2008, vol. 60, no. 1, p. 31-41. |
| institution |
Universidad Nacional del Nordeste |
| institution_str |
I-48 |
| repository_str |
R-184 |
| collection |
RIUNNE - Repositorio Institucional de la Universidad Nacional del Nordeste (UNNE) |
| language |
Portugués |
| topic |
Otimização por colônias de formigas Caminhos de mínimo custo Ambientes raster Ant colony optimization Least cost path Grid raster environments |
| spellingShingle |
Otimização por colônias de formigas Caminhos de mínimo custo Ambientes raster Ant colony optimization Least cost path Grid raster environments Bravo, Juan Martín Collischonn, Walter Pilar, Jorge Víctor Gonçalves, Alexandre Avaliação do desempenho de um algoritmo baseado no comportamento de formigas em problemas de caminho de mínimo custo em ambientes raster |
| topic_facet |
Otimização por colônias de formigas Caminhos de mínimo custo Ambientes raster Ant colony optimization Least cost path Grid raster environments |
| description |
Analogias baseadas na capacidade de algumas espécies de formigas de encontrar o caminho mais curto entre seu ninho e uma fonte de alimento deram origem a uma técnica heurística de otimização denominada Ant Colony Optimization. Essa técnica tem sido amplamente utilizada na resolução de problemas de caminho de mínimo custo em ambientes vetoriais. Neste trabalho é apresentada uma versão do algoritmo Max-Min Ant System adaptada para a resolução de problemas de caminho de mínimo custo em ambientes raster. O algoritmo encontra, muito provavelmente, o caminho ótimo dado o ponto de início do caminho, o ponto final, um campo de atrito em formato raster e uma função que define os custos incrementais de passagem entre duas celas vizinhas. Essa função depende do valor do atrito nessas celas. Foram realizados cinco testes hipotéticos com níveis crescentes de complexidade, incluindo dois sobre o traçado de obras de engenharia. Embora não foram utilizadas funções de custo reais os resultados obtidos são coerentes e mostram as vantagens do algoritmo. O algoritmo foi capaz de encontrar múltiplas soluções num problema com múltiplos caminhos ótimos. Ainda em outros testes o algoritmo conseguiu identificar caminhos complexos e sinuosos como os que definem o traçado de canais de irrigação ou estradas em zonas de montanha. O algoritmo foi implementado num programa na linguagem Visual Fortran permitindo o seguimento dos resultados parciais na tela do computador. |
| format |
Artículo |
| author |
Bravo, Juan Martín Collischonn, Walter Pilar, Jorge Víctor Gonçalves, Alexandre |
| author_facet |
Bravo, Juan Martín Collischonn, Walter Pilar, Jorge Víctor Gonçalves, Alexandre |
| author_sort |
Bravo, Juan Martín |
| title |
Avaliação do desempenho de um algoritmo baseado no comportamento de formigas em problemas de caminho de mínimo custo em ambientes raster |
| title_short |
Avaliação do desempenho de um algoritmo baseado no comportamento de formigas em problemas de caminho de mínimo custo em ambientes raster |
| title_full |
Avaliação do desempenho de um algoritmo baseado no comportamento de formigas em problemas de caminho de mínimo custo em ambientes raster |
| title_fullStr |
Avaliação do desempenho de um algoritmo baseado no comportamento de formigas em problemas de caminho de mínimo custo em ambientes raster |
| title_full_unstemmed |
Avaliação do desempenho de um algoritmo baseado no comportamento de formigas em problemas de caminho de mínimo custo em ambientes raster |
| title_sort |
avaliação do desempenho de um algoritmo baseado no comportamento de formigas em problemas de caminho de mínimo custo em ambientes raster |
| publisher |
Sociedade Brasileira de Cartografia |
| publishDate |
2025 |
| url |
http://repositorio.unne.edu.ar/handle/123456789/58659 |
| work_keys_str_mv |
AT bravojuanmartin avaliacaododesempenhodeumalgoritmobaseadonocomportamentodeformigasemproblemasdecaminhodeminimocustoemambientesraster AT collischonnwalter avaliacaododesempenhodeumalgoritmobaseadonocomportamentodeformigasemproblemasdecaminhodeminimocustoemambientesraster AT pilarjorgevictor avaliacaododesempenhodeumalgoritmobaseadonocomportamentodeformigasemproblemasdecaminhodeminimocustoemambientesraster AT goncalvesalexandre avaliacaododesempenhodeumalgoritmobaseadonocomportamentodeformigasemproblemasdecaminhodeminimocustoemambientesraster AT bravojuanmartin antcolonyalgorithmperformanceassessmentonsolvingleastcostpathproblemsinrasterenvironments AT collischonnwalter antcolonyalgorithmperformanceassessmentonsolvingleastcostpathproblemsinrasterenvironments AT pilarjorgevictor antcolonyalgorithmperformanceassessmentonsolvingleastcostpathproblemsinrasterenvironments AT goncalvesalexandre antcolonyalgorithmperformanceassessmentonsolvingleastcostpathproblemsinrasterenvironments |
| _version_ |
1846204049573019648 |