O que é evolução de programas?
Evolução de programas é o processo automático de gerar código executável por seleção natural. Ela pertence ao campo da programação genética e da computação evolutiva. Em vez de escrever um algoritmo manualmente, o computador descobre a solução. Programas candidatos são representados como árvores de expressão ou sequências de instruções. Esses programas são avaliados por uma função de aptidão que mede seu desempenho. Os melhores são combinados e modificados para criar filhos ligeiramente diferentes. Esse ciclo iterativo produz soluções cada vez mais adaptadas ao problema. Portanto, a evolução de programas automatiza a descoberta de heurísticas e regras.
Como ocorre a evolução passo a passo?
Primeiramente, uma população inicial de programas aleatórios é gerada. Cada programa é executado sobre um conjunto de casos de teste fornecidos. Sua aptidão é calculada com base no erro ou acerto dessas execuções. Indivíduos com alta aptidão são selecionados para serem pais da próxima geração. Operadores genéticos como crossover trocam subpartes entre dois programas pais. A mutação altera aleatoriamente um nó ou instrução de um programa filho. Novos programas substituem os menos aptos, mantendo o tamanho populacional constante. Esse procedimento é repetido por muitas gerações até que um critério pare. A convergência ocorre quando a aptidão média não melhora significativamente. Todo esse processo é guiado apenas pelos dados e pela métrica definida.
Desafios e cuidados importantes
Um desafio comum é o crescimento excessivo das árvores, chamado de “bloat”. Ele pode ser controlado com penalidades no tamanho do programa durante a avaliação. Outro cuidado é evitar o overfitting aos dados de treinamento usados. Para isso, utiliza-se validação cruzada ou conjuntos de teste separados. Além disso, a diversidade populacional deve ser mantida para evitar convergência prematura. Operadores de migração entre subpopulações ajudam a preservar a variabilidade genética. A escolha dos operadores e terminais também afeta drasticamente o sucesso. Portanto, a evolução de programas exige ajustes finos e experimentação constante.
A evolução de programas é uma extensão natural da programação genética clássica. Enquanto aquela otimiza parâmetros, esta otimiza a própria estrutura do código. Isso permite descobrir soluções inesperadas que um programador humano não preveria. Por exemplo, ela pode encontrar aproximações polinomiais para funções complexas. Também pode gerar regras de decisão para classificação de dados médicos. Sua aplicação em robótica evolutiva produz comportamentos emergentes surpreendentes. Contudo, o custo computacional é elevado devido à avaliação de muitos programas. Paralelização e uso de GPUs são frequentemente empregados para acelerar o processo. Apesar disso, a evolução de programas já é usada em indústrias como finanças e jogos. Ela cria agentes inteligentes que aprendem estratégias sem intervenção humana. A interpretabilidade dos programas gerados é um grande diferencial. Diferentemente de redes neurais, podemos ler e entender o código evoluído. Isso facilita a validação e a certificação de sistemas críticos. Portanto, a evolução de programas combina poder de busca com transparência lógica.
Um exemplo clássico é evoluir um programa que resolva a equação de segundo grau. Dados de entrada (coeficientes a, b, c) e saída (raiz real) são fornecidos. O objetivo é descobrir uma fórmula que calcule a raiz sem usar a fórmula pronta. A aptidão mede o erro absoluto médio entre a saída prevista e a real. Operadores permitidos: +, -, *, / e raiz quadrada protetora. Terminais: a, b, c e constantes aleatórias. Após algumas gerações, a PG aproxima a solução tradicional com boa precisão. Esse problema ilustra a capacidade de reinventar algoritmos conhecidos.
Enunciado do exemplo clássico
Evolua um programa que estime a população de bactérias ao longo do tempo. A taxa de crescimento segue o modelo logístico: P(t) = K / (1 + exp(-r*(t-t0))). Gere 50 pontos sintéticos com ruído para t de 0 a 10, com K=100, r=0.8, t0=5. Utilize programação genética com população de 100 indivíduos e 40 gerações. A aptidão será o erro quadrático médio entre a previsão e os dados ruidosos. Ao final, plote os dados reais, a curva ruidosa e a previsão do programa evoluído. Plote também a evolução do melhor erro ao longo das gerações. Use a biblioteca gplearn e funções matemáticas básicas.
|
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 |
# Instale: !pip install gplearn import numpy as np import matplotlib.pyplot as plt from gplearn.genetic import SymbolicRegressor # Gerar dados do modelo logístico com ruído np.random.seed(42) t = np.linspace(0, 10, 50).reshape(-1, 1) K, r, t0 = 100, 0.8, 5.0 P_real = K / (1 + np.exp(-r * (t.ravel() - t0))) P_ruidoso = P_real + np.random.normal(0, 5, size=50) # Regressor simbólico (evolução de programas) est = SymbolicRegressor( population_size=100, generations=40, stopping_criteria=0.01, p_crossover=0.7, p_subtree_mutation=0.15, p_hoist_mutation=0.05, p_point_mutation=0.1, function_set=('add', 'sub', 'mul', 'div', 'exp', 'inv', 'neg'), max_samples=0.9, verbose=1, random_state=0 ) # Treinamento (evolução) est.fit(t, P_ruidoso) # Previsão do programa evoluído P_pred = est.predict(t) # Melhor programa encontrado print("Programa evoluído (expressão):") print(est._program) # Gráfico 1: Dados reais, ruidosos e previsão plt.figure(figsize=(12, 5)) plt.subplot(1, 2, 1) plt.scatter(t, P_ruidoso, color='gray', s=20, label='Dados com ruído') plt.plot(t, P_real, 'g--', linewidth=2, label='Modelo logístico real') plt.plot(t, P_pred, 'r-', linewidth=2, label='Programa evoluído') plt.title('Evolução de Programa - Crescimento Bacteriano') plt.xlabel('Tempo (t)') plt.ylabel('População') plt.legend() plt.grid(True) # Gráfico 2: Evolução do erro (fitness) fitness_hist = est.fitness_history_ erro_medio = [1 - f for f in fitness_hist] # fitness é R², transformamos em erro plt.subplot(1, 2, 2) plt.plot(range(len(erro_medio)), erro_medio, 'b-', linewidth=2) plt.title('Evolução do Erro Quadrático Médio') plt.xlabel('Geração') plt.ylabel('Erro (MSE)') plt.grid(True) plt.tight_layout() plt.show() |
Este código é executado no Colab sem modificações adicionais. Ele demonstra como a evolução de programas descobre uma fórmula para os dados. O primeiro gráfico compara a previsão com o modelo real e os pontos medidos. O segundo gráfico mostra a redução do erro ao longo das gerações. Mesmo sem conhecer a equação logística, o algoritmo encontra uma boa aproximação. A função de aptidão (erro) é minimizada internamente pelo regressor simbólico. Assim, a evolução de programas se mostra uma ferramenta poderosa e acessível. Ela permite que iniciantes compreendam na prática o conceito de evolução artificial.