Algoritmo Genético Estocástico — Busca Evolutiva Aleatória para Otimização
- Proposto por
- Holland, J. H.
- Ano
- 1975
- Tipo
- Stochastic evolutionary metaheuristic
- Família
- Simulation / optimization
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
O Algoritmo Genético Estocástico (SGA) é uma metaheurística baseada em população que mimetiza a evolução biológica — seleção, cruzamento e mutação — para buscar soluções quase ótimas em espaços complexos, não lineares ou combinatórios.
Seus operadores aleatórios o tornam robusto a ótimos locais e amplamente aplicável em engenharia, escalonamento, aprendizado de máquina e pesquisa operacional.
A intuição por trás do método
Imagine uma população de soluções candidatas competindo pela sobrevivência. Soluções melhores têm maior probabilidade de serem escolhidas como pais; seus descendentes herdam e recombinam traços bons, enquanto mutações aleatórias ocasionais introduzem novidade. Ao longo de muitas gerações, esse processo converge para regiões de alta qualidade do espaço de busca sem a necessidade de informações de gradiente. O rótulo estocástico enfatiza que seleção, cruzamento e mutação envolvem sorteios probabilísticos, o que distingue o AG canônico de raras variantes determinísticas e lhe confere capacidade de busca global.
História
John Holland introduziu os fundamentos teóricos dos algoritmos genéticos na Universidade de Michigan em 1975, baseando-se em trabalhos anteriores de Fraser (1957) sobre sistemas genéticos simulados. O livro de David Goldberg de 1989 popularizou os AGs para otimização em engenharia. A natureza estocástica da seleção foi formalizada através do teorema do esquema, e o método tornou-se um pilar da computação evolutiva e da inteligência computacional.
Quando usar
Use um Algoritmo Genético Estocástico quando: (1) o espaço de busca for grande, multimodal ou descontínuo e métodos baseados em gradiente falharem ou forem inaplicáveis; (2) a função objetivo for caixa-preta, ruidosa ou cara de avaliar, mas tratável para amostragem em nível de população; (3) problemas combinatórios ou de inteiros mistos carecerem de solucionadores exatos eficientes; (4) uma solução quase ótima encontrada dentro de um número razoável de avaliações for aceitável. NÃO use SGA quando: o problema for convexo ou o gradiente estiver disponível e for barato — otimização clássica converge mais rápido; quando as avaliações de função forem extremamente caras (dezenas ou centenas), métodos baseados em população podem esgotar o orçamento; ou quando uma solução provadamente ótima for necessária, pois os AGs não oferecem garantias de otimalidade.
Limitações e considerações
- Nenhuma garantia de encontrar o ótimo global; a qualidade da solução depende do tamanho da população, das escolhas de operadores e do número de gerações.
- Computacionalmente caro em relação a métodos baseados em gradiente em problemas suaves e de baixa dimensão — muitas avaliações de função são necessárias.
- Ajuste de hiperparâmetros (tamanho da população, taxa de cruzamento, taxa de mutação) é dependente do problema e frequentemente requer experimentação.
- A convergência prematura pode ocorrer se a pressão de seleção for muito alta ou a taxa de mutação for muito baixa, prendendo a busca em regiões subótimas.
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
- Não requer informação de gradiente — aplicável a objetivos caixa-preta, descontínuos ou não diferenciáveis.
- Lida naturalmente com espaços de busca combinatórios, de inteiros mistos e de permutações com codificação apropriada.
- Paralelizável por design: a população pode ser avaliada em paralelo, reduzindo o tempo de relógio.
- Robusto contra ótimos locais devido à diversidade da população e à exploração estocástica.
- Altamente extensível: operadores, codificações e esquemas de seleção podem ser personalizados para restrições específicas do domínio.
Aplicações
- Escalonamento job-shop e flow-shop em manufatura e logística
- Seleção de características e ajuste de hiperparâmetros em pipelines de aprendizado de máquina
- Otimização estrutural e de topologia em engenharia mecânica e civil
- Problemas do caixeiro viajante e de roteamento de veículos em pesquisa operacional
- Previsão de estrutura de proteínas e descoberta de drogas em bioinformática
- Busca de arquitetura de redes neurais e otimização de pesos
Como funciona
Como funciona
Gere uma população inicial de N soluções candidatas (cromossomos) aleatoriamente ou por semeadura heurística. Cada cromossomo codifica um ponto factível no espaço de decisão — strings binárias, vetores reais, permutações ou árvores, dependendo da representação do problema escolhida.
Calcule o aptidão f(x_i) para cada indivíduo na população usando a função objetivo (ou um substituto). A aptidão quantifica a qualidade da solução; maior aptidão significa uma solução melhor. Para problemas de minimização, a aptidão é frequentemente definida como o recíproco ou uma transformação da função de custo.
Fórmula
f(x_i), \quad i = 1, \ldots, N
Aplique um operador de seleção estocástico para escolher pais. A seleção por roleta (proporcional à aptidão) atribui a cada indivíduo uma probabilidade proporcional à sua aptidão. Seleção por torneio, seleção por ranking e elitismo são variantes comuns que controlam a pressão de seleção.
Fórmula
P(\text{select } x_i) = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)}Com probabilidade p_c (tipicamente 0.6–0.9), recombine pares de pais selecionados para produzir descendentes. Cruzamento de ponto único, ponto duplo ou uniforme trocam material genético entre os cromossomos dos pais, criando filhos que herdam traços de ambos. Este operador impulsiona a exploração de bons blocos de construção.
Com uma baixa probabilidade p_m (tipicamente 0.001–0.05 por gene), altere aleatoriamente genes individuais em cada cromossomo descendente. A mutação mantém a diversidade genética, previne a convergência prematura e garante que o algoritmo possa escapar de ótimos locais. A taxa de mutação é um parâmetro crítico ajustado ao problema.
Substitua a população atual pelos descendentes (substituição geracional) ou use atualizações de estado estável. Reavalie a aptidão e repita a partir da etapa de seleção até que um critério de parada seja atendido — número máximo de gerações, um limiar de aptidão ou nenhuma melhoria em um número definido de gerações.
Erros comuns
- Usar uma taxa de mutação muito alta reduz efetivamente o algoritmo a uma busca aleatória e destrói ganhos de aptidão acumulados.
- Ignorar o elitismo na estratégia de substituição pode fazer com que a melhor solução encontrada seja perdida entre as gerações.
- Aplicar operadores de cruzamento de valor real a problemas codificados em binário (ou vice-versa) quebra a codificação e produz descendentes infactíveis.
- Parar muito cedo — gerações insuficientes — é a razão mais comum para a baixa qualidade da solução na prática.
- Negligenciar o tratamento de restrições: cruzamento e mutação sem restrições frequentemente violam as restrições do problema; funções de penalidade ou operadores de reparo devem ser incorporados explicitamente.
Perguntas frequentes
Como um Algoritmo Genético Estocástico difere de um Algoritmo Genético padrão?
O rótulo 'estocástico' enfatiza que todos os operadores centrais — seleção, cruzamento e mutação — envolvem sorteios probabilísticos. O AG canônico introduzido por Holland é inerentemente estocástico. O rótulo é usado na literatura de simulação/otimização para distinguir de raras variantes determinísticas (por exemplo, crowding determinístico) e para esclarecer que o comportamento do algoritmo varia entre execuções devido à aleatoriedade.
Qual o tamanho da população?
Um ponto de partida comum é de 50 a 200 indivíduos para problemas de dimensão moderada. Populações maiores melhoram a diversidade e reduzem a convergência prematura, mas aumentam o custo computacional por geração. Existem regras práticas baseadas no comprimento do cromossomo (por exemplo, 10× o número de genes), mas o ajuste empírico ou a meta-otimização são frequentemente necessários.
Quando devo preferir Otimização por Enxame de Partículas ou Recozimento Simulado em vez de um Algoritmo Genético?
A Otimização por Enxame de Partículas (PSO) é frequentemente mais rápida em problemas contínuos de valor real porque explora informações de velocidade. O Recozimento Simulado (SA) é mais simples de implementar e pode ser eficaz para busca de trajetória de solução única. AGs são preferidos quando o espaço de busca é combinatório, quando o cruzamento recombina significativamente estruturas de solução, ou quando a diversidade da população é valiosa para paisagens multimodais.
O Algoritmo Genético Estocástico escala para problemas de alta dimensão?
O desempenho degrada em dimensões muito altas (centenas a milhares de variáveis) porque a população deve ser grande o suficiente para amostrar o espaço adequadamente. Variantes especializadas — como AGs de aprendizado de ligação, algoritmos de estimação de distribuição ou modelos de ilhas com migração — abordam a escalabilidade, mas adicionam complexidade.
Como lidar com restrições em um Algoritmo Genético?
Três estratégias principais são usadas: (1) funções de penalidade que reduzem a aptidão para violações de restrições; (2) operadores de reparo que projetam descendentes infactíveis de volta para a região factível; (3) codificações e operadores especializados que produzem apenas soluções factíveis por construção. Métodos baseados em penalidade são os mais fáceis de implementar, mas requerem calibração cuidadosa dos coeficientes de penalidade.
Métodos relacionados
Fontes
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.
ISBN: 978-0262581110Copiado.Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.
ISBN: 978-0201157673Copiado.