💻 computer science

The Effects of Population Size on the Performance of BEAGLE GPU-Based Genetic Programming Runs

Este artigo investiga como os tamanhos de população acelerados por GPU dentro do framework Beagle influenciam o desempenho da regressão simbólica, revelando que as estratégias de busca ótimas variam entre buscas estreitas e profundas e buscas amplas e rasas, ao mesmo tempo em que demonstra a eficácia de tamanhos de população escalonados que transitam de grupos grandes para pequenos.

Autores originais: Nathan Haut, Ilya Basin, Ruchika Gupta, Marzieh Kianinejad, Zachary Perrico, Elijah Smith, Wolfgang Banzhaf

Publicado 2026-04-29

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Nathan Haut, Ilya Basin, Ruchika Gupta, Marzieh Kianinejad, Zachary Perrico, Elijah Smith, Wolfgang Banzhaf

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando encontrar um tesouro específico e escondido em uma ilha massiva e sem mapa. No mundo da ciência da computação, esse "tesouro" é a fórmula matemática perfeita que explica um conjunto de dados. O método usado para encontrá-la é chamado de Programação Genética (PG). Pense na PG como uma versão digital da evolução: você começa com uma multidão enorme de fórmulas aleatórias e desajeitadas (a "população"). Você as testa, mantém aquelas que chegam mais perto do tesouro, mistura suas melhores partes e repete o processo uma e outra vez até que uma fórmula finalmente resolva o enigma.

Por muito tempo, esse processo foi lento. Era como tentar explorar essa ilha com uma única pessoa caminhando devagar, verificando um local de cada vez.

O Fator de Mudança: O Super-Equipe de GPUs

Este artigo apresenta uma nova ferramenta chamada Beagle, que utiliza GPUs (os chips poderosos geralmente encontrados em computadores de videogame) para acelerar o processo.

Se um computador tradicional (CPU) é como um único bibliotecário muito inteligente que pode ler um livro de cada vez, uma GPU é como um estádio cheio de 10.000 bibliotecários que podem ler livros diferentes exatamente ao mesmo tempo. O Beagle aproveita esse poder para testar milhões de fórmulas simultaneamente, algo que anteriormente era impossível de fazer em um tempo razoável.

A Grande Pergunta: Qual Deve Ser o Tamanho da Multidão?

Os pesquisadores queriam saber: Importa quantas fórmulas testamos de uma vez?

Eles testaram duas estratégias principais:

A Busca "Ampla e Rasa": Uma multidão massiva (de até 10 milhões de pessoas) que só consegue dar alguns passos. Isso é como enviar um exército enorme para escanear toda a ilha rapidamente, mas eles não têm tempo para cavar fundo em nenhum local específico.
A Busca "Estreita e Profunda": Uma multidão minúscula (tão pequena quanto 1.000 pessoas) que consegue dar milhões de passos. Isso é como enviar uma equipe pequena e especializada que pode cavar muito fundo em áreas específicas ao longo de um longo período.

O Que Eles Descobriram

Os resultados foram surpreendentes e mostraram que não existe um único tamanho "ideal" de multidão. Tudo depende do terreno da ilha (o problema matemático específico).

Alguns problemas precisam de uma multidão massiva: Para certos quebra-cabeças complicados, os pesquisadores descobriram que precisavam de uma multidão de 5 a 10 milhões de pessoas apenas para encontrar a solução. Se usassem uma multidão pequena, nunca encontrariam a resposta. Parece que esses problemas têm uma paisagem muito "acidentada", onde você precisa examinar milhares de possibilidades diferentes apenas para obter um ponto de apoio.
Alguns problemas precisam de uma equipe focada: Outros problemas foram resolvidos melhor por uma multidão minúscula de 1.000 pessoas. Esses problemas tinham uma paisagem mais "suave". Uma equipe pequena podia cavar lenta e cuidadosamente cada vez mais fundo até encontrar o tesouro, enquanto uma multidão massiva estava muito dispersa para focar o suficiente.
A Estratégia "Cachinhos Dourados": Eles também tentaram uma abordagem em etapas. Imagine começar com um exército massivo para escanear toda a ilha e encontrar as regiões promissoras e, em seguida, assim que souber onde procurar, reduzir o exército para uma equipe pequena e de elite para cavar fundo. Eles descobriram que isso funcionou muito bem, combinando o melhor dos dois mundos.

O Problema: O "Limite de Tempo"

Os pesquisadores realizaram esses experimentos com um limite de tempo rigoroso (15 minutos).

Se você tem uma multidão enorme, só pode executar algumas "gerações" (rodadas de teste) antes que o tempo se esgote.
Se você tem uma multidão minúscula, pode executar milhares de gerações.

O artigo mostra que o Beagle é tão eficiente que não perde tempo gerenciando essas multidões enormes. Ele escala perfeitamente, o que significa que você não perde velocidade apenas porque adicionou mais pessoas.

A Conclusão

Este artigo prova que, com a tecnologia moderna de GPU, finalmente podemos executar experimentos de programação genética com populações na casa dos milhões.

A lição principal é simples: Problemas diferentes exigem estratégias de busca diferentes. Às vezes, você precisa de uma rede larga para pegar um peixe raro; outras vezes, você precisa de uma mergulho profundo. O framework Beagle permite que cientistas tentem ambos os extremos e até os misturem, tornando possível resolver problemas matemáticos complexos que anteriormente eram difíceis demais para serem desvendados.

1. Declaração do Problema

A Programação Genética (PG) é uma técnica de busca heurística utilizada para regressão simbólica, mas enfrenta gargalos computacionais significativos, principalmente durante a fase de avaliação de aptidão. Historicamente, a adoção de Unidades de Processamento Gráfico (GPUs) para acelerar a PG ficou atrás de seu sucesso em Aprendizado Profundo devido a várias incompatibilidades de hardware e arquitetura:

Incompatibilidade Estrutural: Representações tradicionais de PG baseadas em árvores envolvem estruturas de árvore irregulares e dinâmicas que são difíceis de mapear na arquitetura de memória rígida e linear das GPUs (SIMD).
Divergência de Warps: Ramificações condicionais (por exemplo, instruções IF/ELSE) causam divergência de threads nos warps da GPU, levando à degradação do desempenho.
Sobrecarga de Memória: Frameworks existentes frequentemente dependem de preenchimento de árvores com valores "NaN" para atender aos requisitos de tensores ou utilizam soluções complexas (como mascaramento algébrico) que introduzem cálculos redundantes e inchaço de memória.
Coleta de Lixo (GC): Alocação e desalocação frequentes de memória em algoritmos evolutivos baseados em CPU consomem recursos significativos, um problema exacerbado na PG baseada em árvores.

Essas limitações impediram que os pesquisadores utilizassem o paralelismo massivo das GPUs para explorar tamanhos de população na casa dos milhões, forçando um compromisso entre a amplitude da busca (populações grandes) e a profundidade da busca (muitas gerações).

2. Metodologia

Os autores utilizaram o Beagle, um framework de regressão simbólica de código aberto desenvolvido pela Noblis, Inc., especificamente projetado para superar os referidos gargalos de GPU.

Arquitetura do Framework Beagle

Programação Genética Linear (LGP): Em vez de estruturas baseadas em árvores, o Beagle utiliza uma Linguagem de Computador de Genoma (GCL) personalizada baseada em Notação Polonesa Reversa (RPN). Essa estrutura linear é livre de heap, tornando-a altamente compatível com modelos de memória de GPU e eliminando a sobrecarga de GC.
Modelo de Execução em GPU:
- Mapeamento: Cada bloco CUDA representa um único organismo (indivíduo), e cada thread dentro do bloco representa uma única avaliação de caso de aptidão. Esse mapeamento 1 para 1 elimina a divergência de warps.
- Agrupamento (Batching): Para minimizar a sobrecarga de transferência de dados CPU-GPU, os indivíduos são enviados à GPU uma vez por geração para avaliar um lote de casos de aptidão (por exemplo, 512 ou 1024 casos) antes de retornar resultados agregados.
- Sem Cruzamento: A implementação atual depende de mutação e seleção, evitando as complexidades de recombinação estrutural que prejudicam o desempenho da GPU.
Otimização em CPU:
- Reciclagem de Memória: O Beagle evita a desalocação. Indivíduos "mortos" são colocados em um pool e reciclados para novos indivíduos, eliminando efetivamente a Coleta de Lixo e a fragmentação de memória.
- Seleção: É utilizado um processo de seleção inovador e de alto desempenho inspirado em Monte-Carlo. Em vez de ordenar toda a população (o que não escala), ele ordena uma amostra aleatória (por exemplo, 100 indivíduos) para estimar percentis de aptidão para toda a população, permitindo a seleção de populações na casa das dezenas de milhões.
Função de Aptidão: Utiliza uma métrica baseada em correlação ( $r^4$ ) adaptada para lidar com números inválidos (NaNs), recompensando/punindo com base se o modelo produz saídas inválidas onde o alvo é inválido.

Configuração Experimental

Benchmarks: 7 problemas do Benchmarks de Regressão Simbólica Feynman (Equações 7, 14, 31, 56, 57, 86, 91).
Restrições: Cada execução foi limitada a 15 minutos.
Estratégias Testadas:
1. Tamanhos de População Constantes: Variando de 100 a 100 milhões de indivíduos.
2. Tamanhos de População em Etapas: Começando com uma população grande (por exemplo, 5M ou 1M) e reduzindo para um tamanho menor (por exemplo, 100K, 10K, 1K, 100) após um número definido de gerações para equilibrar amplitude e profundidade.
Critérios de Sucesso: Um problema foi considerado resolvido se o erro no conjunto de teste (128 pontos) fosse inferior a 0,1%.

3. Principais Contribuições

Quantificação dos Limites de Escala: O estudo demonstra que a PG acelerada por GPU pode gerenciar efetivamente tamanhos de população de até 100 milhões de indivíduos com sobrecarga computacional insignificante, uma escala anteriormente inatingível.
Caracterização dos Compromissos entre Amplitude e Profundidade: Os autores provaram empiricamente que o tamanho de população ideal é dependente do problema.
- Alguns problemas (por exemplo, Eq 56) exigem buscas "estreitas e profundas" (populações pequenas, muitas gerações).
- Outros (por exemplo, Eq 57) exigem buscas "amplas e rasas" (populações massivas, poucas gerações) para navegar em paisagens de aptidão acidentadas.
Gerenciamento Dinâmico de População: O artigo introduz e valida estratégias "em etapas". Começar com uma população grande para explorar o espaço de busca e depois reduzi-la para focar em regiões promissoras permite que o sistema beneficie-se tanto da alta diversidade quanto da alta pressão de seleção.

4. Resultados

Estabilidade da População: O framework Beagle mantém os tamanhos de população alvo com uma distribuição Gaussiana (majoritariamente dentro de ±20% do alvo), confirmando a estabilidade da abordagem de seleção Monte-Carlo.
Desempenho com População Constante:
- 10 Milhões foi o tamanho constante mais bem-sucedido no geral (resolvendo 112/210 instâncias totais de problemas).
- 1.000 indivíduos performaram excepcionalmente bem para problemas específicos (como Eq 56) que exigem iteração profunda.
- 100 Milhões mostrou retornos decrescentes para alguns problemas, provavelmente devido ao limite de tempo permitir menos gerações, embora tenha resolvido o maior número de problemas no geral.
- 100 indivíduos performaram mal devido à sobrecarga de comunicação em relação à pequena carga de computação.
Desempenho com População em Etapas:
- A estratégia 5M $\to$ 100K foi a mais robusta, resolvendo o maior número de problemas (102/210) e resolvendo com sucesso equações difíceis (como Eq 57) que populações pequenas constantes perderam.
- A estratégia 1M $\to$ 100 destacou-se em problemas que exigem busca profunda (Eq 56), resolvendo-os quase 100% das vezes.
Eficiência de Escala: Existe uma relação inversamente proporcional entre o tamanho da população e o número de gerações concluídas. Um aumento de 10x no tamanho da população resulta em uma diminuição de 10x nas gerações, confirmando que o Beagle escala linearmente sem sobrecarga significativa até 100M de indivíduos.

5. Significado

Este trabalho altera fundamentalmente o paradigma da Programação Genética ao provar que tamanhos de população massivos não são apenas viáveis, mas frequentemente necessários para resolver problemas complexos de regressão simbólica.

Utilização de Hardware: Resolve os problemas históricos de "ocupação" e divergência da PG em GPUs, permitindo que os pesquisadores aproveitem totalmente os clusters de GPU modernos.
Novo Espaço de Soluções: Ao permitir populações na casa dos milhões, o Beagle torna problemas anteriormente intratáveis acessíveis a algoritmos evolutivos.
Insight Estratégico: As descobertas sugerem que um tamanho de população "tamanho único" é subótimo. Em vez disso, estratégias dinâmicas que adaptam o tamanho da população com base na topologia específica da paisagem de aptidão (acidentada vs. suave) produzem resultados superiores.
Impacto de Código Aberto: Ao liberar o Beagle como código aberto, os autores fornecem à comunidade uma ferramenta para experimentar essas escalas massivas, potencialmente acelerando a descoberta de modelos simbólicos em física, engenharia e ciência de dados.