multiobjetivo-ermac-2

Prévia do material em texto

UTFPR
Introdução à Otimização Multiobjetivo - Métodos de
Escalarizações
V ERMAC - Encontro Regional de Matemática Aplicada e
Computacional
Angelo Aliano Filho e Helenice Florentino
Universidade Tecnológica Federal do Paraná
06/07 de Junho de 2018
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 1 / 89
UTFPR
Sumário
1 Método da Soma Ponderada
2 Método das Métricas Ponderadas
3 Método das Métricas Ponderadas Rotacionadas
4 Método da Métrica de Tchebycheff
5 Método do ε−Restrito
6 Método de Benson
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 2 / 89
UTFPR
Problema de Otimização Multiobjetivo
Formulação geral
Um Problema de Otimização Multiobjetivo (POM) tem um número
p > 1 de funções objetivos que devem ser minimizadas, sujeito a um
conjunto viável X ∈ Rn. A forma geral de um POM é
Minimize z = (f1(x), · · · , fp(x))
sujeito a x ∈ X = {x ∈ Rn : gj(x) ≤ 0, j = 1, · · · ,m}.
Suponhamos que os objetivos são conflituantes entre si, isto é, a
melhora do objetivo i acarreta a piora de pelo menos um outro
objetivo j 6= i
Focaremos nosso estudo em r = 2
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 3 / 89
UTFPR
Principais métodos de escalarizações
São métodos que têm em comum o fato de transformarem um POM
num problema escalar. Sob certas condições, a solução ótima do
problema escalar resulta em uma solução eficiente para o POM.
Métodos apresentados:
1 Soma Ponderada
2 Métricas Ponderadas
3 Métricas Ponderadas e Rotacionadas
4 Métrica de Tchebycheff com Ponderações
5 Métrica de Tchebycheff sem Ponderações
6 ε−Restrito
7 Benson
8 Non Inferior Set Estitation (NISE)
9 Simplex Bi-objetivo
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 4 / 89
UTFPR
Método da Soma Ponderada
Procedimento básico
Vários métodos foram apresentados em [1]. Para computar soluções
eficientes para um POM, resolvemos o problema escalar cuja função
objetivo é uma soma-ponderada dos p objetivos com pesos λk ≥ 0:
Minimize z =
p∑
k=1
λkfk(x)
sujeito a x ∈ X
(1)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 5 / 89
UTFPR
Método da Soma Ponderada
Teorema
Se λk > 0 para todo k = 1, · · · , p, então a solução do Problema (1) é
eficiente para o POM original.
Demonstração
Seja x∗ ∈ X uma solução ótima para o Problema (1). Suponha que x∗
não seja eficiente, logo existe uma solução x̄ ∈ X de modo que
fk(x̄) ≤ fk(x∗), k = 1, · · · , p e fi(x̄) < fi(x∗) para ao menos um
i ∈ {1, · · · , r}. Então,
p∑
k=1
λk · fk(x̄) <
p∑
k=1
λk · fk(x∗),
mas isto contradiz o fato de x∗ ser solução ótima de (1), logo x∗ é uma
solução eficiente para o POM.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 6 / 89
UTFPR
Método da Soma Ponderada
Teorema
Se λk > 0 para todo k = 1, · · · , p, então a solução do Problema (1) é
eficiente para o POM original.
Demonstração
Seja x∗ ∈ X uma solução ótima para o Problema (1). Suponha que x∗
não seja eficiente, logo existe uma solução x̄ ∈ X de modo que
fk(x̄) ≤ fk(x∗), k = 1, · · · , p e fi(x̄) < fi(x∗) para ao menos um
i ∈ {1, · · · , r}. Então,
p∑
k=1
λk · fk(x̄) <
p∑
k=1
λk · fk(x∗),
mas isto contradiz o fato de x∗ ser solução ótima de (1), logo x∗ é uma
solução eficiente para o POM.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 6 / 89
UTFPR
Método da Soma Ponderada
Teorema
Se o Problema (1) tem solução uma única x∗, então x∗ é eficiente para
λk ≥ 0.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 7 / 89
UTFPR
Método da Soma Ponderada
Demonstração
Seja x∗ a única solução do Problema (1). Suponha que ela não seja
eficiente, logo, existe uma outra solução fact́ıvel x̄ 6= x∗ de modo que
fk(x̄) ≤ fk(x∗), k = 1, · · · , r e fi(x̄) < fi(x∗) para ao menos um
i ∈ {1, · · · , r}. Como λk ≥ 0, temos que
p∑
k=1
λk · fk(x̄) ≤
p∑
k=1
λk · fk(x∗).
Como x∗ é solução única, podemos afirmar que
p∑
k=1
λk · fk(x∗) <
p∑
k=1
λk · fk(x̄),
mas isto contradiz a desigualdade imediatamente anterior, logo x∗ é
eficiente.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 8 / 89
UTFPR
Método da Soma Ponderada
z1
z2
Figura: Diferentes pontos não-dominados obtidos com o método da Soma
Ponderada em um POM não-convexo
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 9 / 89
UTFPR
Método da Soma Ponderada
z1
z2
Figura: Diferentes pontos não-dominados obtidos com o método da Soma
Ponderada em um POM não-convexo
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 10 / 89
UTFPR
Método da Soma Ponderada
Observações
Os teoremas anteriores afirmam que, a solução do problema (1) é
sempre eficiente se os pesos são todos positivos ou se a solução
do problema (1) é única, sem qualquer hipótese adicional
Se λk ≥ 0 para algum k, podemos ter soluções fracamente
eficientes caso não haja unicidade
Para problemas convexos, temos um importante resultado, dado a
seguir
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 11 / 89
UTFPR
Método da Soma Ponderada
Teorema
Se x∗ é uma solução eficiente para o problema multiobjetivo convexo,
então existe um vetor λ = (λ1, · · · , λp)T ≥ 0 tal que x∗ é solução do
Problema (1).
Demonstração
Ver: [3]
De acordo com este teorema, todas as soluções eficientes de um POM
convexo, podem ser calculadas pela Soma Ponderada
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 12 / 89
UTFPR
Método da Soma Ponderada
z1
z2
Figura: Todos pontos não-dominados obtidos com o método da Soma
Ponderada em um POM convexo
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 13 / 89
UTFPR
Método da Soma Ponderada
Normalização
Sendo f+k (x) e f
−
k (x) os valores de máximo e mı́nimo da função fk(x),
esta pode ser normalizada do seguinte modo:
f̄k(x) =
fk(x)− f−k (x)
f+k (x)− f
−
k (x)
.
Assim, o problema ponderado pode ser redefinido como:
Problema Ponderado Normalizado
Minimize z =
p∑
k=1
λkf̄k(x)
sujeito a x ∈ X
(2)
com
∑p
k=1 λk = 1 e λk ≥ 0.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 14 / 89
UTFPR
Método da Soma Ponderada
Exemplo
Minimize f1(x) = x1
Minimize f2(x) = 1 + x
2
2 − x1 − a sin(bπx1)
sujeito a 0 ≤ x1 ≤ 1, −2 ≤ x2 ≤ 2,
onde a e b são parâmetros que controlam a convexidade do problema
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 15 / 89
UTFPR
Método da Soma Ponderada
Forme então o seguinte problema:
Problema Ponderado
Minimize z = λ · x1 + (1− λ) · [1 + x22 − x1 − a sin(bπx1)]
sujeito a 0 ≤ x1 ≤ 1, −2 ≤ x2 ≤ 2,
Então resolva este problema para vários valores de λ ∈]0, 1[. A cada
problema resolvido, temos uma solução eficiente.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 16 / 89
UTFPR
Método da soma Ponderada
Exemplo
Usando as condições de primeira ordem, temos que:
∂z
∂x1
= 0
∂z
∂x0
= 0
=⇒
{
λ+ (1− λ)[−1− abπ cos(bπx1)] = 0
2(1− λ)x2 = 0
que fornece como ponto estacionário x∗ = (x∗1, x
∗
2) onde
x∗1 =
1
bπ
cos−1
[
1
abπ
(
λ
1− λ
− 1
)]
e x∗2 = 0
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 17 / 89
UTFPR
Método da Soma Ponderada
Exemplo
Para que x∗1 = 0 então λ = 0.620
Para que x∗1 = 1 então λ = 0.271
Para qualquer λ ∈ [0.271, 0.620], podemos achar a soluçãomı́nima
x∗1 usando o cálculo anterior
Para λ ∈ [0, 0.271] ou [0.620, 1], teremos uma das soluções
extremas: x∗1 = 0 ou 1.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 18 / 89
UTFPR
Método da Soma Ponderada
Exemplo
Para que x∗1 = 0 então λ = 0.620
Para que x∗1 = 1 então λ = 0.271
Para qualquer λ ∈ [0.271, 0.620], podemos achar a solução mı́nima
x∗1 usando o cálculo anterior
Para λ ∈ [0, 0.271] ou [0.620, 1], teremos uma das soluções
extremas: x∗1 = 0 ou 1.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 18 / 89
UTFPR
Método da Soma Ponderada
Exemplo
Calculando a matriz Hessiana e determinando a condição para que
x∗ seja mı́nimo, temos que sin(bπx∗1) ≥ 0, isto é, 2ib ≤ x
∗
1 ≤
(2i+1)
b ,
i = 1, 2, · · · .
Mas 0 ≤ x∗1 ≤ 1. Então a equação anterior fornece o valor de
mı́nimo da função ponderada.
Sendo b = 1 e a = 0.2, temos que
x∗1 =
1
π
cos−1
[
5
π
(
λ
1− λ
− 1
)]
e x∗2 = 0,
e será válida apenas para i = 0.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 19 / 89
UTFPR
Método da Soma Ponderada
Espaço objetivo deste problema é apresentado a seguir, com a = 0.2 e
b = 1, e 20 ponderações:
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: 10 pontos não-dominados determinados pelo método da Soma
ponderada
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 20 / 89
UTFPR
Método da Soma Ponderada
Espaço objetivo deste problema é apresentado a seguir, com a = 0.2 e
b = 1, e 40 ponderações:
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: 19 pontos não-dominados determinados pelo método da Soma
ponderada
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 21 / 89
UTFPR
Método da Soma Ponderada
Espaço objetivo deste problema é apresentado a seguir, com a = 0.2 e
b = 1, e 80 ponderações:
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: 35 pontos não-dominados determinados pelo método da Soma
ponderada
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 22 / 89
UTFPR
Método da Soma Ponderada
Vantagens
Simplicidade
Fácil de entender e implementar
POM convexo: garante gerar todas as soluções eficientes
Desvantagens
Uma distribuição uniforme dos pesos não geram pontos
não-dominados uniformemente distribúıdos
Diferentes pesos não necessariamente determinam diferentes
soluções eficientes
Não determina soluções eficientes cuja imagem estejam na parte
não-convexa da fronteira de Pareto
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 23 / 89
UTFPR
Método da Soma Ponderada
Vantagens
Simplicidade
Fácil de entender e implementar
POM convexo: garante gerar todas as soluções eficientes
Desvantagens
Uma distribuição uniforme dos pesos não geram pontos
não-dominados uniformemente distribúıdos
Diferentes pesos não necessariamente determinam diferentes
soluções eficientes
Não determina soluções eficientes cuja imagem estejam na parte
não-convexa da fronteira de Pareto
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 23 / 89
UTFPR
Método da Soma Ponderada
Para a = 0.1 e b = 3, como visto anteriormente, temos que
x∗1 =
1
3π
cos−1
[
1
0.3π
(
λ
1− λ
− 1
)]
e x∗2 = 0,
e
x∗1 =
2
3
+
1
3π
cos−1
[
1
0.3π
(
λ
1− λ
− 1
)]
e x∗2 = 0.
pois
2i
3
≤ x∗1 ≤
2i+ 1
3
.
Se i = 0, então 0 ≤ x∗1 ≤ 1/3
Se i = 1, então 2/3 ≤ x∗1 ≤ 1
então duas regiões na fronteira de Pareto são determinadas.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 24 / 89
UTFPR
Método da Soma Ponderada
Para qualquer λ, o menor x∗1 dentre estes dois é mı́nimo da função
ponderada
z = λ · x∗1 + (1− λ) · [1− x∗1 − 0.1 sin(3πx∗1)]
Para λ ∈ [0.054, 0.660], x∗1 pode ser determinado.
Se λ = 0.5, então x∗1 = 1/6 ou 5/6, z
∗ = 0.455, isto é, temos duas
soluções ótimas.
Assim, se λ ∈ [0.500, 0.660], temos x∗1 ∈ [5/6, 1]
Assim, se λ ∈ [0.054, 0.500], temos x∗1 ∈ [0, 1/6]
Note que para nenhum peso λ, uma solução eficiente x∗1 ∈]1/6, 5/6[
poderá ser determinada
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 25 / 89
UTFPR
Método da Soma Ponderada
−0.2 0.2 0.4 0.6 0.8 1.
f1(x)
−0.2
0.2
0.4
0.6
0.8
1.
f2(x)
0
Fronteira de Pareto
Figura: Método da Soma Ponderada determinando apenas os pontos
não-dominados da parte convexa da fronteira de Pareto
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 26 / 89
UTFPR
Método da Soma Ponderada
Exemplo
Considere o seguinte POM linear:
Maximize f1(x) = 5x1 + 3x2
Maximize f2(x) = 2x1 + 8x2
sujeito a x1 + 4x2 ≤ 100
3x1 + 2x2 ≤ 150
5x1 + 3x2 ≥ 200
x1, x2 ≥ 0
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 27 / 89
UTFPR
Método da Soma Ponderada
O espaço de decisão e de critério são exibidos a seguir
Figura: Espaço de decisão e de critério para o exemplo proposto
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 28 / 89
UTFPR
Método da Soma Ponderada
Veremos que neste exemplo, vários pesos produzem uma mesma
solução eficiente.
Normalize os objetivos, otimizando cada uma das funções. Isso dá
f−1 (x) = 200, f
+
1 (x) = 250, f
−
2 (x) = 80 e f
+
2 (x) = 200
Assim, as funções normalizadas são dadas por:
f̄1(x) =
1
10
x1 +
3
50
x2 e f̄2(x) =
1
60
x1 +
1
15
x2.
Forme o problema ponderado:
Maximize z = λ
(
1
10
x1 +
3
50
x2
)
+ (1− λ)
(
1
60
x1 +
1
15
x2
)
sujeito a x1 + 4x2 ≤ 100
3x1 + 2x2 ≤ 150
5x1 + 3x2 ≥ 200
x1, x2 ≥ 0
para λ ∈]0, 1[.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 29 / 89
UTFPR
Método da Soma Ponderada
Veremos que neste exemplo, vários pesos produzem uma mesma
solução eficiente.
Normalize os objetivos, otimizando cada uma das funções. Isso dá
f−1 (x) = 200, f
+
1 (x) = 250, f
−
2 (x) = 80 e f
+
2 (x) = 200
Assim, as funções normalizadas são dadas por:
f̄1(x) =
1
10
x1 +
3
50
x2 e f̄2(x) =
1
60
x1 +
1
15
x2.
Forme o problema ponderado:
Maximize z = λ
(
1
10
x1 +
3
50
x2
)
+ (1− λ)
(
1
60
x1 +
1
15
x2
)
sujeito a x1 + 4x2 ≤ 100
3x1 + 2x2 ≤ 150
5x1 + 3x2 ≥ 200
x1, x2 ≥ 0
para λ ∈]0, 1[.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 29 / 89
UTFPR
Método da Soma Ponderada
Vetor gradiente da função objetivo ponderada normalizada:
∇z =
(
λ
12
+
1
60
,− λ
150
+
1
15
)
Sua inclinação é
− λ
150
+ 1
15
λ
12
+ 1
60
, de modo que a inclinação do normal à
ele é
−λ
12
− 1
60
− λ
150
+ 1
15
Este normal tem inclinação −3/2 se λ = 25/28 ≈ 0.8929
Assim, se λ ∈ [0.8929, 1], solução eficiente x1 = (50, 0); se
λ ∈ [0, 0.8929], teremos outra solução eficiente, x2 = (40, 15); e se
λ = 0.8929, teremos o segmento unindo x1 e x2 como soluções.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 30 / 89
UTFPR
Método das Métricas Ponderadas
Em vez de usar uma soma ponderada dos objetivos, minimizamos na
norma lq a distância entre a solução fact́ıvel x ao ponto ideal z
∗.
Problema ponderado na norma lq
O problema
Minimize z =
(
q∑
k=1
λk · (fk(x)− z∗k)q
)1/q
sujeito a x ∈ X
(3)
onde 1 ≤ q <∞, com λk ≥ 0, minimiza a distância na métrica lq de x a
z∗
Observações:
se q = 1, temos o Método da soma Ponderada
se q = 2, temos a distância Euclidiana sendo minimizada, em
relação ao ponto de referência
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 31 / 89
UTFPR
Método das Métricas Ponderadas
Interpretação geométricaFigura: Contornos das normas ponderadas
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 32 / 89
UTFPR
Método das Métricas Ponderadas
Problema ponderado normalizado na norma lq
É conveniente utilizar o problema normalizado
Minimize z =
(
q∑
k=1
λk · (f̄(x)− z∗k)q
)1/q
sujeito a x ∈ X
onde 1 ≤ q <∞, λk ≥ 0 e
∑q
k=1 λk = 1
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 33 / 89
UTFPR
Método das Métricas Ponderadas
Resultado teórico:
Teorema
A solução do Problema (3) é de Pareto se
a solução for única ou
todos os pesos λk > 0
Demonstração
Ver [5]
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 34 / 89
UTFPR
Método das Métricas Ponderadas
Exemplo
Considere o problema
Minimize f1(x) = x1
Minimize f2(x) = 1 + x
2
2 − x1 − 0.1 sin(3πx1)
sujeito a 0 ≤ x1 ≤ 1, −2 ≤ x2 ≤ 2,
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 35 / 89
UTFPR
Método das Métricas Ponderadas
Problema ponderado na métrica l2
O problema na norma-2 é dado por:
Minimize z = λ · x21 + (1− λ) · [1 + x22 − x1 − 0.1 sin(3πx1)]2
sujeito a 0 ≤ x1 ≤ 1, −2 ≤ x2 ≤ 2,
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 36 / 89
UTFPR
Método das Métricas Ponderadas
O mı́nimo desta função corresponde a x∗2 = 0 e x
∗
1 satisfazendo a
seguinte equação:
λx∗1 − (1− λ)[1− x∗1 − 0.1 sin(3πx∗1)](1 + 0.3π cos(3πx∗1)) = 0.
Atribuindo 20 valores para λ uniformemente distribúıdos em [0, 1],
obtemos os seguintes pontos não-dominados
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 37 / 89
UTFPR
Método das Métricas Ponderadas
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 20 ponderações para o exemplo
com a métrica l2 (20 pontos)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 38 / 89
UTFPR
Método das Métricas Ponderadas
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 20 ponderações para o exemplo
com a métrica l1 (8 pontos)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 39 / 89
UTFPR
Método das Métricas Ponderadas
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 200 ponderações para o exemplo
com a métrica l1 (65 pontos)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 40 / 89
UTFPR
Método das Métricas Ponderadas
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 200 ponderações para o exemplo
com a métrica l2 (200 pontos)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 41 / 89
UTFPR
Método das Métricas Ponderadas Rotacionadas (caso
q = 2)
E, vez de usar diretamente as normas lq, podemos aplicar a norma
lq com uma arbitrária rotação do ponto z
∗
Digamos que o vetor objetivo rotacionado ponderado seja dado
por f̃(x), onde
f̃(x) =
[
cos θ − sin θ
sin θ cos θ
] [
f̄1(x)
f̄2(x)
]
,
onde θ é o ângulo da rotação
Então resolvemos o seguinte problema
Minimize z =
[
λ · (f̃1(x)− z∗1)q + (1− λ) · (f̃2(x)− z∗2)q
]1/q
sujeito a x ∈ X
onde 1 ≤ q <∞ e λ ≥ 0
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 42 / 89
UTFPR
Método das Métricas Ponderadas
Exemplo
Considere o problema novamente:
Minimize f1(x) = x1
Minimize f2(x) = 1 + x
2
2 − x1 − 0.1 sin(3πx1)
sujeito a 0 ≤ x1 ≤ 1, −2 ≤ x2 ≤ 2,
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 43 / 89
UTFPR
Método das Métricas Ponderadas
Problema ponderado na métrica l2
O problema na norma-2 rotacionado em um ângulo θ é dado por:
Minimize z = λ · [cos θf1(x) + sin θf2(x)]2+
+(1− λ) · [− sin θf1(x) + cos θf2(x)]2
sujeito a 0 ≤ x1 ≤ 1, −2 ≤ x2 ≤ 2,
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 44 / 89
UTFPR
Método das Métricas Ponderadas Rotacionadas
Fixamos θ = π/4 e damos 100 valores para λ:
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 100 ponderações para o exemplo
com a métrica l2 rotacionada em θ = π/4 (100 pontos)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 45 / 89
UTFPR
Método das Métricas Ponderadas Rotacionadas
Fixamos θ = π/6 e damos 100 valores para λ:
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 100 ponderações para o exemplo
com a métrica l2 rotacionada em θ = π/6 (100 pontos)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 46 / 89
UTFPR
Método das Métricas Ponderadas Rotacionadas
Fixamos λ = 0.1 e damos 100 valores para θ ∈ [0, π/2]:
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 100 ângulos para o exemplo com a
métrica l2 rotacionada (100 pontos)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 47 / 89
UTFPR
Método da Métrica de Tchebycheff
Quando q é grande, o problema de minimizar a soma (fk(x)− z∗k) se
reduz em minimizar o maior desvio. Esta métrica é denominada de
Tchebycheff (ou l∞) e o problema associado é definido como:
Problema de Tchebycheff Ponderado
Minimize z =
p
max
k=1
{
λk · (f̄(x)− z∗k)
}
sujeito a x ∈ X
(4)
onde λk ≥ 0 e
∑p
k=1 λk = 1 (supondo f normalizada)
Esta formulação é não linear, e pode ser linearizada da seguinte
maneira
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 48 / 89
UTFPR
Método da Métrica de Tchebycheff
Problema de Tchebycheff Ponderado - linearizado
Minimize z = α
sujeito a x ∈ X
λk · (f̄(x)− z∗k) ≤ α, k = 1, · · · , p
α ≥ 0,
(5)
onde λk ≥ 0 e
∑p
k=1 λk = 1
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 49 / 89
UTFPR
Método da Métrica de Tchebycheff
Contornos das métricas ponderadas: l1, l2 e l∞
Figura: Contornos da métrica l1 (a), l2 (b) e l∞ (c)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 50 / 89
UTFPR
Método da Métrica de Tchebycheff
Em geral, a métrica l∞ pode obter soluções fracamente eficientes; veja
a ilustração a seguir:
Figura: Ponto fracamente não-dominado (à esq.) e contornos da métrica l∞
aumentada
Porém, podemos construir a métrica de Tchebycheff aumentada, cujos
contornos são ilustrados na imagem à direita, e que impede a geração
de soluções fracamente dominadas
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 51 / 89
UTFPR
Método da Métrica de Tchebycheff
Figura: Contornos da métrica l∞ aumentada
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 52 / 89
UTFPR
Método da Métrica de Tchebycheff
Problema de Tchebycheff Ponderado Aumentado
Sua formulação é dada por:
Minimize z =
p
max
k=1
{
λk · (f̄(x)− z∗k)
}
+
p∑
k=1
ρk · f̄k(x)
sujeito a x ∈ X
(6)
onde λk ≥ 0, ρk ≥ 0,
∑p
k=1 λk = 1
e evita soluções eficientes fracamente dominadas
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 53 / 89
UTFPR
Método da Métrica de Tchebycheff
Problema de Tchebycheff Ponderado Aumentado Linearizado
Sua formulação linear equivalente é dada por:
Minimize z = α+
p∑
k=1
ρk · f̄k(x)
sujeito a x ∈ X
λk · (f̄(x)− z∗k) ≤ α, k = 1, · · · , p
α ≥ 0,
(7)
onde λk ≥ 0, ρk ≥ 0,
∑p
k=1 λk = 1. Conforme λk varia, diferentes
soluções eficientes são determinadas
Angelo e Helenice (UTFPR/UNESP)Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 54 / 89
UTFPR
Método da Métrica de Tchebycheff
Resultados teóricos importantes para o Problema de Tchebycheff (4)
Teorema
A solução do Problema de Tchebycheff (4) é fracamente ótima de
Pareto se λk > 0
Teorema
Se o Problema de Tchebycheff (4) tem única solução, então esta é
ótima de Pareto.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 55 / 89
UTFPR
Método da Métrica de Tchebycheff
Resultados teóricos importantes para o Problema de Tchebycheff (4)
Teorema
A solução do Problema de Tchebycheff (4) é fracamente ótima de
Pareto se λk > 0
Teorema
Se o Problema de Tchebycheff (4) tem única solução, então esta é
ótima de Pareto.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 55 / 89
UTFPR
Método da Métrica de Tchebycheff
A convexidade era uma hipótese exigida para as normas lp para
gerarmos todas as soluções eficientes; esta exigência não é necessária
para a métrica de Tchebycheff, como veremos a seguir:
Teorema
Seja x∗ ∈ X eficiente. Então existem λk > 0 tais que x∗ é solução do
Problema (4).
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 56 / 89
UTFPR
Método da Métrica de Tchebycheff
A convexidade era uma hipótese exigida para as normas lp para
gerarmos todas as soluções eficientes; esta exigência não é necessária
para a métrica de Tchebycheff, como veremos a seguir:
Teorema
Seja x∗ ∈ X eficiente. Então existem λk > 0 tais que x∗ é solução do
Problema (4).
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 56 / 89
UTFPR
Método da Métrica de Tchebycheff
Comentários
O Teorema anterior mostra uma vantagem imensa deste método:
pode determinar todas as soluções eficientes para um POM, sejam
elas na parte convexa e não-convexa da fronteira
Infelizmente, algumas soluções fracamente eficientes podem ser
determinadas por este método
Porém, a métrica de Tchebycheff Aumentada resolve esta
inconveniência
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 57 / 89
UTFPR
Método da Métrica de Tchebycheff
Resultado teórico para o Problema de Tchebycheff Aumentado (6) é
apresentado a seguir:
Teorema
Um vetor x∗ ∈ X é eficiente se, e somente se, existem λk > 0 e números
ρk > 0 tal que x
∗ é solução do Problema de Tchebycheff Aumentado
(6).
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 58 / 89
UTFPR
Método da Métrica de Tchebycheff
Resultado teórico para o Problema de Tchebycheff Aumentado (6) é
apresentado a seguir:
Teorema
Um vetor x∗ ∈ X é eficiente se, e somente se, existem λk > 0 e números
ρk > 0 tal que x
∗ é solução do Problema de Tchebycheff Aumentado
(6).
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 58 / 89
UTFPR
Método da Métrica de Tchebycheff
Vantagens
Garante encontrar todas soluções eficientes para um POM
Simples de ser implementado
Gera apenas uma variável decisória adicional
Desvantagens
Necessário normalizar os objetivos, i.e., conhecer o vetor utópico
Senśıvel com ρk e λk
Pode não determinar pontos não-dominados igualmente espaçados
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 59 / 89
UTFPR
Método da Métrica de Tchebycheff
Vantagens
Garante encontrar todas soluções eficientes para um POM
Simples de ser implementado
Gera apenas uma variável decisória adicional
Desvantagens
Necessário normalizar os objetivos, i.e., conhecer o vetor utópico
Senśıvel com ρk e λk
Pode não determinar pontos não-dominados igualmente espaçados
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 59 / 89
UTFPR
Método das Métricas Ponderadas
Exemplo
Considere o problema
Minimize f1(x) = x1
Minimize f2(x) = 1 + x
2
2 − x1 − 0.1 sin(3πx1)
sujeito a 0 ≤ x1 ≤ 1, −2 ≤ x2 ≤ 2,
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 60 / 89
UTFPR
Método das Métricas Ponderadas
Problema de Tchebycheff Aumentado e Linearizado
Resolvemos o seguinte problema:
Minimize z = α+ 10−3[x1 + 1 + x
2
2 − x1 − 0.1 sin(3πx1)]
sujeito a 0 ≤ x1 ≤ 1, −2 ≤ x2 ≤ 2,
λ · x1 ≤ α
(1− λ) · [1 + x22 − x1 − 0.1 sin(3πx1)] ≤ α
α ≥ 0,
pois o vetor de referência é z∗ = (0, 0).
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 61 / 89
UTFPR
Método da Métrica de Tchebycheff
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 20 ponderações para o exemplo
com a métrica de Tchebycheff (20 pontos)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 62 / 89
UTFPR
Método da Métrica de Tchebycheff
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 40 ponderações para o exemplo
com a métrica de Tchebycheff (40 pontos)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 63 / 89
UTFPR
Método da Métrica de Tchebycheff
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 80 ponderações para o exemplo
com a métrica de Tchebycheff (80 pontos)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 64 / 89
UTFPR
Método do ε−Restrito
Introduzido por [4], em 1971.
Uma das funções objetivo é selecionada para ser otimizada
As demais funções objetivo são convertidas em restrições, usando
limitantes superiores adequados
O problema restrito a ser resolvido é dado por:
Minimize z = fi(x)
sujeito a x ∈ X ,
fk(x) ≤ εk, k = 1, · · · , p, k 6= i,
(8)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 65 / 89
UTFPR
Método do ε−Restrito
Resultados teóricos:
Teorema
A solução ótima do Problema (9) é fracamente de Pareto.
Demonstração
Seja x∗ uma solução do Problema (9). Assuma que x∗ não seja
fracamente de Pareto. Então existe uma outra solução x̄ tal que
fj(x̄) < fj(x
∗) para todo j = 1, · · · , p. Isso significa que
fk(x̄) < fk(x
∗), k 6= i e que x̄ é fact́ıvel. Também, fi(x̄) < fi(x∗). Isso
é um absurdo, pois x∗ é ótima. Logo, x∗ é fracamente de Pareto.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 66 / 89
UTFPR
Método do ε−Restrito
Resultados teóricos:
Teorema
A solução ótima do Problema (9) é fracamente de Pareto.
Demonstração
Seja x∗ uma solução do Problema (9). Assuma que x∗ não seja
fracamente de Pareto. Então existe uma outra solução x̄ tal que
fj(x̄) < fj(x
∗) para todo j = 1, · · · , p. Isso significa que
fk(x̄) < fk(x
∗), k 6= i e que x̄ é fact́ıvel. Também, fi(x̄) < fi(x∗). Isso
é um absurdo, pois x∗ é ótima. Logo, x∗ é fracamente de Pareto.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 66 / 89
UTFPR
Método do ε−Restrito
Teorema
Um vetor x∗ é eficiente se, e somente se, é solução do Problema (9)
para todo i = 1, · · · , p e εk = fk(x∗), k 6= i.
Teorema
Se o Problema (9) tiver única solução, para uma dada solução x∗ ∈ X
fact́ıvel, εk = fk(x
∗) e para algum i = 1, · · · , p, i 6= k, então x∗ é
eficiente.
Demonstrações: ver [5].
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 67 / 89
UTFPR
Método do ε−Restrito
Teorema
Um vetor x∗ é eficiente se, e somente se, é solução do Problema (9)
para todo i = 1, · · · , p e εk = fk(x∗), k 6= i.
Teorema
Se o Problema (9) tiver única solução, para uma dada solução x∗ ∈ X
fact́ıvel, εk = fk(x
∗) e para algum i = 1, · · ·, p, i 6= k, então x∗ é
eficiente.
Demonstrações: ver [5].
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 67 / 89
UTFPR
Método do ε−Restrito
−0.2 0.2 0.4 0.6 0.8 1. 1.2
−0.2
0.2
0.4
0.6
0.8
1.
f1(x)
f2(x)
0
Figura: Pontos não-dominados determinados pelo ε−Restrito com i = 1
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 68 / 89
UTFPR
Método do ε−Restrito
−0.2 0.2 0.4 0.6 0.8 1. 1.2
f1(x)
−0.2
0.2
0.4
0.6
0.8
1.
f2(x)
0
Figura: Pontos não-dominados determinados pelo ε−Restrito com i = 1
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 69 / 89
UTFPR
Método do ε−Restrito
−0.2 0.2 0.4 0.6 0.8 1. 1.2
f1(x)
−0.2
0.2
0.4
0.6
0.8
1.
f2(x)
0
Figura: Pontos não-dominados determinados pelo ε−Restrito com i = 1
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 70 / 89
UTFPR
Método das Métricas Ponderadas
Exemplo
Considere o problema novamente:
Minimize f1(x) = x1
Minimize f2(x) = 1 + x
2
2 − x1 − 0.1 sin(3πx1)
sujeito a 0 ≤ x1 ≤ 1, −2 ≤ x2 ≤ 2,
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 71 / 89
UTFPR
Método das Métricas Ponderadas
Problema restrito com i = 1
O problema restrito será dado por:
Minimize z = x1
sujeito a 0 ≤ x1 ≤ 1,
−2 ≤ x2 ≤ 2,
1 + x22 − x1 − 0.1 sin(3πx1) ≤ ε
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 72 / 89
UTFPR
Método do ε−Restrito
Quais valores para ε atribuir?
Exemplo
Achamos os valores de máximo e mı́nimo da função f2(x) resolvendo os
seguintes problemas:
Minimize z = 1 + x22 − x1 − 0.1 sin(3πx1)
sujeito a 0 ≤ x1 ≤ 1,
−2 ≤ x2 ≤ 2,
cujo valor mı́nimo para f2 é ε
− = 0 e
Minimize z = x1
sujeito a 0 ≤ x1 ≤ 1,
−2 ≤ x2 ≤ 2,
cuja solução, avaliada em f2, é 1. Isso dá ε
+ = 1
Atribúımos então, valores para ε ∈= [ε−, ε+] = [0, 1]
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 73 / 89
UTFPR
Método do ε−Restrito
Quais valores para ε atribuir?
Exemplo
Achamos os valores de máximo e mı́nimo da função f2(x) resolvendo os
seguintes problemas:
Minimize z = 1 + x22 − x1 − 0.1 sin(3πx1)
sujeito a 0 ≤ x1 ≤ 1,
−2 ≤ x2 ≤ 2,
cujo valor mı́nimo para f2 é ε
− = 0 e
Minimize z = x1
sujeito a 0 ≤ x1 ≤ 1,
−2 ≤ x2 ≤ 2,
cuja solução, avaliada em f2, é 1. Isso dá ε
+ = 1
Atribúımos então, valores para ε ∈= [ε−, ε+] = [0, 1]
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 73 / 89
UTFPR
Método do ε−Restrito
50 atribuições para ε:
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 50 atribuições para ε para o
exemplo (50 soluções)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 74 / 89
UTFPR
Método do ε−Restrito
100 atribuições para ε:
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 50 atribuições para ε para o
exemplo (100 soluções)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 75 / 89
UTFPR
Método do ε−Restrito
Observação:
Para evitar que o problema restrito gere soluções fracamente eficientes,
convém utilizar o seguinte problema restrito modificado:
Minimize z = fi(x) + ρ ·
p∑
k=1
k 6=i
fk(x)
sujeito a x ∈ X ,
fk(x) ≤ εk, k = 1, · · · , p, k 6= i,
(9)
com ρ > 0, evita soluções fracamente eficientes.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 76 / 89
UTFPR
Método do ε−Restrito
Vantagens
Simplicidade
Fácil de entender e implementar
Determina todas as soluções eficientes para um POM
Desvantagens
Conhecimento dos intervalos de mı́nimo e máximo de cada função
objetivo
Pode gerar muitos problemas ociosos, i.e., como a mesma solução
em iterações anteriores
Dificuldade em estimar o tamanho de passo para se conseguir
sempre uma nova solução eficiente
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 77 / 89
UTFPR
Método do ε−Restrito
Vantagens
Simplicidade
Fácil de entender e implementar
Determina todas as soluções eficientes para um POM
Desvantagens
Conhecimento dos intervalos de mı́nimo e máximo de cada função
objetivo
Pode gerar muitos problemas ociosos, i.e., como a mesma solução
em iterações anteriores
Dificuldade em estimar o tamanho de passo para se conseguir
sempre uma nova solução eficiente
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 77 / 89
UTFPR
Método de Benson
Introduzido por [2], em 1978.
A ideia é escolher alguma solução fact́ıvel x0
Consideramos as variáveis desvios lk ≥ 0:
lk = fk(x
0)− fk(x).
O problema de Benson consiste em maximizar estes desvios
Este problema produz um x dominando x0, “puxando” x o mais
longe posśıvel de x0
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 78 / 89
UTFPR
Método de Benson
Problema de Benson
Maximize z =
p∑
k=1
lk
sujeito a x ∈ X ,
lk = fk(x
0)− fk(x), k = 1, · · · , p
(10)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 79 / 89
UTFPR
Método de Benson
Resultados teóricos:
Teorema
A solução fact́ıvel x0 fact́ıvel é eficiente, se e somente se, o valor ótimo
do Problema (10) é 0.
Proposição
Se o Problema (10) tem uma solução ótima (x∗, l∗) (e o valor ótimo é
finito), então x∗ é eficiente.
Teorema
Suponha que fk sejam convexas, e que X seja convexo. Se o Problema
(10) tem valor ótimo ilimitado então X ∗ = ∅.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 80 / 89
UTFPR
Método de Benson
Resultados teóricos:
Teorema
A solução fact́ıvel x0 fact́ıvel é eficiente, se e somente se, o valor ótimo
do Problema (10) é 0.
Proposição
Se o Problema (10) tem uma solução ótima (x∗, l∗) (e o valor ótimo é
finito), então x∗ é eficiente.
Teorema
Suponha que fk sejam convexas, e que X seja convexo. Se o Problema
(10) tem valor ótimo ilimitado então X ∗ = ∅.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 80 / 89
UTFPR
Método de Benson
Resultados teóricos:
Teorema
A solução fact́ıvel x0 fact́ıvel é eficiente, se e somente se, o valor ótimo
do Problema (10) é 0.
Proposição
Se o Problema (10) tem uma solução ótima (x∗, l∗) (e o valor ótimo é
finito), então x∗ é eficiente.
Teorema
Suponha que fk sejam convexas, e que X seja convexo. Se o Problema
(10) tem valor ótimo ilimitado então X ∗ = ∅.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 80 / 89
UTFPR
Método de Benson
−0.2 0.2 0.4 0.6 0.8 1.
f1(x)
−0.2
0.2
0.4
0.6
0.8
1.
f2(x)
0
f(x0)
f(x∗)
Figura: Interpretação geométrica do Problema (10)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 81 / 89
UTFPR
Método de Benson
Exemplo
Considere o problema:
Minimize f1(x) = x1
Minimize f2(x) = 1 + x
2
2 − x1 − 0.1 sin(3πx1)
sujeito a 0 ≤ x1 ≤ 1, −2 ≤ x2 ≤ 2,
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 82 / 89
UTFPR
Método de Benson
Forme então o seguinte problema de Benson:
Problema de Benson
Maximize z = l1 + l2
sujeito a 0 ≤ x1 ≤ 1, −2 ≤ x2 ≤ 2,
l1 = f1(x
0)− x1
l2 = f2(x
0)− [1 + x22 − x1 − 0.1 sin(3πx1)]
Então resolva este problema para vetores x0 admisśıveis (aleatórios). A
cada problema resolvido, temos uma solução eficiente.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 83 / 89
UTFPR
Método de Benson
Se x0 é talque z0 = f(x0) = (0.7, 0.8)T , o Problema (10) determina o
seguinte problema de Benson a ser resolvido:
Maximizez = l1 + l2
sujeito a 0 ≤ x1 ≤ 1, −2 ≤ x2 ≤ 2
l1 = 0.7− x1
l2 = 0.8− [1 + x22 − x1 − 0.1 sin(3πx1)]
cuja solução é dada por (x∗, l∗) = (0.16, 0.00, 0.53, 0.06) e
f(x∗) = (0.16, 0.73). Pelo Teorema anterior, x∗ = (0.16, 0) é uma
solução eficiente para este problema
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 84 / 89
UTFPR
Método de Benson
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z0 = (0.7, 0.8)
z∗ = (0.16, 0.73)
z1
z2
Figura: Ponto não-dominado obtido com a maximização do desvio em relação
a z0
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 85 / 89
UTFPR
Método de Benson
20 atribuições para x0:
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 20 atribuições para x0 (20
soluções)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 86 / 89
UTFPR
Método de Benson
40 atribuições para x0:
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 40 atribuições para x0 (40
soluções)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 87 / 89
UTFPR
Método de Benson
400 atribuições para x0:
0.2 0.4 0.6 0.8 1
0.2
0.4
0.6
0.8
1
z1
z2
Figura: Pontos não-dominados obtidos com 400 atribuições para x0 (400
soluções)
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 88 / 89
UTFPR
Método de Benson
Vantagens
Simplicidade
Fácil de entender e implementar
Determina soluções suportadas e não-suportadas
Desvantagens
Pode não gerar todas as soluções eficientes
Solução eficiente determinada depende fortemente de x0
Dificuldade em controlar um espaçamento uniforme para os pontos
obtidos
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 89 / 89
UTFPR
Método de Benson
Vantagens
Simplicidade
Fácil de entender e implementar
Determina soluções suportadas e não-suportadas
Desvantagens
Pode não gerar todas as soluções eficientes
Solução eficiente determinada depende fortemente de x0
Dificuldade em controlar um espaçamento uniforme para os pontos
obtidos
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 89 / 89
UTFPR
Aliano Filho, A., et al.
Novas extensões de técnicas de escalarizações no problema de corte
unidimensional inteiro multiobjetivo.
Benson, H. P.
Existence of efficient solutions for vector maximization problems.
Journal of Optimization Theory and Applications 26, 4 (1978),
569–580.
Benson, H. P.
Matthias ehrgott, multicriteria optimization , springer (2005) isbn
3-540-21398-8 323 pages.
European Journal of Operational Research 176, 3 (2007),
1961–1964.
Haimes, Y. Y., and Hall, W. A.
Multiobjectives in water resource systems analysis: The surrogate
worth trade off method.
Water Resources Research 10, 4 (1974), 615–624.
Hillermeier, C.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 89 / 89
UTFPR
Nonlinear multiobjective optimization: a generalized homotopy
approach, vol. 135.
Springer Science & Business Media, 2001.
Angelo e Helenice (UTFPR/UNESP) Introd. à Otimização Multiobjetivo 06/07 de Junho de 2018 89 / 89
	Método da Soma Ponderada
	Método das Métricas Ponderadas
	Método das Métricas Ponderadas Rotacionadas
	Método da Métrica de Tchebycheff
	Método do -Restrito
	Método de Benson