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.