O que é programação evolutiva?
Programação evolutiva (PE) é uma técnica de computação inspirada na evolução natural. Diferentemente dos algoritmos genéticos, ela enfatiza mutação em vez de crossover. Cada indivíduo é uma estrutura que representa um programa ou uma máquina de estados. Originalmente, ela evoluía autômatos finitos para prever sequências temporais. Hoje, a PE é aplicada a problemas de otimização contínua e discreta. A aptidão é medida pelo desempenho do indivíduo em uma tarefa específica. Os melhores indivíduos são selecionados para produzir filhos por mutação. Não há recombinação genética na forma clássica da PE. Portanto, a diversidade é mantida exclusivamente por variações mutacionais. Ela é considerada uma das abordagens evolutivas mais antigas.
Mecanismos centrais de funcionamento
A PE opera com uma população de tamanho fixo, geralmente entre 50 e 200. Cada indivíduo sofre mutação gaussiana ou cauchy em seus parâmetros. A intensidade da mutação pode ser fixa ou auto-adaptativa, como nas ES. Após a mutação, todos os filhos são avaliados pela função de aptidão. A seleção é feita por torneio estocástico ou por truncamento (μ,λ). Os indivíduos sobreviventes formam a próxima geração. Esse ciclo se repete até que um critério de parada seja satisfeito. A PE é particularmente eficaz para funções com muitas variáveis. Além disso, ela lida bem com ruído e incertezas nos dados.
Diferenças e aplicações práticas
A grande diferença da PE para os algoritmos genéticos é a ausência de crossover. Isso a torna mais simples de implementar e ajustar. Por outro lado, ela pode convergir mais lentamente em paisagens complexas. A PE é amplamente usada em previsão de séries temporais e finanças. Também é aplicada em controle de processos industriais e robótica. Sua capacidade de evoluir estratégias de tomada de decisão é notável. Para iniciantes, a PE oferece um ponto de entrada suave na computação evolutiva.
A programação evolutiva foi proposta por Lawrence Fogel nos anos 1960. Ele utilizou autômatos finitos para prever eventos em ambientes incertos. Cada autômato era uma sequência de estados e transições mutáveis. A aptidão media a precisão da previsão ao longo do tempo. Com o tempo, a PE foi generalizada para vetores numéricos reais. Atualmente, ela é frequentemente confundida com estratégias evolutivas. Contudo, a PE mantém sua identidade pela ênfase na mutação pura. Muitos pesquisadores a usam para problemas onde o crossover é prejudicial. Por exemplo, em otimização de redes neurais recorrentes. A mutação pode alterar pesos, arquitetura ou funções de ativação. A PE também é usada para gerar regras fuzzy automaticamente. Sua flexibilidade permite incorporar conhecimentos específicos do domínio. Ela é uma ferramenta valiosa para problemas mal definidos. Assim, a PE complementa outras técnicas evolutivas no arsenal do cientista.
Um exemplo clássico é evoluir um controlador para o problema do pêndulo invertido. O objetivo é manter a haste na vertical aplicando forças laterais. Cada indivíduo é um vetor de parâmetros de um controlador PID. A aptidão é o tempo que o pêndulo permanece equilibrado. A mutação ajusta os ganhos proporcional, integral e derivativo. Após algumas gerações, a PE encontra um conjunto estável de parâmetros. Esse problema ilustra a capacidade de otimização contínua da PE.
Enunciado do exemplo clássico
Utilize programação evolutiva para minimizar a função de Schwefel em 5 dimensões: f(x) = 418.9829*5 – Σᵢ xᵢ * sin(√|xᵢ|), com xᵢ ∈ [-500, 500]. O mínimo global é em xᵢ = 420.9687 para todo i, com f ≈ 0. Use população de 100 indivíduos, mutação gaussiana com sigma=15, auto-adaptação. Seleção por torneio estocástico de tamanho 2, com 80% de chance de vencer. Execute 300 gerações e armazene o melhor fitness por geração. Plote a curva de convergência e a distribuição final dos parâmetros.
|
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 |
import numpy as np import matplotlib.pyplot as plt # Função de Schwefel (minimização) def schwefel(x): return 418.9829 * len(x) - np.sum(x * np.sin(np.sqrt(np.abs(x)))) # Parâmetros pop_size = 100 geracoes = 300 dim = 5 limites = [-500, 500] sigma_inicial = 15.0 tau = 1.0 / np.sqrt(2 * dim) # Inicialização populacao = np.random.uniform(limites[0], limites[1], size=(pop_size, dim)) sigmas = np.full((pop_size, dim), sigma_inicial) # Avaliação inicial fitness = np.array([schwefel(ind) for ind in populacao]) # Histórico do melhor melhor_fitness_hist = [np.min(fitness)] melhor_ind_hist = [populacao[np.argmin(fitness)].copy()] for gen in range(geracoes): # Geração de filhos por mutação (cada pai gera um filho) filhos = np.zeros_like(populacao) sigmas_filhos = np.zeros_like(sigmas) for i in range(pop_size): # Auto-adaptação dos sigmas novo_sigma = sigmas[i] * np.exp(tau * np.random.normal(0, 1, size=dim)) novo_sigma = np.clip(novo_sigma, 1e-8, 100.0) # Mutação gaussiana filho = populacao[i] + np.random.normal(0, novo_sigma) filho = np.clip(filho, limites[0], limites[1]) filhos[i] = filho sigmas_filhos[i] = novo_sigma # Avaliar filhos fitness_filhos = np.array([schwefel(ind) for ind in filhos]) # Seleção por torneio estocástico (tamanho 2, probabilidade 0.8) # Juntamos pais e filhos (abordagem (μ+μ) para PE clássica) populacao_total = np.vstack([populacao, filhos]) fitness_total = np.concatenate([fitness, fitness_filhos]) sigmas_total = np.vstack([sigmas, sigmas_filhos]) nova_populacao = [] nova_sigmas = [] for _ in range(pop_size): # Escolher dois indivíduos aleatórios i1, i2 = np.random.choice(len(populacao_total), 2, replace=False) # Torneio probabilístico if np.random.random() < 0.8: if fitness_total[i1] < fitness_total[i2]: vencedor = i1 else: vencedor = i2 else: vencedor = i1 if np.random.random() < 0.5 else i2 nova_populacao.append(populacao_total[vencedor]) nova_sigmas.append(sigmas_total[vencedor]) populacao = np.array(nova_populacao) sigmas = np.array(nova_sigmas) fitness = np.array([schwefel(ind) for ind in populacao]) # Registrar melhor melhor_fitness_hist.append(np.min(fitness)) melhor_ind_hist.append(populacao[np.argmin(fitness)].copy()) # Resultado final melhor_final = min(melhor_fitness_hist) idx_final = melhor_fitness_hist.index(melhor_final) ponto_final = melhor_ind_hist[idx_final] print(f"Melhor fitness encontrado: {melhor_final:.6f}") print(f"Melhor ponto: {ponto_final}") print(f"Valor teórico global: 0.0 (em x = 420.9687)") # 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 Programação Evolutiva') plt.xlabel('Geração') plt.ylabel('Melhor Fitness (Schwefel)') plt.grid(True) # Gráfico 2: Distribuição final dos parâmetros (violin plot) plt.subplot(1, 2, 2) # Mostrar apenas as 5 dimensões partes = plt.violinplot(populacao.T, showmeans=True, showmedians=True) for pc in partes['bodies']: pc.set_facecolor('skyblue') pc.set_alpha(0.6) plt.axhline(y=420.9687, color='red', linestyle='--', label='Ótimo teórico') plt.title('Distribuição Final dos Parâmetros') plt.xlabel('Dimensão') plt.ylabel('Valor de xᵢ') plt.xticks(range(1, dim+1)) plt.legend() plt.grid(True) plt.tight_layout() plt.show() |
Este código implementa a PE clássica com mutação auto-adaptativa. A curva de convergência mostra a redução do erro ao longo do tempo. O gráfico de violino revela a dispersão dos parâmetros na última geração. Observa-se que a maioria dos indivíduos se aproxima do ótimo teórico. A ausência de crossover é compensada pela diversidade da mutação. Para iniciantes, este exemplo demonstra a eficácia da PE pura. A programação evolutiva é, portanto, uma alternativa simples e poderosa.