O que é o Ant System (AS)?
O Ant System (AS) é o primeiro algoritmo de colônia de formigas proposto na história. Ele foi criado por Marco Dorigo em 1992 como tese de doutorado. O AS resolve problemas de otimização combinatória usando formigas artificiais. Cada formiga constrói uma solução completa passo a passo probabilisticamente. A probabilidade de escolher um caminho depende do feromônio e da heurística local. Após todas as formigas terminarem, o feromônio é atualizado globalmente. As melhores rotas recebem mais feromônio, reforçando o aprendizado coletivo. O AS é considerado o marco zero dos algoritmos de inteligência de enxame. Ele é simples, intuitivo e serve como base para todas as variantes posteriores.
Características fundamentais do AS
O AS possui três características principais que o definem. Primeiro, a regra de transição probabilística combina feromônio (τ) e visibilidade (η). Essa regra usa parâmetros α e β para controlar a influência de cada fator. Segundo, a atualização do feromônio ocorre após todas as formigas construírem rotas. Todas as formigas depositam feromônio, mas as melhores depositam mais intensamente. Terceiro, a evaporação do feromônio reduz todos os valores a cada iteração. Isso evita convergência prematura e permite esquecer caminhos ruins. O AS também usa uma lista tabu para proibir visitas repetidas a cidades. Essa lista garante que cada formiga construa uma rota válida e completa. Por fim, o AS é estocástico, ou seja, tem componentes aleatórios controlados.
Vantagens e limitações do AS
O AS é extremamente fácil de implementar e entender conceitualmente. Ele funciona bem para problemas de pequeno e médio porte, como TSP com 30 cidades. Além disso, ele é robusto a pequenas variações nos parâmetros iniciais. Contudo, o AS tem convergência lenta para problemas grandes (mais de 100 cidades). Ele também pode estagnar em ótimos locais se a evaporação for muito baixa. Outra limitação é o custo computacional, pois cada formiga avalia uma rota completa. Apesar disso, o AS é uma excelente ferramenta educacional e introdutória. Ele ensina os fundamentos do feromônio, exploração e explotação de forma clara.
O AS foi originalmente testado no problema do caixeiro viajante (TSP). Ele superou outras heurísticas simples da época, como vizinho mais próximo. A ideia de feromônio artificial foi inspirada no comportamento real de formigas. Formigas reais depositam feromônio ao caminhar, e outras seguem o rastro. No AS, a intensidade do feromônio é proporcional à qualidade da solução. Rotas mais curtas recebem depósito maior, pois 1/custo é usado como quantidade. A evaporação ocorre a cada iteração, simulando a dissipação natural do feromônio. Os parâmetros α e β são ajustados empiricamente; valores típicos são α=1 e β=2. O número de formigas geralmente iguala o número de cidades no TSP. O AS pode ser paralelizado facilmente, pois cada formiga é independente. Ele também pode ser estendido com heurísticas específicas para cada problema. Por exemplo, em roteamento com janelas de tempo, a visibilidade inclui atrasos. O AS é a base do Ant Colony Optimization (ACO), que engloba várias variantes. Assim, o AS é um algoritmo histórico, didático e ainda relevante.
Um exemplo clássico é o TSP com 10 cidades europeias (coordenadas fixas). O objetivo é encontrar a rota mais curta que visita todas as cidades. O AS constrói rotas, deposita feromônio e evolui a solução iterativamente. Após algumas dezenas de iterações, a rota ótima é encontrada com alta probabilidade.
Enunciado do exemplo clássico
Implemente o Ant System para o TSP com 15 cidades geradas aleatoriamente em [0,50]². Use 20 formigas, 100 iterações, α=1, β=2, ρ=0.3, τ₀=0.1 e depósito proporcional a 1/custo. Armazene o comprimento da melhor rota e o melhor caminho a cada iteração. Plote a evolução do melhor custo e a melhor rota final sobre as cidades.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
import numpy as np import matplotlib.pyplot as plt # Gerar cidades aleatórias np.random.seed(7) n = 15 coords = np.random.rand(n, 2) * 50 # Matriz de distâncias dist = np.zeros((n, n)) for i in range(n): for j in range(n): dist[i,j] = np.linalg.norm(coords[i] - coords[j]) # Parâmetros AS num_formigas = 20 iteracoes = 100 alpha = 1.0 beta = 2.0 rho = 0.3 tau0 = 0.1 # Inicializar feromônio tau = np.full((n, n), tau0) np.fill_diagonal(tau, 0) # Históricos melhor_custo_hist = [] melhor_rota_hist = [] melhor_custo_global = np.inf melhor_rota_global = None for it in range(iteracoes): rotas = [] custos = [] for _ in range(num_formigas): # Escolher cidade inicial aleatória atual = np.random.randint(n) rota = [atual] nao_visitados = list(range(n)) nao_visitados.remove(atual) while nao_visitados: # Calcular probabilidades probs = [] for prox in nao_visitados: prob = (tau[atual, prox] ** alpha) * ((1.0 / dist[atual, prox]) ** beta) probs.append(prob) probs = np.array(probs) probs /= probs.sum() # Escolher próximo prox = np.random.choice(nao_visitados, p=probs) rota.append(prox) nao_visitados.remove(prox) atual = prox # Fechar rota custo = sum(dist[rota[i], rota[(i+1) % n]] for i in range(n)) rotas.append(rota) custos.append(custo) if custo < melhor_custo_global: melhor_custo_global = custo melhor_rota_global = rota.copy() melhor_custo_hist.append(melhor_custo_global) melhor_rota_hist.append(melhor_rota_global.copy()) # Evaporação tau *= (1 - rho) # Depósito de todas as formigas for rota, custo in zip(rotas, custos): deposito = 1.0 / custo for i in range(n): u = rota[i] v = rota[(i+1) % n] tau[u, v] += deposito tau[v, u] += deposito # Depósito extra da melhor formiga (elitismo) deposito_elite = 1.0 / melhor_custo_global for i in range(n): u = melhor_rota_global[i] v = melhor_rota_global[(i+1) % n] tau[u, v] += deposito_elite tau[v, u] += deposito_elite print(f"Melhor custo encontrado: {melhor_custo_global:.2f}") print("Melhor rota (ordem das cidades):", melhor_rota_global) # Gráficos plt.figure(figsize=(12, 5)) plt.subplot(1, 2, 1) plt.plot(melhor_custo_hist, 'g-', linewidth=2) plt.title('Evolução do Melhor Custo - Ant System') plt.xlabel('Iteração') plt.ylabel('Comprimento da rota') plt.grid(True) plt.subplot(1, 2, 2) plt.scatter(coords[:,0], coords[:,1], c='darkred', s=80, zorder=5) rota_fechada = melhor_rota_global + [melhor_rota_global[0]] for i in range(len(rota_fechada)-1): c1 = rota_fechada[i] c2 = rota_fechada[i+1] plt.plot([coords[c1,0], coords[c2,0]], [coords[c1,1], coords[c2,1]], 'b-', linewidth=1.5) for i, (x, y) in enumerate(coords): plt.annotate(str(i), (x+1, y+1), fontsize=9, fontweight='bold') plt.title('Melhor Rota Encontrada pelo AS') plt.xlabel('X') plt.ylabel('Y') plt.grid(True) plt.tight_layout() plt.show() |
Este código implementa o Ant System com atualização elitista. A curva de convergência mostra a queda rápida do custo nas primeiras iterações. A rota final é desenhada sobre as cidades, evidenciando um caminho curto. O AS encontra uma solução de boa qualidade, mesmo com parâmetros simples. Para iniciantes, este exemplo revela o poder do feromônio coletivo. O Ant System é, portanto, a porta de entrada para toda a família ACO.