Prof. Frederico Brito Fernandes [email protected] Busca com Informação CONTEÚDO (1) Estudos de Caso (2) Busca Informada (3) Busca Gulosa (4) Busca A* (5)

Prof. Frederico Brito [email protected]

Busca com Informação

CONTEÚDO

(1) Estudos de Caso(2) Busca Informada(3) Busca Gulosa(4) Busca A*(5) Heurística(6) Busca Local e Problemas de Otimização

Disciplina: Inteligência Artificial

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 2/27Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(1) Estudo de Caso 1: Missão Bregareia

• Problema do menor caminho– Objetivo:

• Ir pro Bregareia, saindo de João Pessoa

– Ações:• Próxima cidade

– Heurística• Distância em linha reta JoãoJoão

PessoaPessoa120120CGCG

AreiaAreia

EsperançaEsperança

Baía da Baía da TraiçãoTraição

GuarabiraGuarabira

MamanguapeMamanguape

5050

2020

9090

5050

5050

60604040

FIM

INÍCIO

3030

Origem h()

JP 134

BT 155

Mamanguape 130

Guarabira 89

Esperança 53

CG 35

Areia 0


(1) Estudo de Caso 2: problema dos sapos

• Problema dos sapos:– Objetivo:

• Faça com que os machos fiquem na direita e as fêmeas na esquerda

– Ações:• Pular para frente, e duas pedras no

máximo

– Heurística• nº de sapos no lugar errado

• somatório da distância que cada sapo está de um lugar final

M1M1 M2M2 M3M3 F3F3 F2F2 F1F1


(1) Estudo de Caso: menor caminho

Início

objetivo

Heurística da Linha Reta novamenteHeurística da Linha Reta novamente


(2) Busca Informada

• Utiliza uma função de avaliação, f(n), para cada nó que estima “o quão desejável” é aquele nó– Expande o nó que parece mais desejável ainda não expandido

• A fronteira (fila de nós gerados mas não expandidos) será uma fila ordenada em ordem decrescente de “desejabilidade”.

• Casos especiais:– Busca Gulosa pela melhor escolha (greedy)

– Busca A*

• Todos os algoritmos de busca pela melhor escolha (busca informada) utilizam uma função heurística h(n)– h(n) é o custo estimado do caminho mais econômico do nó n até um

nó objetivo


(3) Busca Gulosa pela melhor escolha

• Minimizar o custo estimado par alcançar o objetivo

• Muitas vezes o custo para se alcançar o objetivo pode ser estimado mas não pode ser determinado exatamente

• A busca gulosa pela melhor escolha (greedy) expande o nó que aparenta estar mais próximo do objetivo

• Função de Avaliação utiliza somente h(n)– Para o exemplo da Romênia:

• hDLR(n) = distância em linha reta de n até Bucarest.


(3) Busca Gulosa: Exemplo







• O solução encontrada não é a solução ótima.• Arad Sibiu Fagaras Bucharest (140) + (99) + (211) = 450km

• A Solução ótima passa por Rimnicu Vilcea• Arad Sibiu Rimnicu Vilcea Pitesti Bucharest (140) + (80) + (97) + (101) = 418km


(3) Busca Gulosa: Problema

Início

objetivo

g(Sibiu Fagaras) + h(Fagaras) (99) + (178) = 277km

GULOSO:GULOSO:

g(Sibiu Rimnicu) + h(Rimnicu) (80) + (193) = 273km

IDEAL:IDEAL:

Não considera Não considera o custo g()o custo g()


(3) Análise da Busca Gulosa

• Tende a encontrar soluções rapidamente mas nem sempre encontra a solução ótima

• Se um dos nós mais próximos da solução é um beco-sem-saída, então nós serão expandidos sem necessidade

• Se não tomarmos cuidado com os estados repetidos a solução nunca será encontrada

• Sofre dos mesmos problemas da busca em profundidade– Segue somente um caminho, mas tem que voltar se não encontrar

a solução


(3) Análise da Busca Gulosa

• Não é ótima nem completa – porque pode entrar em um caminho infinito

• Complexidade de tempo: O(bm), mas uma boa heurística pode melhorar muito

• Complexidade de espaço: O(bm), mantém todos os nós na memória)

• * Onde m é a profundidade máxima e b é o fator de ramificação do espaço de busca.


(4) Busca A*

• Busca gulosa– minimiza o custo estimado de n até o objetivo => h(n)– Não é completa nem ótima

• Busca por custo uniforme– minimiza o custo do caminho da raiz até n => g(n)– É completa e ótima – mas analisa muitos nós

• Idéia de A*: combinar as duas estratégias– Evitar expandir caminhos que já são caros– Função de Avaliação f(n) = g(n) + h(n)

• f(n) = custo estimado total da solução de custo mais baixo passando por n

»


(4) Busca A*

• É completa e ótima, se h(n) é uma heurística admissível e consistente (monotônica)

• Heurística admissível: – h(n) ≤ h’(n)+ custo real de n até n'

– Assim, f(n) nunca superestima o custo atual da melhor solução até n.

– Ao longo de qualquer caminho a partir da raiz, f nunca decresce

– Por exemplo: • hDLR(n) nunca superestima a distância real pela estrada.


(4) Busca A*

• Problema: – Ir de Arad Bucharest.

• Função heurística: – Distância em linha reta entre a cidade n e Bucharest.

– Satisfaz a condição de admissibilidade, pois não existe distância menor entre dois pontos do que uma reta.

– É uma boa heurística, pois induz o algoritmo a atingir o objetivo mais rapidamente.


(4) Exemplo de Busca A*












(4) Contornos usando A*

• As linhas pontilhadas vermelhas mostram os nós expandidos nos momentos t1, t2 e t3• t1

– Local: Arad– f(Arad) = g(Arad)+ h(Arad) =

0 + 366 = 366

• t2

– Local: Sibiu– f(Sibiu) = g(Sibiu)+h(Sibiu) =

140+253= 393

• t3

– Local: Bucharest– f(Buch) = g(Buch)+h(Buch) =

418+0 = 418

tt11

tt22

tt33

g(Buch) mínimo, passando por Pitestig(Buch) mínimo, passando por Pitesti


(4) Análise de A*

• Completa?: – Sim, a menos que haja uma quantidade infinita de nós com f ≤

g(objetivo)+h(objetivo)

• Tempo?: – Exponencial em relação ao comprimento da solução

• Espaço?: – Mantém todos os nós na memória

• Ótima?: – Sim

• Não é prático para muito problemas de grande escala


(5) Construindo Funções Heurísticas

• Exemplo de heurísticas para o 8-puzzle– h1(n) = número de quadrados em locais errados

– h2(n) = distância Manhattan total => número de espaços que deve ser movido para chegar no local correto

– h1(s) = 7 (só o número 7 está no local correto)

– h2(s) = 2+3+3+2+4+2+0+2 = 18

estado inicial estado final


(5) Heurísticas admissíveis

• h(n) nunca deve superestimar o menor caminho, desta forma h(n) deve ser sempre menor que o caminho real.– Isto é, h(n) <= g(n) onde g(n) é o custo real de n.

• As heurísticas admissíveis tem natureza otimista, pois elas sempre indicam que o custo da solução é melhor do que ele realmente é.

• Desta maneira se uma solução ainda não foi encontrada sempre existirá um nó com f(n) menor do que ela.


(5) Dominância

• Se h2(n) >= h1(n) para todo n (ambas admissíveis) então h2 domina h1 e é melhor para a busca.

• Isto se reflete diretamente no números de nós expandidos para cada heurística

• Custos típicos de busca:– d = 14

• Aprofundamento Iterativo = 3.473.941 nodos

• A*(h1) = 539 nodos

• A*(h2) = 113 nodos


(5) Dominância

• d = 24• Aprofundamento Iterativo = 54.000.000.000

• A*(h1) = 39.135 nodos

• A*(h2) = 1.641 nodos

• Disponibilidade de uma coleção de heurísticas admissíveis onde nenhuma domina a outra– Para cada nó n escolha: h(n) = max(h1(n), h2(n),...,hm(n)), onde

h(n) é admissível e domina as outras heurísticas em n

• Sempre é melhor utilizar uma heurística com valores mais altos, desde que ela seja admissível


(5) Relaxação de problemas

• Várias vezes "relaxar" (tirar restrições) do problema pode resultar em uma boa heurística.

• Heurísticas admissíveis podem ser derivadas do custo de uma solução exata a partir de uma versão relaxada do problema.

– Se as regras do 8-puzzle forem relaxadas para que um quadrado possa se mover para qualquer lugar, então h1(n) dá a solução de caminho mais curto.

– Se as regras forem relaxadas para que um quadrado possa mover-se para qualquer quadrado adjacente, mesmo que ele esteja ocupado, então h2(n) dá a solução com caminho mais curto.


(5) Relaxação de problemas

• Ponto chave: o custo da solução ótima de um problema relaxado não é maior que o custo da solução ótima do problema real. Portanto ela é uma heurística admissível.

• Geração automática de heurísticas– Descrição em linguagem formal do 8-puzzle:

• Um bloco pode se mover do quadrado A para o quadrado B se:– A é horizontal ou verticalmente adjacente a B e B é vazio

– Heurísticas:• Um bloco pode se mover do quadrado A para o B se A é adjacente a B

• Um bloco pode se mover do quadrado A para o B se B está vazio

• Um bloco pode se mover do quadrado A para o B

– Programa ABSOLVER• Gerou a melhor heurística do 8-puzzle das pré-existentes

• Descobriu a primeira heurística útil para o famoso quebra-cabeça do cubo de ubik


(6) 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



• O espaço de estados é o conjunto completo de todas as configurações do problema

• 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



• 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



• 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


(6) Busca de subida de encosta (Hill-Climbing)

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

inputs:problema, um problema

local:atual, um nodo

vizinho, um nodo

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

loop

vizinho <- um sucessor atual com valor mais alto

If VALOR[vizinho] <= VALOR[atual] then

return ESTADO[atual]

atual <- vizinho

end


(6) 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


(6) Hill-Climbing: problema da n-rainhas

• Algoritmos de busca local utilização uma formulação de estados completos– Cada estado tem n rainhas, 1 por coluna

• Função sucessora gera todos os estados possíveis– Gerados pela movimentação de uma única rainha para outro lugar

na mesma coluna

• A função heurística é o números de pares de rainhas que estão se atacando umas às outras– O mínimo global dessa função é zero, que só ocorre em soluções

perfeitas


(6) Hill-Climbing: problema da n-rainhas


(6) Hill-Climbing: problema

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



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



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


(6) 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


(6) Hill-Climbing

• O sucesso deste tipo de busca depende muito da 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


(6) 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.



• 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

eΔET



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 atual

próximo um sucessor de atual aleatoriamente selecionado

E VALOR[próximo] – VALOR[atual]

if E > 0 then atual próximo

else atual próximo somente com uma probabilidade eE/T

end


(6) Busca em feixe local

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

• Começa com k estados gerados aleatoriamente

• Em cada passo gera todos os sucessores dos k estados

• 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


(6) Algoritmo Genético

• Uma variante da busca em feixe estocástica

• Estado sucessor gerado pela combinação de dois estados pais

• Analogia com a seleção natural:

– Busca em feixe estocástica – reprodução assexuada

– Algoritmo genético – reprodução sexuada

Documents

Prof. Frederico Brito Fernandes [email protected] Busca com Informação CONTEÚDO (1) Estudos de Caso (2) Busca Informada (3) Busca Gulosa (4) Busca A* (5)