O que é o Ant Colony System (ACS)?
O Ant Colony System (ACS) é uma evolução do Ant System original, proposta por Dorigo e Gambardella em 1997. Ele melhora a exploração e a convergência usando mecanismos mais sofisticados. Diferentemente do AS, o ACS introduz uma regra de transição pseudo-aleatória. Essa regra equilibra exploração e explotação de forma mais agressiva. Além disso, o ACS usa evaporação local durante a construção da rota. Cada formiga evapora feromônio das arestas que acabou de percorrer. Isso reduz a atratividade de caminhos já usados, promovendo diversidade. Após todas as formigas terminarem, apenas a melhor formiga deposita feromônio globalmente. Essa atualização global é mais seletiva, acelerando a convergência para boas soluções. Portanto, o ACS é mais rápido e eficiente que o AS para problemas grandes.
Características fundamentais do ACS
O ACS possui quatro características distintas que o diferenciam do AS. Primeiro, a regra de transição usa um parâmetro q₀ (entre 0 e 1). Com probabilidade q₀, a formiga escolhe a aresta mais promissora (exploração). Caso contrário, ela faz uma escolha probabilística como no AS (exploração). Segundo, a evaporação local é aplicada imediatamente após cada passo da formiga. Ela reduz o feromônio da aresta percorrida por um fator ξ (geralmente 0.1). Isso incentiva outras formigas a buscar caminhos alternativos. Terceiro, a atualização global é realizada apenas pela melhor formiga da iteração. Ela deposita feromônio nas arestas da rota ótima global ou da melhor iteração. Quarto, os parâmetros α e β são frequentemente fixados em 1 e 2, respectivamente. O ACS também usa uma lista tabu para evitar repetição de cidades. Essas características tornam o ACS mais adaptativo e com melhor desempenho.
Vantagens e aplicações típicas
O ACS é amplamente usado em problemas de roteamento e logística. Ele converge mais rapidamente que o AS, especialmente em TSP com 50+ cidades. Além disso, ele lida melhor com dinâmicas e restrições temporais. Sua regra pseudo-aleatória evita estagnação prematura em ótimos locais. Contudo, o ACS tem mais parâmetros para ajustar (q₀, ξ, β). Isso pode tornar a calibração mais trabalhosa para iniciantes. Ainda assim, o ACS é a base de muitas aplicações comerciais de otimização. Ele é considerado o estado da arte entre os algoritmos de colônia de formigas.
O ACS foi projetado especificamente para melhorar o desempenho do AS no TSP. Ele introduziu a ideia de “exploração guiada” pela regra pseudo-aleatória. Quando q ≤ q₀, a formiga escolhe a aresta com maior τ * η^β (gulosa). Quando q > q₀, ela usa a distribuição de probabilidades clássica. Isso permite um controle fino entre seguir o melhor caminho ou explorar novos. A evaporação local é aplicada com fator ξ, reduzindo τ em (1-ξ)*τ. Esse mecanismo simula o efeito de várias formigas usando a mesma aresta. A atualização global deposita feromônio apenas na melhor rota encontrada. O depósito é proporcional a 1/L_best, onde L_best é o comprimento da melhor rota. O ACS também permite o uso da melhor solução global ou da iteração corrente. Na prática, usar a melhor global acelera a convergência significativamente. O ACS supera o AS em qualidade de solução e tempo de execução. Ele é frequentemente comparado a algoritmos genéticos e simulated annealing. Assim, o ACS é uma ferramenta robusta e confiável para otimização combinatória.
Um exemplo clássico é o TSP com 30 cidades distribuídas aleatoriamente. O ACS encontra rotas muito próximas do ótimo em poucas iterações. A regra pseudo-aleatória evita que todas as formigas sigam o mesmo caminho. A evaporação local garante que arestas recentes percam atratividade temporária. Esse equilíbrio resulta em soluções de alta qualidade de forma consistente.
Enunciado do exemplo clássico
Implemente o Ant Colony System para o TSP com 25 cidades em [0,100]². Use 25 formigas, 150 iterações, α=1, β=2, ρ=0.1 (evaporação global), ξ=0.1 (evaporação local), q₀=0.9. A atualização global deve usar a melhor rota global encontrada até o momento. Armazene o custo da melhor rota a cada iteração e a própria rota. Plote a convergência e a rota final sobre as cidades com setas indicando a direção.
|
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 119 120 121 122 123 124 125 |
import numpy as np import matplotlib.pyplot as plt # Gerar cidades np.random.seed(13) n = 25 coords = np.random.rand(n, 2) * 100 # 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 ACS num_formigas = 25 iteracoes = 150 alpha = 1.0 beta = 2.0 rho = 0.1 # evaporação global xi = 0.1 # evaporação local q0 = 0.9 tau0 = 1.0 / (n * np.mean(dist[dist > 0])) # Inicializar feromônio tau = np.full((n, n), tau0) np.fill_diagonal(tau, 0) # Históricos melhor_custo_hist = [] melhor_rota_global = None melhor_custo_global = np.inf for it in range(iteracoes): rotas = [] custos = [] for _ in range(num_formigas): atual = np.random.randint(n) rota = [atual] nao_visitados = list(range(n)) nao_visitados.remove(atual) while nao_visitados: # Regra de transição pseudo-aleatória if np.random.random() < q0: # Escolha gulosa (exploração) probs = [] for prox in nao_visitados: prob = (tau[atual, prox] ** alpha) * ((1.0 / dist[atual, prox]) ** beta) probs.append(prob) prox = nao_visitados[np.argmax(probs)] else: # Escolha probabilística (exploração) 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() prox = np.random.choice(nao_visitados, p=probs) # Evaporação local (na aresta percorrida) tau[atual, prox] = (1 - xi) * tau[atual, prox] tau[prox, atual] = tau[atual, prox] 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) # Evaporação global tau *= (1 - rho) # Depósito global apenas pela melhor formiga (global) deposito = 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 tau[v, u] += deposito print(f"Melhor custo final: {melhor_custo_global:.2f}") print("Melhor rota:", melhor_rota_global) # Gráficos plt.figure(figsize=(12, 5)) plt.subplot(1, 2, 1) plt.plot(melhor_custo_hist, 'r-', linewidth=2) plt.title('Convergência do Ant Colony System') plt.xlabel('Iteração') plt.ylabel('Melhor comprimento') plt.grid(True) plt.subplot(1, 2, 2) plt.scatter(coords[:,0], coords[:,1], c='darkblue', 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] # Desenhar seta indicando direção dx = coords[c2,0] - coords[c1,0] dy = coords[c2,1] - coords[c1,1] plt.arrow(coords[c1,0], coords[c1,1], dx*0.9, dy*0.9, head_width=2.0, head_length=2.0, fc='green', ec='green', length_includes_head=True, alpha=0.7) for i, (x, y) in enumerate(coords): plt.annotate(str(i), (x+1.5, y+1.5), fontsize=9, fontweight='bold') plt.title('Melhor Rota - ACS com setas') plt.xlabel('X') plt.ylabel('Y') plt.grid(True) plt.tight_layout() plt.show() |
Este código implementa o ACS com todos os seus mecanismos diferenciadores. A curva de convergência mostra uma queda acentuada e estável. A rota final é desenhada com setas, indicando a direção do percurso. A evaporação local e a regra pseudo-aleatória produzem soluções de alta qualidade. Para iniciantes, o ACS demonstra como pequenas melhorias geram grandes ganhos. O Ant Colony System é, portanto, um algoritmo maduro e eficiente.