Heurísticas Construtivas

Heurís'cas e Metaheurís'cas Thiago F. Noronha

Heurís'cas Constru'vas

Belo Horizonte, 2012

Heurís'cas

•  Heurís3cas Constru3vas: – Heurís3cas Constru3vas gulosas – Algoritmos Aproxima3vos – Heurís3cas de Transformação (ou Redução) – Heurís3cas de Arredondamento Aleatorizado

Heurísticas e Metaheurísticas

Heurís'cas (Definição)

“Heurís3ca é parte de um algoritmo de o3mização que u3liza informações

par3culares de um problema para ajudar a decidir como uma solução é construída. Heurís3cas são geralmente de classes

problemas dependentes.” (Thomas Weise)¹


1: Thomas Weise. Global Op3miza3on Algorithms , Theory and Applica3on

Heurís'cas (Definição)

Algoritmos heurís'cos ou heurís'cas são procedimentos que em um curto período de

tempo conseguem encontrar soluções razoáveis, sem garan'as o'malidade.


Heurís'cas Constru'vas

•  Dada uma instância de um problema de o3mização, as heurís'cas constru'vas constroem uma solução viável para o problema, onde: –  Somente a viabilidade da solução é garan3da. –  A princípio, nenhuma propriedade relacionada a qualidade da solução construída é exigida.

•  Entretanto, espera-‐se que esta heurís3ca seja projetada de forma a almejar soluções cujo custo seja próximo ao custo da solução ó3ma para o problema.

•  Algoritmos gulosos encontram soluções ó3mas para diversos problema de o3mização.


Heurís'cas Constru'vas Gulosas

•  Forma mais simples e mais u3lizada para se projetar uma heurís3ca constru3va para um problema de o3mização.

•  Parte de uma solução vazia. •  Adiciona seqüencialmente elementos a solução através de algum critério (função de avaliação) guloso: –  Trata-‐se de um algoritmo míope, pois avalia somente um elemento da

solução de cada vez.

•  Ao final, é gerada uma solução viável.


Heurís'cas Constru'vas Gulosas Alg Heurís3caConstru3va(f(x), s): 1.  s Ø; 2.  Inicializa a lista de elementos candidatos C; 3.   Enquanto (C ≠ Ø) faça: 4.  x = melhor{f(x) | x є C}; 5.  s s U {x}; 6.  Remove x da lista de candidatos C; 7.   Fim enquanto; 8.   Retorne s;


Heurís'cas Constru'vas Problema do Caixeiro Viajante

•  TSP, do inglês Traveling Salesperson Problem. •  Dado um grafo G=(V, E) com custos ce associados às arestas em E. •  O TSP consiste em encontrar um ciclo hamiltoniano de comprimento mínimo.


5

6

12

4

1 3

2 7

5

8

2

3

1 1

Heurís'cas Constru'vas: TSP Heurís'ca Vizinho mais próximo

Escolha um vér3ce inicial

Enquanto houver vér3ce não-‐visitado efetue: •  Selecione vér3ce não-‐visitado mais próximo de uma das extremidades • 

• Se é a aresta entre as extremidades de então:

Retorne ciclo de peso

Observações: " Complexidade: O(n2); " Grande influência do vér3ce

inicial; " Aplicar a par3r de cada nó: O(n3).

V=18

4

1 3

2

5

7

5

1

2

3

4

3

2

1

2 2

3 3

1


Possibilidade de não gerar soluções:


5

4 3

2

1

2

1

1

1

1

2 2

2 2 M

Pode gerar soluções arbitrariamente ruins:



Algoritmos Aproxima'vos

•  Dada uma instância de um problema de o3mização, os algoritmos aproxima'vos constroem uma solução viável para o problema.

•  Neste caso, pode-‐se provar que a qualidade da solução não é pior que um certo fator є do valor da solução ó3ma.

•  Por exemplo, para є = 2, um algoritmo é 2-‐aproxima3vo, se o valor da solução produzida é no pior caso duas vezes pior que o valor da solução ó3ma.


Algoritmos Aproxima'vos Problema do Caixeiro Viajante

•  Heurís3ca da Árvore Geradora Mínima Dupla –  Calcule a Árvore Geradora Mínima (AGM) do grafo.

D

A

C

E

B

13

7

12

12

9

9

8

11 10 4



•  Heurís3ca da Árvore Geradora Mínima Dupla –  Calcule a Árvore Geradora Mínima (AGM) do grafo. –  Duplique as arestas da AGM e calcule um circuito euleriano no grafo

resultante.

E

D

A

C

B

7

9

8

4

D

A

C

B

7

9

8

4

E 8

9 7 4



•  Heurís3ca da Árvore Geradora Mínima Dupla –  Calcule a Árvore Geradora Mínima (AGM) do grafo. –  Duplique as arestas da AGM e calcule um circuito euleriano no grafo

resultante. –  Construa um circuito euleriano, executando uma busca em

profundidade par3ndo de qualquer vér3ce, guardando em uma lista todos os vér3ces que são visitados.

(A, C, D, B, D, E, D, C, A)

D

A

C

B

7

9

8

4

E 8

9 7 4



•  Heurís3ca da Árvore Geradora Mínima Dupla –  Calcule a árvore geradora mínima do grafo. –  Duplique as arestas da AGM e calcule um circuito euleriano no grafo

resultante. –  Construa um circuito euleriano, executando uma busca em

profundidade par3ndo de qualquer vér3ce, guardando em uma lista todos os vér3ces que são visitados.

–  Percorra a lista de vér3ces visitados eliminando os vér3ces repe3dos, formando um Circuito Hamiltoniano.

E

D

A

C

B (A, C, D, B, D, E, D, C, A) (A, C, D, B, E, A)



•  A heurís3ca da Árvore Geradora Mínima Dupla é 2-‐aproximado.

•  Prova: –  Sejam

•  H* o ciclo hamiltoniano ó3mo, •  T* a árvore geradora mínima do grafo e •  H a solução retornada pela heurís3ca da árvore geradora mínima dupla.

–  Temos que •  custo(T*) ≤ H* e •  custo(H) ≤ 2.custo(T*),

–  Sendo assim •  custo(H) ≤ 2.custo(H*)


•  Dado um conjunto de itens (i1,i2,i3, ...im) com diferente volumes (v1, v2,v3, ..., vm) que devem ser empacotados em um número finito de Caixas (c1, c2, ...,cn) de capacidade V igual a 1 de forma a minimizar o número de caixa u3lizadas.

•  O Problema de Bin Packing é NP -‐ Diucil.

Algoritmos Aproxima'vos Problema de Bin Packing 1-‐D


0.5 0.7 0.5 0.2 0.4 0.2 0.5 0.1 0.6 0.6

0.1 0.5 0.4 0.2

0.7

0.2 0.5 0.5

…… 1

Conjunto de itens

Caixas de capacidade 1



0.5 0.7 0.5 0.2 0.4 0.2 0.5 0.1 0.6

….… 1

0.1

0.5

0.4

0.6

0.2 0.7

0.2

0.5

0.5 N0 = 4

Solução ótima:



•  Heurís3ca First-‐fit (FF) –  Os itens são processados em ordem arbitrária. –  Para cada item é verificado se existe uma caixa para acomoda-‐lo. –  Se não exis3r, uma nova caixa é criada e o item inserido.


0.5

0.1 0.5 0.4 0.2 0.2

0.5 0.5 0.6 0.7




0.5 0.7

0.1 0.5 0.4 0.2 0.2

0.5 0.5 0.6 0.7




0.5 0.7

0.5

0.1 0.5 0.4 0.2 0.2

0.5 0.5 0.6 0.7




0.5 0.7

0.5 0.2

0.1 0.5 0.4 0.2 0.2

0.5 0.5 0.6 0.7




0.5 0.7

0.5 0.2

0.4

0.1 0.5 0.4 0.2 0.2

0.5 0.5 0.6 0.7




0.5 0.7

0.5 0.2

0.4

0.6

0.1 0.5 0.4 0.2 0.2

0.5 0.5 0.6 0.7




0.5 0.7

0.5 0.2

0.4 0.5

0.6

0.1 0.5 0.4 0.2 0.2

0.5 0.5 0.6 0.7




0.6

0.5 0.7

0.5 0.2

0.4 0.5

0.1

0.1 0.5 0.4 0.2 0.2

0.5 0.5 0.6 0.7




0.5 0.7

0.5 0.2

0.4

0.2

0.5

0.1 0.6

0.1 0.5 0.4 0.2 0.2

0.5 0.5 0.6 0.7


•  A heurís3ca da FF é 2-‐aproximada. –  No máximo uma caixa com menos da metade da capacidade. –  Só abre uma nova caixa se todas as caixas estão mais do que V/2

cheias ou se chegar um item com volume maior que V/2. –  Dado B caixas, pelo menos B-‐1 caixas estão mais da metade cheias.

–  Um limite inferior para o número ó3mo de caixas é

–  Assim, temos que B -‐ 1 < 2*OPT e portanto B ≤ 2*OPT.

•  A heurís3ca da FF é (1.7*OPT + 2)-‐aproximada. •  A heurís3ca da FFD é (1.23*OPT + 1)-‐aproximada.



Redução Heurís'ca

•  Redução –  uma redução é uma transformação de um problema em outro. –  o problema A é reduzvel ao problema B se existe uma maneira de

transformar uma solução para B numa solução para A

•  Heurís3ca de redução –  Para construir uma heurís3ca para o problema A, –  Transforma-‐se A em um problema B (de forma exata ou heurís3ca), –  resolve B com com algum algoritmo (exato ou heurís3co), –  Constrói uma solução viável para A a par3r da solução gerada para B.

– Heurísticas e Metaheurísticas

•  Mul3plexação WDM. •  As conexões são estabelecidas por caminhos ó3cos. •  Comutadores totalmente ó3cos. •  Sem conversores de comprimentos de onda.


Heurís'cas de Redução Roteamento e atribuição mínima de Comprimentos de onda



•  Estabelecer um conjunto de caminhos ó3cos. •  Atribuir um determinado comprimento de onda para cada uma deles.

•  Dois caminhos ó3cos que compar3lham algum enlace da rede devem ter comprimentos de onda diferentes.

•  Minimizar o número total de comprimentos de onda u3lizado.



•  Problema de Roteamento. –  Calcular o caminho mais curto para cada conexão.

•  Problema de atribuição de comprimentos de onda. –  Grafo de conflitos. –  Coloração de grafos.



-‐ Heurís'cas de Duas Fases -‐

•  Roteamento por caminhos mais curtos.

Conexões: (a -> e) (b -> f) (c -> m) (d -> b) (e -> h)



1

5 2

4 3

•  Grafo de Conflito.




1

5 2

4 3

•  Coloração de Grafos.

Conexões: (a -> e) : w1 (b -> f) : w2 (c -> m) : w3 (d -> b) : w2 (e -> h) : w1



1 0

6

3

2

4 5

7

8


Heurís'cas de Redução Problema de coloração de par'ções

1

6

3

5

8


Heurís'cas de Redução Problema de coloração de par'ções


Coloração de Grafos.



1 0

6

3

2

4 5

7

8



1

6

3

5

8

Conexões: (a -> e) : w1 (b -> f) : w2 (c -> m) : w2 (d -> b) : w1 (e -> h) : w1



Heurís'cas de Redução Problema de Steiner em Grafos

•  Seja o grafo G=(N,A), –  onde N é o conjunto de nós e A o conjunto de arcos valorados.

•  Sejam os conjuntos P (de nós terminais) e B (de nós brancos ou nós de Steiner) –  tais que P U B = N e B ∩ P =Ø .

•  Determinar um subgrafo de custo mínimo G’= (N’,A’), N’ є N, A’ є A tal que G’ é uma árvore contendo todos os nós de P e alguns nós de Steiner opcionalmente.



Nós de Steiner







Heurís'ca da Árvore Geradora Mínima •  Fixa o conjunto de nós de Steiner de tal forma que o grafo

resultante seja conexo.



Heurís'ca da Árvore Geradora Mínima •  Executa um algoritmo para AGM no grafo induzido pelos nós

terminais e pelos nós de Steiner fixados no passo anterior.



Heurís'ca da Árvore Geradora Mínima •  Executa um algoritmo para AGM no grafo induzido pelos nós

terminais e pelos nós de Steiner fixados no passo anterior.



Heurís'ca da Árvore Geradora Mínima •  Elimina da árvore os nós de Steiner de grau 1.




Heurís'ca da Árvore Geradora Mínima •  Elimina da árvore os nós de Steiner de grau 1.

Heurís'cas de Arredondamento Aleatorizado

•  Problema de Programação Linear Inteira (PLI)

•  PLI é NP-‐Diucil



•  Problema de Programação Linear (PL) :

•  Este problema pode ser resolvido em tempo polinomial.



•  Redução para PLI –  Conges-on minimiza-on Mul-commodity flow problem –  Conectar diversos pares de vér-ces no grafo minimizando a aresta

mais conges-onada.


10

4

7

3 9

2 8

6

5

1


•  Redução para PLI –  Conges-on minimiza-on Mul-commodity flow problem


•  Problema de Programação Linear Inteira (PL) : –  Relaxação linear

•  Implementação de Algoritmos aproxima3vos: –  Heurís3cas de arredondamento aleatório (Raghavan e Tompson,

1987)

•  A idéia básica destes métodos é:

–  relaxar um problema de PLI em PL; –  obter uma solução ó3ma do problema relaxado –  converter essa solução numa solução viável aproximada do problema

PLI original.

Heurísticas de Arredondamento Aleatorizado

•  A abordagem básica e composta por três passos: 1.   Formular o problema para ser resolver como um PLI. 2.  Obter uma solução fracionaria do problema resolvendo a

Relaxação Linear do PLI. 3.  Gerar uma solução inteira a par3r da solução fracionária por meio

de arredondamento do valor das variáveis fracionárias.


10

4

7

3 9

2 8

6

5

1

sd(0.33) (0.35)

(0.32)

(0.33) (0,28)


(0.10)

(0.25)

•  Redução para PLI –  Seleciona uma conjunto de rotas para cada par (s,d) em P.

10

4

7

3 9

2 8

6

5

1

sd(0.33) (0.35)

(0.32)

(0.33) (0,28)


(0.10)

(0.25)

•  Redução para PLI –  Seleciona uma conjunto de rotas para cada par (s,d) em P.

•  τi = 0.02

10

4

7

3 9

2 8

6

5

1

sd(0.33) (0.35)

(0.32)

(0.33) (0,28)


(0.10)

(0.25)

•  τi = 0.02

10

4

7

3 9

2 8

6

5

1

sd(0.33) (0.33)

(0.32)

(0.33) (0,28)


(0.08)

(0.25)

•  τi = 0.02

10

4

7

3 9

2 8

6

5

1

sd(0.33) (0.33)

(0.32)

(0.33) (0,28)


(0.08)

(0.25)

•  τi = 0.02, 0.08

10

4

7

3 9

2 8

6

5

1

sd(0.33) (0.33)

(0.32)

(0.33) (0,28)


(0.08)

(0.25)

•  τi = 0.02, 0.08

10

4

7

3 9

2 8

6

5

1

sd(0.25) (0.25)

(0.32)

(0.33) (0,28)


(0.00)

(0.25)

•  τi = 0.02, 0.08

10

4

7

3 9

2 8

6

5

1

sd(0.25) (0.25)

(0.32)

(0.33) (0,28)


(0.25)

•  τi = 0.02, 0.08

10

4

7

3 9

2 8

6

5

1

sd(0.25) (0.25)

(0.32)

(0.33) (0,28)


(0.25)

•  τi = 0.02, 0.08

10

4

7

3 9

2 8

6

5

1

sd(0.25) (0.25)

(0.32)

(0.33) (0,28)


(0.25)

•  τi = 0.02, 0.08, 0.25

10

4

7

3 9

2 8

6

5

1

sd

(0.32)

(0.33) (0,28)


•  τi = 0.02, 0.08, 0.25

10

4

7

3 9

2 8

6

5

1

sd

(0.32)

(0.33) (0,28)


•  τi = 0.02, 0.08, 0.25 , 0.32

10

4

7

3 9

2 8

6

5

1

sd

(0.32)

(0.33) (0,28)


•  τi = 0.02, 0.08, 0.25 , 0.32

10

4

7

3 9

2 8

6

5

1

sd

(0.00)

(0.33) (0,28)


•  τi = 0.02, 0.08, 0.25 , 0.32

10

4

7

3 9

2 8

6

5

1

sd

(0.33) (0,28)


•  τi = 0.02, 0.08, 0.25 , 0.32

10

4

7

3 9

2 8

6

5

1

sd

(0.33) (0,28)


•  τi = 0.02, 0.08, 0.25 , 0.32, 0.05

10

4

7

3 9

2 8

6

5

1

sd

(0.33) (0,28)


•  τi = 0.02, 0.08, 0.25 , 0.32, 0.05

10

4

7

3 9

2 8

6

5

1

sd

(0.28) (0,28)


•  τi = 0.02, 0.08, 0.25 , 0.32, 0.05

10

4

7

3 9

2 8

6

5

1

sd

(0.28) (0,28)


•  τi = 0.02, 0.08, 0.25 , 0.32, 0.05

10

4

7

3 9

2 8

6

5

1

sd

(0.28) (0,28)


•  τi = 0.02, 0.08, 0.25 , 0.32, 0.05, 0.28

10

4

7

3 9

2 8

6

5

1

sd

(0.28) (0,28)


•  τi = 0.02, 0.08, 0.25 , 0.32, 0.05, 0.28

10

4

7

3 9

2 8

6

5

1

sd

(0.00) (0,00)



0.02 0.05

0.08

0.25

0.28

0.32

•  τi = 0.02, 0.08 , 0.25 , 0.32, 0.05, 0.28


0.19 0.21

0.28 0.32

•  τj = 0.19, 0.21 , 0.32, 0.28


0.3 0.3

0.4

•  τK = 0.3 , 0.3, 0.4


0.3 0.3

0.4

•  Aleatorização –  Seleciona uma roda para cada conexão de acordo com o peso da rota. –  A probabilidade de uma rota ser escolhida é proporcional ao seu peso.

0.19 0.21

0.28 0.32

0.02 0.05

0.08

0.25

0.28

0.32

τI

τK

τJ

Representação dos dados de Entrada TSP

•  Matriz de per3nência vs. Listas de adjacências


4

3

2

1

2 2

3 3

1

•  Vetor de per3nência


Soluções viáveis: (1,1,1,1,0,0) (1,0,1,0,1,1) (0,1,0,1,1,1)

c d

a b e1

e5

e6

e2 e4

e3

Representação das Soluções TSP


•  Vetor de sucessores


a - d - c - b - a

b a c d c b a d

c d

a b e1

e5

e6

e2 e4

e3

•  Permutação circular


adcba bcdab dcbad abcda cbadc

c d

a b e1

e5

e6

e2 e4

e3




a

bcd dcb cbd dbc bdc cbd

a

c d

a b e1

e5

e6

e2 e4

e3




bcd dcb cbd dbc bdc cbd

a a

c d

a b e1

e5

e6

e2 e4

e3


Heurís'cas constru'vas Não determinís3cas

•  Aleatorização: •  Algoritmo guloso encontra sempre a mesma solução para um dado problema, exceto por eventuais empates;

•  Aleatorização permite alcançar diversidade nas soluções encontradas;

•  Heurís3cas constru3vas aleatorizadas pode ser u3lizadas em heurís3cas de mul3par3da.



•  Heurís3cas gulosas aleatorizadas – A cada iteração, cria uma lista de candidatos L e força uma escolha aleatória a cada iteração;

– A qualidade das soluções ob3das depende da qualidade dos elementos na lista de candidatos L;

– A diversidade das soluções encontradas depende da cardinalidade da lista L;



•  Heurís3cas gulosas aleatorizadas •  Casos extremos:

•  algoritmo guloso puro (L = Ø) •  solução gerada aleatoriamente (L = C)

•  A cardinalidade pode ser limitada: •  pelo número de elementos: cons3tuída pelos p elementos com melhores custos incrementais à cardinality-‐based ;

•  pela qualidade dos elementos à value-‐based .



•  Aleatorização por perturbação: •  Primeiramente, altera (perturba) os dados de entrada aleatoriamente.

•  Em seguida, aplica uma heurís3ca constru3va tradicional a instância perturbada;

•  Por fim, calcula o custo da solução em função dos dados originais.

•  A qualidade e a diversidade das soluções ob3das depende da intensidade da perturbação realizada;


Heurís'cas de Mul'par'da

•  Pseudocódigo


Até que uma condição de para seja sa-sfeita Faça –  Aplicar uma heurís-ca constru-va randomizada; –  Atualizar a melhor solução encontrada;

Retornar a melhor solução encontrada.

Education

Heurísticas Construtivas