Teoria da Decisão - Universidade Federal de Minas Gerais

Teoria da DecisãoIntrodução às Metaheurísticas

Prof. Lucas S. Batista

[email protected]

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


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


Definições Gerais


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


Definições Gerais


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


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


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


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



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



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




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




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




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




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



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



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



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



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)


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 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.


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





Shift

Realocação de uma tarefa para outra posição da mesma máquina.

32 / 42





Switch

Troca a posição de duas tarefas processadas na mesma máquina.

33 / 42





Task Move

Movimentação de uma tarefa de uma máquina de origem para umaoutra máquina.

34 / 42





Swap

Realocação de duas tarefas aleatórias entre duas máquinas.

35 / 42





Two-Shift

Desloca a posição de duas tarefas processadas em uma mesmamáquina.

36 / 42





Direct Swap

Troca de duas tarefas entre duas máquinas, mantendo as posiçõesoriginais nessas máquinas.

37 / 42




Características das funções de vizinhança:

38 / 42


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

Documents

Teoria da Decisão - Universidade Federal de Minas Gerais