Baixe o app para aproveitar ainda mais
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
Compartilhar