O que é a (1+1)-ES?
A (1+1)-ES é a estratégia evolutiva mais simples que existe. Ela mantém apenas um indivíduo pai e gera um único filho por geração. O filho é criado pela adição de ruído gaussiano ao pai. Se o filho tiver aptidão melhor ou igual, ele substitui o pai. Caso contrário, o pai permanece inalterado para a próxima iteração. Esse mecanismo é chamado de seleção elitista (1+1). A notação indica que um pai e um filho competem pela sobrevivência. Apesar da simplicidade, ela é eficaz para funções contínuas e unimodais. Ela foi proposta por Rechenberg nos anos 1960 como protótipo inicial. Sua principal característica é a auto-adaptação do passo de mutação. O tamanho do passo é ajustado dinamicamente com base na taxa de sucesso. Assim, a (1+1)-ES aprende a velocidade ideal de exploração.
Regra de adaptação do passo (1/5 de sucesso)
Rechenberg introduziu uma regra heurística para ajustar o desvio-padrão. A cada geração, conta-se quantas mutações foram bem-sucedidas (filho aceito). Se a taxa de sucesso for maior que 1/5, o passo de mutação aumenta. Se for menor que 1/5, o passo diminui para refinar a busca local. Essa regra mantém a convergência próxima do ótimo de forma equilibrada. O fator de ajuste típico é multiplicar por 0.85 ou dividir por 0.85. Portanto, o algoritmo se torna autônomo e dispensa ajustes manuais. Isso é especialmente útil para iniciantes que não conhecem a paisagem.
Vantagens e limitações da abordagem
A grande vantagem é a extrema simplicidade de implementação e entendimento. Ela requer poucas linhas de código e nenhuma população grande. Além disso, o custo computacional por geração é mínimo. Contudo, ela pode estagnar em mínimos locais em funções multimodais. Sua natureza determinística (um filho) limita a diversidade exploratória. Para problemas com muitas variáveis, a convergência pode ser lenta. Mesmo assim, ela é um excelente ponto de partida didático. Muitos a utilizam para calibrar parâmetros em experimentos reais.
A (1+1)-ES é um caso particular das estratégias evolutivas maiores. Diferentemente da (μ, λ), ela não mantém múltiplos candidatos simultaneamente. Isso reduz drasticamente a memória e o tempo de avaliação por iteração. Por outro lado, a ausência de crossover limita a recombinação de boas características. Ainda assim, a mutação com passo adaptativo é surpreendentemente poderosa. Ela é capaz de resolver problemas com até dezenas de dimensões. A regra do 1/5 foi provada como ótima para funções esféricas. Em outros cenários, ela funciona bem na prática, embora sem garantia formal. O usuário deve monitorar a taxa de sucesso para evitar passos muito grandes. Passos grandes causam saltos que ultrapassam o ótimo repetidamente. Passos pequenos levam a uma convergência extremamente lenta. O equilíbrio é alcançado pela própria adaptação dinâmica. Assim, a (1+1)-ES ensina conceitos fundamentais de auto-ajuste. Ela é frequentemente a primeira estratégia evolutiva ensinada em cursos.
Um exemplo clássico é minimizar a função esférica f(x) = x₁² + x₂² + … + xₙ². O mínimo global está em (0,0,…,0) com valor zero. A (1+1)-ES encontra esse ponto com alta precisão após algumas centenas de gerações. O passo inicial é escolhido arbitrariamente, mas logo se ajusta. Esse problema é ideal para demonstrar a regra do 1/5 na prática.
Enunciado do exemplo clássico
Implemente a (1+1)-ES para minimizar a função de Rosenbrock em 2 dimensões: f(x,y) = (1 – x)² + 100*(y – x²)², com x,y ∈ [-2, 2]. O mínimo global é em (1,1) com f=0. Use passo inicial sigma=0.1. Aplique a regra de adaptação 1/5 com fator 0.85 a cada 10 gerações. Execute por 500 gerações e armazene o melhor valor e a distância até (1,1). Plote a evolução do valor da função e a trajetória do ponto no espaço 2D. Forneça o código Python completo e auto-contido.
|
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 |
import numpy as np import matplotlib.pyplot as plt # Função de Rosenbrock (aptidão - minimizar) def rosenbrock(x, y): return (1 - x)**2 + 100 * (y - x**2)**2 # Parâmetros sigma = 0.1 fator = 0.85 janela = 10 # a cada 10 gerações ajusta sigma geracoes = 500 limites = [-2, 2] # Inicialização: ponto aleatório pai = np.random.uniform(limites[0], limites[1], size=2) fitness_pai = rosenbrock(pai[0], pai[1]) # Históricos historico_fitness = [fitness_pai] historico_pontos = [pai.copy()] sucessos = 0 for gen in range(geracoes): # Gerar filho com mutação gaussiana filho = pai + np.random.normal(0, sigma, size=2) filho = np.clip(filho, limites[0], limites[1]) fitness_filho = rosenbrock(filho[0], filho[1]) # Seleção (1+1): substitui se filho for melhor ou igual if fitness_filho <= fitness_pai: pai = filho fitness_pai = fitness_filho sucessos += 1 # Registrar histórico historico_fitness.append(fitness_pai) historico_pontos.append(pai.copy()) # Adaptação do passo a cada janela de gerações if (gen + 1) % janela == 0: taxa_sucesso = sucessos / janela if taxa_sucesso > 0.2: # 1/5 = 0.2 sigma *= fator elif taxa_sucesso < 0.2: sigma /= fator # Se for exatamente 0.2, mantém sigma sucessos = 0 # reinicia contador # Resultado final print(f"Melhor solução: x = {pai[0]:.6f}, y = {pai[1]:.6f}") print(f"Valor mínimo de f(x,y) = {fitness_pai:.6f}") print(f"Distância até (1,1) = {np.linalg.norm(pai - np.array([1,1])):.6f}") # Gráfico 1: Evolução do fitness plt.figure(figsize=(12, 5)) plt.subplot(1, 2, 1) plt.semilogy(historico_fitness, 'b-', linewidth=2) plt.title('Convergência da (1+1)-ES na Rosenbrock') plt.xlabel('Geração') plt.ylabel('f(x,y) (escala log)') plt.grid(True) # Gráfico 2: Trajetória no espaço 2D com contornos 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 = rosenbrock(X, Y) plt.subplot(1, 2, 2) contour = plt.contourf(X, Y, Z, levels=50, cmap='viridis', alpha=0.7) plt.colorbar(contour, label='f(x,y)') # Trajetória dos pontos (cada 5 gerações para não poluir) pts = np.array(historico_pontos) plt.plot(pts[:,0], pts[:,1], 'r-', linewidth=1, alpha=0.6, label='Trajetória') plt.scatter(pts[0,0], pts[0,1], color='green', s=80, label='Início') plt.scatter(pts[-1,0], pts[-1,1], color='red', s=100, label='Final') plt.scatter([1], [1], color='white', marker='*', s=200, label='Ótimo (1,1)') plt.title('Trajetória do Ponto no Espaço 2D') plt.xlabel('x') plt.ylabel('y') plt.legend() plt.grid(True) plt.tight_layout() plt.show() |
Este código demonstra a (1+1)-ES na prática com visualização clara. A evolução do fitness em escala log mostra a rápida melhoria inicial. A trajetória revela como o ponto serpenteia até o vale da Rosenbrock. A regra do 1/5 ajusta o sigma automaticamente, sem intervenção manual. Mesmo sendo um único indivíduo, a busca é eficaz e estável. Para iniciantes, esse exemplo conecta teoria, código e gráficos intuitivos. A (1+1)-ES é, portanto, uma porta de entrada simples para computação evolutiva.