23/02/14
Otimização Multiobjetivo
Carlos Henggeler Antunes
Maria João Alves b,c
a
a,c
Deptº de Engª Electrotécnica e de Computadores, Universidade
de Coimbra
b
Faculdade de Economia, Universidade de Coimbra
c INESC Coimbra
([email protected]; [email protected] )
5ª Escola Luso-Brasileira de Computação Evolutiva, LNCC,
Petrópolis, 18-21 Fevereiro 2014
Introdução
Problemas reais são multidimensionais …
n  … não existe uma única medida do que é
melhor.
n  A complexidade dos problemas reais que
surgem nas sociedades tecnológicas
modernas é caracterizada pela existência de
múltiplas perspectivas de análise, reflectindo
aspectos económicos, sociais, políticos,
físicos, de engenharia, administrativos,
psicológicos, éticos, estéticos, etc., num dado
contexto.
n 
2
1
23/02/14
n 
n 
Não existe uma solução admissível que garanta o
melhor valor em todos os aspectos de avaliação
Ao considerar explicitamente os diferentes aspectos da
realidade
• os modelos matemáticos,
• a percepção dos problemas por parte dos
decisores
tornam-se mais realistas.
Alargam a gama de soluções em análise: descobrir um
leque de soluções com diferentes características (não
apenas uma solução óptima), estabelecendo distintos
compromissos entre os aspectos de avaliação
3
n 
Problemas multicritério
multiatributo (definição enumerativa): as acções
potenciais, em número finito, são explicitamente
conhecidas a-priori, bem como os respectivos
índices de mérito avaliados segundo os vários
critérios
n  multiobjectivo (definição analítica): as acções
potenciais formam um contínuo, definidas
implicitamente por um conjunto de restrições;
n 
n 
O espaço de decisão é mapeado no espaço dos
objectivos, no qual cada alternativa tem como
representação um vector, cujos componentes
são os correspondentes valores de cada função
4
objectivo (optimização vectorial)
2
23/02/14
A tomada de decisões neste tipo de problemas
complexos não pode ser reduzida à procura da
solução ótima de uma única função objectivo
(por exº, a eficiência do ponto de vista
económico medida por um qualquer indicador).
n  Solução ótima (melhor valor admissível para
uma única função objectivo) ⇐ solução não
dominada (não existe outra solução
admissível que melhore simultaneamente todas
as FO - a melhoria numa FO é alcançada à
custa da degradação do valor de pelo menos
uma das outras FO)
n 
5
n 
n 
Não existindo um ponto que otimize simultaneamente
todas as funções objectivo a simples comparação
entre soluções não dominadas não fornece qualquer
informação na procura de uma solução não dominada
que constitua uma solução final do problema
multiobjectivo.
Duas soluções não dominadas são incomparáveis
através da ordem natural ≥.
A ordenação completa do conjunto de soluções não
dominadas pressupõe a intervenção de uma
relação de preferências
que reflete a estrutura de preferências do decisor
n 
6
3
23/02/14
n 
n 
Num problema mono-objectivo a pesquisa da solução
ótima é puramente técnica:
• a melhor solução está implícita no modelo,
• cabe ao algoritmo de otimização a sua
descoberta,
• não há lugar à tomada de decisões.
Num problema MO é necessário fazer intervir no
processo de pesquisa
• meios técnicos de calcular soluções não
dominadas
• informação sobre as preferências do decisor.
7
n 
n 
A estrutura de preferências do decisor representa um
conjunto de opiniões, valores, convicções e
perspectivas da realidade, que configuram um modelo
pessoal da realidade sobre o qual se apoia para avaliar
diferentes possibilidades de acções potenciais
Não é possível classificar uma solução como boa ou
má apenas com referência ao modelo matemático e às
técnicas de resolução:
• a qualidade de uma decisão é influenciada pelos
aspectos organizacionais, políticos, culturais, etc.,
subjacentes ao processo de decisão.
8
4
23/02/14
n 
n 
n 
n 
Problema multiobjetivo:
escolha de entre os elementos do conjunto de
soluções não dominadas (geralmente infinito), de uma
que constitua a uma solução de compromisso
aceitável pelo decisor tendo em atenção suas
preferências, que podem evoluir ao longo do processo
de tomada de decisões.
O processo de decisão é uma entidade dinâmica,
constituída por ciclos iterativos de
• geração de ações potenciais,
• avaliação,
• interpretação de informação,
• alterações de valores,
• aprendizagem, e
• adaptação de preferências
9
A consideração de modelos multiobjectivo
- reflecte melhor uma realidade complexa e mal estruturada,
- possibilita a exploração de uma gama mais lata de
soluções alternativas.
A heterogeneidade de objectivos faz surgir problemas
específicos resultantes da:
- conflitualidade entre as FO, dado não haver uma
solução que optimize simultaneamente todas as FO;
- incomensurabilidade entre as FO, que não podem ser
reduzidas a uma unidade de medida comum (por ex.
monetária);
- incerteza, devido ao carácter insuficiente e/ou impreciso
do conhecimento e da informação de preferências do decisor
numa realidade multidimensional.
10
5
23/02/14
n 
n 
n 
As técnicas de modelação e otimização matemática são adequadas
para o cálculo de soluções não dominadas .
É necessário incorporar no processo de decisão aspectos qualitativos
relacionados com as preferências e julgamentos subjetivos do
decisor.
Uma boa decisão deve ser tal que
n 
n 
n 
n 
não exista outra ação potencial que seja melhor em alguns aspectos e
não pior em todos os aspectos em consideração
uma proposta final deve ser escolhida no universo das soluções não
dominadas
necessidade de estabelecer equilíbrios ou compromissos entre os
critérios
solução de compromisso.
n 
alcance de metas satisfatórias para o decisor
n 
maximize uma função valor,
n 
n 
solução de compromisso satisfatória.
a melhor decisão é a que oferece o maior valor
11
Solução satisfatória:
limitações das capacidades cognitivas do ser humano ⇒
racionalidade limitada ("bounded rationality"),
• racionalidade de satisfação ("satisficing rationality")
em detrimento de uma
• racionalidade de optimização ("optimizing rationality").
n 
n 
n 
Não é necessariamente uma falha humana em situações de
escolha que deva ser corrigida,
n  é muitas vezes uma forma de inteligência que deve ser
refinada, e não ignorada, pelas metodologias de apoio à
decisão.
Papel activo
n  a informação não é dada ao decisor sem lhe requerer
qualquer intervenção,
n  obriga-o a obtê-la por meio de um processo iterativo de
exploração, observação e reconhecimento de padrões.
12
6
23/02/14
Métodos de apoio à decisão MO
n 
n 
Não há articulação de preferências do decisor (métodos
geradores).
A articulação de preferências do decisor é feita:
* a-priori (métodos de função valor, ou utilidade)
* progressivamente (métodos interativos)
n  Métodos interativos
• etapas de cálculo,
• etapas de diálogo:
em que o decisor é chamado a expressar as suas
preferências perante soluções que lhe são propostas, até se
atingir uma condição de paragem (variável de método para
método);
n 
n 
A intervenção do decisor é usada para guiar o processo
interativo de decisão, reduzindo o âmbito da pesquisa
13
Métodos interativos
n  Face aos métodos geradores
- reduzem o esforço computacional,
- limitam o esforço cognitivo imposto ao decisor.
n 
Face aos métodos baseados em funções valor
- evitam a extração prévia de informação de preferências para
formular a função valor
- permitem a aprendizagem e a evolução de preferências à medida
que vai sendo reunida informação.
n 
Interatividade
n 
n 
n 
n 
oferecer ao decisor um ambiente operacional que suscite a
exploração, a reflexão, a emergência de novas intuições,
permitir ao decisor compreender com mais profundidade o
problema de decisão em causa,
contribuir para moldar e fazer evoluir as preferências ao
decisor no sentido de guiar o processo de pesquisa,
centrar o processo de pesquisa nas regiões onde se
localizam as soluções que o decisor julga mais interessantes.
7
23/02/14
n 
n 
n 
Aprendizagem
n  aumento do conhecimento disponível,
n  sobretudo aperfeiçoamento das capacidades do decisor de
modo a fazer um uso adequado desse conhecimento.
Tendência de deslocação da importância de
n  produção de decisões (MCDM - "Multiple Criteria Decision Making")
n  para o apoio à decisão (MCDA - "Multiple Criteria Decision Aid").
Métodos
- apoiar o decisor fornecendo-lhe informações de melhor
qualidade,
- dar a possibilidade de fazer evoluir a sua estrutura de
preferências confrontando-a com as propostas geradas pelos
métodos de modo a aumentar a sua compreensão do problema
15
n 
n 
Solução de compromisso satisfatória
• solução não dominada,
• associado um dado compromisso entre as FO,
• FO assumem valores satisfatórios para o decisor
de tal modo que a solução é aceitável como solução final do
processo de decisão.
Qual o significado de uma solução final ?
resultado da análise deve ser usado não como prescrição
definitiva, mas como referência ou como suporte material para
tomar decisões no sentido de encontrar melhores planos de
acção.
16
8
23/02/14
Formulação e Definições
Problema de programação linear com objetivos múltiplos
max f1(x) = c1 x
max f2(x) = c2 x
...
max fp(x) = cp x
s. a x ∈ X≡{x ∈ ℜn : x ≥ 0, Ax=b, b ∈ ℜm}
Ou:
n 
"Max" f (x) = C x
s. a x ∈ X
C = matriz dos objetivos , cujas linhas são os vectores ck (coeficientes da
função objectivo fk).
A = matriz dos coeficientes tecnológicos (mxn)
b = vector dos termos independentes (recursos disponíveis ou requerimentos)
17
n 
n 
Em programação mono-objetivo o espaço de decisão x ∈ X
é mapeado em ℜ
Em PMO o espaço de decisão é mapeado num espaço dos
objetivos p-dimensional
F={f (x) ∈ ℜp : x ∈ X}
n 
n 
n 
Cada alternativa potencial x ∈ X tem como representação
um vector f(x)=(f1(x),f2(x),...,fp(x)) cujos componentes
são os valores de cada FO para esse ponto da região
admissível.
Em geral, não existe uma solução admissível x ∈ X que
optimize simultaneamente todas as funções objetivo.
De um ponto de vista operacional, "Max" representa a
operação de determinar soluções eficientes.
18
9
23/02/14
n 
n 
n 
n 
Solução ótima ⇐ solução eficiente.
Uma solução admissível para um problema MO
diz-se eficiente sse não existir outra solução
admissível que melhore o valor de uma FO,
sem piorar o valor de, pelo menos, outra FO.
Uma solução x' ∈ X é eficiente sse não existe
uma outra solução x ∈ X tal que fk(x) ≥ fk(x’)
para todo o k=1,...,p, sendo a desigualdade
estrita para pelo menos um k, fk(x) > fk(x’).
XE representa o conjunto das soluções
eficientes.
19
n 
O ponto z = f(x) no espaço das funções
objectivo é não dominado (não inferior) sse
x ∈ XE, ou seja FE = {z = f(x) ∈ F : x ∈ XE }
n 
Espaço das funções objetivo: não dominância
n 
Espaço das variáveis de decisão: eficiência
n 
A imagem de uma solução eficiente é uma
solução não dominada
20
10
23/02/14
xn
fp
z'=(f 1 (x' ),..., fk (x' ),..., fp (x' ))
x'
x1
xj
f1
fk
21
n 
n 
n 
n 
Uma solução admissível para um problema
multiobjectivo diz-se fracamente eficiente sse não
existir outra solução admissível que melhore
estritamente o valor de todas as funções objetivo.
Uma solução x' ∈ X é fracamente eficiente sse não
existe uma outra solução x ∈ X tal que fk(x) > fk(x’)
para todo o k (k=1,...,p).
XFE representa o conjunto das soluções fracamente
eficientes.
O ponto z = f(x) no espaço das funções objetivo é
fracamente não dominado sse x ∈ XFE, ou seja
FFE = {z = f(x) ∈ F : x ∈ XFE }
22
11
23/02/14
max f1(x) =
x1 +
x2
max f2(x) = - 4 x1 + 3 x2
s. a
x∈X
x2
D(7,6)
C(4,5)
E(11,5)
F(12,4)
B(2,3)
X
G(13,2)
A(1,1)
H(10,1)
x1
23
n 
Solução ideal (ou ponto utopia) z*= (z1*, z2*, ...zp*)
otimizaria simultaneamente todas as funções objectivo ⇒
componentes são o ótimo de cada FO na região admissível,
quando otimizadas separadamente.
n 
n 
n 
Em geral, a solução ideal não pertence à região admissível
embora cada (z1*, z2*, ...zp*) seja individualmente alcançável.
A solução ideal é por vezes usada como o ponto de referência
(inatingível) do decisor em funções escalarizantes que
representam uma distância a minimizar para determinar uma
solução eficiente de compromisso.
Embora se possa definir sempre a solução ideal z* no espaço
dos objetivos, nem sempre existe a respectiva imagem no
espaço de decisão ⇒ pode não existir x* tal que z*=f(x*)
24
12
23/02/14
n 
Tabela de óptimos individuais ("pay-off")
organiza os valores dos objectivos para cada solução não dominada
resultante da otimização separada de cada função objectivo na
região admissível X.
n 
n 
As componentes da solução ideal são obtidas na diagonal da tabela de
ótimos individuais.
Pode definir-se a partir da tabela de óptimos individuais a solução anti-ideal
(ponto nadir), selecionando em cada linha o pior valor que a correspondente
função objetivo assume
n 
n 
n 
pretende representar o mínimo da função objetivo fk(x) na região eficiente.
É apenas um mínimo "conveniente" (pela facilidade da sua determinação) que
pode ser diferente (superior) do mínimo real na região eficiente.
A tabela de óptimos individuais pode não ser definida unicamente se
existirem óptimos alternativos eficientes para alguma função objetivo.
n 
A solução anti-ideal não será também unicamente definida.
n 
A solução ideal continua a sê-lo.
25
PROCESSOS DE ESCALARIZAÇÃO
n 
n 
n 
Transformação do problema multiobjetivo num problema de
otimização de uma função escalar substituta
n  cuja otimização conduz a uma solução eficiente do problema
multiobjetivo,
n  incluindo parâmetros de informação das preferências do
decisor.
Propriedades objetivas:
n  devem gerar apenas soluções eficientes;
n  devem poder gerar todas as soluções eficientes;
n  devem ser independentes de soluções não eficientes.
Propriedades subjetivas:
n  o esforço computacional envolvido não deve ser muito
grande;
n  os parâmetros de preferência devem ter uma interpretação
simples.
26
13
23/02/14
n 
Significado das funções escalarizantes:
mero artifício técnico para agregar
temporariamente os diversos objectivos e
gerar soluções não dominadas a propor ao
decisor (sem qualquer preocupação em
reflectirem uma expressão das suas
preferências);
n  representação analítica das preferências do
decisor.
n 
27
n 
Optimização de uma função objetivo
restringindo as outras
Função substituta: uma das funções
objetivo (a que se atribui mais importância)
Limitações inferiores nos outros p-1 objetivos:
restrições (níveis mínimos que está disposto a
aceitar)
max fi (x) = ci x
s. a fk (x) = ck x ≥ ek k=1,...,p , k≠i
x∈X
28
14
23/02/14
f1
x2
A
B
f1
1
E
C
f2
D x1
29
n 
n 
n 
Teorema: Se x* ∈ X for solução única para o
problema escalar para algum i, então x* é uma
solução eficiente para o PLMO.
Optimização da função substituta
n  solução eficiente do PLMO original desde que:
n  a região admissível reduzida seja não vazia (o que
pode não acontecer se os níveis mínimos ek forem
demasiado severos)
n  não existam ótimos alternativos da função objectivo
selecionada
n  Se existirem ótimos alternativos, apenas garantia de
pontos fracamente eficientes.
Variável dual associada à restrição correspondente a fk(x):
taxa de compromisso local entre fi e fk na solução
ótima do problema escalar
30
15
23/02/14
n 
n 
n 
n 
n 
n 
o 
o 
Simples de compreender pelos decisores: atitude de dar mais
importância a uma função objetivo e aceitando limitações
inferiores para as outras.
Escolha da função pode revelar-se difícil em muitos problemas
Fixação da função a otimizar durante todo o processo torna o
método pouco flexível.
Resultados demasiado dependentes da função selecionada.
Possível obter todos os pontos da fronteira não dominada,
quer sejam ou não pontos extremos da região admissível.
Informação de preferências associada:
• informação intercritérios
escolher função objetivo a optimizar;
• informação intracritérios
imposição de níveis mínimos para as outras funções objetivo.
31
n 
Soma ponderada das funções objetivo
max { λ1f1(x) + λ2f2(x) +...+ λpfp(x) }
s. a x ∈ X
λ ∈ Λ0
Conjunto de pesos admissível
Λ 0 ≡{λ : λ ∈ ℜp, Σ λk=1, λk ≥ 0, k=1,2,...,p}
Λ ≡ {λ : λ ∈ ℜp, Σ λk=1, λk > 0, k=1,2,...,p}
(interior de Λ)
n  Função bilinear definida em XxΛ.
n 
Fixando um conjunto de pesos ⇒ função linear
escalar ponderada das p funções objetivo, a
otimizar em X.
32
16
23/02/14
n 
n 
Teorema: x* ∈ X é uma solução básica
eficiente para o PLMO sse for uma solução ótima
para o problema escalar soma ponderada, para
um vector de pesos λ*∈ Λ.
Se λ* tiver alguma componente igual a zero
apenas há a garantia de pontos fracamente
eficientes.
33
n 
n 
Quadro simplex multiobjetivo inicial:
A
|
I
|
b
-C
|
0
|
0
Em relação à base B é transformado em:
B-1 N
|
B-1
| B-1 b
-CB B-1 N
| - CN CB B-1
| CB B-1 b
A = [ B , N] ; C = [ CB , CN ].
n 
n 
Matriz dos custos reduzidos associada à base B
Wa= CB B-1 N -CN.
Ba é uma base eficiente sse o sistema
{λT Wa ≥ 0, λ ∈ Λ} for coerente.
34
17
23/02/14
A representação gráfica do conjunto de pesos λ que
conduz a uma solução básica eficiente pode ser obtida
através da decomposição do diagrama paramétrico /
espaço dos pesos Λ.
n  Quadro simplex multiobjetivo
- solução básica eficiente para o PLMO
- λ correspondente definido por λTW≥0
n  wkj da matriz dos custos reduzidos W:
- taxa de variação marginal da função objetivo fk(x)
devido à introdução de uma unidade da variável não
básica xj na base.
n  Coluna de W correspondente a uma variável não básica
eficiente ⇒ tendência de variação unitária das funções
objetivo ao longo da respectiva aresta eficiente.
n 
35
n 
n 
Região de indiferença: conjunto de pesos
correspondente a uma solução básica eficiente (onde
{λTW≥0, λ ∈ Λ} é coerente).
Todas as combinações de pesos nessa região conduzem
à mesma solução eficiente.
36
18
23/02/14
Fronteira comum a 2 regiões de indiferença ⇒ as
respectivas soluções básicas eficientes estão ligadas por
uma aresta eficiente, correspondente à introdução na
base de uma variável não básica eficiente.
n 
n 
n 
Um ponto λ ∈ Λ pertence a várias regiões de indiferença
⇒ estas correspondem a soluções localizadas na mesma
face eficiente.
Regiões de indiferença dependem
n  das ordens de grandeza relativas dos valores das FO
(comprimento relativo dos gradientes),
n  geometria da região admissível.
Área da região de indiferença
n  medida da robustez da solução face à variação dos
pesos.
38
19
23/02/14
n 
n 
n 
n 
n 
o 
Fácil de ser explicada aos decisores, captando a atitude
de expressar o grau de importância que atribui a cada
função objectivo.
Informação de grande dificuldade para o decisor
(embora aparentemente simples).
Não há garantia de que as soluções encontradas estejam
de acordo com as preferências subjacentes à
especificação dos pesos.
Só é possível obter pontos extremos da fronteira não
dominada.
Informação de preferências associada:
• informação intercritérios
coeficientes de importância relativa (pesos) para as
funções objetivo.
39
n 
Minimização de uma distância a um
ponto de referência
Solução eficiente admissível que esteja tão perto quanto
possível (segundo uma dada métrica) das aspirações do
decisor.
n 
Usando uma métrica Lp e tomando a solução ideal
como ponto de referência:
min || z* - f(x) ||p
s. a x ∈ X
ou, com uma métrica Lp ponderada
min λ || z* - f(x) ||p
s. a x ∈ X
λ∈Λ
40
20
23/02/14
n 
n 
n 
p=1: todos os desvios do ponto de referência são
tomados em consideração na proporção directa da sua
grandeza.
2<p<∞: maiores desvios vão tendo cada vez mais
importância,
p=∞: apenas o maior desvio é tido em conta.
41
n 
Seja x0 solução deste problema. Considerando o "pior
caso“, i.e., maior diferença entre as componentes dos
vectores z* e f(x0) através da métrica L∞ (Tchebycheff)
min
x∈X
max
k=1,...,p
[ zk* - fk(x) ]
tem como solução x0 sse x0 e v0 forem solução do
problema linear:
min v
s. a v ≥ zk* - fk(x)
k=1,...,p
x∈X
v≥0
(se o ponto de referência usado zr não verificar zr≥fk(x)
em X, então v ∈ ℜ).
42
21
23/02/14
n 
n 
Em PLMO apenas resultam problemas escalares lineares
usando as métricas L1 ou L∞.
Métrica L∞ ponderada
min
x∈X
n 
n 
max
λk [ zk* - fk(x) ]
k=1,...,p
zk* = ponto de referência (arbitrário, que pode não
ser a solução ideal)
λ ∈ Λ0 é um vector de ponderação.
43
n 
Para garantir que as soluções obtidas são eficientes (e
não apenas fracamente eficientes) pode usar-se a
métrica L∞ (ponderada) aumentada:
min
x∈X
n 
{ max
k=1,...,p
λk [zk* - fk(x) ] } + ε [ zk* - fk(x) ]
O 2º termo é uma perturbação, com ε >0 suficientemente
pequeno, de modo a assegurar a eficiência da solução.
min
s. a
v + ε [ zk* - fk(x) ]
v ≥ zk* - fk(x)
k=1,...,p
x∈X
44
22
23/02/14
f2
z*
z2 *
4 5º
∞
z2
z1
z1 *
f1
45
z2
L1
Minimização da
distância a z*
segundo a
métrica L1:
z*
z2*
Z
•
A
z1*
(Ponto A)
z1
L2
z2
Minimização da
distância a z*
segundo a
métrica L2:
(Ponto B)
z*
z2*
Z
90°
B
z1*
z1
23
23/02/14
z2
Minimização da
distância a z*
segundo a
métrica L∞:
L∞
z*
z2*
45°
Z
C
•
(Ponto C)
z1*
z1
z2
1
z −z
2
λ
∞
= max λi z1i − zi2
dv λ1
=
dh λ2
€
€
n 
n 
n 
n 
o 
o 
λ
L∞
z*
z 2*
i
dh
Z
dv
D
z1*
z1
Teorema: Se x* ∈ X é uma solução para o problema de
Tchebycheff (ponderado) aumentado para algum ponto
de referência, então x* é uma solução eficiente para o
PLMO.
Minimização do "desconforto" de obter uma solução não
dominada de compromisso z0 em vez do ponto ideal (ou
outro ponto de referência) z*.
Possível obter todos os pontos da fronteira não
dominada (quer sejam ou não pontos extremos da
região admissível).
Informação de preferências associada:
• informação intracritérios:
estabelecimento de pontos de referência;
• informação intercritérios:
coeficientes de ponderação da métrica L∞.
48
24
23/02/14
MÉTODOS INTERATIVOS
n 
Etapas básicas:
a) inicialização - estabelecimento automático de informação de
preferências inicial, calibração de parâmetros de terminação,
etc.;
b) preparação - incorporação da informação de preferências nos
parâmetros de preferência da função escalar substituta, que
agrega as várias FO numa única dimensão, a usar na nova fase
de cálculo;
c) cálculo - determinação de uma ou mais soluções eficientes,
através da optimização de uma função escalar substituta, que
serão propostas à avaliação do decisor;
d) diálogo - apresentação da proposta e recolha da informação
de preferências fornecida pelo decisor face à proposta;
e) paragem - de acordo com uma dada regra de terminação, que
pode ser apenas o decisor declarar-se satisfeito com a
informação obtida
49
Inicialização
Preparação
Cálculo
Diálogo
Paragem
50
25
23/02/14
n 
o 
o 
o 
o 
Interatividade
n  dar ao decisor o papel central e condutor do processo
interativo de decisão
n  o método deve desempenhar um papel ativo nesta
convergência mútua
diálogo dinâmico (ajustado às diversas fases do processo
de decisão),
simples (não exigindo demasiada informação ou
desnecessariamente complicada)
positivo (requerendo informação sobretudo sobre o que
pretende melhorar e não sobre o que aceita piorar)
incluir mecanismos de divergência (possibilitando a
exploração de soluções numa dada vizinhança).
51
Concepções básicas para o papel da interatividade:
n 
Orientada para a procura
n  estrutura de preferências pré-existente e estável
(representada por uma função valor implícita)
n  coerência com esta função ao longo da utilização da
metodologia, respondendo de forma determinística às
questões colocadas
n  razoável impor a convergência matemática do método
interativo
n  a convergência é garantida e controlada pelo método
n  o objetivo da interação é a procura de uma proposta
ótima (que não depende da evolução do processo
interativo) face à estrutura de preferências.
A estrutura de preferências é assim "descoberta" durante
o processo.
52
26
23/02/14
Orientada para a aprendizagem
n  recusada a assumpção de que existe uma estrutura
de preferências pré-existente e estável com a qual o
decisor é coerente
n  as preferências do decisor podem ser parcialmente
instáveis e conflituosas
n  o objectivo da interação é a aprendizagem das
preferências (clarificação do que, na perspectiva do
decisor, possa ser uma solução satisfatória)
n  a convergência não é garantida e é controlada pelo
decisor fazendo então sentido falar em "convergência
psicológica" (significando a identificação de uma
solução eficiente como satisfatória graças à
informação entretanto recolhida).
n  o processo termina com uma solução de compromisso
satisfatória de acordo com a informação disponível e
a vontade do decisor quando não parecer possível a
emergência de novas intuições sobre o problema.
A convergência deve ser o resultado da interação entre o
53
decisor e o método.
n 
n 
n 
Divisão do trabalho entre o decisor e o
computador
Potenciam essa diferenciação de tarefas pela
capacidade de
n 
n 
n 
orientar o esforço computacional para as regiões
onde se localizam as soluções que melhor
correspondem à estrutura de preferências do decisor,
acomodar correcções de percurso devidas à evolução
da própria estrutura de preferências à medida que a
informação reunida faz emergir novas pistas e
intuições.
O futuro da programação multiobjectivo está na
sua aplicação interactiva ! (Steuer)
54
27
23/02/14
n 
Críticas
n 
n 
n 
n 
n 
a estrutura de preferências do decisor não está
fundada em investigações empíricas (French),
assumpção demasiado forte: as escolhas do decisor
estão sempre de acordo com uma função valor
implícita,
ancoragem: o decisor fica preso às primeiras soluções
que lhe são propostas, manifestando dificuldade ou
receio em preferir outras,
incapacidade de reconhecer uma resposta como
sendo um erro em relação às assumpções prévias
sobre as preferências ou uma resposta aleatória face
ao método usado.
carácter local da informação de preferências
requerida.
55
n 
Categorização dos métodos interativos
n 
Estratégia de redução do âmbito da pesquisa (explícita
ou implicitamente):
-
n 
redução da região admissível;
redução do espaço dos pesos ;
contração do cone dos gradientes das FO;
pesquisa direcional.
Tipo de função escalar substituta:
- otimização de uma FO
- soma ponderada das FO;
- minimização de uma distância a um ponto de referência.
n 
Possibilidade de o decisor intervir para solicitar a
realização de uma dada função em qualquer momento
do processo de decisão ou ser obrigado a uma sequência
pré-determinada de fases de cálculo e de diálogo:
- não estruturados;
- estruturados.
56
28
23/02/14
Estas classificações
n 
não são mutuamente exclusivas
n 
n 
por exº, há métodos que combinam diferentes
estratégias de redução do âmbito da pesquisa e
técnicas de cálculo de soluções eficientes;
não são exaustivas: há métodos que é difícil
englobar
n 
por exº, adaptações de algoritmos de direcção
admissível ou de planos de corte em programação
não linear.
57
f2
A
F
B
N
I
C
D
f1
58
29
23/02/14
MÉTODO STEM
n 
n 
n 
n 
n 
n 
Redução da região admissível.
Fase de decisão: quantidades que está disposto a sacrificar
nas funções objetivo cujos valores considera satisfatórios de
modo a melhorar as restantes.
Fase de cálculo: minimização de uma distância ponderada de
Tchebycheff à solução ideal.
É apresentada ao decisor a solução de compromisso calculada
em cada iteração minimizando a distância de Tchebycheff à
solução ideal.
Se os valores das funções objetivo são considerados
satisfatórios, o processo termina.
Caso contrário, o decisor deve especificar quais pretende
relaxar, e de que quantidade, por forma a melhorar os outros
objetivos.
59
n 
Passo 1
Otimização de cada função objectivo
Construção da tabela de óptimos individuais.
n 
Passo 2
“Calibração” dos pesos a usar na fase de
cálculo da iteração h
maior peso aos objetivos com maiores variações
relativas.
n  factor de normalização (usando a norma L2) dos
gradientes das funções objetivo.
n 
60
30
23/02/14
n 
Conjunto S:
índices das funções objetivo que serão
relaxadas na próxima iteração (de acordo com
as indicações do decisor, ao considerar os
respectivos valores satisfatórios).
n 
No início S=ø e X(1)≡X.
n 
n 
n 
Passo 3
Pesos que definem a métrica ponderada L∞
Os pesos das funções objetivo cujos valores são
considerados satisfatórios (que são permitidos ser
relaxados) são nulos.
61
n 
Passo 4
n 
n 
Fase de cálculo - resolução do PL de minimização da
distância ponderada da Tchebycheff à solução ideal:
min v
s. a v ≥ λk(h) (zk* - fk(x) )
1≤k≤p
(h)
x∈X
v≥0
Fase de diálogo - é apresentada ao decisor a solução
z(h) = f(x(h)) resultante da resolução do problema da
iteração h:
x(h) é o ponto da região admissível reduzida X(h)
mais próximo de z* de acordo com a métrica ponderada de
Tchebycheff.
62
31
23/02/14
n 
Passo 5
n 
n 
Se o decisor considerar esta solução satisfatória o
processo termina com x(h) como solução final.
Caso contrário, deve indicar
o  quais as funções objetivo fk (x) que está disposto a sacrificar
(S:=S ∪ {k}),
o  qual a quantidade máxima Δk a sacrificar em cada uma.
63
n 
Passo 6
Preparação da nova fase de cálculo: construção da nova
região admissível reduzida através da introdução de
restrições nos valores dos objetivos.
A região admissível reduzida para a iteração (h+1)
integrará as restrições
ck x ≥ fk (x(h)) - Δk
k∈S
(h)
ck x ≥ fk (x )
k∉S
Regressa ao passo 3.
n 
Na versão original
- cada função pode apenas ser relaxada uma vez,
- em cada iteração só pode ser relaxada uma função
Estas limitações podem não ser respeitadas no sentido de
tornar o método mais flexível.
64
32
23/02/14
MÉTODO TRIMAP
n 
n 
n 
Pesquisa livre:
aprendizagem progressiva e selectiva do conjunto das
soluções não dominadas
Informação de preferências:
n  limitações inferiores para os valores da funções
objetivo,
n  restrições no espaço dos pesos.
Fase de cálculo
otimização de uma soma ponderada das funções
objetivo.
65
n 
n 
n 
n 
n 
Espaço dos pesos: meio para recolher e apresentar a informação ao
decisor.
Problemas com três funções objetivo
n  limitação,
n  permite o uso de meios gráficos adequados ao diálogo com o
decisor.
Possibilitar um preenchimento progressivo e seletivo do espaço dos
pesos:
n  informação sobre a forma da superfície não dominada,
n  evitar um estudo exaustivo de regiões onde os valores dos
objetivos são semelhantes.
Redução do âmbito da pesquisa
n  impor limitações nos valores das funções objetivo (tipo de
informação que não exige grande esforço da parte do decisor),
n  traduzidas para o espaço dos pesos.
Através da análise comparativa do espaço dos pesos e do espaço dos
objetivos, o decisor pode fazer uma cobertura progressiva e seletiva
do espaço dos pesos, avaliando o interesse de pesquisar soluções em
áreas do triângulo ainda não exploradas.
66
33
23/02/14
n 
n 
n 
n 
Combina três procedimentos fundamentais:
n  decomposição do espaço dos pesos,
n  introdução de restrições no espaço dos objetivos,
n   introdução de restrições no espaço dos pesos.
As limitações introduzidas nos valores das funções
objetivo são traduzidas para o espaço dos pesos.
Cálculo das soluções eficientes que optimizam cada um
dos objetivos (fornece uma primeira informação sobre a
gama de valores de cada função objetivo).
Informação auxiliar: cálculo da solução eficiente que
minimiza uma distância ponderada de Tchebycheff à
solução ideal (como no STEM).
67
n 
n 
Selecção dos pesos para o cálculo de soluções não
dominadas:
n  escolher um conjunto de pesos de uma zona do
triângulo não preenchida, que parece importante para
continuar a pesquisa;
n  construir uma função ponderada cujo gradiente é
normal ao plano que passa por três soluções não
dominadas já calculadas escolhidas pelo decisor.
Introdução de limitações adicionais nos valores das
funções objetivo:
fk (x) ≥ Lk
(Lk ∈ ℜ, k ∈ {1,2,3})
n 
permite que o diálogo com o decisor seja feito em
termos dos valores das funções objetivo acumulando
a informação resultante no espaço dos pesos
68
34
23/02/14
n 
tradução para o espaço dos pesos:
⇒ construção do problema auxiliar
max fk(x)
s. a
x ∈ Xa
Xa≡ { x ∈ X : fk (x) ≤ Lk }
o  Maximizando fk (x) em Xa são obtidas soluções (básicas) óptimas
alternativas.
o  Os pontos extremos eficientes do poliedro admissível Xa que
otimizam o problema auxiliar são selecionados. As sub-regiões do
espaço dos pesos que correspondem a cada um destes pontos são
calculadas e representadas graficamente.
o  Estas são as regiões de indiferença definidas por λT W≥0, relativas a
cada base eficiente alternativa.
o  A união de todas estas regiões de indiferença determina a sub-região
do espaço dos pesos onde a limitação adicional no valor da função
objetivo é satisfeita.
69
n 
n 
n 
Se o decisor estiver apenas interessado em soluções
que satisfaçam fk (x) ≥ Lk, então é suficiente
restringir a pesquisa a esta sub-região.
Se o decisor pretender impor mais do que uma
limitação então o problema auxiliar é resolvido para
cada uma delas e as sub-regiões correspondentes no
espaço dos pesos são preenchidas com diferentes
padrões permitindo visualizar as zonas onde existem
intersecções.
Impor limitações directamente na variação dos
pesos
λi /λj ≥ uij, i,j ∈ {1,2,3}, i≠j, uij ∈ ℜ+
0 < uL ≤ λk ≤ uH < 1, com k ∈ {1,2,3}
70
35
23/02/14
n 
Dois gráficos principais
n 
n 
n 
espaço dos pesos mostrando as regiões de
indiferença correspondentes às soluções extremas
não dominadas já conhecidas,
projecção do espaço dos objetivos mostrando as
soluções não dominadas já calculadas.
Indicadores complementares sobre cada
solução:
n 
n 
distâncias L1, L2 e L∞ à solução ideal,
área da região de indiferença (% ocupada da área
total do triângulo).
71
INICIO
Cálculo das soluções eficientes que optimizam
cada função objectivo individualmente
Cálculo da solução eficiente que minimiza uma
distância ponderada de Tchebycheff à solução ideal
Cálculo de soluções
eficientes por selecção
directa (gráfica) de pesos
Cálculo de soluções
eficientes por selecção
indirecta de pesos
Informação actualizada em cada interacção
λ2
f2
B
B
A
C
C
A
f1
λ1
λ3
Informação complementar:
f k , x i , L 1 , L 2 , L , Area (%)
Fase de
decisão
"Cortes" do poliedro
admissível
Cálculo da solução eficiente que
minimiza uma distância ponderada de
Tchebycheff a um ponto de referência
Eliminação de sub-regiões do
triângulo por limitações:
- nos valores dos objectivos
- directamente nos pesos
"Varrimento"
contínuo de faces
O AD reuniu informação
considerada suficiente para
basear uma decisão
FIM
72
36
23/02/14
n 
Outros métodos interactivos
ICW – contração do cone dos critérios
n  Pareto Race – pesquisa linear
n  Zionts-Wallenius – redução do espaço paramétrico
n  Nimbus – para funções não diferenciáveis
n  Métodos para MILP
n  GDF
n  SPOT
n  ....
n 
73
n 
Tratamento da incerteza
Análise de sensibilidade
n  Programação estocástica
n  Programação intervalar
n  Programação difusa
n  Análise de robustez (min-max, min-max regret)
n 
74
37
23/02/14
Programação inteira, inteira-mista
e não linear multiobjectivo
Questões adicionais:
n 
Soluções eficientes próprias e não próprias
n 
Soluções eficientes suportadas e não suportadas
n 
Que tipos de soluções podem ser obtidos com os
processos de escalarização referidos atrás?
75
n 
Soluções eficientes próprias e não próprias
Solução eficiente própria:
noção mais restrita de solução eficiente de modo a eliminar
soluções eficientes que apresentem compromissos ilimitados
entre objctivos, ou seja soluções em que a relação melhoria/
degradação entre os valores das FO possa ser feita
arbitrariamente grande.
n 
n 
n 
Em PLMO, todas as soluções eficientes são eficientes
próprias, i.e, XPE ≡ XE.
Também em programação linear inteira e inteira-mista todas
as soluções eficientes são eficientes próprias.
Em problemas não lineares podem existir soluções eficientes
não próprias.
76
38
23/02/14
(f1 e f2 a maximizar)
•  soluções eficientes: arcos AB e CD,
excluindo D que é fracamente
eficiente
•  A, B e C são soluções eficientes não
próprias.
•  soluções eficientes: toda a
fronteira de A a C
•  B é uma solução eficiente
não própria.
77
n 
Soluções eficientes suportadas e não
suportadas
Solução eficiente não suportada:
Um ponto não dominado z’ ∈ FE é não suportado se for
dominado por uma combinação convexa (não
admissível) de pontos pertencentes a FE.
A um ponto z’=f(x’) não dominado não suportado
corresponde uma solução x’ eficiente não suportada.
Em PLMO, todas as soluções eficientes são suportadas.
n  Em programação inteira, inteira-mista ou não linear
podem existir soluções eficientes suportadas e não
suportadas.
n 
78
39
23/02/14
Soluções eficientes não suportadas num
problema de programação inteira
Espaço de decisão
Espaço dos objetivos
max z1= x1 - x2
max z2= -x1 +2x2
s.a:
x1 + 6x2 ≤ 21
14x1 + 6x2 ≤ 63
x1 , x2 ≥ 0
x1 , x2 inteiras
n 
n 
Soluções eficientes suportadas: A, B, E, H (extremas),
F, G (não extremas)
Soluções eficientes não suportadas: C, D
79
Soluções não suportadas num
problema de programação
inteira mista
•  suportadas: [AB] ∪ {E}
•  não suportadas: ]CD] ∪ [DE[
Soluções não suportadas num
problema de programação não
linear
•  suportadas: ponto B e arco CD
•  não suportadas: de B (exclusive)
a C (exclusive)
80
40
23/02/14
Processos de escalarização
n  Soma ponderada das funções objetivo
p
max
s.a :
∑λ f
k k
k =1
x∈X
(x)
} 
Apenas podem ser
obtidas soluções
eficientes suportadas.
} 
Em programação não
linear, soluções eficientes
não próprias (suportadas)
podem ser obtidas desde
que se admita que os
pesos podem ser nulos
(λ∈ Λ0)
81
f2
A
B
f1
82
41
23/02/14
n 
Soma ponderada das funções objetivo
com restrições nas funções objetivo
p
max
s.a :
∑
} 
λ k f k (x)
k =1
f k (x) ≥ e k
x∈X
k = 1,..., p
Permite obter
qualquer solução
eficiente do problema
(suportada ou não
suportada)
Pode incluir-se neste tipo de escalarização a
otimização de uma função objetivo restringindo as
outras
83
n 
Optimização de uma função objetivo
restringindo as outras
max f i ( x )
s.a :
f k (x) ≥ e k
x∈X
} 
k = 1,..., p; k ≠ i
Permite obter
qualquer solução
eficiente do
problema
84
42
23/02/14
85
n 
n 
Minimização da distância de Tchebycheff
a um ponto de referência
distância não pesada (L∞)
} 
min v
s.a v ≥ z +k − f k ( x ) , k = 1,..., p
x∈X
n 
distância pesada (Lλ∞)
min v
s.a v ≥ λ k z +k − f k ( x ) , k = 1,..., p
x∈X
(
)
Permite obter
qualquer solução
eficiente do problema
} 
Por variação de z+∈ℜp
ou
} 
Por variação de λ ∈ Λ0,
considerando z+ fixo a z*
(ou outro ponto de
referência do espaço
dos objetivos ≥ z*)
86
43
23/02/14
Com variação de λ
n 
n 
Com variação de z+
Em problemas multiobjetivo com variáveis inteiras, não
lineares ou combinatórios, a geração de soluções
eficientes pode ser computacionalmente custosa.
Os algoritmos evolutivos, ou outras meta-heurísticas
baseadas em populações, são técnicas capazes de
gerar um conjunto de soluções potencialmente
eficientes numa única execução do algoritmo.
n 
n 
n 
Em geral, não são usados processos de escalarização
São geralmente usados como métodos geradores,
cujo papel é gerarem um conjunto representativo de
soluções “eficientes”
Crescente integração com abordagens interativas
88
44
23/02/14
Exemplo: soluções “não dominadas” ao fim de … (iter.)
89
n 
Bibliografia
n 
n 
“Programação Linear Multiobjectivo
– do modelo de programação linear clássico à
consideração explícita de várias funções objectivo”,
João Clímaco, Carlos Henggeler Antunes, Maria João
Alves. Imprensa da Universidade de Coimbra, 2003.
Capítulo 16 - “Tomada de decisão em ambiente
multiobjectivo”,
Carlos Henggeler Antunes, Maria João Alves, João
Clímaco. In: Manual de Computação Evolutiva e
Metaheurística, Imprensa da Universidade de
Coimbra, pp. 323-356, 2012.
90
45