Mais uma vez, a inteligência artificial busca soluções de algoritmos baseados no comportamento biológico. Hoje, vamos falar do algoritmo de otimização da colônia de formigas ou, do acrônimo inglês, ACO – ant colony optimization. Esse algoritmo é comumente utilizado na solução de problemas de procura de melhor caminho em grafos. Esse algoritmo é uma heurística baseada em probabilidade criada por Marco Dorigo, em 1997, com o objetivo de melhorar o até então conhecido sistemas de formigas.

No mundo natural, o caminho das formigas funciona da seguinte maneira: no início, elas saem do formigueiro em busca de alimentos. Como em sua maioria são cegas e não sabem onde encontrarão comida, elas andam dispersas, cada uma em uma direção. Durante esse trajeto, elas vão deixando no caminho um rastro de feromônio. Ao encontrar comida, as formigas retornam ao formigueiro pelo mesmo rastro deixado para trás. Esse comportamento foi comprovado em 1990 por Deneubourg et al com o experimento da ponte binária:

Quando outras formigas passam pelo mesmo rastro de feromônio, a concentração deste aumenta, dando um feedback positivo para as demais formigas. Porém, essa é uma solução dinâmica. Como o rastro de feromônio é volátil, ele vai se dissipando, o que permite que uma solução inicialmente encontrada não seja obrigatoriamente uma solução ótima, visto que outra formiga pode encontrar outro caminho, mais curto, e o seu rastro será então mais forte.

Podemos então entender que esse algoritmo é indicado para grafos que tendem a mudar dinamicamente, como o caminho que o Waze pode indicar para você fazer no trajeto da sua casa. Mesmo escolhendo sempre o caminho mais rápido, ele provavelmente não envia você sempre pelo mesmo caminho, pois podem existir entraves nesse trajeto (feedbacks negativos), que tornam o grafo (trajeto para sua casa) algo dinâmico.

Modelo artificial

Formigas são heurísticas artificiais construtivas, elas constroem soluções de forma probabilística por meio de duas informações básicas: trilha de feromônio e heurística. A trilha do feromônio artificial muda dinamicamente durante a execução do programa com o objetivo de refletir sobre a experiência já adquirida durante as buscas anteriores. A informação heurística identifica o problema a ser resolvido. Sendo assim, precisamos modelar matematicamente a probabilidade de uma formiga escolher um determinado caminho.

Imagine o seguinte exemplo: temos cinco formigas colocadas aleatoriamente em pontos diferentes. Cada formiga deve se mover de um ponto ao outro e encontrar o ponto com comida mais próximo do seu ponto inicial. A probabilidade de uma formiga K sair de um ponto i e seguir para um ponto j é dada pelo seguinte modelo:

Onde:

• ?ͥij(t): quantidade de feromônio presente no caminho (i,j);
• ɳij = 1/ⅆij: visibilidade do ponto j em relação ao ponto i;
• α e ? são parâmetros para determinar a influência do feromônio e da informação heurística.
• N é a vizinhança factível da formiga k (ou seja, o conjunto dos pontos ainda não visitados pela formiga k).

Para cada aresta (i,j) do grafo, existe um valor heurístico ɳij dado por ɳij = 1/ⅆij. Esse valor representa a atratividade de a formiga visitar o ponto j depois de visitar a cidade i. Assim, o valor ɳij é inversamente proporcional à distância ⅆij entre os pontos i e j.

As rotas são construídas da seguinte maneira:

Formiga	Candidato por probabilidade de transição	Solução parcial
1	2(45%), 3 (21%), 4(23%), 5(11%)	1 – 2
2	1(41%), 3(30%), 4(19%), 5(10%)	2 – 1
3	1(23%), 2(37%), 4(23%), 5(16%)	3 – 4
4	1(27%), 2(24%), 3(24%), 5(24%)	4 – 5
5	1(19%), 2(20%), 3(25%), 4(36%)	5 – 2

Assim, a escolha do candidato é feita de acordo com a probabilidade de transição.

Formiga	Candidato por probabilidade de transição	Solução parcial
1	3 (50%), 4(32%), 5(18%)	1 – 2 – 3
2	3(38%), 4(42%), 5(20%)	2 – 1 – 4
3	1(35%), 2(32%), 5(32%)	3 – 4 – 5
4	1(30%), 2(31%), 3(39%)	4 – 5 – 2
5	1(46%), 3(33%), 4(21%)	5 – 2 – 1

 

Formiga	Candidato por probabilidade de transição	Solução parcial
1	4(59%), 5(41%)	1 – 2 – 3 – 5
2	3(50%), 5(50%)	2 – 1 – 4 – 5
3	1(49%), 2(51%)	3 – 4 – 5 – 1
4	1(58%), 3(42%)	4 – 5 – 2 – 1
5	3(48%), 4(52%)	5 – 2 – 1 – 4

 

Formiga	Candidato por probabilidade de transição	Solução parcial
1	4(100%)	1 – 2 – 3 – 5 – 4
2	3(100%)	2 – 1 – 4 – 5 – 3
3	2(100%)	3 – 4 – 5 – 1 – 2
4	3(100%)	4 – 5 – 2 – 1 – 3
5	3(100%)	5 – 2 – 1 – 4 – 3

 

Formiga	Solução	Comprimento da viagem
1	1 – 2 – 3 – 5 – 4	9,8
2	2 – 1 – 4 – 5 – 3	9,8
3	3 – 4 – 5 – 1 – 2	10,9
4	4 – 5 – 2 – 1 – 3	11,6
5	5 – 2 – 1 – 4 – 3	12,4

Ao final dessa solução, ocorrem dois eventos no feromônio ?ͥij: a evaporação e o depósito. A evaporação é importante, pois evita que o feromônio cresça ininterruptamente. Além disso, ela permite que caminhos ruins possam ser esquecidos. Outro fenômeno que ocorre é o depósito, evidenciando o feromônio de todas as formigas que passaram pela aresta (i,j).

Após esses passos, o que passa a ocorrer é a atualização do feromônio. Entretanto, por mais que o algoritmo se preocupe com a atualização e a evaporação (ou deveria se preocupar), chega um momento em que ele fica estagnado; assim, as formigas passam a fazer sempre o mesmo caminho. É aqui que o algoritmo de colônia de formigas é alterado para que se tenha sua otimização.

E é aqui que surge o ACO – a ideia da otimização é transformar a heurística em uma meta-heurística por meio do elitismo, fazendo um maior uso da intensificação do que o sistema de formigas simples fazia. Assim, apenas a formiga que encontrou a melhor solução até o momento pode depositar o feromônio. Além disso, agora as formigas são capazes de remover o feromônio a fim de aumentar a diversificação das rotas.

Esse algoritmo costuma ser utilizado em problemas de busca de soluções, como redes de roteamento, sistemas de comunicação, análise de rotas de trânsito e até em problemas de release. Ou seja, ele é aplicado na engenharia de software para se descobrir quais requisitos mais importantes devem ser desenvolvidos na próxima entrega de software a fim de maximizar a expectativa dos stakeholders. Interessante, não?