Escalando problemas de otimização multiobjetivo: Comparação de métodos

Já apresentei vários exemplos de codificação que implementam a otimização multiobjetivo. Nestes exemplos, implementei diferentes estratégias para buscar um ótimo multiobjetivo. Uma dessas estratégias foi baseada em escalar vários objetivos em uma única função objetivo usando pesos para cada função objetivo individual. Neste artigo, desejo fornecer uma explicação mais abrangente sobre os diferentes tipos de estratégias de escalarização.

Em problemas de otimização multiobjetivo, enfrentamos objetivos concorrentes. Não existe um único método padrão para resolver problemas de otimização multiobjetivo. Uma abordagem popular, no entanto, é escalar.

Visão geral das técnicas populares

Como já mencionei, as técnicas de escalarização são aplicadas para transformar um problema de otimização multiobjetivo de forma que apenas uma única função objetivo seja otimizada. Descobri que existem muitas técnicas para fazer isso. Neste artigo, apresento três deles:

1. Escalarização linear

2. Método de restrição Epsilon

3. Programação de Sen

Escalar vários objetivos com escalarização linear

Este método aplica fatores de ponderação para combinar funções objetivo concorrentes em uma única função objetivo. Os analistas devem definir ou monitorar os valores de peso, pois eles representam o peso do respectivo objetivo.

Eu descrevo melhor esta abordagem com uma formulação matemática da função objetivo de escala linear, conforme postado abaixo:

\min _{x\in X}\sum _{i=1}^{k}w_{i}f_{i}(x),
scalarizing with linear scalarization

Normalmente, eu gosto de definir a soma dos pesos igual a 100%. Isso torna mais fácil visualizar a ponderação relativa dos respectivos objetivos. Por favor, consulte meu artigo sobre otimização multiobjetiva com PuLP em Python para ver uma demonstração dessa abordagem.

Escalar vários objetivos com o método de restrição épsilon

Os modelos de restrição Epsilon converterão o problema em um problema de objetivo único, mantendo apenas uma função como função objetivo. As outras funções são modeladas como funções de restrição. Cada função deve atingir seus ótimos individuais em alguma extensão, conforme indicado pelo valor épsilon.

Novamente, eu descrevo melhor essa abordagem postando a notação matemática abaixo:

{\displaystyle {\begin{array}{ll}\min &f_{j}(x)\\{\text{s.t. }}&x\in X\\&f_{i}(x)\leq \epsilon _{i}{\text{ for }}i\in \{1,\ldots ,k\}\setminus \{j\},\end{array}}}
scalarizing with epsilon-constraint method

Quando aplico essa abordagem, geralmente resolvo cada objetivo separadamente primeiro. Assim, eu revelo os ótimos individuais de cada objetivo. Em seguida, construo a versão de restrição epsilo do problema. Na formulação do problema, eu defini o modelo para os ótimos individuais por pelo menos uma extensão definida.

Publiquei um artigo neste blog demonstrando a implementação dessa abordagem usando PuLP em Python para otimização multiobjetivo.

Escalando múltiplos objetivos com a programação de Sen

Esta abordagem normaliza cada função objetivo dividindo por meio de seus ótimos individuais absolutos antes da soma em uma única função objetivo conjunta. Ilustro essa abordagem usando notação matemática. Ver abaixo. Observe que, nestes exemplos, os objetivos 1 a r são objetivos de maximização, enquanto os objetivos r + 1 a s são objetivos de minimização.

{\displaystyle {\begin{array}{ll}\max &{\frac {\sum _{j=1}^{r}Z_{j}}{W_{j}}}-{\frac {\sum _{j=r+1}^{s}Z_{j}}{W_{r+1}}}\\{\text{s.t. }}&AX=b\\&X\geq 0,\end{array}}}, scalarizing with Sans programming

Outras abordagens populares para escalar

Muitos analistas da cadeia de suprimentos também aplicam uma técnica de escalarização apresentada por Wiezbicki, sobre a qual você pode ler mais aqui: https://www.sciencedirect.com/science/article/pii/0270025582900380?via%3Dihub

Leave a Reply

Deixe um comentário

O seu endereço de e-mail não será publicado.

Esse site utiliza o Akismet para reduzir spam. Aprenda como seus dados de comentários são processados.

Close

Meta