Computação Evolutiva na Otimização

A busca em grade, a busca aleatória e a otimização bayesiana compartilham uma suposição: o espaço de hiperparâmetros é um conjunto de valores numéricos ou categóricos que se pode amostrar e modelar.

Existe uma classe de problemas em que essa suposição não se sustenta. Quando o que se busca é uma estrutura — quais variáveis selecionar entre 300, qual a arquitetura de uma rede, qual a sequência de transformações de um pipeline —, o espaço é combinatório, descontínuo e sem gradiente. Modelar isso com um processo gaussiano é forçar a barra.

Os algoritmos evolutivos operam de outro jeito. Eles mantêm uma população de soluções candidatas, avaliam todas, e produzem a geração seguinte combinando e perturbando as melhores. Não precisam de derivada, não precisam de continuidade, e lidam naturalmente com representações estruturadas.

Entender os componentes de um algoritmo evolutivo e quando ele supera busca aleatória e otimização bayesiana; aplicar algoritmos genéticos à seleção de variáveis e ao ajuste de hiperparâmetros; e reconhecer o custo computacional que essa escolha implica.

Os cinco componentes

Todo algoritmo evolutivo combina os mesmos cinco elementos. O que muda entre variantes é a implementação de cada um.

Representação. Como um candidato é codificado. Para seleção de variáveis, um vetor binário de tamanho igual ao número de colunas. Para hiperparâmetros, uma lista de valores. A representação é a decisão mais importante — ela determina o que os operadores conseguem explorar.

Aptidão. A medida de qualidade. É aqui que mora o custo: avaliar um candidato costuma significar treinar e validar um modelo.

Seleção. Quem gera descendentes. O torneio é o mecanismo padrão: sorteia-se um pequeno grupo e o melhor dele vence. Ajustar o tamanho do torneio regula a pressão seletiva.

Cruzamento. Combina dois pais. A aposta é que partes boas de soluções diferentes se somem.

Mutação. Perturba um indivíduo ao acaso. É o que impede a população de estagnar num ótimo local.

import numpy as np

def torneio(populacao, aptidoes, k=3, rng=None):
    """Sorteia k indivíduos e devolve o melhor — pressão seletiva ajustável por k."""
    rng = rng or np.random.default_rng()
    idx = rng.choice(len(populacao), size=k, replace=False)
    return populacao[idx[np.argmax(aptidoes[idx])]]

Seleção de variáveis: o caso em que eles brilham

Escolher um subconjunto entre 300 variáveis é um problema com $2^{300}$ possibilidades. Nenhuma busca exaustiva chega perto, e os métodos clássicos têm limitações conhecidas: filtros avaliam variáveis isoladamente e perdem interações; seleção sequencial é gulosa e não desfaz decisões ruins.

Um algoritmo genético trata o subconjunto como um cromossomo binário:

from sklearn.model_selection import cross_val_score
import numpy as np

def selecao_por_ga(X, y, modelo, n_geracoes=40, tam_pop=50,
                   taxa_mut=0.02, penalidade=0.001, semente=42):
    rng = np.random.default_rng(semente)
    n_var = X.shape[1]

    # começa com subconjuntos esparsos: mais realista que 50% das variáveis
    populacao = rng.random((tam_pop, n_var)) < 0.15

    def aptidao(mascara):
        if mascara.sum() == 0:
            return -np.inf
        escore = cross_val_score(modelo, X[:, mascara], y, cv=5,
                                 scoring="roc_auc", n_jobs=-1).mean()
        return escore - penalidade * mascara.sum()   # parcimônia

    historico = []
    for geracao in range(n_geracoes):
        aptidoes = np.array([aptidao(ind) for ind in populacao])
        historico.append(aptidoes.max())

        # elitismo: os dois melhores passam intactos
        ordem = np.argsort(aptidoes)[::-1]
        nova = [populacao[ordem[0]].copy(), populacao[ordem[1]].copy()]

        while len(nova) < tam_pop:
            pai = torneio(populacao, aptidoes, rng=rng)
            mae = torneio(populacao, aptidoes, rng=rng)

            corte = rng.integers(1, n_var)                      # cruzamento de um ponto
            filho = np.concatenate([pai[:corte], mae[corte:]])

            mutacoes = rng.random(n_var) < taxa_mut             # mutação bit a bit
            filho = np.where(mutacoes, ~filho, filho)

            nova.append(filho)

        populacao = np.array(nova)

    aptidoes = np.array([aptidao(ind) for ind in populacao])
    return populacao[np.argmax(aptidoes)], historico

Três decisões escondidas nesse código:

• A penalidade por tamanho (- penalidade * mascara.sum()) é o que impede o algoritmo de simplesmente incluir tudo. Sem ela, mais variáveis quase sempre dão AUC de validação ligeiramente maior, e o resultado é um subconjunto inútil.
• O elitismo garante que o melhor indivíduo nunca seja perdido por azar no sorteio. Sem ele, a melhor aptidão pode piorar de uma geração para outra.
• A inicialização esparsa (15%, não 50%) parte de subconjuntos pequenos, o que é uma hipótese melhor sobre onde está a solução e acelera a convergência.

E o alerta que vale mais que o código: com validação cruzada dentro da função de aptidão, você está selecionando sobre a validação centenas de vezes. A estimativa final é otimista por construção. O subconjunto escolhido precisa ser avaliado num conjunto de teste que o algoritmo nunca viu — idealmente com a seleção inteira aninhada dentro de uma validação cruzada externa.

Hiperparâmetros com representação mista

Algoritmos evolutivos lidam bem com o que atrapalha outros métodos: parâmetros de tipos diferentes, com dependências entre si.

ESPACO = {
    "n_estimators":     ("int",   100, 1500),
    "max_depth":        ("int",   2, 20),
    "learning_rate":    ("logf",  1e-3, 0.5),
    "subsample":        ("float", 0.5, 1.0),
    "colsample_bytree": ("float", 0.4, 1.0),
    "reg_lambda":       ("logf",  1e-3, 100.0),
}

def amostrar(rng):
    ind = {}
    for nome, (tipo, lo, hi) in ESPACO.items():
        if tipo == "int":
            ind[nome] = int(rng.integers(lo, hi + 1))
        elif tipo == "logf":
            ind[nome] = float(np.exp(rng.uniform(np.log(lo), np.log(hi))))
        else:
            ind[nome] = float(rng.uniform(lo, hi))
    return ind

def mutar(ind, rng, forca=0.2):
    """Perturba cada gene com probabilidade fixa, respeitando o tipo e a escala."""
    novo = dict(ind)
    for nome, (tipo, lo, hi) in ESPACO.items():
        if rng.random() > 0.3:
            continue
        if tipo == "logf":
            fator = np.exp(rng.normal(0, forca))
            novo[nome] = float(np.clip(ind[nome] * fator, lo, hi))
        elif tipo == "int":
            passo = max(1, int((hi - lo) * forca))
            novo[nome] = int(np.clip(ind[nome] + rng.integers(-passo, passo + 1), lo, hi))
        else:
            novo[nome] = float(np.clip(ind[nome] + rng.normal(0, forca * (hi - lo)), lo, hi))
    return novo

O logf importa: learning_rate e reg_lambda vivem em escala logarítmica, e mutar aditivamente um valor de 0,001 com desvio 0,1 o jogaria para fora da região útil. Multiplicar por um fator lognormal preserva a escala.

Na prática, prefira bibliotecas maduras a escrever tudo à mão. O DEAP dá os blocos genéricos; TPOT aplica programação genética para montar o pipeline inteiro (pré-processamento incluído); Optuna oferece um amostrador com estratégia evolutiva (CMA-ES) integrado à mesma API dos demais.

import optuna

estudo = optuna.create_study(
    direction="maximize",
    sampler=optuna.samplers.CmaEsSampler(seed=42),
)
estudo.optimize(objetivo, n_trials=200)

Quando escolher evolutivo — e quando não

O critério decisivo é o orçamento de avaliações. A otimização bayesiana foi feita para ser eficiente em número de avaliações: ela constrói um modelo do que já viu e escolhe o próximo ponto com cuidado. Um algoritmo evolutivo é comparativamente perdulário — precisa avaliar uma população inteira a cada geração —, mas cada geração é trivialmente paralelizável.

A conta prática: 50 indivíduos × 40 gerações = 2.000 avaliações. Se cada uma leva 30 segundos, são 16 horas sequenciais; com 16 núcleos, uma hora. Se a avaliação leva 10 minutos, esqueça.

E vale a nota que fecha o assunto: em muitos problemas, a busca aleatória com o mesmo orçamento chega perto do evolutivo com uma fração da complexidade. Sempre estabeleça essa linha de base antes de adotar algo mais elaborado.

Multiobjetivo: quando há mais de um critério

Uma vantagem genuína dos evolutivos é otimizar vários objetivos ao mesmo tempo — desempenho e número de variáveis, ou AUC e tempo de inferência — sem precisar combiná-los numa soma ponderada arbitrária.

Algoritmos como o NSGA-II devolvem a fronteira de Pareto: o conjunto de soluções em que melhorar um objetivo obriga a piorar outro.

import optuna

estudo = optuna.create_study(
    directions=["maximize", "minimize"],    # AUC e nº de variáveis
    sampler=optuna.samplers.NSGAIISampler(seed=42),
)
estudo.optimize(objetivo_multiplo, n_trials=300)

for t in estudo.best_trials:
    print(f"AUC {t.values[0]:.4f} · {int(t.values[1])} variáveis")

Isso é qualitativamente melhor que otimizar auc - 0.001 * n_vars. O peso 0.001 é uma escolha arbitrária feita antes de conhecer o compromisso real; a fronteira de Pareto mostra o compromisso e deixa a escolha para quem tem o contexto de negócio — que pode olhar a curva e dizer "a queda de 0,003 de AUC para usar 12 variáveis em vez de 80 compensa".

Reprodutibilidade

Algoritmos evolutivos são estocásticos do início ao fim. Sem disciplina, dois execuções dão resultados diferentes e nenhuma conclusão é confiável:

• Semente fixa em tudo: no gerador do algoritmo, nas partições da validação cruzada e no modelo.
• Registro completo de cada avaliação — parâmetros, aptidão, geração. Serve para diagnosticar convergência e para auditar depois.
• Várias execuções com sementes diferentes. Se o resultado varia muito entre elas, o processo não convergiu e a solução "vencedora" é sorte.
• Curva de convergência. Se a melhor aptidão parou de subir há quinze gerações, o orçamento restante está sendo desperdiçado.

Os algoritmos evolutivos mantêm uma população, avaliam e geram a geração seguinte por seleção, cruzamento e mutação — sem precisar de gradiente nem de continuidade. São cinco componentes: representação, aptidão, seleção por torneio, cruzamento e mutação, e a representação é a decisão que mais pesa. Eles brilham em espaços combinatórios: seleção de variáveis, arquitetura, estrutura de pipeline. Na seleção de variáveis, é a penalidade por tamanho que impede o algoritmo de simplesmente incluir tudo, e o elitismo que impede a melhor solução de se perder pelo caminho. Cuidado com a armadilha central: avaliar aptidão por validação cruzada centenas de vezes é otimizar sobre a validação — a solução final precisa ser medida num teste intocado, de preferência com validação cruzada aninhada. Parâmetros em escala logarítmica exigem mutação multiplicativa. Na escolha entre abordagens, a bayesiana vence com orçamento pequeno de avaliações, e o evolutivo vence em espaço combinatório, além de escalar por paralelismo. Para múltiplos objetivos, o NSGA-II devolve a fronteira de Pareto, o que é melhor que arbitrar um peso antes de conhecer o compromisso. E, antes de concluir que valeu a pena, compare sempre com uma busca aleatória de mesmo orçamento.

Exercícios

1. Por que a penalidade por número de variáveis é essencial na seleção por GA?

   Ver resposta

   ✓ Resposta:

   Porque acrescentar variáveis quase nunca piora o escore de validação cruzada — na pior das hipóteses o modelo aprende a ignorá-las, e frequentemente elas produzem um ganho marginal por puro ruído. Sem penalidade, a pressão seletiva empurra consistentemente para subconjuntos cada vez maiores, e o algoritmo converge para "usar quase tudo", que é exatamente o que a seleção deveria evitar. A penalidade cria o custo que falta: uma variável só permanece se contribuir mais do que custa. Ajustar o coeficiente é um compromisso — alto demais poda variáveis úteis, baixo demais não segura o crescimento —, e a alternativa mais elegante é tratar o tamanho como segundo objetivo numa otimização multiobjetivo, obtendo a fronteira inteira em vez de um ponto.

2. O que o elitismo evita, e qual sintoma aparece sem ele?

   Ver resposta

   ✓ Resposta:

   Evita que o melhor indivíduo da população seja perdido por azar. Seleção por torneio, cruzamento e mutação são todos estocásticos: o melhor pode não ser sorteado para reprodução, ou pode ser sorteado e ter sua boa configuração destruída por um cruzamento ou uma mutação. O sintoma é direto e fácil de diagnosticar: a curva da melhor aptidão por geração deixa de ser monótona e apresenta quedas. Como a busca deveria ao menos preservar o que já encontrou, essa curva descendente é sinal de que falta elitismo. Copiar intactos os dois ou três melhores para a geração seguinte resolve, sem custo perceptível de diversidade.

3. Descreva o vazamento que ocorre ao usar validação cruzada como função de aptidão e como corrigi-lo.

   Ver resposta

   ✓ Resposta:

   A cada avaliação, o algoritmo mede o desempenho nas mesmas partições de validação — e ao longo de 2.000 avaliações ele efetivamente procura a configuração que melhor se ajusta àquelas partições específicas, incluindo suas peculiaridades aleatórias. O escore do vencedor é, portanto, o máximo de milhares de tentativas sobre o mesmo conjunto, e é otimista por construção: parte do ganho é sobreajuste ao esquema de validação, não desempenho real. A correção tem dois níveis: no mínimo, reservar um conjunto de teste que o processo de busca jamais tocou e reportar o desempenho ali; de forma rigorosa, usar validação cruzada aninhada, com o procedimento de seleção inteiro rodando dentro de cada dobra externa — mais caro, mas é a única forma de estimar de maneira não-enviesada o desempenho do procedimento, e não de uma configuração específica.

4. Por que mutar learning_rate aditivamente é ruim, e qual a alternativa?

   Ver resposta

   ✓ Resposta:

   Porque a learning_rate vive em escala logarítmica: a diferença entre 0,001 e 0,01 é tão significativa quanto entre 0,01 e 0,1, embora a distância aritmética seja dez vezes menor. Uma mutação aditiva com desvio fixo — digamos 0,05 — é catastrófica para um valor de 0,001 (joga-o para fora da região útil ou o torna negativo) e irrelevante para um valor de 0,4. A alternativa é a mutação multiplicativa: novo = antigo * exp(N(0, σ)), que perturba proporcionalmente e mantém o valor na mesma ordem de grandeza. O mesmo raciocínio vale para amostrar o valor inicial — uniforme no log do intervalo, não no intervalo — e para qualquer parâmetro de regularização.

5. Você tem 4 hiperparâmetros contínuos e cada avaliação leva 8 minutos. Evolutivo ou bayesiana?

   Ver resposta

   ✓ Resposta:

   Bayesiana, com folga. O espaço é pequeno, contínuo e sem estrutura combinatória — exatamente o cenário para o qual os métodos bayesianos foram desenhados —, e a avaliação é cara, o que torna o número de avaliações o recurso escasso. A otimização bayesiana constrói um modelo substituto do que já observou e escolhe cada próximo ponto para maximizar o ganho esperado, chegando a bons resultados em 30 a 60 avaliações (4 a 8 horas aqui). Um algoritmo evolutivo com população de 50 precisaria de 50 avaliações só para a primeira geração — mais de 6 horas antes de qualquer evolução — e de milhares no total. O evolutivo só se justificaria se houvesse paralelismo massivo disponível e o espaço fosse combinatório. Como sempre, vale rodar uma busca aleatória de 30 pontos em paralelo como linha de base.

Fontes e leituras recomendadas

• Optuna — amostradores CMA-ES e NSGA-II
• DEAP — framework de computação evolutiva em Python
• TPOT — otimização de pipelines por programação genética
• Deb et al. (2002) — NSGA-II
• Hansen — The CMA Evolution Strategy: A Tutorial
• scikit-learn — validação cruzada aninhada