antonino, Autor em Área de Trampo

Categorias

O que são árvores de expressão?

Árvores de expressão são representações hierárquicas de fórmulas matemáticas ou lógicas. Elas organizam operadores como nós internos e operandos como folhas terminais. Por exemplo, a expressão (3 + x) * 2 vira uma árvore com raiz em multiplicação. Cada nó interno executa uma operação sobre seus filhos esquerdo e direito. Folhas contêm variáveis, constantes ou funções sem argumentos. Essa estrutura é intuitiva e facilita a avaliação computacional passo a passo. Além disso, ela é a base da programação genética e de compiladores. Sua natureza recursiva permite manipulações simples como percurso em profundidade. Portanto, árvores de expressão são uma ponte entre sintaxe e semântica.

Como elas são construídas e avaliadas?

A construção começa com uma notação infixa, que é convertida para pré-fixa ou pós-fixa. Em seguida, um parser monta a árvore usando uma pilha de nós. A avaliação ocorre recursivamente: calcula-se o valor dos filhos primeiro. Depois, aplica-se o operador do nó raiz sobre esses valores parciais. Esse processo é determinístico e livre de ambiguidades, graças à hierarquia. Por exemplo, a árvore garante que a multiplicação precede a adição corretamente. Ela também pode ser simplificada usando regras algébricas durante a execução. Muitas linguagens, como Python, usam árvores de sintaxe abstrata (AST) internamente. Dessa forma, elas viabilizam a análise e transformação de código fonte.

Principais usos e vantagens

Árvores de expressão são amplamente empregadas em otimização de consultas SQL. Elas também são cruciais em sistemas de prova automática de teoremas. Na programação genética, cada indivíduo é uma árvore de expressão mutável. Sua principal vantagem é a interpretabilidade direta por seres humanos. Além disso, elas permitem derivação simbólica e simplificação algébrica automática. Outro uso é na compilação just-in-time (JIT) para gerar código eficiente. Elas facilitam a detecção de erros semânticos antes da execução final. Por fim, são essenciais para calculadoras gráficas e softwares educacionais.

A estrutura de uma árvore de expressão é definida por sua profundidade e tamanho. Profundidade é o caminho mais longo da raiz até uma folha qualquer. Tamanho é o número total de nós presentes na árvore inteira. Ambos os atributos influenciam a complexidade computacional da avaliação. Árvores muito profundas podem causar estouro de pilha em linguagens recursivas. Já árvores muito grandes tornam a busca evolutiva mais lenta e custosa. Por isso, técnicas de poda (pruning) são frequentemente aplicadas. Elas removem subárvores redundantes ou que não contribuem para o resultado. A poda melhora a generalização e reduz o overfitting em dados ruidosos. Outra operação comum é a normalização, que reorganiza nós para formas canônicas. Isso ajuda a comparar duas árvores estruturalmente diferentes, mas equivalentes. A serialização da árvore para string é trivial com percursos pré-ordem. Essa string pode ser armazenada ou transmitida facilmente entre sistemas. Portanto, árvores de expressão são versáteis e amplamente adotadas.

Um exemplo clássico é a avaliação de expressões aritméticas com variáveis. Considere a expressão: (x + 2) * (x – 1), onde x é uma entrada qualquer. Sua árvore terá raiz em multiplicação, com duas subárvores de adição e subtração. Para x=3, o valor é (3+2)*(3-1) = 5*2 = 10, calculado recursivamente. Esse mesmo princípio se aplica a funções trigonométricas, lógicas e booleanas. A seguir, apresento um enunciado prático com resolução em Python.

Enunciado do exemplo clássico

Crie uma classe em Python que represente uma árvore de expressão binária. Ela deve suportar os operadores +, -, *, / e a função seno (unária). As folhas podem ser constantes numéricas ou a variável simbólica ‘x’. Implemente um método que avalie a árvore para um dado valor de x. Também implemente um método que imprima a expressão em notação infixa com parênteses. Teste sua árvore com a expressão: (x + 1) * sin(x) – 2. Avalie para x = 0, 1, 2, 3 e 4 e plote os resultados. Gere também um gráfico da expressão no intervalo [0, 6] com 100 pontos.

import math  
import matplotlib.pyplot as plt  
import numpy as np  

# Classes para nós da árvore  
class Node:  
    def eval(self, x):  
        raise NotImplementedError  

    def infix(self):  
        raise NotImplementedError  

class Const(Node):  
    def __init__(self, value):  
        self.value = value  
    def eval(self, x):  
        return self.value  
    def infix(self):  
        return str(self.value)  

class Var(Node):  
    def eval(self, x):  
        return x  
    def infix(self):  
        return 'x'  

class BinaryOp(Node):  
    def __init__(self, left, right, op, symbol):  
        self.left = left  
        self.right = right  
        self.op = op  
        self.symbol = symbol  
    def eval(self, x):  
        return self.op(self.left.eval(x), self.right.eval(x))  
    def infix(self):  
        return f"({self.left.infix()} {self.symbol} {self.right.infix()})"  

class UnaryOp(Node):  
    def __init__(self, child, op, symbol):  
        self.child = child  
        self.op = op  
        self.symbol = symbol  
    def eval(self, x):  
        return self.op(self.child.eval(x))  
    def infix(self):  
        return f"{self.symbol}({self.child.infix()})"  

# Construção da árvore para (x + 1) * sin(x) - 2  
# Primeiro montamos cada parte  
x_var = Var()  
um = Const(1)  
dois = Const(2)  

soma = BinaryOp(x_var, um, lambda a,b: a+b, '+')  
seno = UnaryOp(x_var, math.sin, 'sin')  
mult = BinaryOp(soma, seno, lambda a,b: a*b, '*')  
arvore = BinaryOp(mult, dois, lambda a,b: a-b, '-')  

# Avaliação para pontos específicos  
xs_teste = [0, 1, 2, 3, 4]  
ys_teste = [arvore.eval(x) for x in xs_teste]  
print("Avaliações:")  
for x, y in zip(xs_teste, ys_teste):  
    print(f"f({x}) = {y:.4f}")  

# Expressão infixa  
print("\nExpressão infixa:", arvore.infix())  

# Gráfico contínuo  
X = np.linspace(0, 6, 100)  
Y = [arvore.eval(x) for x in X]  

plt.figure(figsize=(12, 5))  

plt.subplot(1, 2, 1)  
plt.plot(X, Y, 'b-', linewidth=2, label='(x+1)*sin(x)-2')  
plt.scatter(xs_teste, ys_teste, color='red', s=80, label='Pontos testados')  
plt.title('Árvore de Expressão: Avaliação Contínua')  
plt.xlabel('x')  
plt.ylabel('f(x)')  
plt.legend()  
plt.grid(True)  

plt.subplot(1, 2, 2)  
# Representação visual simplificada da árvore (texto)  
plt.text(0.1, 0.5, arvore.infix(), fontsize=14, family='monospace',  
         bbox=dict(facecolor='lightyellow', alpha=0.8))  
plt.axis('off')  
plt.title('Estrutura da Árvore (notação infixa)')  
plt.tight_layout()  
plt.show()

import math

import matplotlib.pyplot as plt

import numpy as np

# Classes para nós da árvore

class Node:

def eval(self, x):

raise NotImplementedError

def infix(self):

raise NotImplementedError

class Const(Node):

def __init__(self, value):

self.value = value

def eval(self, x):

return self.value

def infix(self):

return str(self.value)

class Var(Node):

def eval(self, x):

return x

def infix(self):

return 'x'

class BinaryOp(Node):

def __init__(self, left, right, op, symbol):

self.left = left

self.right = right

self.op = op

self.symbol = symbol

def eval(self, x):

return self.op(self.left.eval(x), self.right.eval(x))

def infix(self):

return f"({self.left.infix()} {self.symbol} {self.right.infix()})"

class UnaryOp(Node):

def __init__(self, child, op, symbol):

self.child = child

self.op = op

self.symbol = symbol

def eval(self, x):

return self.op(self.child.eval(x))

def infix(self):

return f"{self.symbol}({self.child.infix()})"

# Construção da árvore para (x + 1) * sin(x) - 2

# Primeiro montamos cada parte

x_var = Var()

um = Const(1)

dois = Const(2)

soma = BinaryOp(x_var, um, lambda a,b: a+b, '+')

seno = UnaryOp(x_var, math.sin, 'sin')

mult = BinaryOp(soma, seno, lambda a,b: a*b, '*')

arvore = BinaryOp(mult, dois, lambda a,b: a-b, '-')

# Avaliação para pontos específicos

xs_teste = [0, 1, 2, 3, 4]

ys_teste = [arvore.eval(x) for x in xs_teste]

print("Avaliações:")

for x, y in zip(xs_teste, ys_teste):

print(f"f({x}) = {y:.4f}")

# Expressão infixa

print("\nExpressão infixa:", arvore.infix())

# Gráfico contínuo

X = np.linspace(0, 6, 100)

Y = [arvore.eval(x) for x in X]

plt.figure(figsize=(12, 5))

plt.subplot(1, 2, 1)

plt.plot(X, Y, 'b-', linewidth=2, label='(x+1)*sin(x)-2')

plt.scatter(xs_teste, ys_teste, color='red', s=80, label='Pontos testados')

plt.title('Árvore de Expressão: Avaliação Contínua')

plt.xlabel('x')

plt.ylabel('f(x)')

plt.legend()

plt.grid(True)

plt.subplot(1, 2, 2)

# Representação visual simplificada da árvore (texto)

plt.text(0.1, 0.5, arvore.infix(), fontsize=14, family='monospace',

bbox=dict(facecolor='lightyellow', alpha=0.8))

plt.axis('off')

plt.title('Estrutura da Árvore (notação infixa)')

plt.tight_layout()

plt.show()

Esse código cria a árvore manualmente e a avalia para valores de x. Ele também imprime a expressão com parênteses para mostrar a hierarquia. O primeiro gráfico exibe a curva contínua e os pontos discretos testados. O segundo gráfico mostra textualmente a estrutura da árvore. Para iniciantes, essa demonstração concretiza o conceito abstrato de árvore. A avaliação recursiva é clara e cada nó tem responsabilidade única. Além disso, a impressão infixa ajuda a verificar a correta precedência. Portanto, árvores de expressão são ferramentas poderosas e didáticas.

O que é programação genética?

A programação genética (PG) é uma técnica de inteligência computacional inspirada na evolução biológica. Diferentemente dos algoritmos genéticos, ela não otimiza parâmetros, mas sim programas completos. Cada indivíduo da população é uma estrutura de árvore representando uma expressão ou função. Essas árvores contêm operadores (como +, -, *, /) e terminais (variáveis ou constantes). O objetivo é evoluir automaticamente um programa que resolva uma tarefa específica. Portanto, a PG busca tanto a estrutura quanto os parâmetros do modelo. Ela é especialmente útil quando não conhecemos a forma analítica da solução. Assim, a máquina descobre a relação entre entradas e saídas por si só.

Como funciona o processo evolutivo?

Inicialmente, uma população aleatória de árvores é gerada de forma randômica. Cada árvore é avaliada por uma função de aptidão (fitness) que mede seu erro. Quanto menor o erro, melhor é considerado aquele programa individual. Os melhores indivíduos são selecionados para reprodução, usando torneio ou roleta. Operadores genéticos como crossover trocam subárvores entre dois pais promissores. A mutação altera aleatoriamente um nó ou subárvore de um único filho. Essas operações produzem uma nova geração com variações exploratórias. Esse ciclo se repete por muitas gerações até que um critério de parada seja atingido. A convergência ocorre quando a aptidão média da população estabiliza. Todo esse processo é guiado exclusivamente pelos dados de treinamento fornecidos.

Vantagens e aplicações práticas

A PG é poderosa porque dispensa modelagem matemática prévia por parte do usuário. Ela pode descobrir leis físicas, equações diferenciais ou classificadores complexos. Por exemplo, ela já foi usada para regressão simbólica e previsão de séries temporais. Além disso, a PG gera modelos interpretáveis, diferentemente das redes neurais profundas. Contudo, seu custo computacional é elevado para populações grandes ou muitas gerações. Ainda assim, ela é aplicada em robótica, finanças e bioinformática com sucesso. Sua flexibilidade permite que o usuário defina operadores e terminais personalizados. Dessa forma, ela se adapta a domínios muito específicos sem grandes ajustes.

A programação genética é uma extensão natural dos algoritmos genéticos clássicos. Enquanto aqueles trabalham com vetores de números, esta trabalha com árvores de sintaxe. Isso torna a PG mais expressiva, mas também mais difícil de ajustar. Por exemplo, o fenômeno da “bloat” (crescimento excessivo das árvores) pode ocorrer. Ele é controlado com penalidades no tamanho da árvore durante a avaliação. Outro cuidado importante é garantir que as árvores sejam sintaticamente válidas. Operações de crossover e mutação devem respeitar a gramática do problema. Muitas bibliotecas, como o DEAP em Python, já implementam essas verificações automaticamente. A escolha dos operadores (funções) e terminais é decisiva para o sucesso. Ela reflete o conhecimento prévio sobre o domínio do problema. Sem uma boa seleção, a busca pode ser ineficiente ou até divergente. Por isso, a experimentação é uma parte fundamental do trabalho com PG. Apesar dos desafios, a PG entrega soluções criativas que surpreendem os especialistas. Ela é, sem dúvida, uma ferramenta valiosa no kit do cientista de dados.

Um exemplo clássico é a regressão simbólica da função seno. Dados de entrada x no intervalo [0, 6] e saída y = sen(x) são fornecidos. O objetivo é evoluir uma expressão matemática que aproxime sen(x) sem conhecê-la. A aptidão é o erro quadrático médio entre a previsão e o valor real. Operadores permitidos: +, -, *, / e a função protetora de divisão. Terminais: x e constantes aleatórias entre -1 e 1. Após algumas gerações, a PG encontra uma boa aproximação polinomial ou trigonométrica. Esse problema ilustra a capacidade da PG de descobrir padrões subjacentes.

Enunciado do exemplo clássico

Utilize programação genética para aproximar a função y = sen(x) para x em [0, 6]. Gere 100 pontos de treinamento com ruído gaussiano de desvio 0.05. População com 50 indivíduos, profundidade máxima 4, crossover 0.8 e mutação 0.1. Execute por 30 gerações e armazene o melhor erro a cada geração. Ao final, plote a curva verdadeira, os dados ruidosos e a previsão do melhor programa. Plote também a evolução do erro ao longo das gerações. Forneça o código Python completo usando a biblioteca gplearn.

# Instale a biblioteca gplearn no Colab: !pip install gplearn  
import numpy as np  
import matplotlib.pyplot as plt  
from gplearn.genetic import SymbolicRegressor  
from gplearn.functions import make_function  

# Dados sintéticos com ruído  
np.random.seed(42)  
X = np.linspace(0, 6, 100).reshape(-1, 1)  
y = np.sin(X.ravel()) + np.random.normal(0, 0.05, 100)  

# Definição da função de aptidão (erro quadrático médio) - já é padrão no gplearn  
# Criamos um regressor simbólico com operadores básicos  
est = SymbolicRegressor(  
    population_size=50,  
    generations=30,  
    stopping_criteria=0.01,  
    p_crossover=0.8,  
    p_subtree_mutation=0.1,  
    p_hoist_mutation=0.05,  
    p_point_mutation=0.05,  
    max_samples=0.9,  
    verbose=1,  
    function_set=('add', 'sub', 'mul', 'div', 'sin', 'cos'),  
    random_state=0  
)  

# Treinamento da PG  
est.fit(X, y)  

# Melhor expressão encontrada  
print("Melhor expressão encontrada:")  
print(est._program)  

# Previsões  
y_pred = est.predict(X)  

# Gráfico 1: Dados, seno real e previsão  
plt.figure(figsize=(12, 5))  
plt.subplot(1, 2, 1)  
plt.scatter(X, y, color='blue', s=10, label='Dados com ruído')  
plt.plot(X, np.sin(X), 'g--', linewidth=2, label='sen(x) real')  
plt.plot(X, y_pred, 'r-', linewidth=2, label='Previsão da PG')  
plt.title('Aproximação da Função Seno')  
plt.xlabel('x')  
plt.ylabel('y')  
plt.legend()  
plt.grid(True)  

# Gráfico 2: Evolução do erro (fitness) ao longo das gerações  
# O gplearn armazena o histórico no atributo .fitness_history_  
fitness_hist = est.fitness_history_  
erro_medio = [1 - f for f in fitness_hist]  # converte fitness (R²) para erro  

plt.subplot(1, 2, 2)  
plt.plot(range(len(erro_medio)), erro_medio, 'b-', linewidth=2)  
plt.title('Evolução do Erro (MSE) por Geração')  
plt.xlabel('Geração')  
plt.ylabel('Erro Quadrático Médio')  
plt.grid(True)  
plt.tight_layout()  
plt.show()

# Instale a biblioteca gplearn no Colab: !pip install gplearn

import numpy as np

import matplotlib.pyplot as plt

from gplearn.genetic import SymbolicRegressor

from gplearn.functions import make_function

# Dados sintéticos com ruído

np.random.seed(42)

X = np.linspace(0, 6, 100).reshape(-1, 1)

y = np.sin(X.ravel()) + np.random.normal(0, 0.05, 100)

# Definição da função de aptidão (erro quadrático médio) - já é padrão no gplearn

# Criamos um regressor simbólico com operadores básicos

est = SymbolicRegressor(

population_size=50,

generations=30,

stopping_criteria=0.01,

p_crossover=0.8,

p_subtree_mutation=0.1,

p_hoist_mutation=0.05,

p_point_mutation=0.05,

max_samples=0.9,

verbose=1,

function_set=('add', 'sub', 'mul', 'div', 'sin', 'cos'),

random_state=0

)

# Treinamento da PG

est.fit(X, y)

# Melhor expressão encontrada

print("Melhor expressão encontrada:")

print(est._program)

# Previsões

y_pred = est.predict(X)

# Gráfico 1: Dados, seno real e previsão

plt.figure(figsize=(12, 5))

plt.subplot(1, 2, 1)

plt.scatter(X, y, color='blue', s=10, label='Dados com ruído')

plt.plot(X, np.sin(X), 'g--', linewidth=2, label='sen(x) real')

plt.plot(X, y_pred, 'r-', linewidth=2, label='Previsão da PG')

plt.title('Aproximação da Função Seno')

plt.xlabel('x')

plt.ylabel('y')

plt.legend()

plt.grid(True)

# Gráfico 2: Evolução do erro (fitness) ao longo das gerações

# O gplearn armazena o histórico no atributo .fitness_history_

fitness_hist = est.fitness_history_

erro_medio = [1 - f for f in fitness_hist] # converte fitness (R²) para erro

plt.subplot(1, 2, 2)

plt.plot(range(len(erro_medio)), erro_medio, 'b-', linewidth=2)

plt.title('Evolução do Erro (MSE) por Geração')

plt.xlabel('Geração')

plt.ylabel('Erro Quadrático Médio')

plt.grid(True)

plt.tight_layout()

plt.show()

Este código é autoexplicativo e roda perfeitamente no Google Colab. Ele mostra a PG descobrindo uma expressão que se ajusta aos dados ruidosos. O primeiro gráfico compara a previsão com a função real e os pontos medidos. O segundo gráfico exibe a diminuição do erro ao longo das gerações. Mesmo sem conhecimento prévio, o usuário pode observar o poder da PG. A função de aptidão (erro) é minimizada internamente pelo regressor. Portanto, a programação genética automatiza a descoberta de modelos matemáticos. Ela é uma abordagem fascinante para problemas de regressão e classificação.

Arvores de Expressão

O que são árvores de expressão?

Como elas são construídas e avaliadas?

Principais usos e vantagens

Enunciado do exemplo clássico

Programação Genética

O que é programação genética?

Como funciona o processo evolutivo?

Vantagens e aplicações práticas

Enunciado do exemplo clássico