Busca Tabu - Slides

Prévia do material em texto

Tópicos Especiais em Otimização 
BUSCA TABU 
 
Autora do material: 
Prof. Luciana Brugiolo Gonçalves 
 
Professora: Adria Lyra 
adrialyra@ufrrj.br 
 
Busca Tabu 
Busca Tabu 
•  Busca Tabu 
•  Enquanto o SA analisa parte da vizinhança, a Busca Tabu explora 
toda a vizinhança. 
•  Faz uso de memória para armazenar informações relacionadas ao 
processo de busca; 
•  Explorar o espaço de soluções movendo-se de uma solução para 
seu melhor vizinho; 
•  Aceita movimentos de não melhora para escapar de ótimos locais 
(realiza o movimento, mesmo o melhor vizinho não sendo melhor 
que a solução atual). 
Busca Tabu 
•  Proposto por Fred Glover 
•  “Future Paths for Integer Programming 
and Links to Artificial Intelligence”, 
Computers and Operations Research, 
Vol. 13, No. 5, 533-549, 1986. 
•  Em paralelo: 
 P. Hansen. The steepest ascent mildest 
descent heuristic for combinatorial 
programming. In Congress on Numerical 
Methods in Combinatorial Optimization, 
Capri, Italy, 1986. 
Busca Tabu 
•  Características: 
•  Utilizar Heurística de Descida; 
•  Problema: Fica-se preso no primeiro ótimo local 
•  Mover para o Melhor Vizinho; 
•  O melhor vizinho pode ser de piora 
•  Problema: Ciclagem 
•  Criar uma Lista Tabu! 
Busca Tabu 
•  Lista Tabu 
•  Objetivo: descartar vizinhos previamente visitados; 
•  Ideal: armazenar todas as soluções geradas. 
•  Inviável computacionalmente, a opção é armazenar as últimas soluções 
geradas! 
•  Uma lista com as últimas t soluções evita ciclos de tamanho t . 
•  Pode ser caro armazenar (espaço) e avaliar (esforço) se cada 
solução gerada esta na lista. 
•  Ideia: armazenar na lista apenas os movimentos proibidos! 
•  Memória de curto prazo à atualizada a cada iteração. 
Busca Tabu 
•  Exemplo de Lista Tabu 
•  Problema de otimização por Permutação 
•  Movimento: Troca de dois elementos da permutação (i,j) 
•  Lista Tabu pode proibir 
•  Movimento reverso 
•  Qualquer movimento que envolva os índices i e j 
Busca Tabu 
•  Lista Tabu 
•  Problema: Uma Lista Tabu de movimentos pode ser muito restritiva 
(impede o retorno a uma solução já gerada anteriormente e 
também a outras soluções ainda não geradas). 
•  Exemplo: 
•  Problema mochila binário 
•  Solução: Vetor de n binários 
•  Movimento: para algum k \in {1,...,n}, xk’ ß 1 - xk 
•  Lista Tabu: armazena índice da posição 
•  Para n = 5 e t = |T| = 2 
Busca Tabu 
•  Lista Tabu 
•  Mochila binário 
(01010) 
Solução Inicial 
Busca Tabu 
•  Lista Tabu 
•  Mochila binário 
(01010) 
Solução Inicial 
(11010) 
(00010) 
(01110) 
(01000) 
(01011)* 
Busca Tabu 
•  Lista Tabu 
•  Mochila binário 
(01010) 
Solução Inicial 
(11010) 
(00010) 
(01110) 
(01000) 
(01011)* 
Solução atual 
T={5} 
Busca Tabu 
•  Lista Tabu 
•  Mochila binário 
(01010) 
Solução Inicial 
(11010) 
(00010) 
(01110) 
(01000) 
(01011)* 
Solução atual 
T={5} 
(11011) 
(01001) 
(01111) 
(00011)* 
Busca Tabu 
•  Lista Tabu 
•  Mochila binário 
(01011)* 
Solução atual 
T={5} 
(11011) 
(01001) 
(01111) 
(00011)* 
Solução atual 
T={2,5} 
(01010) 
Solução Inicial 
(11010) 
(00010) 
(01110) 
(01000) 
(10011) 
(00010)* 
(00001) 
(00111) 
Proibindo solução 
não visitada 
Busca Tabu 
•  Características: 
•  Utilizar Heurística de Descida; 
•  Problema: Fica-se preso no primeiro ótimo local 
•  Mover para o Melhor Vizinho; 
•  O melhor vizinho pode ser de piora 
•  Problema: Ciclagem 
•  Criar uma Lista Tabu. 
•  Critério de Aspiração. 
Busca Tabu 
•  Critério de Aspiração 
•  Sob determinadas condições, o status de tabu de um movimento é 
desconsiderado. 
•  Serão aceitas soluções não tabu ou aquelas tabus que atendam 
ao critério de aspiração. 
•  Formas 
•  Critério de Aspiração por Objetivo: 
•  Aceitar o movimento, mesmo que tabu, se este melhorar o valor da função 
objetivo (ou percentual). 
•  Critério de Aspiração por Default: 
•  Se todos os possíveis movimentos forem tabus, realizar o mais antigo. 
Busca Tabu 
•  Critério de Parada (várias possibilidades) 
•  Número de iterações sem melhora; 
•  Número máximo de iterações; 
•  Tempo de CPU; 
•  O valor da melhor solução atinge um valor (solução é julgada 
suficientemente boa). 
Busca Tabu 
•  Os principais parâmetros de controle 
•  Tradicionais 
•  Solução inicial; 
•  Vizinhança N(s); 
•  Critério de parada. 
•  Definir também 
•  Critério de aspiração 
•  O número de elementos da lista tabu (impacto direto no desempenho do 
algoritmo); 
•  Estático (associado ao tamanho da instância e tamanho da vizinhança); 
•  Dinâmico 
•  Exemplo: Tamanho da lista escolhido aleatoriamente no intervalo [tmin, tmax]; 
•  Adaptativo: atualização de acordo com a performance no algoritmo 
•  Exemplo: aumentar o tamanho da lista quando a busca estiver em região plana, ou então, 
aumentar o tamanho da quando ciclos forem identificados. 
Busca Tabu 
[Luiz Lorena, INPE] 
Busca Tabu 
•  Exemplo para o problema da mochila 
•  Luiz Lorena, INPE (slide 21) – disponível em 
http://www.lac.inpe.br/~lorena/cap/Aula_C02.pdf 
Busca Tabu 
•  Embutir na Busca Tabu estratégias de Intensificação e 
Diversificação 
•  Intensificação (Memória de médio prazo): 
•  estratégia incluída na busca tabu com o objetivo de guiar a busca para 
regiões promissoras. 
•  Diversificação (Memória de longo prazo): 
•  direciona a busca para regiões do espaço de soluções ainda não 
exploradas. 
Busca Tabu 
•  Intensificação 
•  Estratégias (Memória de médio prazo) 
•  Armazenar boas soluções encontradas durante a busca (conjunto de 
soluções elite); 
•  Identificar atributos presentes nas melhores soluções e “incentivar ou 
forçar” a presença destes atributos nas próximas soluções. 
•  Fixar atributos: reiniciar a busca com a melhor solução obtida fixando os 
atributos comuns às melhores soluções. 
•  Path Relinking 
Busca Tabu 
•  Intensificação 
•  Ativação da intensificação 
•  Dado um número de iterações; 
•  Dado um número de iterações sem melhora da melhor solução. 
•  Aplicabilidade 
•  O uso de intensificação nem sempre leva a melhores resultados; 
•  Exemplo: para problemas com vários ótimos locais, a intensificação em 
cada bacia de atração pode não melhorar o desempenho do algoritmo. 
Busca Tabu 
•  Intensificação 
•  Path Relinking (Reconexão por caminhos) 
•  Maurício Resende (slide 20) 
Disponível em 
http://www2.research.att.com/~mgcr/talks/telecom-sbpo2004.pdf 
Busca Tabu 
•  Diversificação 
•  Estratégia (Memória de longo prazo); 
•  Armazena informações sobre as soluções visitadas durante toda a 
busca; 
•  Memória de frequência: Armazena o número de vezes que determinado 
componente apareceu nas soluções visitadas; 
•  Diferente da intensificação, a diversificação tem por objetivo gerar 
solução com atributos diferentes daqueles encontrados até então; 
•  Penalização dos atributos mais frequentes ou incentivar aqueles menos 
frequentes. 
Busca Tabu 
•  Diversificação 
•  Estratégia (Memória de longo prazo); 
•  Reinício com diversificação 
•  Gerar solução com atributos menos frequentes a partir da melhor solução ou 
da solução atual e reiniciar a busca; 
•  Diversificação Contínua 
•  Introduzir um fator encorajando a diversificação; 
•  Exemplo: introduzir na FO um fator favorecendo atributos menos frequentes 
ou penalizando os mais frequentes 
•  Estratégia de oscilação 
•  Permite considerar soluções intermediárias inviáveis; 
•  Guia a busca pelo espaço de soluções inviáveis e, posteriormente, retorna ao 
espaço de soluçõesviáveis, alterando a função de avaliação. 
Busca Tabu 
•  Diversificação 
•  Ativação da intensificação 
•  Dado um número de iterações; 
•  Dado um número de iterações sem melhora da melhor solução. 
•  Aplicabilidade 
•  O uso de diversificação nem sempre leva a melhores resultados; 
•  Exemplo: para problemas onde as melhores soluções estão 
concentradas, diversificação pode não gerar melhores resultados. 
Busca Tabu 
[Talbi] 
Busca Tabu 
•  Diferentes estruturas de memória do algoritmo 
[Talbi] 
Dúvidas 
•  Perguntas ou comentários? 
Luciana Brugiolo Gonçalves 
lbrugiolo@ufv.br 
Referências 
•  EL-GHAZALI TALBI. Metaheuristics: From Design to 
Implementation, Wiley, 2009. 
•  Notas de aula da prof Luiz Lorena (INPE). 
•  Notas de aula da prof Celso Ribeiro (UFF). 
•  Maurício Resende (AT&T) – disponível em http://
www2.research.att.com/~mgcr/talks/telecom-sbpo2004.pdf