Ir para o conteúdo

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

O NSGA-II é um algoritmo genético evolutivo especializado em otimização multi-objetivo. É um dos samplers mais populares para problemas onde múltiplos objetivos conflitantes precisam ser otimizados simultaneamente.

Como Funciona

O NSGA-II utiliza uma população de soluções que evolui ao longo das gerações através de:

  1. Ordenação por Não-Dominância: Soluções são classificadas em fronts de Pareto
  2. Crowding Distance: Dentro de cada front, soluções mais isoladas são preferidas para manter diversidade
  3. Seleção por Torneio: Combinação de rank e crowding para seleção
  4. Crossover e Mutação: Operadores genéticos para gerar novas soluções
            ┌─────────────────────────────────────────────────┐
            │              NSGA-II: Ciclo                     │
            │                                                 │
            │   População     Seleção      Crossover/Mutação  │
            │       │            │               │            │
            │   ●●●●●●●  →  ▌▌▌▌▌▌▌  →    ○○○○○○○           │
            │       │            │               │            │
            │       └────────────┴───────────────┘            │
            │                    │                            │
            │               Nova Geração                      │
            │                    │                            │
            │           Ordenação por                         │
            │           Não-Dominância                        │
            │                    ▼                            │
            └─────────────────────────────────────────────────┘

Pontos Fortes e Fracos

Pontos Fortes

  • ✅ Excelente para problemas multi-objetivo (2-3 objetivos)
  • ✅ Mantém diversidade na Fronteira de Pareto
  • ✅ Suporte nativo a constraints
  • ✅ Escalável para populações grandes
  • ✅ Robusto a ótimos locais

Pontos Fracos

  • ❌ Requer mais avaliações que métodos Bayesianos
  • ❌ Desempenho diminui com muitos objetivos (>3)
  • ❌ Sensível a parâmetros de população e operadores
  • ❌ Convergência pode ser lenta em espaços grandes

Aplicabilidade à Otimização Semafórica

O NSGA-II é ideal para cenários onde:

  • Múltiplos objetivos: Minimizar atraso E maximizar fluxo
  • Trade-offs necessários: Entender compensações entre objetivos
  • Visualização da fronteira: Analisar opções antes de decidir
  • Constraints: Restrições de fila, velocidade mínima, etc.

Configuração no OptFlow

{
  "sampler": "NSGAIISampler",
  "sampler_params": {
    "population_size": 50,
    "mutation_prob": 0.05,
    "crossover_prob": 0.9
  },
  "objectives": [
    {"name": "Atraso", "formula": "\"Delay Time\"", "direction": "minimize"},
    {"name": "Fluxo", "formula": "\"Flow\"", "direction": "maximize"}
  ]
}

Parâmetros Importantes

Parâmetro Descrição Valor Típico
population_size Número de soluções por geração 50-100
mutation_prob Probabilidade de mutação 0.01-0.1
crossover_prob Probabilidade de crossover 0.8-0.95

Comparação com Outros Samplers

Aspecto NSGA-II TPE GPSampler
Multi-objetivo ✅ Nativo ⚠️ Adaptado ⚠️ Adaptado
Eficiência de amostragem ⚠️ Média ✅ Alta ✅ Alta
Constraints ✅ Nativo ✅ c-TPE ⚠️ Limitado
Fronteira de Pareto ✅ Excelente ⚠️ Aproximada ⚠️ Aproximada

Dicas de Uso

  1. Comece com população moderada: 50-100 soluções
  2. Use pelo menos 100 gerações: NSGA-II precisa de tempo para convergir
  3. Monitore a diversidade: Se a fronteira estiver "colapsando", aumente a população
  4. Combine com constraints: NSGA-II lida bem com restrições

Quando usar NSGA-II

Use NSGA-II quando você tem 2-3 objetivos conflitantes e quer visualizar toda a Fronteira de Pareto antes de escolher uma solução.

Próximos Passos