Otimiza¸c˜ao por Colˆonia de Formigas (Ant
Colony Optimization - ACO)
Eros Moreira de Carvalho
Gabriel Silva Ramos
{emc06,gsr04}@c3sl.ufpr.br
11 de Junho de 2007
Resumo
Neste artigo, apresentamos a metaheur´ıstica Ant Colony Optimiza-
tion (ACO) e algums dos algoritmos que a implementam, em especial,
o Ant System (AS), Ant Colony System (ACS) e MAX-MIN Ant Sys-
tem (MMAS). Aplicaremos esses algoritmos ao problema do caixeiro
viajante, usando algumas bases da TSPLIB. Nosso objetivo, al´em de
acentuar como a metaheur´ıstica ACO obt´em um bom equil´ıbrio dos
conceitos de diversifica¸c˜ao e intensifica¸c˜ao, ´e evidenciar, pelo resul-
tados emp´ıricos apresentados, que o ACO ´e uma boa metaheur´ıstica
para a solu¸c˜ao de problemas combinat´orios e o MMAS a sua imple-
menta¸c˜ao de melhor desempenho.
1 Introdu¸c˜ao
Problemas de otimiza¸c˜ao combinat´oria s˜ao dif´ıceis de resolver, isto ´e, o seu
custo computacional cresce exponecialmente com o aumento da entrada.
´
E
o caso, por exemplo, do problema do caixeiro viajante (Traveling Salesman
Problem - TSP). Imagine um conjunto de cidades completamente conectadas
entre si, isto ´e, para cada par de cidades, h´a uma estrada que as liga. O pro-
blema consiste, ent˜ao, em encontrar o menor caminho para percorrer todas
as cidades uma ´unica vez. O conjunto de todos os caminhos poss´ıveis definem
o espa¸co de busca para este problema. Para conjuntos de poucas cidades, at´e
cinco ou seis, p odemos testar todas as possibilidades para encontrar o me-
nor caminho. Mas o problema se torna computacionalmente intrat´avel para
conjuntos maiores de cidades. Tal fato despertou a necessidade de se elabo-
rar estrat´egias computacionalmente baratas, mas que encontrassem solu¸c˜oes
1
´otimas ou pr´oximas delas para esse tipo de problema. Essa ´e a id´eia princi-
pal por tr´as das metaheur´ısticas. S˜ao estrat´egias para explorar o espa¸co de
busca de maneira eficiente, encontrando solu¸c˜oes ´otimas, pr´oximas da melhor
solu¸c˜ao, mas sem ter de explorar o espa¸co de busca exaustivamente.
H´a basicamente duas maneiras de abordar um problema combinatorial
de maneira computacionalmente vi´avel: uma ´e a constru¸c˜ao passo a passo
de uma solu¸c˜ao usando algum tipo de informa¸c˜ao heur´ıstica ou obtida por
experiˆencia para produzir uma solu¸c˜ao ´otima. Outra abordagem ´e partir de
uma solu¸c˜ao pronta e modificar alguns dos seus elementos para obter outras
solu¸c˜oes melhores. Algoritmos baseados na primeira abordagem s˜ao chama-
dos de algoritmos de constru¸c˜ao de solu¸c˜ao, ao passo que aqueles baseados
na segunda abordagem s˜ao chamados de algoritmos de busca local. Uma
metaheur´ıstica, enquanto estrat´egia mais geral para obter solu¸c˜oes ´otimas
a um custo razo´avel, pode se basear em uma das duas abordagens ou em
ambas conjuntamente. ACO, como veremos, ´e primordiamlmente uma me-
taheur´ıstica baseada na constru¸c˜ao de solu¸c˜ao, embora ela possa ser combi-
nada tamb´em com buscas locais.
Dois conceitos importantes para o e studo de metaheur´ısticas s˜ao o de in-
tensifica¸c˜ao e diversifica¸c˜ao. A intensifica¸c˜ao ´e a explora¸c˜ao mais exaustivia
de uma regi˜ao do espa¸co de busca onde se espera encontrar boas solu¸c˜oes, ao
passo que a diversifica¸c˜ao ´e a mudan¸ca do foco da busca para regi˜oes ainda
n˜ao exploradas [2]. Uma boa metaheur´ıstica deve obter um equil´ıbrio entre
intensifica¸c˜ao e diversifica¸c˜ao. Ao longo do artigo, tentaremos mostrar como
a metaheur´ıstica ACO obt´em os efeitos de intensifica¸c˜ao e diversifica¸c˜ao no
processo de busca de uma boa s olu¸c˜ao e quais dos seus componentes s˜ao
respons´aveis por estes efeitos.
O presente artigo tem a seguinte estrutura. Na pr´oxima se¸c˜ao, apresen-
taremos a metaheur´ıstica ACO e trˆes algoritmos que visam implement´a-la,
AS, ACS e MMAS, tentando sempre focar os elementos respons´aveis pelos
efeitos de intensifica¸c˜ao e diversifica¸c˜ao. Em seguida, explicitamos as bus-
cas locais usadas em conjunto com ACO em nossos testes. Em uma outra
se¸c˜ao, explicitamos alguns detalhes da implementa¸c˜ao que fizemos. Em se-
guida, apresentamos os testes, algumas aplica¸c˜oes para o ACO e as nossas
conclus˜oes.
2 Otimiza¸c˜ao por Colˆonia de Formigas
A otimiza¸c˜ao por colˆonia de formigas (Ant Colony Optimization - ACO) ´e
uma metaheur´ıstica recente para a solu¸c˜ao de problemas combinat´orios. Ela
´e inspirada no comportamento de formigas na busca de alimentos. Quando
2
uma formiga precisa decidir para onde ir, ela usa informa¸c˜ao proveniente
de feromˆonio previamente depositado por outras formigas que passaram por
aquele local. A dire¸c˜ao que tiver maior dep´osito de feromˆonio ser´a escolhida
pela formiga. Por este processo de busca, formigas s˜ao capazes de encontrar
o menor caminho de uma fonte de comida para o seu ninho [3].
A metaheur´ıstica ACO est´a baseada em um processo de constru¸c˜ao de
solu¸c˜ao e sua principal inova¸c˜ao ´e usar formigas artificiais que, ao percorrer
um caminho, depositam uma certa quantidade de feromˆonio, que, ent˜ao,
ir´a influenciar a decis˜ao das formigas que vierem em seguida. A inova¸c˜ao do
processo de constru¸c˜ao de solu¸c˜ao do ACO ficar´a mais clara se a compararmos
com outros processos de constru¸c˜ao. A constru¸c˜ao de solu¸c˜ao mais simples e
empregada em muitas outras metaheur´ısticas para produzir solu¸c˜oes iniciais
a um custo pequeno ´e a constru¸c˜ao completamente gulosa. Para o problema
do caixeiro viajante, ela funciona assim. Dado um conjunto de N cidades,
escolhe-se uma delas e a coloca na solu¸c˜ao. Avalia-se, ent˜ao, qual das cidades
restantes est´a mais pr´oxima daquela e ela ´e adicionada tamb´em na solu¸c˜ao.
Esse processo ´e repetido N vezes, at´e que se tenha um caminho completo, isto
´e, uma solu¸c˜ao para o problema do caixeiro viajante. Repare, no entanto,
que se tivermos N cidades, teremos apenas N solu¸c˜oes gulosas distintas.
Uma vez escolhida a cidade inicial, a constru¸c˜ao da solu¸c˜ao gulosa torna-se
completamente determin´ıstica.
O processo de constru¸c˜ao de solu¸c˜ao completamente guloso tem um efeito
de diversifica¸c˜ao e intensifica¸c˜ao fracos. O n´umero de solu¸c˜oes geradas ´e
muito pequeno, o que limita a diversifica¸c˜ao. E a intensifica¸c˜ao ´e pratica-
mente inexistene, j´a que nenhuma solu¸c˜ao ´e usada como ponto de partida
para uma explora¸c˜ao mais intensa na sua vizinhan¸ca por solu¸c˜oes melho-
res. Para piorar, as solu¸c˜ao geradas por uma constru¸c˜ao completamente
gulosa s˜ao em geral sub-´otimas[5]. Uma id´eia para contornar parcialmente
esse problema ´e introduzir um elemento aleat´orio na constru¸c˜ao gulosa. Por
exemplo, para cada passo da constru¸c˜ao, pode-se pegar as 4 cidades mais
pr´oximas `a ´ultima cidade colocada na solu¸c˜ao e fazer um sorteio entre elas
para decidir qual ser´a colocada no caminho em constru¸c˜ao. Essa modifica¸c˜ao
da constru¸c˜ao gulosa, com elementos aleat´orios, ´e usada, por exemplo, pela
metaheur´ıstica GRASP [1]. Embora essa modifica¸c˜ao produza um ef eito de
diversifica¸c˜ao, aumentando substancialmente a quantidade de solu¸c˜oes gera-
das, ela ainda continua sem um efeito de intensifica¸c˜ao.
A metaheur´ıstica ACO pode ser considerada uma melhoria do processo
de constru¸c˜ao de solu¸c˜ao, buscando obter, pela influˆencia dos feromˆonios,
um efeito tanto de diversifica¸c˜ao quanto de intensifica¸c˜ao. O processo de
constru¸c˜ao de solu¸c˜ao no ACO ´e estoc´astico. Ele constroi uma solu¸c˜ao itera-
tivamente adicionando componentes de solu¸c˜ao a uma solu¸c˜ao parcial levando
3
em considera¸c˜ao informa¸c˜ao heur´ıstica e informa¸c˜ao de feromˆonio, que muda
dinamicamente para refletir a experiˆencia da formiga [5]. Quando a formiga
d´a um passo na constru¸c˜ao da s olu¸c˜ao, ela faz um c´alculo probabil´ıstico ba-
seada na quantidade de feromˆonio depositada nas arestas que ligam a sua
posi¸c˜ao atual at´e posi¸c˜oes ainda n˜ao visitadas e na informa¸c˜ao heur´ıstica
relacionada a estas arestas. O feromˆonio depositado tem um efeito de di-
versifica¸c˜ao, ao possibilitar um n´umero muito maior de solu¸c˜oes do que uma
estrat´egia puramente gulosa. Mas o feromˆonio tamb´em tem um efeito de
intensifica¸c˜ao, ao refletir a experiˆencia das formigas, pois componentes que
foram largamente usados no passado em boas solu¸c˜oes ter˜ao preferˆencia pelas
formigas que est˜ao construindo uma solu¸c ˜ao.
Em seguida, passaremos a expor a estrutura geral da metaheur´ıstica ACO.
Como caracterizada por Dorigo[5], seu pseudo-c´odigo pode ser formulado
como mostra a figura 1.
Iniciar par^ametros, iniciar rastros de ferom^onio
Agendar Atividades
Constru¸c~ao de Solu¸c~oes
A¸c~oes Globais [Opcional]
Atualiza¸c~ao dos Ferom^onios
Fim do Agendamento
Figura 1: Pseudo-c´odigo da metaheur´ıstica ACO
Como j´a dissemos, ACO ´e uma metaheur´ıstica baseada na constru¸c˜ao de
solu¸c˜oes. ACO tamb´em ´e uma metaheur´ıstica baseada em popula¸c˜ao, no
caso, na coopera¸c˜ao entre formigas. Como podemos ver pelo pseudo-c´odigo,
o ACO ´e dividido basicamente em trˆes etapas. Na primeira fase, as formigas
da colˆonia constroem passo a passo uma solu¸c˜ao, aplicando uma decis˜ao local
estoc´astica com base na informa¸c˜ao de feromˆonio e na informa¸c˜ao heur´ıstica.
´
E importante notar que n˜ao ´e necess´ario que as formigas caminhem em sin-
cronia na constru¸c˜ao da solu¸c˜ao, o que facilita implementa¸c˜oes concorrentes
e ass´ıncronas do ACO[5]. Enquanto caminha, construindo uma solu¸c˜ao, a
formiga avalia a solu¸c˜ao parcial e, dependendo do algoritmo ACO, pode vir
a depositar feromˆonio do ´ultimo componente visitado, cooperando, assim,
com as formigas que vierem em seguida por aquele caminho.
Depois que uma formiga completa uma solu¸c˜ao, algumas a¸c˜oes globais
podem ser realizadas sobre essa solu¸c˜ao. Essa fase ´e opcional. A id´eia ´e
que um agente com conhecimento global realize sobre uma solu¸c˜ao a¸c˜oes
que formigas individuais n˜ao teriam condi¸c˜oes de fazer. Por exemplo, um
agente global pode observar o caminho de cada formiga e resolver depositar
4
feromˆonio extra nos componentes usados pela formiga que construiu a melhor
solu¸c˜ao[5]. Outro procedimento muito comum usado nesta fase ´e a aplica¸c˜ao
de uma busca local sobre as solu¸c˜oes constru´ıdas na primeira etapa, obtendo
assim um efeito maior de intensifica¸c˜ao. De acordo com St¨utzle, usar a
busca local nesta etapa ´e uma forma de hibridizar o ACO e as melhores
implementa¸c˜oes do ACO geralmente se valem desse recurso[6].
Por fim, temos a etapa de atualiza¸c˜ao dos feromˆonios. Essa etapa envolve
tanto o dep´osito de feromˆonio, quanto a evapora¸c˜ao de feromˆonio. Vimos
que as formigas podem depositar feromˆonio ap´os cada passo da constru¸c˜ao,
o que acontece na fase de constru¸c˜ao da solu¸c˜ao. No entanto, a formiga
tamb´em pode depositar feromˆonio ap´os construir uma solu¸c˜ao completa, o
que pode ser feito nesta terceira fase do algoritmo. Al´em disso, para evitar
uma convergˆencia muito precoce do ACO, ou que ele fique preso em um
´otimo local, o feromˆonio depositado deve evaporar ao longo do tempo. Essa
atividade tamb´em ´e realizada neste etapa e atrav´es dela obtemos um efeito
de diversifica¸c˜ao.
Em seguida, iremos apresentar trˆes varia¸c˜oes do ACO. Como ficar´a claro
adiante, a principal diferen¸ca entre eles geralmente recai sobre quando fazem
o incremento do feromˆonio e como o fazem. Era de se esperar que assim fosse,
pois esses s˜ao justamente os procedimentos respons´aveis por incorporar ao
processo de busca a experiˆencia acumulada pelas formigas.
2.1 Problema do Caixeiro Viajante - TSP
Como os testes comparativos foram feitos com o problema do Caixeiro Via-
jante, ´e oportuno que o apresentemos agora de uma maneira mais formal. O
problema, como j´a dissemos, consiste em encontrar o menor caminho para
percorrer um conjunto de cidades que est˜ao completamente conectadas entre
si. Neste trabalho, trabalhamos ap enas com a vers˜ao sim´etrica do problema.
Cada cidade ´e associada a um n´o do grafo de constru¸c˜ao das formigas. A
distˆancia entre uma cidade i e j ´e chamada de d
ij
. Assim, uma instˆancia do
TSP ´e um grafo (N, E), onde N ´e o conjunto de cidades e E o conjunto de
arestas entre as cidades.
2.2 Ant System - AS
Ant System (AS) foi o primeiro exemplo de algoritmo ACO, desenvolvido por
por Marco Dorigo, Vitorio Maniezzo e Alberto Colorni em 1996[4]. Embora o
seu desempenho n˜ao seja suficiente para competir com os melhores algoritmos
propostos para resolver o TSP, ele ´e usado como ponto de partida para a
formula¸c˜ao de outros algoritmos ACO[5].
5