Ant Colony Optimization - Ant System

12 Jul 2011 . category: article . Comments
#algoritmos #aco #python

Implementei para um disciplina da graduação um algoritmo chamado Ant System ou AS para encontrar um valor bom ou ótimo para um determinado problema. Esse algoritmo foi proposto por Marco Dorigo e Vittorio Maniezzo. O Ant System é inspirado no comportamento de uma colonia de formigas em busca de alimento. Ele pertence a uma classe de algoritmos chamados Ant Colony Optimization(ACO), muito utilizados para encontrar valores de minimizam ou maximizam uma função. Este problema pode ser utilizado para resolver problemas como o do caixeiro viajante. De forma simples o AS pode ser adaptado para qualquer função com domínio discreto.

O motivo da escrita deste post é que não encontrei nenhum exemplo deste tipo de algoritmo implementado, diferente do que acontece com outros algoritmos como o Genético. Meu objetivo é deixar esta implementação como exemplo e espero que seja útil para outras pessoas.

A minha implementação foi feita em Python, sei que o código não está o melhor possível, porém agora não estou com tempo para melhorá-lo.

O problema resolvido com esta implementação foi proposto por um professor da Unicamp chamado Eduardo C. Xavier durante uma disciplina de algoritmos. Porém o algoritmo e a linguagem usadas na minha implementação não estavam dentre as opções dadas pelo professor, por isso a implementação não poderia ser utilizada por seus alunos. E de qualquer forma eu esperei o encerramento do semestre para publicar este post. A descrição do problema pode ser encontrado aqui.

Os arquivos fonte do projeto podem ser entrado aqui e o relatório final apresentado por ser visto aqui. Neste relatório contém algumas explicações e abordagens utilizadas.

Espero que esta implementação seja útil para alguém.


Me

Tenho estudado esse mundo mágico da programação desde 2005. Já consegui sustentar minha família usando Ruby, Java, Python, C++ e Javascript. O resto tenho usado para diversão ou aprendizado.