Inteligencia Artificial Busca TABU

Prévia do material em texto

BUSCA
TABU
E. G. M. de Lacerda
UFRN/DCA 
23/10/2006
Parte I
Busca Tabu
● BT guia a busca local utilizando uma estrutura de 
memória com aceitação de movimentos que não são 
de melhora.
● Usa a memória para:
● Prevenir ciclos (isto é, evitar visitar soluções já visitadas);
● Explorar regiões não visitadas do espaço de busca;
● Melhorar, através de experiências passadas, processo de 
tomada de decisão.
Componentes da Busca Tabu
● Vizinhança;
● Movimentos;
● Memória de Curto Prazo;
● Critérios de Aspiração;
● Memória de Longo Prazo.
Origem
BT 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 idéias básicas de BT também foram sugeridas por:
Hansen, P. “The steepest ascent mildest descent heuristic for 
combinatorial programming”, Congress on Numerical Methods 
in Combinatorial Optimization, Capri, Italy, 1986. 
Memória de Curto Prazo (1/2)
Em geral, é registrado apenas alguns  atributos das 
soluções já visitadas em vez da solução completa
(é mais barato).
● A principal meta é evitar:
● reverter o movimento
● ciclos.
● Lista tabu: registra o histórico das t mais recentes 
soluções visitadas.
Memória de Curto Prazo (2/2)
● A lista tabu possue um tamanho t denominado de 
período tabu (do inglês, tabu tenure).
● A lista é circular: quando um novo atributo entra na 
lista, o mais antigo sai.
Soluções que possuem atributos na 
lista tabu são proibidas de serem visitadas.
Lista tabu para o problema da mochila
a)Suponha que a variável sj mudou de 0 para 1;
b)Então, o valor sj = 0 torna­se um atributo tabu 
porque pertenceu a uma solução já visitada;
c)A lista tabu contém todos os atributos tabu e 
proibirá movimentos que mudem sj  de 1 para 0.
A lista tabu evita que soluções já visitadas sejam
novamente visitadas.
EXEMPLO
Critérios de Aspiração
Note que a lista tabu pode proibir soluções atraentes
de serem visitadas.
Critérios de aspiração permitem que 
soluções sejam visitadas mesmo que 
elas sejam tabu.
Critérios de Aspiração
● Aspiração por objetivo: 
● a aspiração é satisfeita se o movimento leva a uma 
solução melhor do todas as outras que já foram obtidas.
● Outros tipos de aspiração:
● Por Default
● Por Direção de Busca
● Por influência
Conceito de Intensificação
● Seu objetivo é concentrar a busca em regiões 
promissoras do espaço de busca.
● Estratégias de intensificação modifica as regras 
de escolha para encorajar combinaçãoes ou 
características historicamente boas.
Conceito de Diversificação
● Seu objetivo é dirigir a busca para novas regiões 
do espaço de busca.
● Estratégias de diversificação encoraja a busca a 
examinar soluções que diferem substancialmente 
das soluções já visitadas.
Algoritmo Busca Tabu
Passo 1. Selecione uma solução inicial s ∈S. Faça s* = s.
Passo 2. Gere um subconjunto V ⊆ N(s) tal que cada
               elemento de V não é Tabu ou satisfaz o critério 
               de aspiração.             
Passo 3. Escolha a melhor solução v ∈V 
Passo 4. Se v é melhor que s* então faça s* = v 
Passo 5. Faça s = v
Passo 6. Atualize a Lista Tabu.
Passo 7. Se o critério de parada for satisfeito vá ao
               passo 8, caso contrário vá ao passo 2. 
Passo 8. Retorne s*
O problema das n­rainhas
A meta é colocar n rainhas em um  tabuleiro n x n 
de modo que nenhuma ataque a outra.
1 2 3 4
3
2
1
4
Uma solução para o problema 
das 8­rainhas
Representação
● O problema das n­rainhas será tratado como um 
problema de permutação;
● A rainha i esta na linha i e na coluna(i);
● Uma solução é representada por uma permutação 
= ((1)2),… ,))
Exemplo
= (2,3,1,4)
1 2 3 4
3
2
1
4
A Estrutura da Vizinhança
● Operador do movimento:
4 5 3 6 7 1 2 4 1 3 6 7 5 2
troca da rainha 2 pela 6
A Estrutura da Vizinhança
O operador define uma vizinhança
com 6 vizinhos para o problema das 
4­rainhas.
(1,3,2,4) (3,2,1,4)
(1,2,4,3) (1,2,3,4) (1,4,3,2)
(2,1,3,4) (4,2,3,1)
A estrutura da lista tabu
Todos os movimentos realizados serão classificados
como tabu durante três iterações.
1 2 3 4 5 6 7
3
2
1
4
5
6
7
Cada célula armazena
a última iteração em que um 
atributo ainda é tabu. 
*
1 2 3 4 5 6 7
Iteração 0 1
2
3
solução corrente 4
4 5 3 6 7 1 2 5
6
2 3 4 5 6 7 7
1 troca valor No. colisões = 4
2 1 7 -2
3 2 4 -2
4 2 6 -2
5 5 6 -2
6 1 5 1
Os 5 melhores 
dos 21 
candidatos
estrutura 
tabu
1 2 3 4 5 6 7
Iteração 1 1
2
3
solução corrente 4
2 5 3 6 7 1 4 5
6
2 3 4 5 6 7 7
1 4 troca valor No. colisões = 2
2 2 4 -1 *
3 1 6 0
4 2 5 0
5 1 2 1
6 1 3 1
Os 5 melhores 
candidatos
estrutura 
tabu
1 2 3 4 5 6 7
Iteração 2 1
2
3
solução corrente 4
2 6 3 5 7 1 4 5
6
2 3 4 5 6 7 7
1 4 troca valor No. colisões = 1
2 5 1 3 0 *
3 1 7 1
4 2 4 1
5 4 5 1
6 6 7 1
Tabu
estrutura 
tabu
Tabu Os 5 melhores 
candidatos
1 2 3 4 5 6 7
Iteração 3 1
2
3
solução corrente 4
3 6 2 5 7 1 4 5
6
2 3 4 5 6 7 7
1 6 4 troca valor No. colisões = 1
2 5 1 3 0
3 1 7 0
4 5 7 1 *
5 6 7 1
6 1 2 2
Tabu
Tabu
estrutura 
tabu
Os 5 melhores 
candidatos
1 2 3 4 5 6 7
Iteração 4 1
2
3
solução corrente 4
3 6 2 5 4 1 7 5
6
2 3 4 5 6 7 7
1 6 4 troca valor No. colisões = 2
2 5 4 7 -1 *
3 5 7 -1
4 1 5 0
5 7 2 5 0
6 2 4 2
Tabu
estrutura 
tabu
Os 5 melhores 
candidatos
Tabu
1 2 3 4 5 6 7
Iteração 5 1
2
3
solução corrente 4
3 6 2 7 4 1 5 5
6
2 3 4 5 6 7 7
1 6 4 troca valor No. colisões = 1
2 5 1 3 -1 *
3 5 6 -1
4 8 5 7 0
5 7 1 6 0
6 1 7 2
Tabu 
Satisfaz o 
critério de 
aspiraçãoestrutura 
tabu
Tabu
1 2 3 4 5 6 7
Iteração 6 1
2
3
solução final 4
2 6 3 7 4 1 5 5
6
7
Fim da busca No. colisões = 0
Memória baseada na freqüência (1/4)
● É um tipo de memória de longo prazo.
● Usada para Implementar estratégias de 
diversificação ou intensificação.
Memória baseada na freqüência (2/4)
● Exemplo de estratégia de diversificação para o 
problema das n­rainhas:
● Armazena­se a freqüência de trocas rainhas.
● A informação da freqüência penalizará troca de rainhas 
com grande freqüência de troca.
● Neste exemplo,  sua aplicação será restrita apenas a 
movimentos sem melhora.
Memória baseada na frequência (3/4)
Iteração 26
Solução
1 3 6 2 7 5 4 valor
troca valor penalizado
1 2 3 4 5 6 7 1 6 0 1
1 29 1 3 1 6
2 1 5 1 3 *
3 5 28 2 7 1 5
4 3 27 3 7 1 4
5 2 4
6 1 2
7 4 3 1
Tabu
A matriz triangular Inferior 
armazena a frequência de trocas 
de rainhas.
ValorMovimento' =  ValorMovimento  +  Freq(i,j)
Memória baseada na frequência (4/4)
● É também usada para intensificar a busca em uma 
região promissora do espaço de busca.
● Exemplo:
1)Registre os atributos das melhores soluções 
encontradas;  
2)Calcule a frequência dos atributos das soluções de elite;
3)Incentive movimentos com atributos de alta freqüência.