Busca com Informação e
Exploração
“Busca heurística”
Humberto César Brandão de Oliveira
[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 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
Características da Busca
Gulosa pela melhor escolha


Não é ótima (como dado no exemplo
anterior);
É incompleta;
Porque incompleta?
Exemplo: Origem: Neamt. Destino: Fagaras
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*
Distância em linha
reta para Bucharest:
449
75 + 374
239
239 + 178
140 + 253
220
417
118 + 329
447
393
220 + 193
413
317
418
366
415
455
496
336 + 160
317 + 98
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*)



A atividade constante de paginação causa
degradação do desempenho do sistema .
É 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.
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.
Heurísticas de aprendizagem a
partir da experiência


Utiliza-se aprendizado indutivo;
São utilizadas técnicas como o
aprendizado por reforço para
diagnosticar o valor de h(n).
Busca local

Existem problemas, que o caminho até
a solução é irrelevante:

N-rainhas;
Caixeiro Viajante
Roteamento de Veículos

Timetabling


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 sistemáticos são inadequados.
A busca local não estima a distância do estado
atual até o objetivo:

Em alguns problemas não é trivial (ou impossível)
estimar esta distância.
Conceitos básicos
Máximo global
f(x)
Planície
Máximo local
Máximo local (plano)
x
Subida na encosta
“Hill Climbing”

O algoritmo procura o pico, onde nenhum
vizinho tem valor mais alto.
Subida na encosta
Algoritmo básico
Função SubidaNaEncosta(problema) retorna um ótimo local
Entrada: um problema
Variáveis:
corrente : Nó
vizinho: Nó
corrente = criarEstadoInicial(problema)
Repita
vizinho = acharMelhorSucessor(corrente)
se vizinho.funcaoObjetivo <= corrente.funcaoObjetivo então
retornar corrente;
fim se
corrente = vizinho;
Fim repita
Variações 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: Reinicia a subida
várias vezes, até encontra um valor satisfatório. Muito
utilizado em redes neurais (técnica para melhor adaptar os
pesos sinápticos do backpropagation).
Subida na encosta
Análise



O algoritmo é completo?
 SIM, uma vez que cada nó tratado pelo algoritmo é
sempre um estado completo (uma solução)
O algoritmo é ótimo?
 TALVEZ, quando iterações suficientes forem permitidas...
O sucesso deste método depende muito do formato da
superfície do espaço de estados:
 Se há poucos máximos locais, o reinício aleatório
encontra uma boa solução rapidamente
Recozimento simulado




Meta heurística baseada no
resfriamento de metais.
Adaptação da Subida na encosta
Pode adotar um estado que oferece
perda (encosta abaixo).
Capaz de fugir de ótimos locais.
Quando descer a encosta?

O algoritmo admite descidas desde que
estas não sejam ”bruscas demais”
(decisão tomada em função do tempo)
Busca em feixe local





Passo 0: Começa com k estados gerados
aleatoriamente.
Passo 1: Os sucessores dos k estados são
calculados.
Passo 2: Caso algum estado seja o objetivo, o
algoritmo pára.
Passo 3: São selecionados os melhores k
sucessores de todos os estados para o
próximo passo.
Passo 4: Volta ao passo 1.
Busca em feixe local

Muito parecido com a execução paralela de
uma busca local, mas o algoritmo oferece
uma vantagem:

Ele concentra a busca onde são oferecidas as
melhores soluções (onde ele supõe que pode
encontrar os melhores valores para o
problema).
Exemplo:







f(k0) = 25 -> N(k0) = S1, S2, S3
f(k1) = 49 -> N(k1) = S4, S5, S6, S7
f(k2) = 52 -> N(k2) = S8, S9
________________________
f(S1) = 26; f(S2) = 23; f(S3) = 30;
f(S4) = 49; f(S5) = 48; f(S6) = 53 ; f(S7) = 56;
f(S8) = 50; f(S9) = 55;
Algoritmos Genéticos


Baseados na teoria da evolução das
espécies de Darwin.
É uma variação da busca em feixe local.
Algoritmos Genéticos
Conceitos básicos

População Inicial

Gerada Randomicamente – tamanho m.

Direcionada:


Em alguns problemas, encontrar um indivíduo
válido é uma problema de otimização, portanto
necessitam de heurísticas para gera-lo.
Exemplos: Problema de Roteamento de
Veículos com Janela de Tempo, Timetabling
(horários escolares).
Algoritmos Genéticos
Conceitos básicos

Seleção dos Pais:

Inclui o passo de avaliação dos indivíduos:

Fitness (mensura o quanto cada indivíduo está
adaptado ao ambiente).

Pode ter executada por diferentes técnicas:


Roleta (probabilístico)
Torneio entre indivíduos
Algoritmos Genéticos
Seleção dos Pais: Adaptabilidade
Algoritmos Genéticos
Conceitos básicos

Recombinação (cruzamento)


Merge entre dois ou mais indivíduos (n:1):
r(i1, i2, ...) = ix
A maneira com que é feito depende da
representação dos indivíduos:





Binária
Inteira
Ponto flutuante
Objetos Compostos
Acrescenta indivíduos na população
Recombinação
Exemplo:
+
=
Algoritmos Genéticos
Conceitos básicos

Mutação

Ocorre na relação de 1:1


A maneira com que é feito depende da
representação dos indivíduos:





m(i1) = ix
Binária
Inteira
Ponto flutuante
Objetos Compostos
Não afeta no tamanho da população
Mutação
Exemplo:
Seleção dos sobreviventes
Exemplo






População
S1 -> f(S1) = 10;
S2 -> f(S2) = 12;
S3 -> f(S3) = 11;
NS1 -> f(NS1) = 13;
NS1 -> f(NS2) = 9;
Nova população:
S1 -> f(S1) = 12;
S2 -> f(S2) = 13;
S3 -> f(S3) = 10;
Algoritmos Genéticos
Resumo
Característica de sucesso para o
algoritmo genético: Diferencial

A recombinação eleva a qualidade da
busca, pois oferece uma maior diversidade
para a população de indivíduos.
Busca local em espaço
contínuo

Origem no século XVII (Newton e
Leibniz).

Função sucessor gera infinitos novos
estados
Busca local em espaço
contínuo. Exemplo:
Problema:
 Objetivo: Construir 3 aeroportos no estado
de modo a minimizar a distância de todas
as cidades ao aeroporto mais próximo.
 Espaço de busca: R2
Encontrar os melhores
(x1, y1)(x2, y2)(x3, y3) segundo o objetivo

Exemplo: Aeroportos


Para solucionar o problema, é utilizado o
gradiente da função, onde é fornecido a direção
e a magnitude da inclinação mais íngreme do
problema.
Solução corrente = solução corrente + alfa *
gradiente, onde alfa é uma constante
suficientemente pequena, para obter precisão no
resultado.
Busca local em espaço contínuo
Exemplo bidimensional
Como encontrar o máximo?
f(x) = y;
f(x)
y’ = 0
Igualando a tangente a 0, podemos
obter TODOS os pontos de máximo e
mínimo da função y=f(x).
x
Busca local em espaço
contínuo – outra solução

Em problemas de espaços de busca
contínuos podemos tornar o ambiente
discreto e aplicar algoritmos como a
subida na encosta, recozimento simulado
ou algoritmos genéticos, para fugir de
ótimos locais.
Busca on-line



Algoritmos de busca on-line não podem
calcular a vizinhança de um estado.
Eles só conhecem um estado quando
estão nele.
São baseados em ações. Primeiro
executa uma ação, depois observa o
ambiente.
Analogia – Busca on-line

Bebê

Pode tomar várias ações, conhece algumas
conseqüências. Está em estado de
exploração do mundo.
Busca on-line

Visão do agente:


Ações(n): Retorna todas as ações que o
agente pode tomar a partir do estado n;
custo(n,a,n’): apenas pode ser utilizado
quando o agente já tomou a ação a no
estado n anteriormente;
Busca on-line


Em uma busca off-line, o sistema para
retroceder apenas retira elementos da
fila ou desempilha nós para explorar
outras ramificações da busca;
Na busca on-line, o agente necessita
retroceder fisicamente até o estado
desejado.
Busca on-line

Voltando a busca local....

A busca local já é um agente de busca online, pois “enxerga” apenas o seu estado
atual (não possui memória);
Aprendizado em busca on-line


O agente pode armazenar um mapa do
ambiente (como no mundo de
Wumpus);
O aprendizado deve considerar se o
mundo é determinístico ou não;
Potencial de agentes de busca
on-line

Fatores aumentam a qualidade dos agentes
de busca on-line:



Conhecimento;
Raciocínio;
Tais artefatos fazem o agente capaz de
prever a função sucessora de cada estado.
Busca heurística
Dúvidas?