Busca com Informação e Exploração “Busca heurística”

Embed Size (px)

DESCRIPTION

Busca com Informação e Exploração “Busca heurística”. Eduardo Araujo Oliveira eao@cin.ufpe.br Patricia Endo pte@cin.ufpe.br. 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 - PowerPoint PPT Presentation

Text of Busca com Informação e Exploração “Busca heurística”

  • Busca com Informao e ExploraoBusca heursticaEduardo Araujo Oliveiraeao@cin.ufpe.br

    Patricia Endopte@cin.ufpe.br

  • Busca heurstica - EscopoDefinioEstratgias de busca com InformaoFunes heursticasAlgoritmos de busca local e problemas de otimizaoBusca local em espao contnuoAgente de busca on-line e ambientes desconhecidos

  • Problema da busca cega

    Se a combinao de caminhos at o objetivo for exponencial a busca cega dificilmente encontrar a resposta do problema em um tempo polinomial.

  • Instncia

    Como encontrar um barco perdido?No podemos procurar no oceano inteiro...

    Informaes relevantes: Velocidade do vento;Direo do vento;...

  • DefinioComo na busca cega, utiliza a definio do problema para efetuar a busca.

    Utiliza conhecimento especfico do problema (informaes)

    No procura a melhor soluo do problema, procura uma boa soluo, ou simplesmente alguma soluo.

  • Busca gulosa pela melhor escolhaEstratgia: tenta expandir o n supostamente mais prximo a origem (heurstica), atravs de uma estimativa;

    Avalia ns atravs da funo h(n)h(n) depende do problema

  • ExemploObjetivo: Encontrar um bom caminho de Arad Bucareste.

    h(n) = distncia 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

  • Caractersticas da Busca Gulosa pela melhor escolha

    No tima;

    incompleta, pois pode entrar em loops infinitos;

  • Busca A*Avalia a combinao de duas funes:

    f(n) = g(n) + h(n); onde:g(n) o custo real da origem at o n n;h(n) a distncia em linha reta do objetivo at o n n.

  • A*: CaractersticasDesde que h(n) no superestime o custo para alcanar o objetivo, A* tima.Completa.A* expande o n de menor valor de f na fronteira do espao de estados.Olha o futuro sem esquecer do passado, armazenando todos os caminhos anteriores.

  • A*

  • A*

  • A*

  • A*

  • ComportamentoCusto de tempo:exponencial com o comprimento da soluo, porm boas funes heursticas diminuem significativamente esse custoCusto 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 timo

  • A* de aprofundamento iterativo (AIA*)Igual ao aprofundamento iterativo, sua principal diferena que seu limite dado pela funo de avaliao (f) (contornos), e no pela profundidade (d).

  • Busca heurstica com limite de memriaBRPM Busca recursiva pelo melhorSemelhante a busca recursiva em profundidade;Diferena: No desce indefinidamente. Ela controla a recurso pelo valor de f. Se existir algum n em um dos ancestrais que oferea melhor estimativa que o n atual, a recurso retrocede e a busca continua no caminho alternativo.

  • BRPMAradSibiuAradFagarasOradeaR. VilceaPitestiSibiu366393415

    526417447413553

  • BRPMAradSibiuAradFagarasOradeaR. Vilcea366393415

    526447417SibiuBucareste591

    450

  • BRPMAradSibiuAradFagarasOradeaR. VilceaPitestiSibiu366393450

    526417447417553BucaresteR. Vilcea418607

  • A* Limitado pela memria simplificado (LMSA*)

    Utiliza toda a memria disponvel;Quando a memria est cheia, ele elimina o pior n folha (maior custo de f) para continuar a busca.

  • A* Limitado pela memria simplificado (LMSA*) completo, se a profundidade do n objetivo mais raso for menor que o tamanho da memria.

    timo se qualquer soluo tima for alcanvel.

  • Funes heursticasO desempenho da busca est totalmente relacionado a qualidade da funo heurstica utilizada.

    Como medir a qualidade de uma funo heurstica?

  • Exatido heursticaUma maneira de caracterizar a exatido heurstica atravs do fator de ramificao efetiva (b*). Considere N o nmero de ns gerados para alcanar o objetivo, e d a profundidade da soluo. Ento:N = 1 + b* + (b*)2 + ... + (b*)dUma boa funo heurstica ter b* bem prximo de 1.

  • Exemploh1 = o nmero de blocos em posies erradasH2 = a soma das distncias de suas posies objetivoEstado inicialEstado objetivo

  • Funes heursticasSe o custo real para alcanar n 150.h1(n) = 56; //heurstica 1h2(n) = 140; //heurstica 2h2(n) >= h1(n);Dizemos que h2 domina h1. Isso pode ser traduzido na forma: A heurstica 2 melhor que a heurstica 1, pois ter um menor fator de ramificao. Desde que h1 e h2 no superestimem o custo real.

  • 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:Relaxar restries do problema;Resolver subproblemas de maneira exata.

  • Exemplo de problema relaxadoUm 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 BUm bloco pode se mover do quadrado A para B, se B est vazioUm bloco pode se mover do quadrado A para o quadrado B

  • Exemplo de subproblemaEstado inicialEstado objetivo

    *24***31

    1234****

  • Busca com Informao e ExploraoBusca heursticaBusca LOCAL

  • Busca localExistem problemas, que o caminho at a soluo irrelevante:N-rainhas;Caixeiro Viajante

    Preocupao apenas com o estado corrente e estados vizinhos.

  • Vantagens de algoritmos de busca localUtilizam pouqussima memria (geralmente constante);

    Freqentemente encontram boa solues em espaos de busca infinitos (contnuos) para os quais, os algoritmos globais so inadequados.

    As heursticas da busca local no estimam a distncia do estado atual at o objetivo:Vantajoso para problemas nos quais no trivial estimar esta distncia.

  • Os algoritmos de busca local

    Estado Corrente;

    Problemas de Otimizao;

  • Topologia de Espao de EstadosEspao de estadosFuno objetivoMximo globalPlancieMximo localMximo local (plano)

  • Subida da encostaAlgoritmo bsicoFuno Subida-de-Encosta(problema) retorna um estado Entrada: problema, um problemaVariveis locais: corrente : N vizinho: Ncorrente = criar-NO(EstadoInicial[problema])Repitavizinho = acharMelhorSucessor(corrente)se vizinho.funcaoObjetivo
  • Diagrama de Atividades

  • Subida da encostaHill ClimbingO algoritmo procura o pico, onde nenhum vizinho tem valor mais alto.Subindo o everest na neblina com amnsiaPASSO

  • Subida da EncostaExemplo Porco Espinho ou Ourico

  • Exemplo: N-Rainhas

  • Exemplo: 8-RainhasEstado inicial: colocao aleatria de uma rainha por colunaOperador: mudar um rainha de posioh = nmero de pares de rainha que se atacamTaxa de sucesso em encontrar soluo tima: 14%O que fazer quando no 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 Seleo aleatria

  • Subida da encostaHill ClimbingMove na direo do incremento da funo, terminando quando acha um pico Guloso: steepest ascent Problemas Mximos Locais; Mximo local plano; Plancies.

  • Variantes da Subida na encostaSubida de encosta estocstica: gera vrios sucessores (vizinhana N(S)), e escolhe ao acaso, um que oferea melhora na funo 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 reincio aleatrio: se no tiver sucesso na primeira vez, continue tentando. Gera estados iniciais ao acaso, parando ao encontrar um objetivo.

  • Subida na encostaAnlise

    O algoritmo completo?SIM, para problemas de otimizacao (onde cada NO tratado e um estado completo, uma solucao)NO, para problemas onde os NOS no so estados completosE.g. jogo dos 8-numerosO algoritmo timo?TALVEZ, quando iteraes suficientes forem permitidas...NO, para problemas onde os NOS no so estados completos

  • Simulated Annealing Simula o processo de arrefecimento dos materiais Arrefecimentos lentos conduzem a produtos mais puros, sem imperfeiesNormalmente interpretado como o algoritmo de busca local com os melhores resultados

  • Simulated AnnealingAdaptao da Subida na encostaPode adotar um estado que oferece perda (encosta abaixo).Capaz de fugir de mximos locais.

  • Simulated Annealing necessrio definir:

    Uma funo objetivo/custo

    Qual o espao de solues S

    Uma vizinhana sobre o espao de solues N(s0)

    Funo de reduo de temperatura

    Uma temperatura inicial T0

  • Temperatura no SAA temperatura, T0 inicialmente selecionada deve ser elevadaDurante o processo de procura da soluo, a temperatura vai decrescendo com base numa funo de reduo de temperatura

    O processo de pesquisa da soluo repete-se at que a temperatura seja to pequena que mais nenhum movimento seja aceito e o slido esteja no seu estado fundamental

  • Algoritmofuncao RECOZIMENTO-SIMULADO(problema, escalonamento) retorna SOLUCAOentradas: 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 descendentescorrente = CRIAR-NO (Estado-Inicial[problema])para t =1 ate infinito facaT = escalonamento[t]se T = 0 entao retornar correnteproximo = um sucessor de corrente selecionado ao acasoE = VALOR[proximo] VALOR[corrente]se E > 0 entao corrente = proximosenao corrente = proximo somente com probabilidade e ^ E/T

  • Diagrama de Ativid