29
BUSCA TABU Parte I

Tabu Parte1

Embed Size (px)

DESCRIPTION

descrição do funcionamento da busca tabu

Citation preview

  • BUSCATABUParte I

  • Busca TabuBT guia a busca local utilizando uma estrutura de memria com aceitao de movimentos que no so de melhora.Usa a memria para:Prevenir ciclos (isto , evitar visitar solues j visitadas);Explorar regies no visitadas do espao de busca;Melhorar, atravs de experincias passadas, processo de tomada de deciso.

  • Componentes da Busca TabuVizinhana;Movimentos;Memria de Curto Prazo;Critrios de Aspirao;Memria de Longo Prazo.

  • OrigemBT foi primeiramente sugerido por:Glover, F. (1986) Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, Vol. 13, pp. 533-549.

    As idias bsicas de BT tambm foram sugeridas por:Hansen, P. The steepest ascent mildest descent heuristic for combinatorial programming, Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy, 1986.

  • Memria de Curto Prazo (1/2)Em geral, registrado apenas alguns atributos das solues j visitadas em vez da soluo completa( mais barato).A principal meta evitar:reverter o movimentociclos.Lista tabu: registra o histrico das t mais recentes solues visitadas.

  • Memria de Curto Prazo (2/2)A lista tabu possui um tamanho t denominado de perodo tabu (do ingls, tabu tenure).A lista circular: quando um novo atributo entra na lista, o mais antigo sai.Solues que possuem atributos na lista tabu so proibidas de serem visitadas.

  • Lista tabu para o problema da mochilaSuponha que a varivel sj mudou de 0 para 1;Ento, o valor sj = 0 torna-se um atributo tabu porque pertenceu a uma soluo j visitada;A lista tabu contm todos os atributos tabu e proibir movimentos que mudem sj de 1 para 0.A lista tabu evita que solues j visitadas sejamnovamente visitadas.EXEMPLO

  • Critrios de AspiraoNote que a lista tabu pode proibir solues atraentesde serem visitadas.Critrios de aspirao permitem que solues sejam visitadas mesmo que elas sejam tabu.

  • Critrios de AspiraoAspirao por objetivo: a aspirao satisfeita se o movimento leva a uma soluo melhor do todas as outras que j foram obtidas.Outros tipos de aspirao:Por defaultPor direo de buscaPor influncia

  • Conceito de IntensificaoSeu objetivo concentrar a busca em regies promissoras do espao de busca.Estratgias de intensificao modificam as regras de escolha para encorajar combinaes ou caractersticas historicamente boas.

  • Conceito de DiversificaoSeu objetivo dirigir a busca para novas regies do espao de busca.Estratgias de diversificao encorajam a busca a examinar solues que diferem substancialmente das solues j visitadas.

  • Algoritmo Busca TabuPasso 1. Selecione uma soluo inicial s S. Faa s* = s.Passo 2. Gere um subconjunto V N(s) tal que cada elemento de V no Tabu ou satisfaz o critrio de aspirao. Passo 3. Escolha a melhor soluo v V Passo 4. Se v melhor que s* ento faa s* = v Passo 5. Faa s = vPasso 6. Atualize a Lista Tabu.Passo 7. Se o critrio de parada for satisfeito v ao passo 8, caso contrrio v ao passo 2. Passo 8. Retorne s*

  • O problema das n-rainhasA meta colocar n rainhas em um tabuleiro n x n de modo que nenhuma ataque a outra.

  • Uma soluo para o problema das 8-rainhas

  • RepresentaoO problema das n-rainhas ser tratado como um problema de permutao;A rainha i esta na linha i e na colunai;Uma soluo representada por uma permutao Exemplo

  • A Estrutura da VizinhanaOperador do movimento:45367124136752troca da rainha 2 pela 6

  • A Estrutura da VizinhanaO operador define uma vizinhanacom 6 vizinhos para o problema das 4-rainhas.

  • A estrutura da lista tabuTodos os movimentos realizados sero classificadoscomo tabu durante trs iteraes.3214567Cada clula armazenaa ltima iterao em que um atributo ainda tabu. *

  • Memria baseada na freqncia (1/4) um tipo de memria de longo prazo.Usada para Implementar estratgias de diversificao ou intensificao.

  • Memria baseada na freqncia (2/4)Exemplo de estratgia de diversificao para o problema das n-rainhas:Armazena-se a freqncia de trocas rainhas.A informao da freqncia penalizar troca de rainhas com grande freqncia de troca.Neste exemplo, sua aplicao ser restrita apenas a movimentos sem melhora.

  • Memria baseada na frequncia (3/4)Iterao 26A matriz triangular Inferior armazena a frequncia de trocas de rainhas.ValorMovimento' = ValorMovimento + Freq(i,j)

  • Memria baseada na frequncia (4/4) tambm usada para intensificar a busca em uma regio promissora do espao de busca.Exemplo:Registre os atributos das melhores solues encontradas; Calcule a frequncia dos atributos das solues de elite;Incentive movimentos com atributos de alta freqncia.