Você já prestou atenção no comportamento de uma colônia de formigas ao procurar por alimento? Pare um pouco e vá até a sua cozinha, mas, antes de espantá-las, dê uma olhada no padrão formado por elas, pois falaremos disso aqui.
Formigas são bastante faladas pelo pessoal aqui do Deviante, já foi tema de spins de notícias ([1] e [2]) e posts ([1] e [2], [3]).
Existem diversos algoritmos baseados em colônia de formigas. Mas o que falaremos aqui será utilizado para encontrar o menor caminho entre dois pontos.
Basicamente elas se espalham pelo ambiente até encontrar a fonte, e ao encontrar voltam ao formigueiro e indicam o caminho para as suas companheiras.
As formigas são insetos sociais, possuidores de um complexo sistema de organização e divisão de tarefas, tendo como função principal a garantia da sobrevivência do formigueiro.
Inicialmente as formigas percorrem, de forma aleatória, as proximidades do formigueiro. Caso alguma delas encontre alimento nas proximidades, esta então retorna a sua casa, excretando a substancia crucial para a comunicação entre elas, o feromônio. As próximas formigas, então, irão perceber a quantidade de feromônio presente no ambiente e irão escolher se seguem por esta rota ou tentam procurar por outra. Quanto maior a quantidade de feromônio em uma rota, maior a probabilidade de uma formiga seguir por este caminho.
Isto ocorre devido a quantidade de feromônio depositada pelas formigas aumentar cada vez que uma nova formiga escolhe aquele caminho. Com isso a probabilidade de selecionar o caminho de menor distância aumenta à medida que a diferença de tamanho entre os caminhos torna-se maior. Inicialmente, a probabilidade de escolha é a mesma para ambos, pois não existe feromônio no caminho. Com o tempo, caminhos menores demandarão menos tempo para serem percorridos e, consequentemente, para depositar feromônio, e com isso terão mais feromônio do que os demais.
A experiência realizada com formigas reais por Goss, Aron, Deneubourg e Pasteels serviu de inspiração à criação do algoritmo de otimização de colônia de formigas. Esta experiência consistia na submissão de uma colônia de formigas Iridomyrmex humilis a uma fonte de alimento através de caminhos distintos, como na imagem (F – Fonte de alimento, N – Ninho):
Experimento de Goss e sua equipe [1]
O Dr. Marco Dorigo, tendo observado o modelo desenvolvido por Goss e sua equipe, desenvolveu o Algoritmo de Otimização por Colônia de Formigas.
Este algoritmo se baseia nesse comportamento e no modo como elas decidem tomar um caminho em detrimento de outro. Foi proposta como uma abordagem multi-agente para solucionar problemas de otimização combinatórias difíceis, como o Problema do Caixeiro Viajante (TSP – Traveling Salesman Problem) (já discutido pelo Felipe Augusto aqui).
Computacionalmente, formigas são heurísticas artificiais construtivas, elas constroem soluções para o problema ao qual são empregadas de forma probabilística.
Para isso elas utilizam duas informações. O feromônio excretados por cada uma e as distancias entre os pontos que elas irão percorrer.
Uma formiga decide qual rota tomar baseada em uma equação de probabilidade de escolha. Quanto maior a quantidade de feromônio depositada e menor a distância entre dois pontos (essa informação local é conhecida pela formiga), maior é a probabilidade dela escolher esse caminho.
O algoritmo de colônia de formigas faz parte de um conjunto de técnicas da computação bioinspirada. A computação bioinspirada pode ser definida como uma linha de pesquisa da ciência da computação baseada ou inspirada na natureza, que busca compreender os padrões nela encontrados, e posteriormente aplicá-los na resolução de problemas, desenvolvimento de novas tecnologias e/ou aperfeiçoamento de sistemas já existentes. São aplicados a diversos problemas que são difíceis de ser solucionados de forma direta. Entre esse conjunto de algoritmos, além do Algoritmo de Colônia de Formigas, temos também o Algoritmo de Côlonia de Abelhas, Algoritmo Genético, Redes Neurais Artificiais e diversos outros, e são divididos em três grandes áreas:
- Neurocomputação, que se inspira nas redes neurais do ser humano.
- Computação evolutiva, baseada na teoria da evolução.
- Inteligência coletiva, inspirada em pássaros, abelhas, etc.
- Imunocomputação, baseada no sistema imunológico do ser humano.
Esse algoritmo é bastante estudado na ciência da computação e possui muitas aplicações, por exemplo: otimizar a distribuição e melhorar a eficiência de pequenas antenas RFID; processamento de imagens para detecção de bordas e vinculação de arestas; problema de dimensionamento de dispositivos no projeto físico de nanoeletrônica; problemas de Conjuntos; problemas de roteamento de veículos.
Se estiver interessado em saber mais ou tirar dúvidas, deixe um comentário.
Veja mais:
Algoritmo de Colônia de Formigas
Funcionamento do Algoritmo de Colônia de Formigas
Fonte da Imagem:
