Algoritmos Evolutivos

Visão geral

Algoritmos evolutivos (Evolutionary Algorithms, EAs) são uma família de métodos de otimização baseados em população (population-based) e sem gradientes (gradient-free) inspirados na evolução biológica. Em vez de melhorar uma única solução candidata usando derivadas (como em Descenso do Gradiente), EAs mantêm uma população de soluções candidatas e aplicam iterativamente:

  • Seleção (selection) (preferir candidatos melhores),
  • Mutação (mutation) (variação aleatória),
  • Recombinação / cruzamento (recombination / crossover) (combinar partes de múltiplos candidatos),

para buscar em paisagens de objetivo grandes, acidentadas, ruidosas, descontínuas ou não convexas.

EAs são especialmente úteis quando:

  • O objetivo é uma caixa-preta (black box) (sem gradientes, sem forma fechada).
  • O espaço de busca é combinatório ou envolve escolhas discretas.
  • O objetivo é multimodal (multi-modal) (muitos ótimos locais).
  • As avaliações podem ser paralelizadas (por exemplo, execuções de simulação).
  • As restrições são complexas e é melhor tratá-las de forma heurística.

Eles complementam métodos clássicos de Otimização Convexa e Otimização Estocástica, e frequentemente competem com otimização bayesiana (Bayesian optimization, BO) e outros otimizadores de caixa-preta em ajuste de hiperparâmetros e problemas de projeto.

O problema de otimização que EAs resolvem

A maioria dos EAs é formulada como:

[ \max_{x \in \mathcal{X}} \ f(x) \quad \text{ou} \quad \min_{x \in \mathcal{X}} \ f(x) ]

onde:

  • (x) é uma solução candidata (vetor de valores reais, sequência de bits, permutação, árvore de programa, …),
  • (\mathcal{X}) é o espaço de busca,
  • (f(x)) é a aptidão (fitness) (objetivo) que você pode avaliar, mas talvez não consiga diferenciar.

Ao contrário de métodos baseados em gradiente, EAs não exigem suavidade, convexidade ou mesmo continuidade.

Laço evolutivo central (template genérico)

A maioria dos EAs compartilha a mesma estrutura de alto nível:

  1. Inicialize uma população (P_0) com (N) candidatos.
  2. Repetidamente:
    • Avalie a aptidão dos candidatos.
    • Selecione pais (parents) com viés em direção a maior aptidão.
    • Gere descendentes (offspring) via mutação e (opcionalmente) recombinação.
    • Forme a próxima população usando substituição (frequentemente com elitismo).
  3. Pare quando um orçamento for esgotado (iterações ou avaliações) ou quando uma aptidão-alvo for atingida.

Pseudocode

initialize population P with N random candidates
evaluate fitness f(x) for x in P

repeat until stopping criterion:
    parents = select(P)                      # fitness-biased sampling
    offspring = vary(parents)                # mutation and/or recombination
    evaluate fitness for offspring
    P = replace(P, offspring)                # generational or steady-state, often with elitism

return best candidate seen

Dois detalhes dominam o desempenho na prática:

  • Representação (encoding) dos candidatos
  • Operadores de variação (variation operators) que respeitam essa representação

Principais variantes

Algoritmos Genéticos (GAs)

Algoritmos genéticos (Genetic Algorithms, GAs) são o EA clássico mais associado a:

  • Representações discretas ou estruturadas:
    • sequências de bits (seleção de atributos),
    • vetores inteiros,
    • permutações (roteamento/agendamento),
    • codificações mistas discretas/contínuas.

Componentes típicos de GA:

  • Seleção: seleção por torneio, roleta (proporcional à aptidão), seleção baseada em ranking
  • Recombinação (cruzamento):
    • cruzamento de um ponto / dois pontos (sequências de bits),
    • cruzamento uniforme,
    • cruzamento parcialmente mapeado (PMX) para permutações
  • Mutação:
    • inversão de bit (sequências de bits),
    • mutação por troca (permutações),
    • reinicialização aleatória / mutação creep (inteiros)

Quando GAs se destacam: otimização combinatória, busca discreta com muitas restrições e problemas de “projeto” em que blocos de construção significativos podem se recombinar.

Cuidado: cruzamento ingênuo pode ser prejudicial se a codificação não estiver alinhada com a estrutura do problema (a clássica lição de “a representação importa”).

Estratégias Evolutivas (ES)

Estratégias evolutivas (Evolution Strategies, ES) foram desenvolvidas historicamente para otimização contínua e enfatizam a busca guiada por mutação. Uma família canônica é:

  • ((\mu, \lambda))-ES e ((\mu+\lambda))-ES
    • (\mu): número de pais
    • (\lambda): número de descendentes

Uma forma comum usa mutação gaussiana (Gaussian mutation):

[ x' = x + \sigma \cdot \mathcal{N}(0, I) ]

onde (\sigma) é um tamanho do passo (step size) (força da mutação).

Métodos modernos de ES fortemente associados a sucesso prático incluem:

  • CMA-ES (Estratégias Evolutivas com Adaptação da Matriz de Covariância, Covariance Matrix Adaptation ES): adapta uma matriz de covariância completa para a distribuição de mutação, aprendendo correlações e escalas entre variáveis. CMA-ES é amplamente considerado um dos otimizadores sem derivadas mais fortes para uso geral em problemas contínuos, não convexos e de dimensão moderada (aproximadamente dezenas a poucas centenas de variáveis, dependendo do orçamento de avaliações).

Quando ES se destacam: otimização contínua de caixa-preta, objetivos ruidosos, paisagens mal condicionadas e problemas em que a informação de derivadas é não confiável.

Evolução Diferencial (DE)

Evolução diferencial (Differential Evolution, DE) é um método simples e eficaz baseado em população para domínios contínuos. Sua ideia-chave é gerar um vetor mutante somando uma diferença escalonada de dois membros da população a um terceiro:

[ v = x_{r1} + F \cdot (x_{r2} - x_{r3}) ]

Em seguida, ela realiza cruzamento entre o candidato atual (x_i) e o mutante (v) para formar um vetor de teste, mantendo aquele que for melhor.

Parâmetros típicos de DE:

  • (F): peso diferencial (escala do passo), geralmente 0.4–0.9
  • (CR): taxa de cruzamento, geralmente 0.1–0.9
  • Tamanho da população (N): frequentemente (5D) a (20D) onde (D) é a dimensão (regra prática, não uma lei)

Quando DE se destaca: problemas contínuos com variáveis limitadas; um otimizador de base forte com relativamente poucas partes móveis.

Um exemplo prático: Evolução Diferencial em Python (mínimo)

Abaixo está um exemplo compacto otimizando a função Rastrigin (multimodal, benchmark clássico não convexo). Ele é intencionalmente mínimo para ilustrar a mecânica algorítmica.

import numpy as np

def rastrigin(x):
    A = 10.0
    return A * len(x) + np.sum(x**2 - A * np.cos(2 * np.pi * x))

def differential_evolution(f, bounds, pop_size=50, F=0.8, CR=0.9, iters=200, seed=0):
    rng = np.random.default_rng(seed)
    D = len(bounds)
    lo = np.array([b[0] for b in bounds])
    hi = np.array([b[1] for b in bounds])

    # init population uniformly in bounds
    pop = lo + (hi - lo) * rng.random((pop_size, D))
    fit = np.array([f(x) for x in pop])

    for _ in range(iters):
        for i in range(pop_size):
            idxs = [j for j in range(pop_size) if j != i]
            r1, r2, r3 = rng.choice(idxs, size=3, replace=False)
            v = pop[r1] + F * (pop[r2] - pop[r3])
            v = np.clip(v, lo, hi)

            # binomial crossover
            cross = rng.random(D) < CR
            cross[rng.integers(0, D)] = True  # ensure at least one dimension from v
            u = np.where(cross, v, pop[i])

            fu = f(u)
            if fu <= fit[i]:
                pop[i], fit[i] = u, fu

    best = pop[np.argmin(fit)]
    return best, np.min(fit)

best_x, best_f = differential_evolution(
    rastrigin, bounds=[(-5.12, 5.12)] * 10, pop_size=80, iters=400
)
print(best_f, best_x)

Na prática, você normalmente usaria uma implementação de biblioteca bem testada (por exemplo, differential_evolution do SciPy) e focaria em codificação, limites, restrições e custo de avaliação.

Principais escolhas de projeto (o que determina o desempenho)

1) Representação (encoding)

Codificações comuns incluem:

  • Vetores reais: parâmetros contínuos (controle, calibração, pesos de modelos em redes pequenas)
  • Sequências de bits: seleção de atributos, conjuntos de regras, alternâncias de arquitetura
  • Vetores inteiros: hiperparâmetros discretos, alocações de recursos
  • Permutações: roteamento (TSP), agendamento, problemas de ordenação
  • Árvores/grafos: programação genética, regressão simbólica, busca de arquitetura neural (Neural Architecture Search, NAS)

Boas representações fazem com que pequenas mudanças genéticas correspondam a pequenas mudanças comportamentais — isso é frequentemente chamado de mapeamento genótipo–fenótipo (genotype–phenotype) suave.

2) Projeto da função de aptidão

O projeto prático da aptidão frequentemente envolve:

  • Escalonamento / normalização quando a aptidão bruta tem enorme faixa dinâmica
  • Tratamento de ruído (média de múltiplas avaliações, usar ranking de aptidão em vez de valores brutos)
  • Métricas multiobjetivo (acurácia vs latência vs memória)

Para casos de uso em ML, a aptidão pode ser a perda de validação, a recompensa em simulação ou uma combinação ponderada de métricas.

3) Pressão de seleção (selection pressure)

A seleção controla o equilíbrio entre explotação e exploração:

  • Fraca demais: progresso lento
  • Forte demais: convergência prematura (perda de diversidade)

Métodos comuns de seleção:

  • Seleção por torneio (simples, robusta)
  • Seleção por ranking (estável sob outliers)
  • Proporcional à aptidão (pode ser instável se a escala da aptidão for ruim)

4) Operadores de variação (mutação e recombinação)

A mutação deve ser ajustada à geometria do espaço de busca:

  • Em espaços contínuos: mutação gaussiana, perturbações por coordenada, adaptação de covariância (CMA-ES)
  • Em espaços discretos: inversões de bit, trocas, edições locais

A recombinação ajuda quando “blocos de construção” podem ser combinados de forma significativa, mas pode prejudicar com codificações ruins.

5) Tamanho da população e manutenção da diversidade

O tamanho da população (N) é um ajuste central:

  • (N) maior: mais diversidade, melhor busca global, mais paralelismo, maior custo de avaliação
  • (N) menor: iterações mais rápidas, maior risco de estagnação

Técnicas de diversidade:

  • Compartilhamento de aptidão / formação de nichos (niching) (incentivar múltiplos nichos)
  • Busca por novidade (novelty search) (otimizar por diversidade comportamental)
  • Modelos de ilhas (island models) (múltiplas subpopulações com migração)

6) Estratégia de substituição e elitismo

  • Geracional: substitui toda a população a cada iteração (comum em GA, DE)
  • Estado estacionário (steady-state): substitui alguns indivíduos por vez (pode ser mais estável)

Elitismo (elitism) (manter o melhor até agora) melhora a confiabilidade, mas pode reduzir a diversidade se for usado em excesso.

7) Tratamento de restrições

Problemas reais frequentemente têm restrições (g(x)\le 0), (h(x)=0). As abordagens incluem:

  • Funções de penalidade (penalty functions): otimizar (f(x) + \lambda \cdot \text{penalty}(x))
  • Regras de viabilidade (feasibility rules): sempre preferir soluções viáveis; entre inviáveis, preferir as que “violam menos”
  • Operadores de reparo (repair operators): mutar ou projetar de volta para a viabilidade
  • Codificações especializadas: garantir que todos os candidatos gerados sejam viáveis por construção

Para uma base mais formal, veja Otimização com Restrições. Para restrições mistas discretas/contínuas, EAs frequentemente complementam Programação Inteira Mista quando a otimização exata é custosa demais.

8) Critérios de parada e orçamentos

Como EAs podem continuar melhorando lentamente, a parada geralmente é baseada em orçamento:

  • Máximo de avaliações (comum para simulações caras)
  • Tempo de relógio (wall-clock time) máximo
  • Sem melhoria por (k) gerações
  • Aptidão-alvo alcançada

Fundamentos teóricos (intuição útil, não magia)

EAs são heurísticos, mas há várias lentes teóricas importantes:

EAs como processos de busca estocásticos

Um EA induz um processo estocástico (frequentemente modelado como uma cadeia de Markov (Markov chain)) sobre populações. Essa perspectiva é usada para raciocinar sobre:

  • convergência (em um sentido probabilístico),
  • efeitos da pressão de seleção,
  • deriva em direção/afastamento da diversidade.

Na prática, orçamentos finitos de avaliações importam mais do que convergência assintótica.

Exploração vs explotação

A seleção explora regiões atualmente boas; mutação/recombinação exploram novas regiões. Muitos “truques” de EAs dizem respeito a manter um equilíbrio produtivo:

  • explotação demais → convergência prematura,
  • exploração demais → busca aleatória.

Esse trade-off é um tema recorrente em otimização, incluindo Otimização Estocástica.

Intuição de No Free Lunch (NFL)

De maneira informal, os teoremas de No Free Lunch (No Free Lunch) dizem que, em média sobre todas as funções objetivo possíveis, nenhum otimizador é melhor do que outro. O aprendizado prático:

  • EAs funcionam bem quando seus vieses combinam com a estrutura do problema (representação + operadores).
  • Desempenho vem de explorar regularidades do domínio, não de superioridade universal.

Aplicações em IA/ML e além

Otimização de hiperparâmetros (Hyperparameter Optimization, HPO)

EAs são frequentemente usados para:

  • hiperparâmetros discretos/condicionais (por exemplo, “se optimizer=Adam então ajustar beta1/beta2”),
  • espaços mistos (taxa de aprendizado contínua + escolhas de arquitetura discretas),
  • ajuste paralelo em clusters.

Eles frequentemente competem com otimização bayesiana; veja a comparação abaixo.

Neuroevolução e busca de políticas

Em cenários de aprendizado por reforço (reinforcement learning) em que gradientes são ruidosos, indisponíveis ou indesejáveis, EAs podem otimizar:

  • parâmetros de política diretamente (“neuroevolução”),
  • políticas estruturadas (regras, programas),
  • parâmetros de controladores em robótica.

Eles são atraentes quando:

  • as avaliações são simulações paralelas,
  • as superfícies de recompensa não são suaves,
  • você quer comportamentos diversos (busca por novidade, métodos de qualidade-diversidade).

(Antecedentes relacionados: Aprendizado por Reforço.)

Busca de arquitetura neural (Neural Architecture Search, NAS)

EAs podem buscar por:

  • tipos de camadas e conectividade,
  • larguras/profundidades,
  • escolhas de operadores.

Eles são especialmente úteis quando o espaço de busca é fortemente discreto e modular.

Projeto e calibração em engenharia

Território clássico de EAs:

  • otimização de forma aerodinâmica,
  • ajuste de controladores,
  • projeto baseado em simulação onde cada avaliação é cara.

Otimização combinatória

GAs (e métodos relacionados) são baselines comuns para:

  • agendamento,
  • roteamento,
  • seleção de subconjuntos,
  • problemas de atribuição.

Para métodos exatos e garantias, estes também podem ser formulados em Programação Linear ou Programação Inteira Mista, mas EAs podem ser mais escaláveis ou flexíveis quando o modelo é difícil de expressar exatamente.

Comparando algoritmos evolutivos com otimização bayesiana e outros métodos de caixa-preta

Versus otimização bayesiana (BO)

Otimização bayesiana normalmente constrói um modelo substituto probabilístico (frequentemente processos gaussianos ou modelos baseados em árvores) e seleciona novas avaliações via uma função de aquisição.

Principais diferenças:

  • Eficiência amostral

    • BO frequentemente é mais eficiente em amostras em dimensões baixas a moderadas quando avaliações são muito caras (por exemplo, minutos a horas).
    • EAs frequentemente precisam de mais avaliações, mas ainda podem vencer quando há paralelismo abundante.

  • Dimensionalidade

    • BO com processos gaussianos sofre conforme a dimensionalidade cresce (regra prática: fica difícil após algumas dezenas de variáveis sem estrutura especial).
    • EAs (especialmente CMA-ES/DE) lidam com dimensões maiores de forma mais natural, embora também tenham limites.

  • Paralelismo

    • EAs são naturalmente paralelos: avalie uma população inteira de uma vez.
    • BO pode ser paralelizada, mas é mais complexa e pode se tornar menos eficiente em amostras quando muito “batelada”.

  • Tipo de espaço de busca

    • BO pode lidar com espaços mistos com o substituto adequado (por exemplo, métodos no estilo TPE/SMAC).
    • GAs frequentemente são diretos para espaços discretos/estruturados se você consegue definir operadores.

  • Objetivos ruidosos

    • Ambos conseguem lidar com ruído; EAs frequentemente dependem de ranking e amostragem repetida; BO precisa de substitutos cientes de ruído.

Uma heurística prática:

  • Escolha BO quando as avaliações forem muito caras e a dimensionalidade não for muito alta, e você quiser forte eficiência amostral.
  • Escolha EAs quando você tiver muito compute paralelo, problemas contínuos de maior dimensão, representações estruturadas/discretas ou quando você esperar muitos ótimos locais.

(Se seu wiki tiver, esse tópico costuma ser coberto em Otimização Bayesiana.)

Versus busca aleatória e busca em grade

  • Busca em grade (grid search) raramente é eficiente, exceto para espaços muito pequenos.
  • Busca aleatória (random search) é um baseline forte em HPO de alta dimensão (surpreendentemente difícil de superar no início).
  • EAs tipicamente superam busca aleatória quando:
    • operadores de variação exploram estrutura,
    • você consegue reutilizar boas soluções parciais via seleção/recombinação,
    • você roda tempo suficiente para a adaptação fazer diferença.
  • Métodos locais podem ser excelentes quando a paisagem é mais ou menos suave e unimodal perto do ótimo, mas é mais fácil ficarem presos em mínimos locais.
  • EAs fornecem exploração mais global via populações e diversidade, frequentemente tornando-os melhores escolhas padrão para problemas fortemente multimodais.

Dicas práticas e armadilhas comuns

Dicas que geralmente ajudam

  • Comece com um baseline forte conhecido:
    • contínuo: CMA-ES ou DE,
    • discreto/permutação: GA com mutação/cruzamento específicos do problema.
  • Limite e escale variáveis (normalize parâmetros contínuos para faixas semelhantes).
  • Use seleção baseada em ranking para reduzir sensibilidade a escalonamento de aptidão e ruído.
  • Adicione elitismo com cuidado (mantenha 1–5% melhores), mas evite destruir a diversidade.
  • Explore paralelismo: EAs frequentemente são “ávidos por computação, mas amigáveis ao tempo de relógio”.
  • Registre tudo: melhor/mediana aptidão, métricas de diversidade, violações de restrições.

Armadilhas comuns

  • Codificação ruim: cruzamento/mutação desorganiza o significado, causando deriva aleatória.
  • Pressão de seleção excessiva: convergência rápida para soluções medianas.
  • Ignorar restrições: a população gasta esforço em regiões inviáveis.
  • Overfitting na aptidão: em ML, selecionar repetidamente com base em um conjunto de validação pode superajustar essa métrica de validação (use protocolos de avaliação adequados).

Extensões que vale a pena conhecer

  • EAs multiobjetivo (Multi-objective EAs, MOEAs): otimizam trade-offs (frentes de Pareto). Populares: NSGA-II, SPEA2.
  • Métodos de qualidade-diversidade (quality-diversity, QD): buscam muitas soluções diversas e de alta qualidade (útil em robótica e projeto).
  • Algoritmos meméticos (memetic algorithms): combinam busca global de EA com melhoria local (híbrido global + local).
  • EAs assistidos por substitutos (surrogate-assisted EAs): integram modelos aprendidos para reduzir avaliações caras (combinando ideias de EA com modelagem substituta no estilo de BO).

Resumo

Algoritmos evolutivos são otimizadores versáteis sem gradientes, baseados em população inspirados pela seleção natural. As variantes centrais mais comuns são:

  • Algoritmos genéticos (GA): flexíveis para representações discretas/estruturadas.
  • Estratégias evolutivas (ES, especialmente CMA-ES): fortes para otimização contínua de caixa-preta.
  • Evolução diferencial (DE): otimizador contínuo simples e eficaz.

Na prática, o sucesso depende menos de “qual EA” e mais de representação, operadores de variação, tratamento de restrições, diversidade populacional e orçamento de avaliações. Em comparação com otimização bayesiana, EAs frequentemente são menos eficientes em amostras, mas mais naturalmente paralelos, mais robustos em paisagens altamente multimodais e, com frequência, mais fáceis de aplicar a espaços de busca estruturados/discretos.

Para leitores vindos de treinamento baseado em gradientes, EAs são melhor entendidos como uma ferramenta complementar: quando Descenso do Gradiente é indisponível ou não confiável, a busca evolutiva oferece uma forma fundamentada e prática de explorar paisagens complexas de otimização.