View
16
Download
0
Category
Preview:
Citation preview
Teoria da DecisãoIntrodução às Metaheurísticas
Prof. Lucas S. Batista
lusoba@ufmg.br
www.ppgee.ufmg.br/⇠lusoba
Universidade Federal de Minas GeraisEscola de Engenharia
Graduação em Engenharia de Sistemas
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Definições Gerais
Sumário
1 Problema de OtimizaçãoDefinições Gerais
2 Introdução às MetaheurísticasVisão Geral do Tema
3 Simulated AnnealingConceitos Gerais e Implementação
2 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Definições Gerais
Processo de Otimização
Frequentemente, o benefício ou o custo (i.e., o efeito) da implan-tação de uma solução xxx pode ser expresso por meio de umafunção f (·) de variáveis de decisão, onde xxx = (x1, x2, . . . , xn).
Então, determinar o melhor arranjo dessas variáveis que mini-miza ou maximiza essa função mérito consiste em um processode otimização.
3 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Definições Gerais
Processo de Otimização
OtimizaçãoProcesso que utiliza métodos computacionais para encontrar a “me-lhor” forma de projetar e/ou operar um dado sistema, representadapela melhor combinação de valores para as variáveis do problema,considerando seus objetivos e suas restrições de projeto e de opera-ção.
O processo de otimização sempre resulta, ou busca justificação,em um impacto econômico, representado por:
qualidade do produto, custo da produção, competitividade.
4 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Definições Gerais
Processo de Otimização
OtimizarSignifica minimizar (ou maximizar) uma dada função:
Encontrar xxx 2 F : f (xxx) f (yyy), 8 yyy 2 F
minxxx
f (xxx), xxx 2 F
5 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Definições Gerais
Problema de Otimização Mono-objetivo
Formulação geral:
minxxx
f (xxx) 2 R, xxx 2 F
X = {xxx = (x1, x2, . . . , xn), xi 2 Di}
F =
8><
>:
gi(xxx) 0; i = 1, . . . , phj(xxx) = 0; j = 1, . . . , qxxx 2 X
6 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Definições Gerais
Problema de Otimização Mono-objetivo
Caso particular (programação linear):
minxxx
cxcxcx 2 R, xxx 2 F
F =
8>>><
>>>:
Pk
aik xk 0; i = 1, . . . , pPk
bjk xk = 0; j = 1, . . . , q
xk � 0
7 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Visão Geral do Tema
Sumário
1 Problema de OtimizaçãoDefinições Gerais
2 Introdução às MetaheurísticasVisão Geral do Tema
3 Simulated AnnealingConceitos Gerais e Implementação
8 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Visão Geral do Tema
Motivação
Todos os dias, engenheiros e tomadores de decisão são confron-tados com problemas de crescente complexidade.
Esses problemas emergem de diversos setores técnicos:
projeto de circuitos elétricos/eletrônicos;
projeto de sistemas de controle;
projeto de sistemas mecânicos;
processamento de imagens;
pesquisa operacional.
Esses desafios podem, frequentemente, ser modelados comoproblemas de otimização.
9 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Visão Geral do Tema
Otimização “Difícil”
Dois tipos de problemas de otimização são claramente postos:problemas “discretos” e problemas com variáveis contínuas.
Problemas discretos: caixeiro viajante, roteamento de veículos.
Problemas contínuos: máquinas elétricas, controladores PI.
Problemas mistos: envolvem simultaneamente variáveis discre-tas e contínuas.
Essa diferenciação é útil para definir o domínio de “dificuldade”do problema de otimização.
10 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Visão Geral do Tema
Otimização “Difícil”
Problemas discretos “difíceis”Não se conhece um algoritmo polinomial exato. Este é o caso, parti-cularmente, dos problemas “NP-difíceis”.
Problemas contínuos “difíceis”Não se conhece um algoritmo exato capaz de localizar o ótimo globalem um número finito de iterações.
11 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Visão Geral do Tema
Otimização “Difícil”
Muito esforço foi dedicado, separadamente, à solução dessesproblemas:
No campo dos problemas contínuos “difíceis”. . .Existe um arcabouço significativo de métodos tradicionais para otimi-zação global. Entretanto, sua efetividade depende de propriedadesespecíficas do problema, e.g., diferenciabilidade, convexidade, moda-lidade.
No campo dos problemas discretos “difíceis”. . .Existe um arsenal de heurísticas, as quais encontram soluções pró-ximas do ótimo. Entretanto, a maioria delas é concebida para umproblema específico.
12 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Visão Geral do Tema
Otimização “Difícil”
A chegada das Metaheurísticas (MH) marca uma reconciliaçãode ambos os domínios.
De fato, elas são aplicadas a todos os tipos de problemas discre-tos, e podem ser adaptadas a problemas contínuos.
Possuem em comum as seguintes características:
são estocásticas;
possuem origem discreta, e mesmo em problemas contínuos nãoexigem diferenciabilidade, convexidade, modalidade;
são inspiradas em analogias físicas (SA), biológicas (TS, EAs) ouetológicas (ACO, PSO);
compartilham as mesmas desvantagens, i.e., ajuste de parâmetrose alto custo computacional.
13 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Visão Geral do Tema
Otimização “Difícil”
Em geral, é impossível assegurar com certeza a efetividade deuma dada MH quando aplicada a um dado problema.
As MHs não são mutualmente excludentes. A tendência atualé a utilização de métodos híbridos, buscando beneficiar-se devantagens específicas combinadas.
As MHs podem ser facilmente estendidas para:
otimização multiobjetivo;
otimização multimodal;
otimização dinâmica;
implementações paralelas.
14 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Visão Geral do Tema
Limitação Geral de Métodos Clássicos
Métodos clássicos, ou métodos de decida, aceitam somente “mo-vimentos” de melhora (possuem convergência monotônica).
Esses algoritmos de aperfeiçoamento iterativo não conduzem,em geral, ao ótimo global, mas a um mínimo local específico (cn).
15 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Visão Geral do Tema
Limitação Geral de Métodos Clássicos
Para melhorar a efetividade dos métodos clássicos, eles podemser aplicados repetidas vezes, partindo de configurações iniciaisdistintas.
Esse processo, entretanto, aumenta o custo computacional doalgoritmo, não garante a determinação do ótimo c⇤, e torna-seinefetivo com o aumento do número de mínimos locais.
16 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Visão Geral do Tema
Fonte de Efetividade das MHs
MHs são capazes de escapar de ótimos locais!!!
MHs baseadas em “vizinhança” (SA, VNS, ILS) aceitam a degra-dação temporária da solução, permitindo encontrar cn, c0
n e c⇤.
MHs “distribuídas” (EAs) evoluem paralelamente uma populaçãode soluções candidatas, e empregam estratégias específicas paraexploração do espaço de busca.
17 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Visão Geral do Tema
Classificação Geral dos Métodos de Otimização Mono-objetivo
18 / 42
Prof. Lucas de Souza Batista - DEE/EE/UFMG
Otimização de Redes Variable Neighborhood Search(VNS)
Variable Neighborhood Search
❖ VNS é uma metaheurística proposta por N. Mladenovic, P. Hansen (1997).
❖ Baseia-se na ideia de uma mudança sistemática de vizinhança:
❖ na fase de refinamento, para encontrar um ótimo local; e
❖ na fase de perturbação, para escapar de bacias de atração.
Estratégias Básicas
❖ VNS baseia-se em três fatos simples:
❖ Fato 1. Um mínimo local relacionado a uma estrutura de vizinhança não é necessariamente mínimo local de outra estrutura;
❖ Fato 2. Um mínimo global é um mínimo local relacionado a todas as possíveis estruturas de vizinhança;
❖ Fato 3. Para muitos problemas, mínimos locais relacionados a uma ou várias estruturas de vizinhança (Nk) estão relativamente próximos um dos outros.
Estratégias Básicas
❖ Ao usar várias estruturas de vizinhança, os Fatos 1 a 3 podem ser aplicados de três formas diferentes:
❖ determinística;
❖ estocástica;
❖ determinística e estocástica.
Algoritmo: Variable neighborhood descentFunction VND (x, kmax)k ← 1repeat
x’ ← arg miny ∈ Nk(x) f(y) % Find the best neighbor in Nk(x)x, k ← NeighborhoodChange (x, x’, k) % Change neighborhood
until k = kmax return x
❖ No VND, a mudança de vizinhança é realizada de maneira determinística.
❖ Frequentemente, kmax ≤ 2 em heurísticas de busca local.
Variable Neighborhood Descent (VND)
Variable Neighborhood Descent (VND)
Algoritmo: Neighborhood changeFunction NeighborhoodChange (x, x’, k)
if f(x’) < f(x) thenx ← x’ % Make a movek ← 1 % Initial neighborhood
elsek ← k + 1 % Next neighborhood
endreturn x, k
Reduced VNS (RVNS)Algoritmo: Reduced VNS
Function RVNS (x, kmax, tmax)repeat
k ← 1repeat
x’ ← Shake (x, k)x, k ← NeighborhoodChange (x, x’, k)
until k = kmaxt ← CpuTime()
until t > tmaxreturn x
❖ No RVNS, soluções aleatórias são selecionadas a partir de Nk(x).
❖ Uma técnica de refinamento não é aplicada.
Basic VNS (BVNS)
❖ O método BVNS combina mudanças de vizinhança determinística e estocástica.
❖ A determinística é representada por uma heurística de busca local.
❖ A estocástica é representada por uma seleção aleatória de uma solução da k-ésima vizinhança.
Basic VNS (BVNS)
Algoritmo: Best improvement (steepest descent) heuristicFunction Best Improvement (x)
repeatx’ ← xx ← arg miny ∈ N(x) f(y)
until f(x) ≥ f(x’)return x
Basic VNS (BVNS)
Algoritmo: First improvement (first descent) heuristicFunction First Improvement (x)
repeatx’ ← x; i ← 0;repeat
i ← i + 1x ← arg min {f(x), f(xi)}, xi ∈ N(x)
until (f(x) < f(x’) or i = |N(x)|)until f(x) ≥ f(x’)
return x
Basic VNS (BVNS)Algoritmo: Basic VNS
Function BVNS (x, kmax, tmax)t ← 0while t < tmax do
k ← 1repeat
x’ ← Shake (x, k) % shakingx’' ← BestImprovement (x’) % local searchx, k ← NeighborhoodChange (x, x'’, k)
until k = kmaxt ← CpuTime()
endreturn x
General VNS (GVNS)
❖ O método GVNS combina as técnicas VNS e VND.
❖ Esta estratégia está relacionada às aplicações de maior sucesso citadas na literatura sobre VNS.
General VNS (GVNS)Algoritmo: General VNS
Function GVNS (x, lmax, kmax, tmax)repeat
k ← 1repeat
x’ ← Shake (x, k) x’' ← VND (x’, lmax) x, k ← NeighborhoodChange (x, x'’, k)
until k = kmaxt ← CpuTime()
until t > tmaxreturn x
General VNS (GVNS)
Algoritmo: Variable neighborhood descentFunction VND (x, kmax)k ← 1repeat
x’ ← arg miny ∈ Nk(x) f(y) % Find the best neighbor in Nk(x)x, k ← NeighborhoodChange (x, x’, k) % Change neighborhood
until k = kmax return x
Reference
❖ M. Gendreau, J.-Y. Potvin (eds.), Handbook of Metaheuristics, Springer, 2nd ed., 2010.
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Conceitos Gerais e Implementação
Considerações Adicionais
Exemplos de estruturas de vizinha:
Suponha um problema de sequenciamento de máquinas paralelasnão relacionadas com tempos de preparação.
Quais estruturas de vizinhança podem ser empregadas?
31 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Conceitos Gerais e Implementação
Considerações Adicionais
Exemplos de estruturas de vizinha:
Shift
Realocação de uma tarefa para outra posição da mesma máquina.
32 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Conceitos Gerais e Implementação
Considerações Adicionais
Exemplos de estruturas de vizinha:
Switch
Troca a posição de duas tarefas processadas na mesma máquina.
33 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Conceitos Gerais e Implementação
Considerações Adicionais
Exemplos de estruturas de vizinha:
Task Move
Movimentação de uma tarefa de uma máquina de origem para umaoutra máquina.
34 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Conceitos Gerais e Implementação
Considerações Adicionais
Exemplos de estruturas de vizinha:
Swap
Realocação de duas tarefas aleatórias entre duas máquinas.
35 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Conceitos Gerais e Implementação
Considerações Adicionais
Exemplos de estruturas de vizinha:
Two-Shift
Desloca a posição de duas tarefas processadas em uma mesmamáquina.
36 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Conceitos Gerais e Implementação
Considerações Adicionais
Exemplos de estruturas de vizinha:
Direct Swap
Troca de duas tarefas entre duas máquinas, mantendo as posiçõesoriginais nessas máquinas.
37 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Conceitos Gerais e Implementação
Considerações Adicionais
Características das funções de vizinhança:
38 / 42
Problema de Otimização Introdução às Metaheurísticas Simulated Annealing Literatura Especializada
Literatura Especializada
M. Gendreau, J.-Y. Potvin (eds.), Handbook of Metaheuristics, Springer, 2nd ed.,2010.
J. Dréo, P. Siarry, A. Pétrowski, E. Taillard, Metaheuristics for Hard Optimization:Methods and Case Studies, Springer, 2006.
L.M. Pereira, Análise de estruturas de vizinhança para o problema de sequen-ciamento de máquinas paralelas não relacionadas com tempos de preparação,Dissertação de Mestrado, PPGEE/UFMG, 2019.
Início
42 / 42
Recommended