Recozimento Simulado Multiobjetivo (MOSA)
- Proposto por
- Serafini, P.; Czyzak, P. and Jaszkiewicz, A.
- Ano
- 1992–1998
- Tipo
- Metaheuristic / Pareto-based 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?
O Recozimento Simulado Multiobjetivo (MOSA) estende a meta-heurística clássica de recozimento simulado para problemas com duas ou mais funções objetivo conflitantes.
Em vez de convergir para um único ótimo, o MOSA explora o espaço de soluções estocasticamente e mantém um arquivo de soluções não dominadas (Pareto-ótimas), oferecendo aos tomadores de decisão uma fronteira de trade-off diversa, em vez de uma única resposta prescrita.
A intuição por trás do método
O recozimento simulado clássico imita o resfriamento controlado de metais para escapar de ótimos locais — aceitando ocasionalmente soluções piores em alta temperatura, e tornando-se mais seletivo à medida que a temperatura diminui. O MOSA aplica esse mesmo mecanismo de escape probabilístico em múltiplos objetivos simultaneamente. Quando uma solução candidata piora alguns objetivos, mas melhora outros, a lógica de dominância determina se ela entra no arquivo de Pareto. O cronograma de resfriamento reduz gradualmente a aleatoriedade, focando a busca perto da fronteira de Pareto. O resultado é uma aproximação da verdadeira fronteira de Pareto alcançada sem a necessidade de informações de gradiente ou suposições de convexidade.
História
O recozimento simulado foi introduzido por Kirkpatrick et al. em 1983. Serafini (1992) foi um dos primeiros a propor formalmente sua extensão para múltiplos objetivos. Czyzak e Jaszkiewicz (1998) desenvolveram o Recozimento Simulado de Pareto (PSA), que estabeleceu o arquivo de Pareto como a estrutura de saída central e forneceu a formulação do critério de aceitação amplamente adotada hoje. O MOSA tem sido aplicado desde então em projeto de engenharia, agendamento e logística.
Quando usar
Use o MOSA quando você enfrentar um problema de otimização com dois ou mais objetivos conflitantes e variáveis de decisão contínuas ou combinatórias, particularmente quando o cenário objetivo é não convexo, multimodal ou livre de gradiente. É bem adequado para problemas de agendamento, roteamento, projeto de engenharia e alocação de recursos, onde uma fronteira de trade-off explícita é mais útil do que um único agregado ponderado. Prefira o MOSA em vez do Monte Carlo puramente estocástico quando você precisa de otimização em vez de quantificação de incerteza. NÃO use o MOSA quando o problema tiver um único objetivo (o SA clássico é suficiente), quando a fronteira de Pareto deve ser encontrada exatamente (algoritmos exatos são melhores para problemas pequenos), quando o número de objetivos excede aproximadamente cinco (métodos baseados em hipervolume escalam melhor), ou quando a avaliação dos objetivos é extremamente cara por chamada (métodos baseados em substitutos são preferíveis).
Limitações e considerações
- A qualidade da solução e a cobertura da fronteira de Pareto são sensíveis à escolha da temperatura inicial, taxa de resfriamento e operador de vizinhança, exigindo ajuste específico do problema.
- A convergência para uma fronteira de Pareto de alta qualidade pode exigir muitas avaliações de objetivos, tornando-o lento para simulações de caixa preta caras.
- Manter e atualizar o arquivo de Pareto introduz sobrecarga e o arquivo pode crescer muito, aumentando os custos de memória e comparação.
- Ao contrário dos métodos baseados em população (por exemplo, NSGA-II), a natureza de trajetória única do MOSA básico pode produzir cobertura desigual da fronteira de Pareto.
- As garantias teóricas de convergência exigem um cronograma de resfriamento infinitamente lento, o que é impraticável; cronogramas finitos sacrificam a garantia de otimalidade.
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ções de gradiente e lida com cenários objetivos não convexos, descontínuos e multimodais.
- A aceitação probabilística de soluções inferiores permite o escape de fronteiras de Pareto locais que aprisionam abordagens puramente gulosas.
- Produz uma aproximação diversa da fronteira de Pareto completa em uma única execução, oferecendo aos tomadores de decisão opções explícitas de trade-off.
- A implementação é direta e o cronograma de resfriamento fornece um parâmetro intuitivo para ajustar o equilíbrio exploração-explotação.
- Aplicável a problemas de otimização contínua e combinatória com reformulação mínima.
Aplicações
- Agendamento de job-shop e flow-shop multiobjetivo (minimizando o makespan e a tardiness simultaneamente)
- Problemas de projeto e roteamento de redes com objetivos de custo e confiabilidade
- Otimização de projeto de engenharia (por exemplo, minimizando peso e tensão em componentes estruturais)
- Otimização de portfólio equilibrando retorno esperado e risco
- Planejamento de uso da terra e espacial com objetivos econômicos e ambientais concorrentes
- Alocação de recursos de saúde equilibrando custo, cobertura e qualidade do serviço
Como funciona
Como funciona
Gere uma solução inicial (aleatória ou heurística), defina uma temperatura inicial T_0 suficientemente alta para permitir ampla exploração, inicialize o arquivo de Pareto com quaisquer soluções não dominadas encontradas e defina os critérios de parada (número máximo de iterações ou um limite mínimo de temperatura).
Perturbe a solução atual usando um operador de vizinhança apropriado para a estrutura do problema (por exemplo, troca, inserção ou perturbação Gaussiana para variáveis contínuas) para produzir uma ou mais soluções vizinhas candidatas.
Avalie todas as funções objetivo para a solução vizinha candidata. Determine se ela domina, é dominada por, ou é não dominada em relação à solução atual e às soluções no arquivo de Pareto. Candidatos não dominados são adicionados ao arquivo; membros dominados do arquivo são removidos.
Aplique um critério de aceitação multiobjetivo. Se o vizinho for não dominado em relação à solução atual, ele é aceito. Se for dominado, ainda pode ser aceito com probabilidade P = exp(−ΔF / T), onde ΔF agrega a deterioração do objetivo, permitindo o escape de fronteiras de Pareto locais.
Fórmula
P(\text{accept}) = \exp\!\left(-\frac{\Delta f}{T}\right)Reduza a temperatura de acordo com um cronograma de resfriamento, comumente geométrico: T_{k+1} = α · T_k com α ∈ (0.8, 0.99). Temperaturas mais baixas restringem a aceitação de movimentos inferiores, intensificando progressivamente a busca em regiões promissoras da fronteira de Pareto.
Fórmula
T_{k+1} = \alpha \cdot T_k, \quad \alpha \in (0,1)Retorne o arquivo de Pareto final como resultado. Pós-processe para podar soluções dominadas que possam ter se acumulado e apresente o arquivo como uma aproximação discreta da fronteira Pareto-ótima para seleção pelo tomador de decisão.
Erros comuns
- Definir a temperatura inicial muito baixa causa convergência prematura para uma região local da fronteira de Pareto; sempre calibre T_0 para que a taxa de aceitação inicial seja em torno de 70–90%.
- Usar uma taxa de resfriamento α muito próxima de 1.0 torna a execução proibitivamente longa; muito próxima de 0 causa convergência rápida antes que a fronteira de Pareto seja adequadamente explorada.
- Definir ΔF para a probabilidade de aceitação com uma soma ingênua de diferenças de objetivos mistura escalas incomparáveis — normalize cada objetivo antes da agregação.
- Negligenciar a remoção periódica de soluções dominadas do arquivo o infla e degrada a qualidade da saída final.
- Avaliar o sucesso em uma única execução é enganoso dada a variação estocástica; sempre agregue os resultados de múltiplas execuções independentes.
Perguntas frequentes
Como o MOSA difere do NSGA-II?
O NSGA-II é um algoritmo evolucionário baseado em população que evolui um conjunto de soluções simultaneamente usando cruzamento, mutação e ordenação não dominada. O MOSA é um método baseado em trajetória que explora uma solução por vez usando movimentos probabilísticos. O MOSA tende a ser mais simples de implementar e funciona bem para problemas combinatórios, enquanto o NSGA-II geralmente fornece melhor cobertura da fronteira de Pareto para problemas contínuos e escala de forma mais previsível.
Como devo definir a temperatura inicial T_0?
Uma heurística comum é executar uma fase preliminar curta e escolher T_0 de modo que aproximadamente 80% dos movimentos vizinhos aleatórios sejam aceitos. Isso garante uma ampla exploração no início. A calibração específica do problema é aconselhável porque a escala de temperatura apropriada depende da magnitude das diferenças da função objetivo.
O MOSA pode lidar com mais de dois objetivos?
Sim, mas o desempenho degrada à medida que o número de objetivos aumenta. O custo de gerenciamento do arquivo de Pareto aumenta, e a fração de soluções não dominadas cresce rapidamente, tornando o critério de aceitação menos discriminatório. Para problemas com mais de quatro ou cinco objetivos, métodos baseados em indicadores de hipervolume ou baseados em decomposição (por exemplo, MOEA/D) são geralmente preferidos.
Como sei quando parar o algoritmo?
Critérios de parada comuns incluem atingir uma temperatura mínima, esgotar um orçamento máximo de iterações ou não observar melhoria no indicador de hipervolume do arquivo de Pareto ao longo de um número especificado de iterações. Na prática, comparar a qualidade do arquivo em múltiplas execuções com diferentes orçamentos de iteração é uma maneira confiável de diagnosticar a convergência.
O MOSA é adequado para modelos de simulação caros?
Geralmente não, sem modificação. Cada iteração requer pelo menos uma avaliação da função objetivo, e o MOSA normalmente precisa de milhares de iterações para uma boa aproximação da fronteira de Pareto. Quando cada avaliação envolve uma simulação custosa, versões do MOSA assistidas por substitutos (usando metamodelos para aproximar objetivos) são preferíveis.
Métodos relacionados
Fontes
Czyzak, P., Jaszkiewicz, A. (1998). Pareto simulated annealing — a metaheuristic technique for multiple-objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 7(1), 34–47.
Abrir referência DOICopiado.Serafini, P. (1992). Simulated annealing for multi-objective optimization problems. In Proceedings of the Tenth International Conference on Multiple Criteria Decision Making, Taipei, Taiwan, pp. 87–96.
Abrir referência da publicaçãoCopiado.