Otimização
Prof. Benedito C. Silva
IRN UNIFEI
Adaptado de: Walter Collischonn / IPH UFRGS
Simulação e Otimização
Simulação é o processo de representar matematicamente um
sistema, e realizar experimentações para prever seu
comportamento quando sujeito a determinadas condições.
Ex: Modelos chuva-vazão, modelo de reservatórios, modelos
de redes hidráulicas, modelos de redes de fluxo...
Otimização é a determinação das condições que resultam no
melhor desempenho do sistema. Normalmente envolve a
execução de diversas simulações.
Exemplos de algoritmos: programação linear, não-linear,
dinâmica, técnicas de inteligência artificial...
Em ambos os caso podem ser necessários mais de um modelo
para representar o sistema.
Muitas vezes o modelo de otimização está inserido no modelo de
simulação.
Construção de Modelos Matemáticos
Sistema Real
Simplificação
Definição e
Descrição do Problema
Revisão
Modelo Matemático
Solução do Modelo
Decisão
Teórica x
Política
Implementação da Solução
3
Elementos de um modelo matemático de
otimização
DECISÕES
Identificar quais decisões efetivamente resolvem o problema.
O que não conhecemos no problema?
RESTRIÇÕES
Identificar quais as restrições que limitam as decisões a tomar
OBJETIVOS
Definir objetivos capazes de indicar que uma decisão é preferível a
outras
4
Ex.: Ajuste de modelo hidrologico
Encontrar o valor
dos parâmetros de
um modelo
matemático que
resultem em uma
boa concordância
entre dados
observados e
calculados.
Gupta et al.
Otimização

Encontrar o mínimo ou o máximo de uma
função
160
140
120
100
80
60
40
20
0
0
10
20
30
Cálculo analítico

Encontrar pontos da função em que a derivada é zero.


Vantagens: pode ser rápido, é mais elegante)
Desvantagens: problemas de recursos hídricos apresentam
funções de picos múltiplos, funções descontínuas, ausência da
forma analítica da função, por exemplo
160
140
F(x)  a  b.x  c.x 2
120
100
80
60
40
dF
0
dx
20
0
0
10
20
30
Otimização de Sistemas de Recursos
Hídricos





Superfícies de resposta complexas
Pontos extremos mal definidos
Regiões planas
Muitos ótimos locais
Ótimo global apenas pouco melhor do que os
ótimos locais
Técnicas de otimização


Cálculo analítico
Técnicas numéricas



Busca aleatória
Busca direta
Mistos
Técnicas numéricas - Busca Aleatória

Vantagens:
funções
descontínuas;
picos múltiplos
160
140
“Ótimo”
120
100
80
60
40

Desvantagens:
demorado; não
existe garantia
de atingir o
ponto ótimo
global
20
0
0
10
20
30
Técnicas numéricas - Busca direta
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0

0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Estratégia de caminhar “morro acima”
Função objetivo: F(x1,x2)
5
4.5
4
3.5
3
x2
2.5
2
1.5
Máximo local
1
Máximo global
0.5
0
0
0.5
1
1.5
2
x1
2.5
3
3.5
4
4.5
5
Início: ponto coordenadas (parâmetros) aleatórias
5
4.5
X2=valor
aleatório entre
ced
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
X1=valor aleatório entre a e b
Determina direção de busca: exemplo x2=x2+0,3; x1=x1
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Função objetivo melhorou? Não, então tenta no outro sentido.
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Não, então volta para o ponto anterior...
...e muda a direção de busca.
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
E assim segue até encontrar um ponto em que não existe
direção de busca que melhore o valor da FO
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Rosenbrock: Método um pouco mais eficiente
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Direção de busca é a que potencialmente dará maior incremento da FO
Limitação da busca direta: Ótimos locais
5
4.5
4
3.5
Região que
atrai solução
para o ótimo
local
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Tentativa de contornar problema: Busca
direta com inicialização múltipla
5
4.5
Várias
tentativas;
espera se que
o ótimo global
seja a melhor
solução
testada.
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Problema: Ineficiente e ineficaz quando a FO tem muitos ótimos locais
Modelos de Otimização






Programação linear (Simplex)
Programação não-linear
Programação dinâmica
Algoritmos genéticos
Caminhos de formiga
…
Algoritmos Genéticos




Definição da faixa de validade dos parâmetros
geração aleatória de pontos (conjuntos de
parâmetros)
avaliação das funções objetivo para cada
ponto
reprodução, evolução

conjuntos com melhores F.O. têm maior chance de
contribuir na reprodução
Inspiração na natureza
Algumas regras gerais dos
algoritmos genéticos
•Conceitos de população, reprodução e gerações
•Filhos são semelhantes aos pais
•Os pais mais “adaptados” tem maior
probabilidade de gerar filhos
•Os filhos não são completamente iguais aos
pais
Pais mais adaptados têm maior
probabilidade de gerar filhos
(sobrevivência do mais apto = seleção natural)


Na natureza: indivíduos mais adaptados têm
maior probabilidade de sobreviver até chegar
à fase reprodutiva e de participar do
processo de reprodução.
No algoritmo: pontos com maior FO têm
maior probabilidade de serem escolhidos
para participar dos complexos.
5
4.5
4
3.5
3
Passo 1
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5
4.5
4
3.5
3
Passo 2
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5
4.5
4
3.5
3
Passo 3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5
4.5
4
3.5
3
Passo 4
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5
4.5
4
3.5
3
Passo 5
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5
4.5
4
3.5
3
Passo 6
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5
4.5
4
3.5
3
Passo 7
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5
4.5
4
3.5
3
Passo 8
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5
4.5
4
3.5
3
Passo 9
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5
4.5
4
3.5
3
Passo 10
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5
4.5
4
3.5
3
Passo 20
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Otimização multi-objetivo




Considerar mais de uma FO.
Calibração de modelos hidrológicos
distribuídos
Otimização de sistemas de reservatórios de
usos múltiplos (controle de cheias x
regularização de vazão)
Vazão e evapotranspiração
Novos métodos evolutivos



Colônia de formigas
Enxame de abelhas
...