Meta - heurísticas Prof. Aurora - ppt carregar
PublicouRicardo Cal Alterado mais de 4 anos atrás
Apresentação em tema: "Meta - heurísticas Prof. Aurora"— Transcrição da apresentação:
1 Meta - heurísticas Prof. Aurora
Busca Tabu Meta - heurísticas Prof. Aurora
2 Tabu Search Fred Glover e Pierre Hansen. é um método de busca local
explorar o espaço de soluções movendo-se de uma solução para outra que seja seu melhor vizinho. uma estrutura de memória para armazenar as soluções geradas Ou características destas
3 Algoritmo BT Começando com uma solução inicial s0, a cada iteração,
Um subconjunto V da vizinhança N(s) da solução corrente s é explorado O membro s0 de V com melhor valor nesta região segundo a função f(:) torna-se a nova solução corrente mesmo que s0 seja pior que s.
4 Evitando Ciclos existe uma lista tabu T, a qual é uma lista de movimentos proibidos. A lista tabu clássica contém os movimentos reversos aos últimos |T| movimentos realizados |T| funciona como uma fila de tamanho fixo, isto é, quando um novo movimento é adicionado à lista, o mais antigo sai. Assim, na exploração do subconjunto V da vizinhança N(s) da solução corrente s, ficam excluídos da busca os vizinhos s0 que são obtidos de s por movimentos m que constam na lista tabu
5 Função de Aspiração A lista tabu
por um lado, reduz o risco de ciclagem por outro, também pode proibir movimentos para soluções que ainda não foram visitadas Função de aspiração é um mecanismo que retira, sob certas circunstâncias, o status tabu de um movimento.
6 Aspiração por Objetivo
Mais precisamente, para cada possível valor v da função objetivo existe um nível de aspiração A(v): uma solução s0 em V pode ser gerada se f(s0) < A(f(s)), mesmo que o movimento m esteja na lista tabu. A função de aspiração A é tal que, para cada valor v da função objetivo, retorna outro valor A(v) que representa o valor que o algoritmo aspira ao chegar de v. Um exemplo simples de aplicação desta idéia é considerar A(f(s)) = f(s*) onde s* é a melhor solução encontrada até então. Neste caso, aceita-se um movimento tabu somente se ele conduzir a um vizinho melhor que s*. Esta é a chamada aspiração por objetivo.
7 Critério de Parada Duas regras são normalmente utilizadas de forma a interromper o procedimento. Pela primeira, pára-se quando é atingido um certo número máximo de iterações sem melhora no valor da melhor solução. Pela segunda, quando o valor da melhor solução chega a um limite inferior conhecido (ou próximo dele). Esse segundo critério evita a execução desnecessária do algoritmo quando uma solução ótima é encontrada ou quando uma solução é julgada suficientemente boa.
8 Parâmetros Principais
a cardinalidade |T| da lista tabu, a função de aspiração A, a cardinalidade do conjunto V de soluções vizinhas testadas em cada iteração e BTmax, o número máximo de iterações sem melhora no valor da melhor solução.
10 Estratégias de Intensificação
Uma estratégia típica é retornar à uma solução já visitada para explorar sua vizinhança de forma mais efetiva. Outra estratégia consiste em incorporar atributos das melhores soluções já encontradas estimular componentes destas soluções a tornar parte da solução corrente. Um critério de término tal como um número fixo de iterações, é utilizado para encerrar o período de intensificação.
11 Busca Tabu Fred Glover (1986) & Pierre Hansen (1986)
13 1ª Idéia: Utilizar heurística de descida
14 1ª Idéia: Utilizar heurística de descida
15 2ª Idéia: Mover para o melhor vizinho
16 2ª Idéia: Mover para o melhor vizinho
17 3ª Idéia: Criar Lista Tabu
18 3ª Idéia: Criar Lista Tabu
19 Problemas com uma Lista Tabu de soluções.
É computacionalmente inviável armazenar todas as soluções geradas! Idéia: Armazenar apenas as últimas |T| soluções geradas Observação: Uma lista com as |T| últimas soluções evita ciclos de até |T| iterações Problema: Pode ser inviável armazenar |T| soluções e testar se uma solução está ou não na Lista Tabu Idéia: Criar uma Lista Tabu de movimentos reversos 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).
20 Exemplo de que uma Lista Tabu de movimentos pode ser restritiva
21 Exemplo de que uma Lista Tabu de movimentos pode ser restritiva
22 4ª Idéia: Critério de Aspiração
23 Busca Tabu aplicada ao Problema da Mochila
24 Busca Tabu aplicada ao Problema da Mochila
25 Busca Tabu aplicada ao Problema da Mochila
26 Busca Tabu aplicada ao Problema da Mochila
27 Busca Tabu aplicada ao Problema da Mochila
28 Busca Tabu aplicada ao Problema da Mochila
29 Busca Tabu aplicada ao Problema da Mochila
30 Método de Subida aplicado ao Problema da Mochila
31 Método de Subida aplicado ao Problema da Mochila
32 Prescrições especiais para a Busca Tabu
Lista tabu dinâmica: Tamanho variável no intervalo [tmin, tmax] Tamanho deve ser mudado periodicamente (p.ex., a cada 2tmax iterações) Objetivo: Se há ciclagem com um determinado tamanho, mudando-se o tamanho, muda-se a quantidade de movimentos tabu e possivelmente a seqüência de soluções geradas e conseqüentemente, diminui-se a probabilidade de ciclagem Passagem por regiões planas Aumentar o tamanho da lista enquanto estiver na região plana Retornar ao tamanho original quando houver mudança no valor da função de avaliação