Intervjuer med forvaltningen

ACO tem sido aplicado com sucesso em problemas de otimização combina- torial (Bonabeau et al., 1999), em que um grande conjunto de soluções disc- retas é admissível. Nesses casos, técnicas tradicionais, como programação dinâmica, podem não ser eficientes. Castro (2006) lista alguns desses pro- blemas: roteamento de veículos, ordenação sequencial, coloração de grafos, escalonamento de máquinas e caixeiro viajante. A fim de ilustrar a aplicação do ACO, discute-se, nesta seção, o último problema.

3.4.1 O problema do caixeiro viajante

Um exemplo clássico em otimização combinatorial é o Problema do Caixeiro Viajante (Traveling Salesman Problem - TSP) (Deneubourg et al., 1990). Em sua versão tradicional, um caixeiro deve visitar n cidades em sua área de atuação. Ele começa por uma cidade base e visita cada uma das n cidades uma única vez e retorna ao ponto de partida. O custo de viajar entre duas cidades é proporcional à distância entre elas. A solução final do problema consiste em percorrer a rota com a menor distância total.

Na prática, o TSP é representado por um grafo ponderado, em que cada cidade corresponde a um nó, e o peso das arestas indicam a distância entre as cidades conectadas. O grafo é dito completamente conectado quando há ligações entre todos os pares de nós e parcialmente conectado caso contrário. A Figura 3.2 ilustra um exemplo de TSP. Nela tem-se um grafo ponderado totalmente conectado.

Figura 3.2: Exemplo do problema do caixeiro viajante

Apesar de parecer trivial, o TSP é um problema NP-Difícil (Dorigo et al., 2006), sendo que seu custo computacional cresce fatorialmente em função do

número de cidades. Para n cidades completamente interconectadas, há (n−1)! rotas possíveis, o que demanda (n−1)(n−1)! operações de soma para que todos os possíveis ciclos sejam encontrados utilizando métodos exatos. Por exemplo, para calcular todos os possíveis caminhos entre 50 cidades, seria necessário

calcular aproximadamente 1064 _{operações de soma. Uma alternativa para o}

alto custo computacional dos métodos exatos na solução do TSP é o uso de meta-heurísticas, que são capazes de encontrar boas soluções, mas não ne- cessariamente ótimas, em um intervalo de tempo razoável.

3.4.2 Solução por ACO

Dorigo (1992) desenvolveu o primeiro algoritmo heurístico de otimização por colônia de formigas, nomeado Ant System (AS). Esse algoritmo pode ser aplicado a problemas mais complexos àquele exemplificado na Figura 3.1, em que os valores para os feromônios são associados diretamente à solução do problema, ou seja, um único parâmetro para o caminho mais curto e outro para o mais longo. Esse modelo implica que as soluções sejam conhecidas previamente. No entanto, em problemas de otimização combinatorial, os va- lores de feromônio são parte da solução, que é desconhecida, e a combinação das partes resulta na solução ótima do problema.

Nesse sentido, Dorigo adaptou o comportamento das formigas para en- contrar soluções ótimas para o TSP. Uma instância do TSP pode ser re- presentada pelo grafo completamente conectado, não direcionado e valorado

G(V, E), onde V = {v1, v2, . . . , vn} representa o conjunto de vértices (localidades)

e E = {ei,j = {i, j} |vi, vj ∈ V, i 6= j} consiste no número de arestas (estradas, por

exemplo) do grafo. Cada aresta {i, j} possui seu respectivo custo (distância)

para o agente ir de vi até vj. Portanto, o espaço de busca C é formado por

todos os ciclos possíveis em G. A função objetivo de um ciclo c ∈ C resulta na soma do custo das arestas que estão em c. O modelo mais comum para o problema TSP é o binário, em que uma aresta é marcada como visitada ou

não visitada para compor a solução final.

Aplicando o algoritmo AS para solucionar o problema TSP, os agentes equivalem às formigas e a colônia de formigas tem a função de encontrar o menor caminho tal que todos os vértices do grafo sejam visitados uma única

vez (voltando ao vértice de origem). Nota-se, então, que a aresta ei,j é consider-

ada parte da solução do menor caminho. Diferentemente do exemplo anterior, no TSP, a formiga deve encontrar combinações de arestas cujo trajeto seja o mais curto possível. À medida que uma formiga constrói sua solução (com- pleta seu ciclo), as demais são atraídas a realizar o mesmo percurso se esta for considerada uma boa solução. Para construir a solução, as arestas do

probabilidades para a formiga escolher qualquer outro vértice são idênticas. Todos os vértices do grafo devem ser marcados como não-visitados, exceto o(s) vértice(s) de origem, que é(são) escolhido(s) aleatoriamente e onde todas as formigas iniciam seu ciclo (onde cada formiga inicia em um vértice distinto). A partir desse ponto, cada formiga move-se do seu vértice corrente até outro que ainda não esteja visitado, assinalando-o, em seguida, como visitado. As arestas escolhidas são agregadas a fim de construir uma solução candidata. Um ciclo é finalizado quando todos os vértices estão marcados como visitados por uma formiga e esta volta à sua origem. Esta maneira de encontrar uma

solução candidata implica que cada formiga k possui uma memória Tk, que

armazena os vértices já visitados, indicando o caminho percorrido. Por meio

de Tk, é possível contabilizar o tamanho do caminho percorrido pela formiga k

após completar seu ciclo, que é denotado por Lk. No entanto, o interesse do

algoritmo é minimizar a função objetivo f(c), que consiste no tamanho do ciclo c (percurso) realizado pelas formigas

Um fator relevante para a construção da solução é a escolha da próxima aresta. Um dos problemas encontrados nesse processo é a saturação da con- centração de feromônios, levando a colônia a tender por soluções locais (óti- mos locais). Conforme o sistema citado em Dorigo et al. (1991a), dois fatores devem ser considerados no processo de escolha de uma determinada locali- dade:

• A visibilidade da localidade, denotada por ηij, é dada por 1/di,j, em que

di,j é a distância entre os vértices vi e vj. Essa visibilidade considera a

proximidade (custo) da localidade no processo de escolha, fornecendo ao algoritmo uma característica de uma heurística construtiva;

• A intensidade de feromônio no caminho, dada por τei,j(t), onde o sistema

considera o quão interessante é o caminho, visto que quanto maior o

valor de τei,j(t) maior é a probabilidade desse caminho ser escolhido. Com

este fator, a heurística ganha a característica de autocatalítica.

Diante disso, a probabilidade da formiga k se mover do vértce vi para o

vértice vj no instante t é dada por:

pk_ij(t) = [τei,j(t)] α_[η i,j]β P j /∈Tk[τei,j(t)] α_[η i,j]β (3.3) em que α ≥ 0 controla a influência do feromônio e β ≥ 1 controla a influência da informação heurística. Além disso, ambos controlam a qualidade da aresta (de acordo com a quantidade de feromônio depositada) e sua visibilidade.

Uma das peculiaridades desta abordagem consiste no depósito de feromô-

duzindo que outras formigas tenham maiores chances de passar pelas mes- mas arestas. É considerado que a quantidade de feromônio depositada nas arestas percorridas é constante para todas as formigas. A concentração de feromônio deixada pela formiga k ocorre durante o deslocamento entre dois vértices, portanto, entre os instantes t e t + 1, e é denotada como:

∆τk ei,j(t, t + 1) =    Q f (c), se ei,j ∈ Tk 0, caso contrário (3.4)

em que a constante positiva Q é um parâmetro do modelo e a função ob-

jetivo equivale ao comprimento do percurso realizado, f(c) = Lk. Em out-

ras palavras, a quantidade de feromônio adicionada em uma aresta depende do comprimento do caminho escolhido representado por uma solução candi- data: quanto menor o caminho, maior é a concentração de feromônio adi- cionada. Esta variação de feromônio permite que os caminhos mais curtos sejam alcançados pela intensificação da concentração de feromônio nas mel- hores arestas.

Após todas as formigas completarem um ciclo, a adição de feromônio em cada aresta do grafo é dada por:

∆τei,j(t, t + 1) =

n

X

k=1

∆τ_ek_i,j(t, t + 1) (3.5)

em que n é o número de formigas.

Assim, a concentração de feromônio nas arestas é modelada como segue:

τei,j(t + 1) = (1 − ρ)τei,j(t) + ∆τei,j(t, t + 1) (3.6)

em que ρ é a taxa de evaporação do feromônio (ver equação (3.2)).

O algoritmo para encontrar a solução do problema TSP é iterado aplicando n formigas em cada iteração. Durante a construção da solução, as formigas são atraídas a percorrer o caminho com maior quantidade de feromônio dei- xada pelas formigas nas iterações anteriores. O processo é executado até que um critério de parada seja satisfeito, por exemplo, número máximo de itera- ções, limite de tempo ou estagnação do sistema. No caso de estagnação, é mais provável que a solução ótima seja encontrada. Desde que a quantidade de feromônio depositada nas arestas é proporcional à qualidade do caminho no qual estas pertencem, os caminhos que representam as melhores soluções possuirão maior concentração de feromônio. Ao longo das inúmeras iterações, o caminho que representa a melhor solução passar a ser mais utilizado, ou en- tão, a única utilizada pelas formigas, ocasionando na estagnação do sistema e resultando na descoberta da solução do problema (o caminho ótimo).