Ir para o conteúdo

NSGA-III (Non-dominated Sorting Genetic Algorithm III)

O NSGA-III é uma evolução do NSGA-II, projetado especificamente para problemas de otimização com muitos objetivos (3 ou mais). Utiliza pontos de referência para manter a diversidade da fronteira de Pareto em espaços de alta dimensão.

Como Funciona

O NSGA-III introduz melhorias chave sobre o NSGA-II:

  1. Pontos de Referência: Define uma grade de pontos no espaço objetivo
  2. Associação de Soluções: Cada solução é associada ao ponto de referência mais próximo
  3. Niching: Soluções são selecionadas para manter uma distribuição uniforme
  4. Preservação de Diversidade: Evita o "colapso" da fronteira em dimensões altas
                    Objetivo 3
                        ▲
                       /│\
                      / │ \
                     /  │  \
                    /   │   \    ● Soluções
                   /  ★ │ ★  \   ★ Pontos de Referência
                  /   ●●│●    \
                 /   ★  │  ★   \
                /       │       \
               ─────────┼─────────►  Objetivo 1
                        │
                    Objetivo 2

Pontos Fortes e Fracos

Pontos Fortes

  • ✅ Excelente para problemas com muitos objetivos (3+)
  • ✅ Mantém diversidade em espaços de alta dimensão
  • ✅ Suporte nativo a constraints
  • ✅ Fronteira de Pareto bem distribuída
  • ✅ Escalável para 10+ objetivos

Pontos Fracos

  • ❌ Mais complexo de configurar que NSGA-II
  • ❌ Requer definição de pontos de referência
  • ❌ Pode ser excessivo para apenas 2 objetivos
  • ❌ Requer mais avaliações que métodos Bayesianos

Aplicabilidade à Otimização Semafórica

O NSGA-III é recomendado quando:

  • 3+ objetivos: Atraso, fluxo, emissões, segurança
  • Trade-offs complexos: Múltiplas dimensões de desempenho
  • Análise abrangente: Entender todas as opções antes de decidir
  • Stakeholders múltiplos: Diferentes prioridades a considerar

Exemplo: 3 Objetivos

{
  "sampler": "NSGAIIISampler",
  "objectives": [
    {"name": "Atraso", "formula": "\"Delay Time\"", "direction": "minimize"},
    {"name": "Fluxo", "formula": "\"Flow\"", "direction": "maximize"},
    {"name": "Emissões", "formula": "\"CO2 Emissions\"", "direction": "minimize"}
  ]
}

Configuração no OptFlow

{
  "sampler": "NSGAIIISampler",
  "sampler_params": {
    "population_size": 100
  },
  "objectives": [
    {"name": "Atraso", "formula": "\"Delay Time\"", "direction": "minimize"},
    {"name": "Fluxo", "formula": "\"Flow\"", "direction": "maximize"},
    {"name": "Paradas", "formula": "\"Number of Stops\"", "direction": "minimize"}
  ]
}

Parâmetros

Parâmetro Descrição Valor Típico
population_size Número de soluções por geração 100-200

Pontos de Referência

O OptFlow configura automaticamente os pontos de referência com base no número de objetivos. Não é necessário especificá-los manualmente.

Comparação NSGA-II vs NSGA-III

Aspecto NSGA-II NSGA-III
Objetivos ideais 2-3 3+
Mecanismo de diversidade Crowding distance Reference points
Complexidade Menor Maior
Distribuição em alta dimensão ⚠️ Degrada ✅ Mantém
Uso recomendado Casos comuns Problemas complexos

Quando Escolher NSGA-III

Cenário Sampler Recomendado
2 objetivos simples NSGA-II
2 objetivos com análise detalhada NSGA-II
3 objetivos NSGA-III
4+ objetivos NSGA-III
Restrições críticas NSGA-II ou NSGA-III

Dicas de Uso

  1. Use apenas quando necessário: Para 2 objetivos, NSGA-II é suficiente
  2. Aumente a população: Problemas com mais objetivos precisam de mais soluções
  3. Planeje mais iterações: A convergência é mais lenta com mais objetivos
  4. Analise trade-offs: Use visualizações para entender as compensações

Custo Computacional

Otimização com muitos objetivos requer significativamente mais avaliações. Considere usar Filtro de Demanda para acelerar cada simulação.

Próximos Passos