O que são estratégias evolutivas?
Estratégias evolutivas (EE) são algoritmos de otimização inspirados na evolução biológica. Diferentemente dos algoritmos genéticos, elas focam em parâmetros contínuos e reais. Cada indivíduo é um vetor de números, não uma árvore ou cadeia binária. A principal inovação é a auto-adaptação dos passos de mutação durante a busca. Cada indivíduo carrega seus próprios desvios-padrão, que também evoluem. Assim, o algoritmo aprende qual a melhor intensidade de variação para cada dimensão. Isso torna as EE muito eficientes para problemas numéricos de alta precisão. Elas são populares em robótica, controle de processos e aprendizado de máquina.
Mecanismos centrais de funcionamento
As EE operam com uma população de candidatos, geralmente pequena. Cada geração produz filhos por mutação gaussiana a partir dos pais. A mutação adiciona ruído proporcional ao desvio-padrão de cada indivíduo. Os melhores filhos substituem os piores pais, seguindo uma regra de seleção. Existem duas variantes principais: (μ, λ) e (μ + λ). Na primeira, apenas os λ filhos competem entre si para os próximos μ pais. Na segunda, pais e filhos juntos são avaliados, e os μ melhores sobrevivem. A seleção é determinística e baseada exclusivamente no valor da aptidão. Portanto, as EE são rápidas e requerem poucos parâmetros ajustáveis.
Vantagens e aplicações típicas
Uma grande vantagem é a capacidade de lidar com paisagens ruidosas e não-lineares. Elas também convergem mais rapidamente que algoritmos genéticos em muitos casos. Além disso, a auto-adaptação elimina a necessidade de ajustar a taxa de mutação. Isso as torna ideais para problemas com muitas variáveis interdependentes. Por exemplo, são usadas para calibrar modelos climáticos e financeiros. Também são aplicadas no design de antenas e na sintonia de controladores PID. Sua simplicidade conceitual atrai iniciantes que desejam resultados práticos.
As estratégias evolutivas foram propostas por Rechenberg e Schwefel nos anos 1960. Elas se diferenciam dos algoritmos genéticos pelo uso de codificação real direta. Não há crossover na forma clássica, apenas mutação como operador principal. Contudo, variantes modernas incorporam crossover para melhorar a diversidade. A aptidão é calculada diretamente a partir do vetor de parâmetros do indivíduo. Quanto menor o erro ou maior o lucro, melhor é o indivíduo avaliado. A seleção é elitista, garantindo que a melhor solução nunca seja perdida. Isso confere estabilidade e monotonicidade à melhoria ao longo das gerações. As EE são particularmente robustas para funções com múltiplos mínimos locais. Elas escapam desses mínimos ajustando dinamicamente os passos de mutação. Um passo grande explora regiões distantes; um passo pequeno refina a solução. Essa dualidade é controlada pela evolução dos próprios desvios-padrão. Assim, a estratégia evolutiva é um método adaptativo e autossuficiente. Ela é frequentemente a primeira escolha para otimização contínua.
Um exemplo clássico é a minimização da função de Rastrigin em duas dimensões. Ela tem muitos mínimos locais, mas um mínimo global em (0,0). A EE deve encontrar esse ponto com alta precisão usando mutação auto-adaptativa. A população inicial é espalhada aleatoriamente no intervalo [-5, 5]. Após 100 gerações, a solução converge para próximo de zero. Esse problema ilustra a eficácia da auto-adaptação em paisagens complexas.
Enunciado do exemplo clássico
Utilize uma estratégia evolutiva (μ, λ) com μ=10 e λ=50 para minimizar a função de Rastrigin: f(x,y) = 20 + x² + y² – 10*(cos(2πx) + cos(2πy)), com x,y ∈ [-5,5]. Execute 200 gerações e armazene o melhor valor de aptidão por geração. Ao final, plote a evolução do melhor erro (curva de convergência). Plote também um mapa de contorno da função com o ponto final encontrado. Forneça o código Python completo, sem usar bibliotecas de evolução prontas.
|
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 |
import numpy as np import matplotlib.pyplot as plt # Função de Rastrigin (aptidão - minimizar) def rastrigin(x, y): return 20 + x**2 + y**2 - 10*(np.cos(2*np.pi*x) + np.cos(2*np.pi*y)) # Parâmetros da EE mu = 10 lambda_ = 50 geracoes = 200 dim = 2 limites = [-5, 5] # Inicialização: população de pais (mu indivíduos) pais = np.random.uniform(limites[0], limites[1], size=(mu, dim)) sigmas = np.random.uniform(0.1, 1.0, size=(mu, dim)) # desvios individuais # Histórico do melhor fitness melhor_fitness_hist = [] for gen in range(geracoes): # Gerar lambda filhos a partir dos mu pais (cada pai gera lambda/mu filhos) filhos = [] sigmas_filhos = [] for i in range(mu): for _ in range(lambda_ // mu): # Mutação dos sigmas (auto-adaptação) novo_sigma = sigmas[i] * np.exp(np.random.normal(0, 0.2, size=dim)) novo_sigma = np.clip(novo_sigma, 1e-6, 2.0) # evitar valores extremos # Mutação dos parâmetros filho = pais[i] + np.random.normal(0, novo_sigma) filho = np.clip(filho, limites[0], limites[1]) filhos.append(filho) sigmas_filhos.append(novo_sigma) filhos = np.array(filhos) sigmas_filhos = np.array(sigmas_filhos) # Avaliar aptidão de todos os filhos fitness_filhos = np.array([rastrigin(f[0], f[1]) for f in filhos]) # Seleção: escolher os mu melhores filhos (estrategia (μ, λ)) indices_melhores = np.argsort(fitness_filhos)[:mu] pais = filhos[indices_melhores] sigmas = sigmas_filhos[indices_melhores] # Registrar o melhor fitness da geração melhor_fitness_hist.append(np.min(fitness_filhos)) # Melhor solução final melhor_idx = np.argmin([rastrigin(p[0], p[1]) for p in pais]) melhor_x, melhor_y = pais[melhor_idx] melhor_f = rastrigin(melhor_x, melhor_y) print(f"Melhor solução: x = {melhor_x:.6f}, y = {melhor_y:.6f}") print(f"Valor mínimo de f(x,y) = {melhor_f:.6f}") # Gráfico 1: Curva de convergência plt.figure(figsize=(12, 5)) plt.subplot(1, 2, 1) plt.plot(melhor_fitness_hist, 'b-', linewidth=2) plt.title('Convergência da Estratégia Evolutiva') plt.xlabel('Geração') plt.ylabel('Melhor Fitness (Rastrigin)') plt.grid(True) # Gráfico 2: Mapa de contorno e ponto encontrado x_vals = np.linspace(limites[0], limites[1], 200) y_vals = np.linspace(limites[0], limites[1], 200) X, Y = np.meshgrid(x_vals, y_vals) Z = rastrigin(X, Y) plt.subplot(1, 2, 2) contour = plt.contourf(X, Y, Z, levels=50, cmap='viridis') plt.colorbar(contour, label='f(x,y)') plt.scatter([melhor_x], [melhor_y], color='red', s=100, edgecolor='white', label='Mínimo encontrado') plt.title('Função de Rastrigin e Mínimo') plt.xlabel('x') plt.ylabel('y') plt.legend() plt.grid(True) plt.tight_layout() plt.show() |
Este código implementa uma EE do zero, sem bibliotecas especializadas. Ele mostra claramente a auto-adaptação dos sigmas a cada geração. O gráfico de convergência evidencia a rápida melhoria nas primeiras iterações. O mapa de contorno revela a complexidade da função com seus múltiplos mínimos. A solução final, próxima de (0,0), confirma a eficácia da abordagem. Para iniciantes, esse exemplo conecta a teoria à prática de forma tangível. As estratégias evolutivas, portanto, são ferramentas robustas e educativas.