O que são algoritmos de colônias de formigas?
Algoritmos de colônias de formigas (ACO) são meta-heurísticas inspiradas no forrageamento real. Formigas depositam feromônio no caminho percorrido para comunicar boas rotas. Quanto mais formigas usam um caminho, mais feromônio ele acumula. Caminhos mais curtos são percorridos mais rapidamente, recebendo mais depósito. Assim, a colônia converge coletivamente para a rota ótima. O ACO traduz esse comportamento para resolver problemas de otimização combinatória. Cada “formiga” artificial constrói uma solução passo a passo probabilisticamente. A probabilidade depende do feromônio atual e de uma heurística local (ex.: distância). Portanto, o ACO é um algoritmo estocástico baseado em população e memória.
Componentes principais do algoritmo
O ACO possui três elementos centrais: feromônio, visibilidade e evaporação. O feromônio τ representa a atratividade acumulada de cada aresta (caminho). A visibilidade η é uma informação heurística, como o inverso da distância. A regra de transição combina τ e η com pesos α e β (parâmetros ajustáveis). Após todas as formigas construírem soluções, o feromônio é atualizado. As melhores soluções depositam mais feromônio nas arestas que as compõem. Antes disso, uma taxa de evaporação ρ reduz todo o feromônio existente. Isso evita convergência prematura e permite esquecer caminhos ruins. Dessa forma, o algoritmo equilibra exploração e explotação ao longo do tempo.
Aplicações clássicas e vantagens
O ACO é famoso pelo problema do caixeiro viajante (TSP). Ele também é aplicado em roteamento de veículos, escalonamento e redes. Uma grande vantagem é a capacidade de encontrar boas soluções rapidamente. Além disso, ele lida bem com restrições complexas e dinâmicas. O algoritmo é paralelizável, pois cada formiga trabalha independentemente. Contudo, seu desempenho depende de ajustes finos dos parâmetros (α, β, ρ). Para iniciantes, o ACO oferece uma analogia biológica clara e intuitiva.
O ACO foi proposto por Marco Dorigo em 1992 em sua tese de doutorado. Desde então, muitas variantes surgiram: Ant System, Max-Min Ant System, etc. A versão original (Ant System) é simples, mas pode ser lenta para grandes problemas. Melhorias como a atualização elitista (depósito extra na melhor rota) aceleram a convergência. Outra variação é o uso de listas tabu para evitar que formigas revisitam cidades. A evaporação do feromônio é crucial para evitar estagnação em ótimos locais. Sem ela, o algoritmo ficaria preso na primeira boa solução encontrada. A combinação de feromônio e heurística cria um equilíbrio dinâmico. Em problemas com muitas restrições, o ACO pode ser estendido com penalidades. Por exemplo, em roteamento com janelas de tempo, a heurística inclui atrasos. O ACO também é usado em problemas de agrupamento (clustering) e classificação. Sua flexibilidade permite acoplamento com outras técnicas (híbridos). Ele é considerado um dos algoritmos swarm intelligence mais bem-sucedidos. Assim, o ACO é uma ferramenta indispensável para otimização discreta.
Um exemplo clássico é o problema do caixeiro viajante com 10 cidades. As coordenadas são geradas aleatoriamente em um plano 2D. O objetivo é encontrar a rota mais curta que visita cada cidade uma vez. O ACO constrói rotas, deposita feromônio e evolui a solução. Após algumas iterações, a rota ótima (ou próxima) é descoberta.
Enunciado do exemplo clássico
Implemente o Ant System (AS) para resolver o TSP com 20 cidades aleatórias em [0,100]². Use 50 formigas, 200 iterações, α=1, β=2, ρ=0.5, e depósito inicial τ₀=1. Aplique atualização elitista (melhor formiga deposita feromônio extra). Armazene o comprimento da melhor rota a cada iteração. Ao final, plote a curva de convergência e a melhor rota encontrada 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 119 120 121 |
import numpy as np import matplotlib.pyplot as plt # Gerar cidades aleatórias np.random.seed(42) n_cidades = 20 coords = np.random.rand(n_cidades, 2) * 100 # Matriz de distâncias euclidianas dist = np.zeros((n_cidades, n_cidades)) for i in range(n_cidades): for j in range(n_cidades): dist[i,j] = np.linalg.norm(coords[i] - coords[j]) # Parâmetros ACO num_formigas = 50 iteracoes = 200 alpha = 1.0 beta = 2.0 rho = 0.5 tau0 = 1.0 elite = 1 # número de melhores formigas para depósito extra # Inicialização do feromônio tau = np.full((n_cidades, n_cidades), tau0) np.fill_diagonal(tau, 0) # Histórico do melhor comprimento melhor_hist = [] melhor_rota = None melhor_custo = np.inf for it in range(iteracoes): # Construir soluções para cada formiga rotas = [] custos = [] for _ in range(num_formigas): # Escolher cidade inicial aleatória cidade_atual = np.random.randint(n_cidades) rota = [cidade_atual] visitados = set([cidade_atual]) while len(rota) < n_cidades: # Calcular probabilidades para as cidades não visitadas nao_visitados = [c for c in range(n_cidades) if c not in visitados] probs = [] for prox in nao_visitados: prob = (tau[cidade_atual, prox] ** alpha) * ((1.0 / dist[cidade_atual, prox]) ** beta) probs.append(prob) probs = np.array(probs) probs /= probs.sum() # Escolher próxima cidade por roleta prox_cidade = np.random.choice(nao_visitados, p=probs) rota.append(prox_cidade) visitados.add(prox_cidade) cidade_atual = prox_cidade # Fechar a rota (voltar à origem) custo = sum(dist[rota[i], rota[(i+1) % n_cidades]] for i in range(n_cidades)) rotas.append(rota) custos.append(custo) if custo < melhor_custo: melhor_custo = custo melhor_rota = rota.copy() melhor_hist.append(melhor_custo) # Evaporação do feromônio tau *= (1 - rho) # Depósito de feromônio (todas as formigas) for rota, custo in zip(rotas, custos): deposito = 1.0 / custo for i in range(n_cidades): u = rota[i] v = rota[(i+1) % n_cidades] tau[u, v] += deposito tau[v, u] += deposito # simétrico # Atualização elitista (melhor formiga deposita extra) for _ in range(elite): deposito_elite = 1.0 / melhor_custo for i in range(n_cidades): u = melhor_rota[i] v = melhor_rota[(i+1) % n_cidades] tau[u, v] += deposito_elite tau[v, u] += deposito_elite # Resultados print(f"Melhor comprimento encontrado: {melhor_custo:.2f}") print("Melhor rota (ordem das cidades):", melhor_rota) # Gráfico 1: Curva de convergência plt.figure(figsize=(12, 5)) plt.subplot(1, 2, 1) plt.plot(melhor_hist, 'b-', linewidth=2) plt.title('Convergência do ACO - TSP') plt.xlabel('Iteração') plt.ylabel('Melhor comprimento da rota') plt.grid(True) # Gráfico 2: Melhor rota sobre as cidades plt.subplot(1, 2, 2) # Desenhar cidades plt.scatter(coords[:,0], coords[:,1], c='red', s=80, zorder=5) # Desenhar a rota rota_fechada = melhor_rota + [melhor_rota[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) # Numerar cidades for i, (x, y) in enumerate(coords): plt.annotate(str(i), (x+1, y+1), fontsize=8, fontweight='bold') plt.title('Melhor Rota Encontrada') plt.xlabel('Coordenada X') plt.ylabel('Coordenada Y') plt.grid(True) plt.tight_layout() plt.show() |
Este código implementa o Ant System clássico com atualização elitista. A curva de convergência mostra a rápida melhoria nas primeiras iterações. O gráfico da rota exibe a ordem das cidades e o caminho percorrido. O ACO encontra uma rota curta, embora não necessariamente a ótima global. Para iniciantes, este exemplo demonstra a emergência de soluções coletivas. Os feromônios guiam as formigas, mesmo sem controle centralizado. Assim, os algoritmos de colônias de formigas são poderosos e inspiradores.