IMPRIMIR VOLTAR
B. Engenharias - 1. Engenharia - 6. Engenharia de Produção
A MODELAGEM “ANT SYSTEM” (AS) PARA RESOLVER O PROBLEMA DO CAIXEIRO VIAJANTE (TSP)
Fernando Cesar Mendonca  1
Ruben Augusto Romero Lazaro  1
(1. Departamento de Engenharia Elétrica DEE/FEIS/UNESP)
INTRODUÇÃO:
Se observarmos o comportamento de uma colônia de formigas, perceberemos que há uma grande organização social, com papéis muito bem definidos a cada membro. Toda organização é feita através de uma comunicação química de feromônios. Experimentalmente, observou-se que formigas sempre encontram os menores caminhos do formigueiro e o alimento. Quando surge um obstáculo, uma formiga aprende o novo caminho ótimo e, via feromônio, ensina as companheiras a seguí-la. Enquanto caminha do formigueiro ao alimento (ou vice-versa), uma formiga deposita feromônio. Com o passar do tempo, este feromônio, por ser gás, evapora, diminuindo sua concentração na trilha. Assim, em um caminho é curto, a concentração de feromônios aumentará por dois motivos: muitas formigas passarão por ele e, devido à sua pequenez, o feromônio pouco evapora; já com os caminhos longos ocorre o oposto, surgindo um processo autocatalítico para encontrar bons e descartar maus caminhos. O Problema do Caixeiro-viajante (TSP) consiste em um caixeiro-viajante que sai de sua casa para atender várias cidades (nós) e depois retornar ao lar, otimizando tempo e custo de viagem. Cada nó é como um ponto de demanda e deverá, então, ser atendido. A única restrição do TSP é que todos os nós devam ser visitados pelo menos uma vez. Para minimizar custos, cada nó será visitado uma e apenas uma vez. O TSP se enquadra no grupo de problemas NP-hard. A literatura diz que é praticamente impossível a resolução exata do TSP para mais de 70 nós.
METODOLOGIA:
Foi modelado um algoritmo e uma implementação computacional em Fortran para simular o algoritmo AS e suas fases para um exemplo conhecido do TSP. Uma estrutura simplificada do algoritmo pode ser vista abaixo: Programa ACO Iniciar Enquanto (não terminar) Construção de soluções Busca local Atualização de estatística Atualização de feromônio Fim do enquanto Fim do programa A construção de um caminho é gerenciada pelo procedimento Construção de Soluções. O “gargalo” deste procedimento é a escolha da próxima cidade a ser visitada por cada agente, o computador usará uma roleta aleatória, onde o tamanho de cada fatia da roleta relativa à cada idade é proporcional à heurística. O último passo de uma iteração é a atualização do feromônio. Há duas ações para esta atualização: evaporação e depósito. A evaporação provoca uma diminuição do valor do feromônio em todos os arcos ij através de um fator ρ. Já o depósito adiciona feromônio em todos arcos ij que pertençam aos caminhos construídos por cada agente. Uma vez gerada uma solução, ela pode ser melhorada através de uma busca local 2-opt, que consiste em trocar dois ramos do caminho por dois novos ramos. Os últimos passos da implementação consistem em atualizar estatísticas, principalmente o melhor caminho da iteração ou o global, ou o número de iterações. Foram testados vários exemplos de TSP com diferentes quantidades de nós e observada a convergência computacional neste aumento. Também se estudou a sensibilidade dos parâmetros envolvidos.
RESULTADOS:
Obteve-se, a partir do programa, para um exemplo contendo 16 cidades distribuídas em um grid de 4x4 e com 10 unidades de comprimento para cada nó. Foi encontrada uma solução ótima, já esperada, com um trecho de 160 unidades de comprimento. Ao aumentar para um exemplo contendo 20 cidades, distribuídas em um grid de 5x4 e com as mesmas 10 unidades de comprimento a cada nó, obteve-se a solução ótima esperada com um trecho de 200 unidades de comprimento, entretanto com um esforço computacional muito maior do que o exemplo com 16 cidades. Um exemplo contendo 25 nós distribuídos de modo circular e distância 10 unidades de comprimento convergiu rapidamente para um caminho circular com 250 unidades de comprimento. Exemplos até 30 nós não foram resolvidos de maneira exata, mas com erro inferior a 5%. Exemplos com mais de 30 nós não foram resolvidos. Percebeu-se também que baixa evaporação facilitaria a estagnação (um agente encontra uma solução fraca e todos o seguem).
CONCLUSÕES:
Com os resultados obtidos na implementação, pôde-se perceber que realmente há uma convergência semelhante ao comportamento das formigas. O sistema começou com uma solução inicial qualquer e, para problemas pequenos, rapidamente convergiu para uma solução ótima e, no caso de problemas maiores, convergiu lentamente para solução ótima ou solução muito boa. Como se era de esperar, problemas enormes não se obtiveram soluções. Pôde-se também analisar comportamentos do problema com alterações nos diversos parâmetros do problema (depósito e evaporação de feromônio, porcentagem máxima e mínima de feromônio depositada, etc).
 
Palavras-chave: TSP; roteamento; Pesquisa operacional.
Anais da 58ª Reunião Anual da SBPC - Florianópolis, SC - Julho/2006