26
Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Embed Size (px)

Citation preview

Page 1: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Busca informada (heurística)

Parte 2

Sistemas Inteligentes junho/2005

Page 2: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

A* com limite de memória (IDA*)

Interative Deepening A* - IDA ou em português AIA*

A busca em profundidade interativa é modificada para usar um limite custo f(n) ao invés do limite de profundidade

A cada interação todos os nós dentro do contorno do custo corrente são expandidos

Prático para problemas de passo unitário

Evita a sobrecarga de manter uma fila ordenada de nós

Dois tipos de algoritmos: BRPM e LMA*

Page 3: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Busca Recursiva pelo melhor (BRPM)

Tenta imitar a busca pela melhor escolha-padrão

Utiliza espaço linear

É semelhante à busca em profundidade recursiva, mas guarda o valor de f do melhor caminho alternativo

Se o custo do nó atual exceder f, a recursão retorna ao caminho alternativo

Repõe o valor de f de cada nó ao longo do caminho com o melhor valor de f de seus filhos

Podendo decidir se vale a pena voltar a expandir uma árvore esquecida

Page 4: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005
Page 5: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005
Page 6: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005
Page 7: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Busca Recursiva pelo melhor (BRPM)

Ainda sofre da geração excessiva de nós toda vez que o melhor caminho é expandido, há

uma boa chance que o valor de f aumente E então um 2º melhor caminho deve ser seguido,

reexpandindo os nós esquecidos

É ótimo se h(n) é admissível

Complexidade de espaço O(bd)

Complexidade de tempo depende: Da exatidão da função heurística Da freqüência com que o melhor caminho muda a

medida que os nós são expandidos

Page 8: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

A* limitado pela memória (LMA*) (simplificado)

Executa o algoritmo A* porém este só explora um limite máximo de memória

Define o número de nós que podem estar simultaneamente na memória

Guarda informações sobre as sub-árvores esquecidas

É completo: se existir memória suficiente para alcançar a solução de menor profundidade

É ótimo: se existir memória suficiente para alcançar a solução ótima de menor profundidade

Caso contrário ele irá retornar a melhor solução dentro dos limites de memória.

Page 9: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

LMSA*

Page 10: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

LMSA*

Em problemas muito complexos:

O algoritmo será forçado a alternar continuamente entre um conjunto de caminhos de soluções candidatas

Somente um pequeno conjunto pode caber na memória

Lembra problema de trashing em sistemas de paginação

Problemas solúveis com A* podem ser tornar intratáveis com LMSA*

Page 11: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Exercício: LMSA* com 4 nós

Início

objetivo

Page 12: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Algoritmos de busca local e problemas de otimização

Em muitos problemas de otimização o caminho até a solução é irrelevante

O estado objetivo é a solução

Exemplo: n-rainhas – o que importa é a configuração final e não a ordem em que as rainhas foram acrescentadas

Outros exemplos: Projeto de CIs Layout de instalações industriais Escalonamento de jornadas de trabalho Otimização de redes de telecomunicações Roteamento de veículos Outras aplicações

Page 13: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Algoritmos de busca local e problemas de otimização O espaço de estados é o conjunto completo de todas as

configurações

Operam sobre um único estado corrente, ao invés de vários caminhos

Em geral se movem apenas para os vizinhos desse estado

Vantagens:

Ocupam pouquíssima memória (normalmente constante)

Podem encontrar soluções razoáveis em grandes ou infinitos espaços de estados, para os quais os algoritmos sistemáticos são inadequados

Page 14: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Algoritmos de busca local

Algoritmos de busca local são úteis para resolver problemas de otimização puros

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

Normalmente o espaço de estados é considerado como tendo uma topologia onde existe:

Uma posição – definida pelo estado

Uma elevação – definida pelo valor da função de custo da heurística ou da função objetivo

Page 15: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Algoritmos de busca local

Elevação = custo -> objetivo = mínimo global Elevação = função objetivo -> objetivo = máximo global É completo se sempre encontra um objetivo É ótimo se sempre encontra um mínimo/máximo

global

Page 16: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Busca de subida de encosta (Hill-Climbing)

function HILL-CLIMBING(problema) returns um estado que é o máximo local

inputs:problema, um problemalocal:atual, um nodo

vizinho, um nodo

atual <- CRIAR-NÓ(ESTADO_INICIAL[problema])

loopvizinho <- um sucessor atual com valor mais altoIf VALOR[vizinho] <= VALOR[atual] then

return ESTADO[atual]atual <- vizinho

end

Page 17: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Busca de subida de encosta (Hill-Climbing)

Se move de forma contínua no sentido do valor crescente

Termina quando alcança um pico, em que nenhum vizinho tem valor mais alto

Não mantém árvore de busca, somente o estado e o valor da função objetivo

Não examina antecipadamente valores de estados além de seus vizinhos imediatos (busca gulosa local)

É como subir o Everest em meio a um nevoeiro e sofrendo de amnésia

Page 18: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Hill-climbing - problema

Dependendo do estado inicial, pode ficar preso em um máximo local.

Page 19: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Hill-climbing - problema

Podem existir platôs fazendo com que em certas áreas a função tenha valores muito próximos.

Page 20: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Hill-climbing - problema

Podem existir picos que fazem com que a função de qualidade oscile entre vários máximos locais.

Page 21: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Hill-climbing

Formas de resolver o problema de máximos locais

Ao atingir o máximo fazer alterações aleatórias para ver se não há estados melhores (random-restart-hill-climbing)

Pode-se usar também uma função que testa se o estado é solução em vez de procurar somente pelo máximo

Pode usar backtracking para procurar estados melhores

Término do algoritmo Número fixo de interações Porcentagem de melhoramento Tempo fixo

Page 22: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Hill-climbing

O sucesso deste tipo de busca depende muito doa topologia do espaço de estados

Muitos problemas reais tem uma topologia mais parecia com uma família de ouriços em um piso plano

Com ouriços em miniatura vivendo na ponto de cada espinho de um ouriço, ad infinitum

Problemas NP-difíceis têm um número exponencial de máximos locais em que ficam paralisados

Page 23: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Simulated Annealing (Têmpera simulada)

Têmpera: processo usado para temperar ou endurecer metais e vidro aquecendo-os a alta temperatura e depois resfriando gradualmente

Idéia:

Fugir do máximo local permitindo alguns movimentos “ruins” para fora do máximo, mas gradualmente decrescendo seu tamanho e freqüência

A temperatura diminui em função do tempo diminuindo a probabilidade de se escolher um estado pior

Amplamente utilizado para layout de VLSI, planejamento de linhas aéreas, etc.

Page 24: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Propriedades do Simulated Annealing

Na “temperatura” fixa T, a probabilidade de ocupação de um estado pior que o atual é

T decrescendo suficientemente lento sempre alcança o melhor estado

Para valores maiores de T, soluções ruins são permitidas

T próximo de zero, a probabilidade de se escolher soluções ruins diminui

E determina qual é a variação entre a solução corrente e a próxima solução

T

E

e

T

E

e

Page 25: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Simulated Annealing

function SIMULATED_ANNEALING(problema, escala) returns um estado solução

inputs: problema, um problema escala, um mapeamento do tempo pela temperatura

local: atual, um nodo próximo, um nodo T, uma temperatura controlando a probabilidade de dar passos pra baixo

atual CRIAR-NÓ(ESTADO_INICIAL[problema])

for tempo 1 to T escala[tempo]if T = 0 then return atualpróximo um sucessor de atual aleatoriamente selecionadoE VALOR[próximo] – VALOR[atual]if E > 0 then atual próximoelse atual próximo somente com uma probabilidade eE/T

end

Page 26: Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

Busca em feixe local

Mantém o controle de k estado ao invés de somente um

Começa com k estados gerados aleatoriamente

Em cada passo gera todos os sucessores de k

Se algum sucessor for o objetivo, termina

Se não escolhe os k melhores sucessores e repete a ação

É diferente da busca com reinício aleatório porque os k estados compartilham informações entre eles

Problema: os k estados podem rapidamente ficar concentrados em uma pequena região do espaço de estados

Solução: escolher k sucessores melhores que seus pais ao acaso