Avaliação do desempenho de um algoritmo baseado no comportamento de formigas em problemas de caminho de mínimo custo em ambientes raster

Abstract

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.