Busca com Informação e
Exploração
“Busca heurística”
Eduardo Araujo Oliveira
[email protected]
Patricia Endo
[email protected]
Busca heurística - Escopo






Definição
Estratégias de busca com Informação
Funções heurísticas
Algoritmos de busca local e problemas
de otimização
Busca local em espaço contínuo
Agente de busca on-line e ambientes
desconhecidos
Problema da busca cega

Se a combinação de caminhos até o objetivo
for exponencial a busca cega dificilmente
encontrará a resposta do problema em um
tempo polinomial.
Instância
Como encontrar um barco perdido?
Não podemos procurar no oceano inteiro...
Informações relevantes:
Velocidade do vento;
Direção do vento;
...
Definição



Como na busca cega, utiliza a definição do
problema para efetuar a busca.
Utiliza conhecimento específico do
problema (informações)
Não procura a melhor solução do
problema, procura uma boa solução, ou
simplesmente alguma solução.
Busca gulosa pela melhor
escolha


Estratégia: tenta expandir o nó
supostamente mais próximo a origem
(heurística), através de uma estimativa;
Avalia nós através da função h(n)

h(n) depende do problema
Exemplo


Objetivo: Encontrar um bom caminho
de Arad à Bucareste.
h(n) = distância em linha reta do nó n
até o objetivo (Bucareste)
Busca pela melhor escolha
Busca pela melhor escolha
Busca pela melhor escolha
Busca pela melhor escolha
Busca pela melhor escolha
Características da Busca
Gulosa pela melhor escolha


Não é ótima;
É incompleta, pois pode entrar em
loops infinitos;
Busca A*




Avalia a combinação de duas funções:
f(n) = g(n) + h(n); onde:
g(n) é o custo real da origem até o nó n;
h(n) é a distância em linha reta do
objetivo até o nó n.
A*: Características



Desde que h(n) não superestime o custo
para alcançar o objetivo, A* é ótima.
Completa.
A* expande o nó de menor valor de f na
fronteira do espaço de estados.
 Olha
o futuro sem esquecer do passado,
armazenando todos os caminhos
anteriores.
A*
A*
A*
A*
Comportamento

Custo de tempo:


exponencial com o comprimento da solução,
porém boas funções heurísticas diminuem
significativamente esse custo
Custo memória: O(bd)
 guarda todos os nós expandidos na memória


para possibilitar o backtracking
Eficiência ótima
 só expande nós com f(n)  f*, onde f* é o
custo do caminho ótimo
A* de aprofundamento
iterativo (AIA*)

Igual ao aprofundamento iterativo,
sua principal diferença é que seu
limite é dado pela função de
avaliação (f) (contornos), e não pela
profundidade (d).
Busca heurística com limite de
memória

BRPM – Busca recursiva pelo melhor


Semelhante a busca recursiva em
profundidade;
Diferença: Não desce indefinidamente. Ela
controla a recursão pelo valor de f. Se existir
algum nó em um dos ancestrais que ofereça
melhor estimativa que o nó atual, a recursão
retrocede e a busca continua no caminho
alternativo.
BRPM
Arad
Sibiu
Fagaras
415
Oradea
366
Arad
393
R. Vilcea
526
Pitesti
447
413
Sibiu
417
553
BRPM
Arad
Sibiu
Fagaras
Oradea
415
Sibiu
591
Bucareste
450
Arad
393
R. Vilcea
526
366
447
417
BRPM
Arad
Sibiu
Fagaras
Oradea
450
366
Arad
393
R. Vilcea
526
447
417
Pitesti
Sibiu
417
Bucareste
418
553
R. Vilcea
607
A* Limitado pela memória
simplificado (LMSA*)


Utiliza toda a memória disponível;
Quando a memória está cheia, ele
elimina o pior nó folha (maior custo de
f) para continuar a busca.
A* Limitado pela memória
simplificado (LMSA*)


É completo, se a profundidade do nó
objetivo mais raso for menor que o
tamanho da memória.
É ótimo se qualquer solução ótima for
alcançável.
Funções heurísticas


O desempenho da busca está totalmente
relacionado a qualidade da função
heurística utilizada.
Como medir a qualidade de uma função
heurística?
Exatidão heurística




Uma maneira de caracterizar a exatidão
heurística é através do fator de ramificação
efetiva (b*).
Considere N o número de nós gerados para
alcançar o objetivo, e d a profundidade da
solução. Então:
N = 1 + b* + (b*)2 + ... + (b*)d
Uma boa função heurística terá b* bem
próximo de 1.
Exemplo
7


h1 = o número de blocos
em posições erradas
H2 = a soma das distâncias
de suas posições objetivo
2
5
8
4
6
3
1
Estado inicial
1
2
3
4
5
6
7
8
Estado objetivo
Funções heurísticas





Se o custo real para alcançar n é 150.
h1(n) = 56; //heurística 1
h2(n) = 140; //heurística 2
h2(n) >= h1(n);
Dizemos que h2 domina h1. Isso pode ser
traduzido na forma: A heurística 2 é melhor
que a heurística 1, pois terá um menor fator
de ramificação. Desde que h1 e h2 não
superestimem o custo real.
Funções heurísticas



Como escolher uma boa função heurística h?
h depende de cada problema particular.
h deve ser admissível


não superestimar o custo real da solução
Existem estratégias genéricas para definir h:

Relaxar restrições do problema;

Resolver subproblemas de maneira exata.
Exemplo de problema
relaxado

Um bloco pode se mover do quadrado A
para o quadrado B se A é horizontal ou
verticalmente adjacente a B e B é vazio.



Um bloco pode se mover do quadrado A
para o quadrado B, se A é adjacente a B
Um bloco pode se mover do quadrado A
para B, se B está vazio
Um bloco pode se mover do quadrado A
para o quadrado B
Exemplo de subproblema
*
2
*
*
3
4
1
2
*
3
4
*
1
*
*
*
Estado inicial
Estado objetivo
Busca com Informação e
Exploração
“Busca heurística”
Busca LOCAL
Busca local

Existem problemas, que o caminho até
a solução é irrelevante:


N-rainhas;
Caixeiro Viajante

Preocupação apenas com o estado corrente e
estados vizinhos.
Vantagens de algoritmos de
busca local



Utilizam pouquíssima memória (geralmente
constante);
Freqüentemente encontram boa soluções em
espaços de busca infinitos (contínuos) – para os
quais, os algoritmos globais são inadequados.
As heurísticas da busca local não estimam a
distância do estado atual até o objetivo:

Vantajoso para problemas nos quais não é trivial estimar
esta distância.
Os algoritmos de busca local

Estado Corrente;

Problemas de Otimização;
Topologia de Espaço de Estados
Máximo global
Função
objetivo
Planície
Máximo local
Máximo local (plano)
Espaço de estados
Subida da encosta
Algoritmo básico
Função Subida-de-Encosta(problema) retorna um estado
Entrada: problema, um problema
Variáveis locais: corrente : Nó
vizinho: Nó
corrente = criar-NO(EstadoInicial[problema])
Repita
vizinho = acharMelhorSucessor(corrente)
se vizinho.funcaoObjetivo <= corrente.funcaoObjetivo então
retornar corrente;
fim se
corrente = vizinho;
Fim repita
Diagrama de Atividades
Subida da encosta
“Hill Climbing”

O algoritmo procura o pico, onde nenhum
vizinho tem valor mais alto.
“Subindo o everest na neblina com amnésia”
PASSO
Subida da Encosta
Exemplo Porco Espinho ou Ourico
Exemplo: N-Rainhas
Exemplo: 8-Rainhas






Estado inicial: colocação aleatória de uma
rainha por coluna
Operador: mudar um rainha de posição
h = número de pares de rainha que se atacam
Taxa de sucesso em encontrar
solução ótima: 14%
O que fazer quando não há melhor
vizinho
 Passos “laterais”
 Limite de 100 passos laterais
consecutivos permite atingir
taxa de 94%
O que fazer quando há muitos
vizinhos igualmente melhor
 Seleção aleatória
Subida da encosta
“Hill Climbing”



Move na direção do incremento da função,
terminando quando acha um pico
􀂄 Guloso: steepest ascent
􀂄 Problemas



􀂄 Máximos Locais;
􀂄 Máximo local plano;
􀂄 Planícies.
Variantes da Subida na
encosta



Subida de encosta estocástica: gera vários sucessores
(vizinhança – N(S)), e escolhe ao acaso, um que ofereça
melhora na função objetivo.
Subida de encosta pela primeira escolha: O primeiro
sucessor de N(S) gerado que oferece melhora, passa a ser
o novo estado corrente. É muito utilizada quando cada
estado possui milhares de sucessores.
Subida de encosta com reinício aleatório: “se não tiver
sucesso na primeira vez, continue tentando”. Gera estados
iniciais ao acaso, parando ao encontrar um objetivo.
Subida na encosta
Análise

O algoritmo é completo?



SIM, para problemas de otimizacao (onde cada NO tratado e’ um
estado completo, uma solucao)
NÃO, para problemas onde os NOS não são estados completos
 E.g. jogo dos 8-numeros
O algoritmo é ótimo?


TALVEZ, quando iterações suficientes forem permitidas...
NÃO, para problemas onde os NOS não são estados completos
Simulated Annealing

Simula o processo de arrefecimento
dos materiais
– Arrefecimentos lentos conduzem a produtos mais
puros, sem imperfeições

Normalmente é interpretado como o
algoritmo de busca local com os
melhores resultados
Simulated Annealing



Adaptação da Subida na encosta
Pode adotar um estado que oferece
perda (encosta abaixo).
Capaz de fugir de máximos locais.
Simulated Annealing
É necessário definir:
– Uma função objetivo/custo
– Qual o espaço de soluções S
– Uma vizinhança sobre o espaço de soluções N(s0)
– Função de redução de temperatura
– Uma temperatura inicial T0
Temperatura no SA


A temperatura, T0 inicialmente selecionada deve ser
elevada
Durante o processo de procura da solução, a temperatura
vai decrescendo com base numa função de redução de
temperatura
O processo de pesquisa da solução repete-se até que a temperatura
seja tão pequena que mais nenhum movimento seja aceito e o sólido
esteja no seu estado fundamental
Algoritmo
funcao RECOZIMENTO-SIMULADO(problema, escalonamento) retorna SOLUCAO
entradas: problema, um problema
escalonamento, um mapeamento de tempo para “temperatura”
variaveis locais: corrente, um NO
proximo, um NO
T, uma “temperatura” que controla a prob. de passos descendentes
corrente = CRIAR-NO (Estado-Inicial[problema])
para t =1 ate infinito faca
T = escalonamento[t]
se T = 0 entao retornar corrente
proximo = um sucessor de corrente selecionado ao acaso
∆E = VALOR[proximo] – VALOR[corrente]
se ∆E > 0 entao corrente = proximo
senao corrente = proximo somente com probabilidade e ^ ∆E/T
Diagrama de Atividades
Aceitação

Como a temperatura diminui com o
decorrer das iterações, a probabilidade de
aceitação também diminui, o que faz com
que não sejam aceitos movimentos
descendentes na função objetivo
Criterios de Parada


O número máximo de iterações admitidas
na resolução do problema
A temperatura, quando esta tomar valores
tão pequenos que não permitam mais
nenhuma alteração na solução
Exemplo da Mochila


Objetivo do problema – Maximizar o benefício face a
capacidade de peso admitido pela mochila
Dados do problema:
– Capacidade máxima da mochila: b=23
Inicializacao

Inicialização:








Selecionar uma solução s0 qualquer:
s0= (0 1 0 1 0) com valor f(s0)=6
Selecionar uma temperatura inicial T>0:
T0 = 31
Selecionar uma função de redução de temperatura
(escalonamento)
Tk=αTk-1 com 0 ≤ α ≤ 1 (Função Geométrica)
Nesta aplicação foi considerado o valor de α =0,8
Selecionar o número máximo de iterações admitida:

Nmax=3
Exemplo da Mochila
Selecionar um vizinho de s0 qualquer:
• s=(1 1 0 1 0)
∑ j=1 ate 5, Wj Sj = 4+5+9=18 < 23
f(s)=2+2+4=8
∆E = f(s)-f(s0)=8-6=2>0 ( Aceita-se a solução gerada s)
T1=α*T0=0,8*31=24,8
• Contador =contador+1=0+1=1
– A nova solução admitida é:
• s0= (1 1 0 1 0) com f(s0)=8
Exemplo da Mochila – Passo2
Selecionar um vizinho de s0 qualquer:
• s=(1 1 1 1 0)
∑ j=1 ate 5, Wj Sj = 4+5+7+9 = 25 >23 (Não pertence à região admissível)
• s=(1 0 0 1 0)
∑ j=1 ate 5, Wj Sj = 4+9= 13<23
f(s)=2+4=6
∆E = f(s)-f(s0)=6-8=-2<0 (∆E < 0, calcula-se valor aleatório x  U[0,1])
» x=0,43
» exp- (∆E/T1)=exp-(2/24,8)=0,923
» Como x<exp-(δ/T1) então não se rejeita s
• contador = contador +1=1+1=2
• T2=α*T1=0,8*24,8=19,84
Exemplo da Mochila – Passo3
s=(1 0 0 1 1)
∑ j=1 ate 5, Wj Sj = 4+9+6= 19<23
f(s)=2+4+4=10
∆E = f(s)-f(s0)=10-6=4>0 (Aceita-se a solução gerada s)
contador=contador+1=2+1=3 e
Nmax=3 logo verifica-se um dos critérios de paragem
Solução final considerada:
s0=(1 0 0 1 1) com f(s0)=10
Conclusao do Exemplo do SA
• O decréscimo permitido no valor da função objetivo levou a uma solução melhor;
•Verificou-se um decréscimo lento na temperatura;
• Se nas restrições iniciais o número de iterações fosse muito elevado, o processo
da busca da solução iria ser feito até que o valor da temperatura fosse muito perto
de zero de forma a não serem permitidas mais mudanças.
Exemplo da Mochila no Subida
na Encosta

Calculo do menor peso na mochila:







Estado inicial = 0 1 0 1 0
F = soma dos beneficios entre cada NO, na ordem escolhida
Operadores = permutar dois NOS quaisquer do caminho
Restricao = somente caminhos conectados sao estados validos
Estado final = NO onde valor de F e’ minimo
E1 = { 0 1 0 1 0 }
F(01010) = 6
E2 = { 1 1 0 1 0 }
F(11010) = 8!
Vantagens X Desvantagens
1.
Permite encontrar soluções
próximas da ótima, com um
esforço computacional baixo
2.
Método de busca local fácil de
adaptar
3.
Permite a degradação temporária
da função objetivo
4.
Converge para a solução ótima
1.
É necessário um conhecimento
profundo do problema para ajustar os
parâmetros convenientemente
2.
Os parâmetros mais adequados para
uma dada aplicação só podem ser
estabelecidos por experimentação
3.
Tanto a temperatura inicial como a
forma de arrefecimento influenciam os
resultados finais
4.
Não é possível saber se a melhor
solução encontrada é o ótimo global
Busca on-line

Diferença entre agente off-line e on-line


Off-line: calcula uma solução completa
antes de entrar no mundo real e depois
executam a solução sem recorrer as suas
percepções
On-line: opera pela intercalação de
computação e ação. Executa uma ação,
observa o ambiente e calcula a próxima
ação
Busca on-line

Problema de exploração


O agente no estado de ignorância usa suas
ações como experimentos para determinar
o que fazer em seguida.
Exemplos:


Um robô colocado num novo edifício e tem que
explorá-lo para elaborar um mapa que possa
ser usado com a finalidade de ir de A para B.
A descoberta gradual de um bebê de como o
mundo funciona
Agentes de busca on-line

Visão do agente



Ações (s): retorna todas as ações
permitidas do estado s
Testa-objetivo (s)
Custo (s,a,s´)
Agentes de busca on-line



O agente não tem acesso prévio ao
estado sucessor s´, nem ao valor do
custo de s para s´
Memoriza e atualiza o espaço de
estados
Só pode expandir um nó que ele ocupa
fisicamente
Exemplo

Problema de labirinto simples


Espaço de estados desconhecidos
Inicia em S e tem que alcançar G
Busca on-line em profundidade


Off-line: A medida que os nós são
expandidos, eles são retirados da borda
e a busca retorna para o nó seguinte
mais raso que ainda tem sucessores
inexplorados.
On-line: O agente tem que regressar
fisicamente.
Busca on-line em profundidade




Armazena um mapa das relações entre ações
e estados.
Resultado [a, s]
O agente mantém uma tabela, para cada
estado, que lista os estados predecessores
que o agente ainda não regressou.
Se o agente esgotar todos os estados que ele
pode regressar, a busca estará completa.
Hill-climbing



Pelo fato de manter apenas um estado
corrente na memória, já é um algoritmo
de busca on-line.
Fica paralisada (máximos locais)
Reinícios aleatórios não podem ser
usados, pois o agente não tem como se
transportar para um novo estado.
Hill-climbing



Alternativa: Percurso aleatório para
explorar ambiente
Desde que o espaço seja finito, encontra
um objetivo ou completa a exploração
Porém, o processo pode ser muito lento
ATRA*





Aprendizado em Tempo Real A*
Adição de memória em vez de
aleatoriedade
Armazena a melhor estimativa atual H(s)
O agente vai para o nó vizinho mais
promissor e atualiza o nó anterior:
H(s) = C(s,a,s’) + H(s’)
ATRA*
ATRA*
ATRA*
ATRA*
ATRA*
UML

Heuristic Search Class Diagram
goal = true implies full = true
Problem
PbGraph
State
*
*
initial: Boolean
goal: Boolean
*
PbNode
MethodArc
*
*
PathSolution
*
*
MethodGraph
OptimalPathSolution
NodeSolution
Solution
OptimalNodeSolution
Method
search(pb: Problem):Solution
gensuc(n:Node):Node[*]
getFringe(g:MethodGraph):Node[*]
OptimalSolution
PathSolution.last().PbNode.State.goal = true
OneShotMethod
DFS
BFS
IterativeMethod
IterativeDeepening
Full State Problem
all suc from partial state to partial state
except suc to goal state
*
* suc
MethodNode
expanded:Boolean
Path
action:string
cost: real
*
*
Partial State Problem
PbArc
suc
ExhaustiveMethod
HeuristicMethod
LocalMethod
GlobalMethod
Busca heurística
Dúvidas?