Métodos de Busca Heurística

Embed Size (px)

DESCRIPTION

UPE – Caruaru – Sistemas de Informação Disciplina: Inteligência Artificial Prof.: Paulemir G. Campos. Métodos de Busca Heurística. Este material é uma adaptação do original elaborado por Ana Emília (UFPE / CIn, 2003). Roteiro da Aula. Estratégias de Busca com Informação Funções Heurísticas - PowerPoint PPT Presentation

Text of Métodos de Busca Heurística

  • Mtodos de Busca Heurstica

    UPE Caruaru Sistemas de InformaoDisciplina: Inteligncia ArtificialProf.: Paulemir G. CamposEste material uma adaptao do original elaborado por Ana Emlia (UFPE/CIn, 2003)

  • Roteiro da AulaEstratgias de Busca com Informao

    Funes Heursticas

    Algoritmos de Busca Local e Problemas de Otimizao

    Referncias

  • Busca Heurstica: EstratgiaEssa funo de avaliao estima o custo de caminho do n atual ao objetivo mais prximo utilizando uma funo heurstica.Qual dos ns supostamente o mais prximo do objetivo?Estratgias de busca heurstica utilizam conhecimento especfico do problema na escolha do prximo n a ser expandido e aplicam uma funo de avaliao a cada n na fronteira do espao de estados.Como encontrar um barco perdido?no podemos procurar no oceano inteiro...

  • Busca Heurstica:Funo HeuristicaFuno heurstica h(n) estima o custo do caminho entre o n n e o objetivodepende do problemaExemplo: encontrar a rota mais barata de Jeremoabo a Cajazeirashdd(n) = distncia direta entre o n n e o n final.Como escolher uma boa funo heurstica?ela deve ser admissvel i.e., nunca superestimar o custo real da soluoDistncia direta (hdd) admissvel porque o caminho mais curto entre dois pontos sempre uma linha reta

  • Busca Heurstica - Busca pela melhor escolhaBusca genrica onde o n de menor custo aparente na fronteira do espao de estados expandido primeiro

    Duas abordagens bsicas:1. Busca Gulosa (Greedy search) 2. Algoritmo A*

  • Busca Heurstica - Busca pela melhor escolha - Busca GulosaSemelhante busca em profundidade com backtrackingTenta expandir o n mais prximo ao n final com base na estimativa feita pela funo heurstica h.Custo de busca minimizado no expande ns fora do caminhoEscolhe o caminho que mais econmico primeira vistaNo tima... (semelhante busca em profundidade)porque s olha para o futuro! ... nem completa:pode entrar em loop se no detectar a expanso de estados repetidospode tentar desenvolver um caminho infinitoCusto de tempo e memria: O(bd)guarda todos os ns expandidos na memria

  • Busca Heurstica - Busca pela melhor escolha - Busca GulosaDistncia em linha reta para Bucharest:

  • Busca Heurstica - Busca pela melhor escolha - Algoritmo A*Tenta minimizar o custo total da soluo combinando:Busca Gulosaeconmica, porm no completa nem timaBusca de Custo Uniformeineficiente, porm completa e timaFuno de avaliao:f(n) = g(n) + h(n), onde g(n) = distncia de n ao n inicial e h(n) = distncia estimada de n ao n finalA* expande o n de menor valor de f na fronteira do espao de estados.Olha o futuro sem esquecer do passado!Se h admissvel, f(n) nunca ir superestimar o custo real da melhor soluo atravs de n.Neste caso, pode-se encontrar a rota de fato mais curta entre Arad e Bucarest.

  • Busca Heurstica - Busca pela melhor escolha - Algoritmo A* Como procurar a soluo de um problema?Busca Heurstica - Busca pela melhor escolha - Algoritmo A*449393447417413415496

  • Busca Heurstica - Define Contornos. f(n) f* (f admissvel) . fator de expanso prximo de 1

  • Busca Heurstica - Busca pela melhor escolha - Algoritmo A* : anlise do comportamentoCusto de tempo:exponencial com o comprimento da soluo, porm boas funes heursticas diminuem significativamente esse custoo fator de expanso fica prximo de 1Custo memria: O (bd) guarda todos os ns expandidos na memriapara possibilitar o backtrackingEficincia timas expande ns com f(n) f*, onde f* o custo do caminho timof no decrescentenenhum outro algoritmo timo garante expandir menos ns.

  • Busca Heurstica Busca com Limite de Memria Memory Bounded SearchIDA* (Iterative Deepening A*)igual ao aprofundamento iterativo, sua principal diferena que seu limite dado pela funo de avaliao (f) (contornos), e no pela profundidade (d).necessita de menos memria do que A* mas continua timaRBFS*(Recursive Best-First-Search) Limita o best-first-search atravs da utilizao de um espao linear.Semelhante ao busca em profundidade recursiva.Mantm no n corrente a melhor alternativa a partir do ancestral do n corrente.SMA* (Simplified Memory-Bounded A*) O nmero de ns guardados em memria fixado previamenteConforme vai avanando, descarta os piores Mantm no n corrente a melhor alternativa a partir do ancestral do n corrente. completa e tima se a memria alocada for suficienteAtividade constante da paginao causando a degradao do desempenho do sistema.

    Adaptao da tcnica de aprofundamento iterativo ao conceito de busca heurstica, com a finalidade de reduzir as exigncias de memria do A*.

  • Funo Heurstica: Inventando Funes HeursticasComo escolher uma boa funo heurstica h?h depende de cada problema particular.h deve ser admissvel no superestimar o custo real da soluo Existem estratgias genricas para definir h:1) Relaxar restries do problema;2) Usar informao estatstica;3) Identificar os atributos mais relevantes do problema.

  • Busca Heurstica:(1) Relaxando o problemaProblema Relaxado:verso simplificada do problema original, onde os operadores so menos restritivosExemplo: jogo dos 8 nmeros: operador original: um nmero pode mover-se de A para B se A adjacente a B e B est vaziobusca exaustiva 320 estados possveismdia de 3 de fator de expanso e 20 passos

    Operadores relaxados:1. um nmero pode mover-se de A para B (h1)2. um nmero pode mover-se de A para B se A adjacente a B (h2)

  • Heurstica : para jogo 8 nmerosHeursticas possveish1 = no. de elementos fora do lugar (h1=7)h2 = soma das distncias de cada nmero posio final (h2=2+3+3+2+4+2+0+2=18) Manhattan Distance d de dois pontos (x,y) e (u,v), d = |x-u| + |y-v|

  • Busca Heurstica:(2) Usando informao estatsticaFunes heursticas podem ser melhoradas com informao estatstica:Cada soluo tima para o problema dos 8 nmeros oferece exemplos, os quais podem ser aprendidos.Um algoritmo de aprendizagem pode ser utilizados para predizer h(n) para os outros estados.Utilizao de caractersticas dos estados que so relevantes na avaliao, objetivando melhorar os resultados oferecidos pelo algoritmo de busca. ex: Nmero de nmeros fora do lugar ajuda a predizer a distncia do estado atual at o estado alvo.

  • Busca Heurstica :Qualidade da funo heursticaQualidade da funo heurstica: medida atravs do fator de expanso efetivo (b*).b* o fator de expanso de uma rvore uniforme com N ns e nvel de profundidade dN = 1 + b* + (b*)2 + ... + (b*)d , onde N = total de ns expandidos para uma instncia de problemad = profundidade da soluo;Mede-se empiricamente a qualidade de h a partir do conjunto de valores experimentais de N e d. uma boa funo heurstica ter o b* muito prximo de 1.

  • Busca Heurstica : Experimento com 100 problemasUma boa funo heurstica ter o b* muito prximo de 1.

  • Busca Heurstica : Busca LocalEste espao pode ser visto como uma superfcie com vales e cumes O caminho at o objetivo no importa.Partida: soluo inicial.Iterao: melhoria sucessiva da soluo corrente atravs de uma busca na sua vizinhana.Parada: primeiro timo local encontrado (no existe soluo melhor na vizinhana)Heurstica : utilizada para obter uma soluo melhor na vizinhana.Hill-Climbing (Subida da Encosta)EstocsticoSimulated Annealing (Tmpera Simulada)Local Beam Search (Busca em Feixe Local)EstocsticoAlgoritmos Genticos

  • Busca Heurstica : Problemas de OtimizaoOs estados podem ser representados sobre uma superfcie (igual a funo de avaliao)a altura de qualquer ponto na superfcie corresponde a sua avaliaoO algoritmo se move pela superfcie em busca de pontos mais altos/baixoso ponto mais alto/baixo (mximo/mnimo global) corresponde soluo tima

  • Busca Heurstica : Exemplo de Subida da Encosta: TSP (Caixeiro viajante)Clculo da menor rotas com 5 ns:estado inicial = (N1, N2, N3, N4, N5)f = soma das distncias diretas entre cada n, na ordem escolhida (admissvel!)operadores = permutar dois ns quaisquer do caminhorestrio = somente caminhos conectados so estados vlidosestado final = n onde valor de f mnimoe6 = {N5, N2, N4, N3, N1}f(e6) = 11O algoritmo no mantm uma rvore de busca:guarda apenas o estado atual e sua avaliao simplesmente um loop que se move na direo crescente (para maximizar) ou decrescente (para minimizar) da funo de avaliao

  • Busca Heurstica : Subida da EncostaO algoritmo move-se sempre na direo que apresenta maior taxa de variao para f Isso pode acarretar em 3 problemas:1. Mximos locais2. Plancies (plats)3. Encostas e picos

  • Busca Heurstica : Subida da Encosta: anliseO algoritmo completo?SIM, uma vez que cada n tratado pelo algoritmo sempre um estado completo (uma soluo)O algoritmo timo?TALVEZ, quando iteraes suficientes forem permitidas...O sucesso deste mtodo depende muito do formato da superfcie do espao de estados:Se h poucos mximos locais, o reincio aleatrio encontra uma boa soluo rapidamente

  • Busca Heurstica : Resfriamento/Recozimento Simulado.Este algoritmo semelhante Subida da Encosta com grau de aleatoriedade porm sem reiniciar a buscao algoritmo admite retroceder para situaes piores com certa probabilidade que diminui com o tempoApesar de aumentar o tempo de busca, essa estratgia consegue escapar dos mximos locaisAnalogia com cozimento de vidros ou metais: processo de resfriar um lquido gradualmente at ele se solidificar

  • Busca Heurstica : Local Beam SearchEste algoritmo guarda k estados na memria ao invs de apenas um.Ele comea com k estados gerados randomicamente.Em cada passo todos os sucessores de todos os k estados so gerados.Se algum deles o objetivo, o algoritmo para.Caso contrrio, selecionado os k melhores sucessores e o processo repetido.Compartilhamento de informaes de bons sucessores.Abandono de sucessores ruins.Problemas com pouca variao dos k estados(Verso mais simples).Variao: Estoctico Bean Search.

  • Busca Heurstica : Algo