COMPLEX : Uma evolução do SIMPLEX
Otimização de Processos
COQ – 897
PEQ/COPPE/UFRJ
Método SIMPLEX
• Spendley et al.,
Technometris,4
(p.441),1962
• Idéia simples e robusta
• Fácil implementação
Elementos do SIMPLEX
• Elementos definidos
para problemas em
várias dimensões
• Número de vértices do
SIMPLEX equivale ao
número de dimensões
mais 1
Passos no SIMPLEX
• Avanço na direção
colinear àquela que
é definida pelo pior
ponto e pelo
centróide, no
sentido oposto;
• Reflexão do ponto
xW tendo como
linha de base a
aresta xBxN.
xB
xW
xC
xR
xN
Localização do Centróide
• Localização
vetorial do
centróide
• Corresponde ao
ponto médio no
espaço vetorial
xB
xW  xN  xB
n
n = número de vértices do simplex
xC 
xW
xC
xN
Avanço na direção escolhida
• O novo ponto
corresponderá a
diferença dos
vetores vezes
coeficiente de
avanço, tendo
como ponto de
partida o centróide
• Abandona-se
sempre o pior
ponto avaliado
pela Fobj
xB
xC-xW
alfa(xC-xW)
xW
xC
xN
xC + alf a(xC - xW)
Otimização com o SIMPLEX
• Varredura na direção do ponto de ótimo
Problemas no SIMPLEX
• Regra de avanço rígida
• Pouco refinamento da solução
Método COMPLEX
• Nelder, A.J. & Mead, R., The Computer
Journal, 3 (p.308), 1965
• O poliedro que representa o SIMPLEX
poderá ser não regular
• Possibilidade de adicionar vértices extras
Elementos do COMPLEX
• Elementos
irregulares que
avançam mais
rapidamente
nas direções
mais
vantajosas
Passos no COMPLEX
•
•
•
•
Reflexão (=SIMPLEX)
Expansão
Contração Positiva
Contração Negativa
Algoritmo do COMPLEX
Inicia a Otimização
Construção do
SIMPLEX
T ermina
Sim
Avaliação ,
ordenamento dos
valores da Fobj e
determinação do
centróide
Não
T olerância
alcançada ?
Reflexão
xR = xC+alf a(xC-xW)
alfa = 1
xR é melhor
que xB ?
Não
Sim
xR é melhor
que xN ?
Sim
Não
Não
xR é melhor
que xW ?
Sim
Contração na
direção positiva
Expansão
Contração na
direção negativa
xE = xC+gama(xC-xW)
gam a > 1
xE é melhor
que xR ?
xC = xC+beta(xC-xW)
Não
0 < be ta < 1
xC = xC-beta(xC-xW)
Sim
xW = xE
xW = xR
xW = xC
Função Teste
u( x1 , x2 )  x  x
2
1
2
2
Solução na MatLab com o COMPLEX
10
8
start point
optimum
6
4
2
0
-2
-4
-6
-8
-10
-10
-8
-6
-4
-2
0
2
4
6
8
10
Função de Rosenbrock
• Função “banana”: u( x1 , x2 )  100 ( x2  x12 ) 2  (1  x1 ) 2
Gráfico de Níveis da Função “banana”
20
10
-150
-100
0
-50
0
-10
50
100
-20
150
Solução no MatLab – “banana”
• Rotina programada pelo Prof. Argimiro
20
start point
optimum
15
10
5
0
-5
-10
-15
-20
-20
-15
-10
-5
0
5
10
15
20
Desempenho: COMPLEX — “banana”
Nº de avaliações da Fobj
Ponto
Inicial
(10,10)
Rosenbrock
COMPLEX
273
304
(-10,10)
279
283
(-10,-10)
479
187
(10,-10)
543
198
Função Alpina
u( x1, x2 )  sin( x1 )  sin( x2 )  x1  x2
Solução no MatLab - Alpina
• Rotina programada pelo Prof. Argimiro
10
start point
optimum
9
8
7
6
5
4
3
2
1
0
0
1
2
3
4
5
6
7
8
9
10
Região da Solução - Alpina
6.5
start point
optimum
6
5.5
5
4.5
4
3.5
4.5
5
5.5
6
6.5
7
7.5
8
8.5
9
Mais de perto ...
start point
optimum
5.8
5.6
5.4
5.2
5
4.8
4.6
4.4
4.2
7.2
7.4
7.6
7.8
8
8.2
8.4
8.6
Avaliação do Número de Vértices Extras
u( x1 , x2 )  x  x
2
1
10
10
start point
optimum
8
2
2
start point
optimum
8
6
6
4
4
2
2
0
0
-2
-2
-4
-4
-6
-6
-8
-8
-10
-10
-10
-10
-8
-6
-4
-2
0
2
4
6
8
10
r=0; nS=125
-8
-6
-4
-2
0
2
4
6
8
10
r=1; nS=167
10
10
start point
optimum
8
start point
optimum
8
6
6
4
4
2
2
0
0
-2
-2
-4
-4
-6
-6
-8
-8
-10
-10
-8
-6
-4
-2
0
2
4
6
8
r=2; nS=208
10
-10
-10
-8
-6
-4
-2
0
2
4
6
8
10
r=3; nS=258
Conclusões
• Método Robusto
• Eficiência comparável aos demais métodos diretos
• Testes com os fatores alfa, beta e gama mostraram
que o número de avaliações da função objetivo
altera-se significativamente
• Aumentar o número de vértices não ofereceu
vantagens imediatas
• Excelente capacidade de refino da solução