Algoritmo Genético Multiobjetivo (MOGA) — Busca Evolucionária por Soluções Ótimas de Pareto
- Proposto por
- Schaffer, J. D. (early MOGA); Goldberg, D. E. (GA foundations)
- Ano
- 1984
- Tipo
- Population-based evolutionary optimizer
- 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?
Um Algoritmo Genético Multiobjetivo (MOGA) é um método de computação evolucionária que desenvolve uma população de soluções candidatas em direção a uma fronteira ótima de Pareto, otimizando simultaneamente duas ou mais funções objetivo conflitantes.
Ele evita colapsar os trade-offs em uma única pontuação, produzindo, em vez disso, um conjunto de soluções não dominadas para o tomador de decisão escolher.
A intuição por trás do método
Imagine gerar sucessivas gerações de projetos candidatos, onde apenas as soluções que não são claramente superadas em todos os objetivos sobrevivem e se reproduzem. Ao longo de muitas gerações, a população converge para uma fronteira dos melhores trade-offs possíveis — nenhuma solução nesta fronteira de Pareto pode melhorar em um objetivo sem piorar outro. MOGAs utilizam operações genéticas — seleção, cruzamento e mutação — para explorar essa fronteira eficientemente, mesmo em espaços de busca de alta dimensão, não convexos ou descontínuos, onde os métodos clássicos de gradiente falham.
História
Algoritmos genéticos multiobjetivo surgiram com o Algoritmo Genético Avaliado por Vetor (VEGA) de Schaffer em 1984, o primeiro GA a lidar explicitamente com múltiplos objetivos. O livro de Goldberg de 1989 formalizou a classificação baseada em Pareto como a estratégia de atribuição de aptidão principiada. O campo amadureceu rapidamente com o MOGA de Fonseca e Fleming (1993), o NSGA de Srinivas e Deb (1994), e o marcante NSGA-II (Deb et al., 2002), que se tornou o benchmark padrão do campo e permanece o algoritmo evolucionário multiobjetivo mais amplamente citado.
Quando usar
Use MOGA quando um problema tiver dois ou mais objetivos conflitantes e nenhuma solução ótima única existir — projeto de engenharia, configuração de cadeia de suprimentos, otimização de portfólio e planejamento ambiental são domínios típicos. Ele é adequado para paisagens de objetivos não convexas, multimodais ou de caixa preta, onde métodos baseados em gradiente não podem ser aplicados. NÃO o use quando um único objetivo bem definido for suficiente (use um GA padrão ou programação matemática em vez disso), quando a avaliação da população for computacionalmente proibitiva e substitutos não estiverem disponíveis, quando os objetivos puderem ser legitimamente agregados por uma soma ponderada conhecida sem perda de informação, ou quando um pequeno conjunto viável permitir enumeração exaustiva.
Limitações e considerações
- O custo computacional escala com o tamanho da população e o número de avaliações de função; cada avaliação de simulações complexas pode ser cara.
- A convergência para a verdadeira fronteira de Pareto não é garantida — os resultados são aproximações heurísticas sensíveis às escolhas de hiperparâmetros (tamanho da população, taxa de cruzamento, taxa de mutação).
- O desempenho degrada à medida que o número de objetivos cresce além de três ou quatro (a otimização multiobjetivo requer algoritmos especializados como NSGA-III ou MOEA/D).
- Requer ajuste cuidadoso dos operadores genéticos e manutenção da diversidade para evitar convergência prematura ou cobertura deficiente da fronteira.
- Não fornece uma única solução recomendada — a seleção final da fronteira de Pareto ainda requer julgamentos de valor ou uma regra de decisão secundária.
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
- Produz um conjunto diversificado de soluções ótimas de Pareto em uma única execução, oferecendo aos tomadores de decisão opções explícitas de trade-off em vez de uma única resposta.
- Funciona em paisagens de objetivos não convexas, descontínuas e multimodais sem exigir gradientes ou estrutura matemática específica do problema.
- Inerentemente baseado em população, tornando-o fácil de paralelizar em núcleos ou sistemas distribuídos.
- A codificação flexível permite variáveis contínuas, inteiros, strings binárias e permutações dentro do mesmo framework.
- Bem suportado por bibliotecas de software maduras (DEAP, pymoo, jMetal) e décadas de evidências de benchmark.
Aplicações
- Otimização de projeto de engenharia — minimizando simultaneamente peso, custo e tensão em componentes estruturais.
- Cadeia de suprimentos e logística — equilibrando custo, tempo de entrega e emissões de carbono em configurações de rede.
- Política ambiental e energética — otimizando portfólios de energia renovável para custo, confiabilidade e emissões.
- Projeto de processos farmacêuticos e químicos — maximizando rendimento e pureza enquanto minimiza o tempo de reação.
- Ajuste de hiperparâmetros de aprendizado de máquina — trocando precisão do modelo por tempo de treinamento ou interpretabilidade.
- Planejamento urbano e transporte — otimizando redes de rotas para cobertura, tempo de viagem e custo de infraestrutura.
Como funciona
Como funciona
Gere uma população inicial de N soluções candidatas (cromossomos) aleatoriamente ou usando heurísticas de domínio, codificando cada solução como um vetor de variáveis de decisão. Defina k funções objetivo f1(x), f2(x), ..., fk(x) a serem minimizadas ou maximizadas simultaneamente.
Avalie todas as k funções objetivo para cada indivíduo na população. A aptidão reflete tanto a qualidade da solução em relação aos objetivos quanto a diversidade de cobertura no espaço objetivo.
Classifique os indivíduos por não-dominação: uma solução x domina y se for pelo menos tão boa em todos os objetivos e estritamente melhor em pelo menos um. Identifique a fronteira não dominada (candidatos à fronteira de Pareto) e atribua maior prioridade de seleção a indivíduos menos dominados. Métricas de diversidade, como a distância de aglomeração (crowding distance), evitam o agrupamento em uma região estreita da fronteira.
Aplique seleção (por exemplo, seleção por torneio) para favorecer indivíduos de classificação mais alta, depois aplique cruzamento para combinar pares de pais e mutação para introduzir variação. Mecanismos de elitismo preservam as melhores soluções não dominadas encontradas ao longo das gerações.
Repita a avaliação de aptidão, classificação e reprodução por um número predefinido de gerações ou até que os critérios de convergência sejam atendidos. O conjunto final não dominado aproxima a fronteira ótima de Pareto, apresentando ao tomador de decisão um espectro de soluções ótimas de trade-off.
Erros comuns
- Tratar todas as soluções na fronteira de Pareto como igualmente válidas sem envolver especialistas do domínio para fazer a seleção final do trade-off pode levar a escolhas arbitrárias ou mal justificadas.
- Usar uma população muito pequena produz frentes esparsas e não representativas; uma população muito grande inflaciona o cálculo sem benefício proporcional.
- Ignorar o tratamento de restrições — soluções inviáveis devem ser penalizadas ou reparadas explicitamente; não fazer isso distorce a busca em direção a regiões inviáveis.
- Aplicar MOGA a problemas com mais de quatro objetivos sem mudar para um algoritmo multiobjetivo resulta em frentes desordenadas e pouco informativas, onde quase todas as soluções são não dominadas.
- Relatar apenas a fronteira de Pareto final sem diagnósticos de convergência (hipervolume ao longo das gerações) impossibilita avaliar se o algoritmo realmente convergiu.
Perguntas frequentes
Como o MOGA difere de executar um GA de objetivo único com uma soma ponderada de objetivos?
Uma abordagem de soma ponderada colapsa todos os objetivos em um escalar usando pesos pré-atribuídos, produzindo uma única solução dependente desses pesos. O MOGA produz simultaneamente uma fronteira inteira de soluções não dominadas sem exigir a especificação de pesos antecipadamente, permitindo que o tomador de decisão inspecione os trade-offs e escolha posteriormente.
O que é a fronteira de Pareto e por que ela é importante?
A fronteira de Pareto é o conjunto de soluções onde a melhoria de qualquer objetivo único necessariamente piora pelo menos um outro. Ela representa o panorama completo dos trade-offs alcançáveis. Os tomadores de decisão podem inspecionar essa fronteira para entender o quanto um objetivo deve ser sacrificado para ganhar em outro.
Quantos objetivos o MOGA pode lidar efetivamente?
Variantes padrão do MOGA, como o NSGA-II, funcionam bem para dois ou três objetivos. Acima de quatro objetivos, a proporção de soluções não dominadas cresce rapidamente (a maldição da dimensionalidade no espaço objetivo), tornando a fronteira de Pareto grande e a pressão de seleção fraca. Algoritmos multiobjetivo (NSGA-III, MOEA/D, IBEA) são recomendados para quatro ou mais objetivos.
Qual critério de parada devo usar?
Critérios comuns incluem um número fixo de avaliações de função, um número máximo de gerações ou a convergência do indicador de hipervolume — o volume do espaço objetivo dominado pela aproximação atual da fronteira de Pareto — ao longo de gerações sucessivas. Monitorar o crescimento do hipervolume é a abordagem mais fundamentada.
O MOGA pode lidar com restrições?
Sim, através de técnicas de tratamento de restrições: funções de penalidade que degradam a aptidão de soluções inviáveis, seleção por torneio de viabilidade (soluções viáveis sempre superam as inviáveis na seleção), ou operadores de reparo que projetam soluções inviáveis de volta para a região viável. A escolha afeta o comportamento de convergência e deve ser deliberada.
Métodos relacionados
Fontes
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.
ISBN: 9780201157673Copiado.Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
Abrir referência DOICopiado.