Aula 05 Busca com informação - Unespservicosgasi.sorocaba.unesp.br/assimoes/lectures/iac/downloads/bu… · Aula 05 Busca com informação Prof. Dr. Alexandre da Silva Simões Inteligência

1

Aula 05 Busca com informação Prof. Dr. Alexandre da Silva Simões

Inteligência Artificial - Prof. Dr. Alexandre da Silva Simões 2 9-11

Revisão Principais estratégias de busca sem informação: busca em

amplitude e profundidade

Estratégias derivadas: • Busca com custo uniforme • Busca em profundidade limitada • Busca de aprofundamento iterativo • Busca bidirecional

1

2 3 4

5 6 7 X

X

1

2

3 4

5 6

7 X


Busca baseada em informação

Como um agen te pode u t i l i za r informações sobre o espaço de estados para evitar que os algoritmos se percam?


Estratégia geral

• Busca pela melhor escolha (Best-First Search): um nó é selecionado para expansão com base em uma função de avaliação f(n) que mede a distância até o objetivo

• Faz uso de uma função heurística

2


Heurística

• Palavra originada do grego “heuriskein”1 (descobrir).

• Forma mais comum de aplicar conhecimento adicional do problema ao algoritmo de busca

1É atribuída a Arquimedes a passagem de gritar “heureka” (“eu descobri!”) quando este descobriu o princípio da flutuação


Função heurística

• Função que descreve o quão bom é um estado • Guia algoritmos baseados em busca pela melhor

escolha na direção mais promissora, sugerindo que caminho seguir

• Matematicamente: • h(n) = custo estimado do caminho mais econômico do nó n até

um nó objetivo • Se n é objetivo, então h(n)=0

• Problema: • É escolhida caso a caso, de acordo com a natureza do

problema


Algoritmos

• Estratégias de busca com informação: exploram sistematicamente o espaço de busca • Busca gulosa pela melhor escolha • A*

• Algoritmos de busca local: operam usando um único estado corrente • Busca de subida de encosta • Busca de têmpera simulada • Busca em feixe local • Algoritmos genéticos


Busca gulosa pela melhor escolha

• Tenta expandir o nó mais próximo da meta, partindo do princípio que isso levará a uma solução mais rápida

• A avaliação dos nós é feita utilizando a função: f(n)=h(n)

• Exemplo: • Problema: ir de Arad a Bucareste • Heurística: distância em linha reta. h(n) é a distância

em linha reta até Bucareste.

3


Busca gulosa: exemplo







4


Busca gulosa: avaliação

• Complexidade: Não expandiu nenhum nó fora do caminho da solução: baixo custo de busca!

O caminho passando por Sibiu e Fagaras é 32 quilômetros mais longo do que passando por Rimnicu Vilcea e Pitesti.



• Complexidade: Não expandiu nenhum nó fora do caminho da solução: baixo custo de busca!

• Otimização: O caminho passando por Sibiu e Fagaras é 32 quilômetros mais longo do que passando por Rimnicu Vilcea e Pitesti. Não é ótimo.

310

278



• Desempenho é muito dependente da escolha de uma boa heurística

• Semelhante à busca em profundidade: • Prefere seguir um único caminho até o objetivo, mas voltará ao

encontrar um beco sem saída • Não é ótima e é incompleta (pode entrar em um caminho infinito

se não houver o cuidado de detectar estados repetidos) • Complexidade de tempo e espaço no pior caso: O(bm).

Contudo, uma boa função heurística pode reduzir drasticamente esta complexidade


A*

• Forma mais amplamente conhecida de busca pela melhor escolha

• Avalia nós fazendo: f(n) = g(n) + h(n)

• g(n): custo para alcançar cada nó • h(n): custo para ir do nó até o objetivo

5


A*: exemplo


A*: exemplo


A*: exemplo


A*: exemplo

6


A*: exemplo


A*: exemplo


A*: Avaliação

• Para encontrar uma solução de baixo custo, parece razoável experimentar primeiro o nó com o menor valor de g(n)+h(n)

• Mais do que razoável, se a função heurística h(n) satisfizer certas condições a busca A* será ao mesmo tempo completa e ótima...


Heurística admissível

• A* será ótima se o espaço de busca for uma árvore e h(n) for uma heurística admissível • Heurística admissível: nunca superestima o custo

para alcançar o objetivo. É uma função otimista. Exemplo:

• Distância em linha reta: a estrada entre duas cidades pode ser mais comprida do que a distância em linha reta, mas nunca menor (estimativa otimista).

7


Consistência (monotonicidade)

• A* será ótima se o espaço de busca for um grafo1 e h(n) for uma heurística consistente (ou monotônica) • Uma heurística h(n) é consistente (ou monotônica)

se para todo nó n e todo sucessor n’ de n gerado por qualquer ação a, o custo estimado de alcançar o objetivo a partir de n não é maior que o custo do passo de se chagar a n’ somado ao custo estimado de alcançar o objetivo a partir de n’, ou seja:

1 grafo = árvore + lista de nós visitados Inteligência Artificial - Prof. Dr.

Alexandre da Silva Simões 26 9-11

Consistência (monotonicidade)

Para todo nó n: h(n) ≤ c(n, a, n’)+h(n’)

Observações: • Toda heurística consistente é admissível • Frequentemente quando h(n) é admissível, é também

consistente

n

n’

g h(n)

c(n,a,n’) h(n’) n: nó n‘: sucessor de n g: meta a: ação

Exercícios…

Inteligência Artificial - Prof. Dr. Alexandre da Silva Simões 27 9/12/11


Nos do is exerc íc ios an te r io res , ambos encontraram a mesma resposta. Contudo, em apenas um deles pode-se garantir que a resposta é ótima. Qual? Por que?

Exercício 3

8


Exercício 1: heurística

0

4

3 5 5

3 3 4

2 3 4 3 3

1 3

2

1

0

f(n)=5(3+2)

2 31 8 47 6 5

1 2 3 8 4

7 6 5 f(n)=5(4+1)

1 2 3 8 4 7 6 5 f(n)=5(5+0)

h(n)=2

c(n,a,n’)=1

h(n’)=1

h(n) = c(n,a,n’)+h(n’)

heurística consistente, portanto admissível

Valores de heurística

h(n) c(n,a,n’)

h(n)


Exercício 2: heurística 4

3,1 5,1 5,1

3,2 3,2 4,2

2,3 3,3

1,4 3,4

0,5

h(n)=2

c(n,a,n’)=0,1

h(n’)=1

h(n) > c(n,a,n’)+h(n’)

2

1

0

f(n)=2,3(0,3+2)

2 31 8 47 6 5

f(n)=1,4(0,4+1)

1 2 3 8 4

7 6 5

1 2 3 8 4 7 6 5

f(n)=0,5(0,5+0) A função é pessimista, e podem haver nós de custo menor do que o esperado acima da meta encontrada!

Valores de heurística

h(n) c(n,a,n’)

h(n)


Consistência: considerações

• Se a função é consistente, então os valores de f ao longo de qualquer caminho são não-decrescentes

• Se a seqüência de nós expandido por A* está em ordem não-decrescente, então o primeiro nó objetivo selecionado para expansão tem de ser a solução ótima, pois todos os nós posteriores serão pelo menos tão dispendiosos quanto ele


Custos como contornos • Se f é consistente, os custos

apresentam contornos no espaço de estados, semelhantes a um mapa topográfico

• Na busca de custo uniforme (A* usando h(n)=0) as faixas serão circulares em torno do estado inicial

• Com heurísticas mais precisas, as faixas se alongarão em direção ao estado objetivo

• Considerando que o A* expande o nó de borda que tem o menor custo de f, podemos verificar que uma busca A* diverge a partir do nó inicial, acrescentando nós em faixas de custo crescente

9


A*: Considerações

• Completa • Ótima • Em geral esgota o espaço (memória) bem

antes de esgotar o tempo, pois mantém todos os nós gerados na memória


AIA*

• Aprofundamento iterativo A* • O corte utilizado é o custo de f(g+h) em vez da

profundidade • A cada iteração o valor de corte é o menor custo

de f de qualquer nó que tenha excedido o corte na iteração anterior

• Evita sobrecarga substancial associada à manutenção de uma fila ordenada de nós


BRPM

• “Busca recursiva pelo melhor” • Tenta imitar a operação da busca pela melhor escolha-

padrão, mas utiliza apenas espaço linear • Estrutura semelhante à busca recurs iva em

profundidade, porém em vez de continuar a descer indefinidamente pelo caminho atual, ela controla o valor de f do melhor caminho alternativo disponível a partir de qualquer ancestral do nó atual. Se o nó atual exceder esse limite, a recursão retornará ao caminho alternativo


Funções heurísticas

• Custo da solução média gerada: 22 passos • Fator de ramificação ≅ 3 • Número de estados examinados em uma busca

sem informação: 322 = 3,1 x 1010 estados

10


Funções heurísticas

• Heurísticas utilizadas no quebra-cabeças de oito peças: • h1: o número de blocos em posições erradas.

Para o estado inicial, h1=8. • h2: a soma das distâncias (horizontal e

vertical: distância Manhattan) dos blocos de suas posições objetivo. Para o estado inicial:

h2 = 3+1+2+2+2+3+3+2 = 18


Função heurística: avaliação Número médio de nós expandidos utilizando algoritmo A* com h1 e

h2 e busca por aprofundamento iterativo (BAI) para 1.200 problemas aleatoriamente gerados

d BAI A* (h1) A* (h2) 2 10 6 6

4 112 13 12

6 680 20 18

8 6384 39 25

10 47127 93 39

12 3644035 227 73

14 - 539 113

16 - 1301 211

18 - 3056 363

20 - 7276 676

22 - 18094 1219


Algoritmos de busca local

• Algoritmos de busca: exploram sistematica-mente espaços de busca. Mantêm um ou mais caminhos na memória registrando-se as alternativas que foram exploradas. Quando um objetivo é encontrado, o caminho até esse objetivo também constitui uma solução para o problema

• Algoritmos de busca local: classe de algoritmos que pode ser utilizada se o caminho até a solução não é importante


Algoritmos de busca local

• Utilizam um único estado (estado corrente) e em geral se movem apenas para os vizinhos desse estado

• Objetivo: encontrar um estado de acordo com uma função objetivo

• Vantagens: • Usam pouquíssima memória • Podem encontrar soluções razoáveis em grandes ou

infinitos espaços de estados para os quais algoritmos sistemáticos são inadequados

11


Problemas de otimização

• O objetivo é encontrar o melhor estado de acordo com uma função objetivo


Busca de subida na encosta

• Laço repetitivo que se move de forma contínua no sentido do valor crescente, isto é, encosta acima

função SUBIDA-DE-ENCOSTA(problema) retorna um estado que é um máximo local entradas: problema, um problema variáveis locais: corrente (um nó) e vizinho (um nó)

corrente ← CRIAR-NÓ(ESTADO-INICIAL[problema]) repita vizinho ← um sucessor de corrente com valor mais alto se VALOR[vizinho] ≤ VALOR[corrente] então retornar ESTADO[corrente] corrente ← vizinho


Subida na encosta: exemplo

• Problema: 8 rainhas • Cada estado tem 8 rainhas no tabuleiro, 1 por coluna • Função sucessora retorna todos os estados possíveis

gerados pela movimentação de uma única rainha para outro quadrado da mesma coluna (cada estado tem 8x7=56 sucessores)

• A função de custo da heurística h é o número de pares de rainhas que estão atacando umas às outras

• Soluções têm h=0


Subida na encosta: calculando h

h=4

12



h=4+3



h=4+3+3



h=4+3+3+3



h=4+3+3+3+2

13



h=4+3+3+3+2+1



h=4+3+3+3+2+1+1 = 17


Subida na encosta: mínimo local

Esq. Estado com h=17, mostrando o valor de h para cada sucessor possível obtido pela movimentação de uma rainha dentro de sua coluna. As casas marcadas são o melhor movimento Dir. Mínimo local: o estado tem h=1, mas todo sucessor tem um custo mais alto


Subida na encosta: variações

• Algoritmo com grande número de variações: • Subida na encosta estocástica: escolhe ao acaso

entre os movimentos encosta acima • Subida na encosta pela primeira escolha: subida

na encosta estocástica gerando sucessores ao acaso até gerar sucessor melhor que o estado corrente

• Subida na encosta com reinício aleatório: série de buscas de subida de encosta a partir de estados iniciais gerados ao acaso

...

14


Busca de têmpera simulada • Um algoritmo de subida na encosta que nunca faz movimentos

“encosta abaixo” sem dúvida é incompleto (máximo local) • Percurso puramente aleatório é completo, porém extremamente

ineficiente • Têmpera simulada: combina esses dois algoritmos. Idéias gerais:

• Mudança do ponto de vista de “subida na encosta” para “descida de gradiente”

• Para colocar uma bola de ping-pong na fenda mais profunda em uma superfície acidentada basta soltar a bola. Quando ela parar, agita-se a bola para que ela saia do mínimo local

• Têmpera, em metalurgia, é o processo para endurecer metais e vidro aquecendo-os a altas temperaturas e depois esfriando-os gradualmente

• Idéia: começar a agitar com força (alta temperatura), e reduzir gradualmente a intensidade da agitação (baixar a temperatura)


Têmpera simulada: algoritmo função TÊMPERA-SIMULADA (problema, escalonamento) retorna um estado solução entradas: problema (um problema), escalonamento (um mapeamento de tempo

para “temperatura”) variáveis locais: corrente (um nó), próximo (um nó), T (uma “temperatura” que

controla a probabilidade de passos descendentes”)

corrente ← CRIAR-NÓ(ESTADO-INICIAL([problema]) para t ←1 até ∞, faça: T ← escalonamento[t] //diminui o valor de T com o tempo se T=0 então retornar corrente próximo ← um sucessor de corrente selecionado ao acaso ΔE ← VALOR[próximo] – VALOR[corrente] se ΔE>0 então corrente ← próximo //movimento melhora a situação! senão corrente ← próximo somente com probabilidade eΔE/T


Têmpera simulada: considerações

• Laço de seleção interno muito semelhante à subida na encosta. Porém, em vez de escolher o melhor movimento, ele escolhe um movimento aleatório

• Se o movimento melhorar a situação, ele sempre será aceito. Se piorar, o algoritmo aceitará o movimento com alguma probabilidade menor do que 1

• A probabilidade se reduz: • Exponencialmente com a “má qualidade do movimento” • À medida que a temperatura T se reduz: movimentos ruins têm

maior probabilidade de serem permitidos no início, quando a temperatura é alta, e depois se tornam mais improváveis


Busca em feixe local

• Em vez de manter um único estado na memória, mantém o controle de k estados

• Começa com k estados gerados aleatoriamente. Em cada passo são gerados todos os sucessores de todos os k estados. • Se qualquer um deles for um objetivo, o algoritmo

para • Caso contrário, ele selecionará os k melhores

sucessores a partir da lista completa e repetirá a ação

15


Algoritmos genéticos

• Variante de busca em feixe estocástica, na qual os estados sucessores são gerados pela combinação de dois estados pais

• Começam com um único conjunto de k estados gerados aleatoriamente chamado população

• Cada estado (ou indivíduo) é representado como uma cadeia sobre um alfabeto finito (usualmente composto por 0s e 1s)

• Cada estado é avaliado pela função de avaliação (ou função de fitness), que retorna valores mais altos para estados melhores


Algoritmos genéticos

• Os melhores indivíduos são escolhidos para reprodução

• Para cada par é escolhido um ponto de crossover dentre as posições da cadeia

• Os descendentes são gerados com uma pequena mutação aleatória


Algoritmos genéticos: exemplo

• Problema: 8 rainhas • Estado: representado em 8 dígitos, cada qual

representando a posição de uma rainha em uma coluna. Ex: [8 6 4 2 7 5 3 1]

8

1


• Função de fitness: deve retornar um valor maior para estados melhores. Exemplo: número de pares de rainhas não-atacantes (28 é a solução do problema).


f = 6 +

16




f = 6 + 6 +




f = 6 + 6 + 5 +




f = 6 + 6 + 5 + 4 +




f = 6 + 6 + 5 + 4 + 3 +

17




f = 6 + 6 + 5 + 4 + 3 + 2 +




f = 6 + 6 + 5 + 4 + 3 + 2 + 1 = 27


• Pares para reprodução: escolhidos de acordo com as probabilidades da função de fitness

[24748552] (f=24) 35,8% [32752411] (f=23) 34,3% [24415124] (f=20) 29,8%

Probabilidades para escolha Inteligência Artificial - Prof. Dr.

Alexandre da Silva Simões 72 9-11

T = 67 100%

Algoritmos genéticos: exemplo • O ponto de crossover: escolhido ao acaso dentre as posições

na cadeia

• Mutação: parte do novo estado gerado pode sofrer uma mutação aleatória em relação ao produto do crossover.


Ponto de crossover

18




Atividades extra-classe

• Leitura: • RUSSELL, S. NORVIG, P. Inteligência Artificial.

Campus. Capítulo 4, exceto os tópicos: • Busca heurística limitada pela memória • Aprendizagem para fazer buscas melhores • Busca local em espaço contínuo em diante.

• Exercícios recomendados: 4.1 a 4.12, 4.15 a 4.17

Documents

Aula 05 Busca com informação - Unespservicosgasi.sorocaba.unesp.br/assimoes/lectures/iac/downloads/bu… · Aula 05 Busca com informação Prof. Dr. Alexandre da Silva Simões Inteligência