Skip to content
Voltar aos resultados

Algoritmo Genético — Otimização Evolucionária

Proposto por
John Henry Holland
Ano
1975
Tipo
Population-based metaheuristic

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

Um algoritmo genético (AG) é um método de otimização meta-heurístico baseado em população, introduzido por John Henry Holland (1975), que mimetiza os princípios da seleção natural. Ele mantém uma população de soluções candidatas e as aprimora iterativamente através de operadores de seleção, cruzamento (crossover) e mutação, tornando-o especialmente poderoso em espaços de busca descontínuos, não convexos e multimodais, onde métodos clássicos baseados em gradiente falham.

A intuição por trás do método

Imagine que você tem milhares de respostas possíveis para um problema difícil e nenhuma fórmula para encontrar a melhor. Um algoritmo genético trata cada resposta candidata como um indivíduo em uma população. Em cada geração, ele mantém os indivíduos mais aptos, os cruza para misturar suas boas características e ocasionalmente muta os descendentes para introduzir novidade. Ao longo de muitas gerações, a população deriva para soluções cada vez melhores — não seguindo um gradiente, mas mimetizando a forma como a evolução molda os organismos ao longo do tempo.

História

O algoritmo genético foi introduzido por John Henry Holland em seu livro de 1975, Adaptation in Natural and Artificial Systems, que formalizou a noção de um esquema (bloco de construção) e forneceu a análise teórica fundamental do porquê o cruzamento e a seleção impulsionam a busca em direção a regiões mais aptas. Alunos de Holland — notavelmente David Goldberg — popularizaram os AGs através de aplicações de engenharia nos anos 1980. Kalyanmoy Deb posteriormente estendeu o framework para configurações multiobjetivo, culminando no amplamente adotado algoritmo NSGA-II (2002). Hoje, os AGs permanecem uma ferramenta padrão em computação evolutiva, com pesquisa ativa em métodos híbridos que combinam busca evolutiva com refinamento local.

Quando usar

Algoritmos genéticos são apropriados quando o espaço de busca é grande, descontínuo, não diferenciável ou altamente multimodal — condições onde solucionadores baseados em gradiente não podem operar ou ficam presos em ótimos locais. Eles se aplicam a tipos de variáveis contínuas, categóricas, binárias e ordinais e não impõem suposições de normalidade ou distribuição. O único requisito é uma função de aptidão computável. Para problemas onde existe uma formulação analítica ou convexa, métodos clássicos (programação linear, descida de gradiente) são mais rápidos e devem ser preferidos. Iterações suficientes (tipicamente bem acima de 1.000 gerações) são necessárias para uma convergência significativa; executar poucas gerações é o modo de falha mais comum.

Limitações e considerações

  • Não há garantia de convergência para o ótimo global; os resultados podem variar entre execuções.
  • Computacionalmente caro: cada geração requer a avaliação de toda a população, o que é proibitivo quando a função de aptidão é lenta.
  • O desempenho é sensível às escolhas de hiperparâmetros — tamanho da população, probabilidade de cruzamento e taxa de mutação — que frequentemente requerem ajuste específico do problema.
  • Para problemas suaves, convexos ou bem estruturados, métodos clássicos baseados em gradiente ou lineares serão mais rápidos e confiáveis.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Funciona em paisagens de objetivos descontínuas, não diferenciáveis e multimodais onde métodos baseados em gradiente falham.
  • Não impõe suposições de distribuição — o único input necessário é uma função de aptidão computável.
  • Lida naturalmente com uma ampla gama de tipos de variáveis: contínuas, binárias, categóricas e ordinais.
  • A diversidade da população permite a exploração simultânea de múltiplas regiões do espaço de busca, reduzindo o risco de aprisionamento prematuro em ótimos locais.
  • Altamente extensível: operadores de cruzamento e mutação específicos do domínio, manipulação de restrições e variantes multiobjetivo (por exemplo, NSGA-II) são bem estabelecidos na literatura.

Aplicações

  • Otimização de projeto de engenharia: encontrar configurações ótimas de parâmetros para estruturas, circuitos ou sistemas mecânicos.
  • Problemas de escalonamento e roteamento: escalonamento de job-shop, roteamento de veículos e elaboração de horários onde o espaço de busca combinatório é muito grande para busca exaustiva.
  • Aprendizado de máquina: ajuste de hiperparâmetros, busca de arquitetura neural e seleção de características.
  • Pesquisa operacional: otimização de cadeia de suprimentos, alocação de portfólio e atribuição de recursos sob restrições complexas.
  • Bioinformática: alinhamento de sequências, predição de estrutura de proteínas e inferência de rede regulatória de genes.

Como funciona

Como funciona

1

Uma população de soluções candidatas (indivíduos) é criada, tipicamente de forma aleatória dentro do espaço de busca. Cada indivíduo codifica uma solução potencial — por exemplo, como uma string binária, um vetor de valores reais ou uma permutação — e o tamanho da população é um parâmetro chave que determina quão amplamente o espaço de busca é amostrado desde o início.

2

Cada indivíduo na população é avaliado por uma função de aptidão (fitness function) que quantifica quão boa é essa solução em relação ao objetivo do problema. A função de aptidão é o único componente específico do domínio que o usuário deve fornecer; pode ser qualquer medida computável — a saída de uma simulação, uma fórmula de custo ou uma métrica de erro de modelo.

3

Indivíduos com maior aptidão são escolhidos preferencialmente para se tornarem pais da próxima geração. Mecanismos comuns de seleção incluem seleção por torneio, seleção por roleta (proporcional à aptidão) e seleção baseada em ranking. A pressão de seleção controla o trade-off entre explorar soluções de alta qualidade e manter a diversidade da população.

4

Pais selecionados produzem descendentes através do cruzamento (recombinação), onde segmentos das codificações de dois pais são combinados para formar um novo indivíduo, e através da mutação, onde pequenas alterações aleatórias são aplicadas a genes individuais. A probabilidade de cruzamento e a taxa de mutação são parâmetros críticos de ajuste: pouca mutação causa convergência prematura, muita mutação transforma a busca em um passeio aleatório.

5

O ciclo de avaliar → selecionar → reproduzir continua por um número definido de gerações ou até que um critério de convergência seja atingido (por exemplo, nenhuma melhoria em uma janela de gerações). O melhor indivíduo encontrado em todas as gerações é retornado como a solução. Como a convergência para o ótimo global não é garantida, múltiplas execuções independentes são recomendadas para problemas de alto risco.

Erros comuns

  • Executar poucas gerações é o erro mais comum: com gerações insuficientes, o algoritmo não converge, portanto, métodos analíticos ou baseados em gradiente devem ser preferidos quando apenas um pequeno orçamento de iteração está disponível.
  • Convergência prematura — a perda de diversidade da população muito cedo — produz um resultado localmente ótimo, mas globalmente subótimo; mantenha um tamanho de população e taxa de mutação adequados para neutralizar isso.
  • Usar uma função de aptidão mal definida ou especificada incorretamente produz resultados enganosos, independentemente da correção algorítmica; valide a função de aptidão independentemente antes de executar o AG.
  • Aplicar um AG a um problema suave e convexo onde a descida de gradiente ou a programação linear seriam suficientes desperdiça recursos computacionais e introduz estocasticidade desnecessária.
  • Relatar uma única execução como solução sem verificar a reprodutibilidade; para aplicações de alto risco, execute o algoritmo várias vezes e relate a distribuição dos resultados.

Perguntas frequentes

Como um algoritmo genético difere da descida de gradiente?

A descida de gradiente requer um objetivo diferenciável e segue o gradiente local para baixo. Um algoritmo genético requer apenas que a aptidão possa ser calculada para qualquer solução candidata; ele busca evoluindo uma população em vez de seguir um gradiente, portanto, pode lidar com paisagens descontínuas, não diferenciáveis e multimodais onde a descida de gradiente falha ou fica presa.

Quantas gerações e qual o tamanho da população eu preciso?

Não há regras universais; ambos dependem da complexidade do espaço de busca. Uma população muito pequena ou uma execução muito curta arriscam convergência prematura. Como ponto de partida prático, tamanhos de população de 50–200 e contagens de gerações de 100–1.000 são comuns na literatura, mas problemas desafiadores rotineiramente exigem mais. Sempre inspecione as curvas de convergência em vez de fixar critérios de parada arbitrários.

Um algoritmo genético tem garantia de encontrar o ótimo global?

Não. AGs são heurísticas e não oferecem garantia de convergência para o ótimo global em tempo finito. Para garantias determinísticas, você precisa de métodos exatos como solucionadores de programação inteira. Para decisões de alto risco, execute o AG várias vezes, relate a distribuição dos resultados e compare a melhor solução com quaisquer limites conhecidos.

Quando devo escolher um AG em vez de recozimento simulado (simulated annealing) ou otimização por enxame de partículas (particle swarm optimization)?

AGs tendem a ser preferidos quando a solução é naturalmente codificada como uma estrutura combinatória (permutações, strings binárias) ou quando extensões multiobjetivo são necessárias. A otimização por enxame de partículas é frequentemente mais rápida em problemas contínuos unimodais. O recozimento simulado é mais simples de implementar para problemas combinatórios com uma vizinhança bem definida. Na prática, é aconselhável comparar duas ou três métodos em uma pequena instância de problema antes de se comprometer com um.

Métodos relacionados

Fontes

  1. Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

    Abrir referência da publicação
    Copiado.
  2. Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.

    ISBN: 9780471873396
    Copiado.