Inteligência Artificial (SI 214)
Aula 4
Resolução de Problemas por meio de Busca Heurística
Prof. Josenildo Silva [email protected]
2015
© 2012-2015 Josenildo Silva ([email protected])
Este material é derivado dos slides de Hwee Tou Ng, disponível no site
do livro AIMA (Russel & Norvig) para professores e instrutores.
http://aima.eecs.berkeley.edu/slides-ppt
• Busca cega é eficaz, entretanto não é eficiente: gerar muitos nodos desnecessários
• Grande espaços de estados são inviáveis
• Como cortar caminho no espaço de estado em direção ao objetivo?
Direto ao ponto
Busca do Melhor Primeiro
• Use uma função de avaliação f(n) para cada nodo
• Ordenar os nodos na borda (fringe) em ordem decrescente de f(n)
Melhor Primeiro Guloso
• Função de avalição f(n) = heuristica
Estimativa do custo restante, de n até o objetivo
• Ex: hSLD(n) = straight-line distance (distancia em linha reta)
Melhor Primeiro Guloso
• Melhor Primeiro Guloso expande o nodo que parece estar mais próximo do objetivo
Propriedades da busca melhor primeiro gulosa
• Completo? Não, pois pode ficar preso em laços
• Tempo? O(bm), mas uma boa heurística pode melhorar dramaticamente
• Espaço? O(bm) pois mantém todos os nodos em memória
• Ótimo? Não
Busca A*
• Ideia: evitar expandir caminhos que já se mostraram caros
• Função de avaliação f(n) = g(n) + h(n)
g(n) = custo real do início até nodo n
h(n) = custo estimado de n até o objetivo
Heuristicas Admissíveis
• Uma heuristica h(n) é admissivel se para todo nodo n, h(n) ≤ h*(n), onde h*(n) é o verdadeiro custo para chegar ao objetivo a partir de n.
Heuristicas Admissíveis
• Uma heurística admissível nunca superestima o custo para atingir o objetivo
• Ex: hSLD(n) nunca superestima a distancia rodoviária
A* é ótimo (prova)
• Suponha que haja um objetivo subótimo G2 , gerado e que está na borda. Seja n um nodo não expandido na borda tal que n está no caminho mais curto para o objetivo G.
• f(G2) = g(G2), pois h(G2) = 0 • g(G2) > g(G), pois G2 é subótimo • f(G) = g(G), pois h(G) = 0 • f(G2) > f(G), por definição •
A* é ótimo
• Se o bjetivo subótimo G2 está na borda.
• E n está no caminho mais curto para G.
• Então f(G2) > f(G) pois é subótimo e f(G2)> f(n),
• Logo A* nunca selecionará G2 para expansão.
Heurísticas Consistentes
• Uma heuristica é consistente se para cada nodo n, todos os successores n' de n gerados por uma ação a, h(n) ≤ c(n,a,n') + h(n')
• Se h é consistente, temos • f(n') = g(n') + h(n') = g(n) + c(n,a,n') + h(n') ≥ g(n) + h(n) = f(n) • i.e., f(n) é não-decrescente ao longo de qualquer
caminho. • Teorema: se h(n) é consistente, A* é ótimo
usando GRAPH-SEARCH
A* é ótimo (grafos)
• A* expande nodos em order of increasing f value
• Gradualmente adiciona "f-contours" dos nodos
• Contorno i tem todos os nodos com f=fi, where fi < fi+1
Propriedades do A*
• Completo? Sim (a menos que haja infinitos nodos com f ≤ f(G))
• Tempo? Exponencial
• Espaço? Mantém todos os nodos na memória
• Otimo? Sim
Heurísticas Admissíveis
• Ex: 8-puzzle: h1(n) = numero de peças fora do lugar h2(n) = total da distancia de Manhattan
• Total de peças fora de posição
• h1(S) = ? • h2(S) = ?
Heurísticas Admissíveis
• Ex: 8-puzzle: h1(n) = numero de peças fora do lugar h2(n) = total da distancia de Manhattan
• Total de peças fora de posição
• h1(S) = 8 • h2(S) = 3+1+2+2+2+3+3+2 = 18
Dominância
• Se h2(n) ≥ h1(n) para todos os n (ambas admissiveis), então h2 domina h1
• A dominante é melhor para busca
Dominância
• Se h2(n) ≥ h1(n) para todos os n (ambas admissiveis), então h2 domina h1
• A dominante é melhor para busca
Exemplo
• Média de nodos expandidos do 8-puzzle: • Profundidade d=12
• IDS = 3,644,035 nodes • A*(h1) = 227 nodes • A*(h2) = 73 nodes
• Profundidade d=24 • IDS = too many nodes • A*(h1) = 39,135 nodes • A*(h2) = 1,641 nodes
Exemplo
• Média de nodos expandidos do 8-puzzle: • Profundidade d=12
• IDS = 3,644,035 nodes • A*(h1) = 227 nodes • A*(h2) = 73 nodes
• Profundidade d=24 • IDS = too many nodes • A*(h1) = 39,135 nodes • A*(h2) = 1,641 nodes
Relaxamento de problemas
• Elimine restrições
• O custo em um problema relaxado é uma heurística admissível no original
Exemplo: 8 puzzle
• Relaxamento 1: gera h1
uma peça pode ser movida para qualquer lugar.
• Relaxamento 2: gera h2
as peças possam ser movidas para qualquer quadrado adjacente
Algoritmos de Busca Local
• Soluções em algorimtos de busca clássicos são caminhos.
• Entretanto muitos problemas exigem somente o estado final.
• E daí?
Algoritmos de Busca Local
• Economia de espaço
Mantenha na memória um nó apenas e tente melhorá-lo.
• Podemos resolver instancias maiores
Exemplo: n-rainhas
• Coloque n rainhas em um tabuleiro n × n sem que haja duas rainhas na mesma linha, coluna ou diagonal
Escalada da montanha: 8-rainhas
• h = número de pares de raínhas em ataque mútuo.
• h = 17 no estado da figura acima
É preciso fugir do ótimo ...
• Algoritmos locais terminam quando todos os vizinhos são piores que o estado atual
• Entretanto o atual pode ser um ótimo local e não global
• Como fugir desta armadilha?
Arrefecimento simulado
• Ideia: escapar de maximos locais permitindo movimentos “ruins” mas gradualmente decaindo sua frequencia
Propriedades da busca por arrefecimento simulado
• Se T decresce devagar o suficiente, então a busca por arrefecimento simulado vai encontar um global ótimo com probabilidade proxima de 1
• Muito utilizado em layout VLSI, escalas de companias areas, etc
Busca por Feixe Local
• Mantém k estados e não apenas um.
• Começa com k estados gerados randomicamente
• A cada iteração, todos os sucessores de todos os estados k são gerados
• Se algum estado é um estado objetivo, pare. Senão, selecione os melhores k sucessores da lista completa e repita.
Algoritmos Genéticos
• Um estado sucessor é gerado através da combinação de dois outros estados pais.
• Inicia com k estados gerados randomicamente (população)
• Um estado é representado como uma string sobre um alfabeto finito (geralmente 0 e 1s)
• A função de avaliação (fitness) dá valores maiores para estados melhores.
• Produz a próxima geração de estados por seleção, crossover e mutação.
Algoritmos genéticos
• Função de fitness: numero de pares de rainha que não se atacam (min = 0, max = 8 × 7/2 = 28)
• 24/(24+23+20+11) = 31%
• 23/(24+23+20+11) = 29% etc