Universidade Federal do ABC

Centro de Matemática, Computação e Cognição

MCTA014-15 - Inteligência Artificial

Aula 05 – Busca Informada e Busca Local

Profa: Karla Vittori

Santo André - SP
Outubro - 2022
Estratégias de busca sem informação

 Encontram soluções:
 Gerando sistematicamente novos estados e

 Comparando-os com o objetivo

 São muito ineficientes na maioria dos casos

 São capazes de calcular apenas o custo de um caminho do nó atual ao nó
inicial (função g), para decidir qual o próximo nó da fronteira a ser expandido

 Essa medida não necessariamente conduz a busca na direção do objetivo

(ollha só para o passado)

 Exemplo: como encontrar um barco perdido?

 Não podemos procurar no oceano inteiro...
1 - Busca com informação

 Estratégias de busca com informação

 Busca heurística
 Usam conhecimento específico do problema na expansão dos nós
 Além da definição do próprio problema

 Ex.: barco perdido: correntes marítimas, vento, etc...

 Podem encontrar soluções de maneira mais eficiente

 Aplicam uma função de avaliação f(n) a cada nó na fronteira da

árvore de busca
 Essa função estima o custo do caminho do nó atual ao objetivo
utilizando uma função heurística
 Qual dos nós supostamente é o mais próximo do objetivo?
Função de avaliação
 Componente fundamental da função de avaliação: função heurística
h(n)

 Estima o custo do caminho mais curto de um nó n até um nó objetivo

 Estima o que resta do caminho ao objetivo

 Enquanto o g(n) (em custo uniforme) só considera a distância

em relação ao início da busca
 Exemplo: Arad a Bucareste

 Uma heurística é a distância em linha reta entre essas cidades

 A função heurística é a forma mais comum de adicionar

conhecimento do problema à busca
 Específica para cada problema
 Restrição: se n é um nó objetivo, h(n) = 0
1 - Busca com informação

 Abordagem geral: busca pela melhor escolha (best-first search)

 Expande os nós com base em uma função de avaliação f(n)

 Mede a distância até o nó objetivo

 Estimativa de quão promissor é um nó

 Nó com menor distância (mais próximo) é selecionado para expansão

 Expande nó mais promissor ainda não expandido
 Nó de menor custo “aparente” na fronteira

 Duas abordagens:
1. Busca Gulosa (Greedy search)
2. Algoritmo A* e suas variantes
2 - Busca pela melhor escolha

 Algoritmo:
Função Busca-Melhor-Escolha (problema, h)
fronteira  Inserir(Nó (Estado-Inicial[problema] ) )
faça
se fronteira está vazia então retorna falha
nó  Remove-Mais-Promissor(fronteira)
se Teste-Término[problema] aplicado a Estado[nó] tiver sucesso
então retorna sucesso (retorna o nó e o caminho até ele)
fronteira  Inserir-Todos(fronteira, Expandir[problema, nó])
fim
2.1 - Busca gulosa

 Tenta expandir o nó mais próximo à meta

 Supondo que provavelmente levará a uma solução rápida
 Avalia os nós usando apenas a função heurística
 f(n) = h(n)
 Considerando o custo estimado de n ao objetivo
 Expande o nó que aparentemente esteja mais perto do objetivo

Semelhante à busca em profun-

didade com backtracking

Tenta expandir o nó mais próximo

do nó final com base na estimativa

feita pela função heurística h

Exemplo
 Ir de Arad a Bucareste
Arad
Exemplo
 Ir de Arad a Bucareste
Bucareste
Exemplo
 Ir de Arad a Bucareste
 Heurística da distância em linha reta hDLR
 Experiência – hDLR está relacionada com as distâncias percorridas
nas estradas
Exemplo

 (a) Estado inicial

Arad (366)
Exemplo
 (b) Expansão de Arad

Arad (366)

Sibiu (253) Timisoara (329) Zerind (374)

Exemplo
 Ir de Arad a Bucareste
Exemplo
 (b) Expansão de Arad

Arad (366)

Sibiu (253) Timisoara (329) Zerind (374)

Exemplo
 Ir de Arad a Bucareste
 Exemplo
 (c) Expansão de Sibiu

Arad (366)

Sibiu (253) Timisoara (329) Zerind (374)

Arad (366) Fagaras (176) Oradea (380) Rimnicu (193)

 Exemplo
 (c) Expansão de Sibiu

Arad (366)

Sibiu (253) Timisoara (329) Zerind (374)

Arad (366) Fagaras (176) Oradea (380) Rimnicu (193)

Exemplo
 Ir de Arad a Bucareste
 Heurística da distância em linha reta hDLR
 Experiência – hDLR está relacionada com as distâncias percorridas
nas estradas
 Exemplo
 (c) Expansão de Fagaras

Arad (366)

Sibiu (253) Timisoara (329) Zerind (374)

Arad (366) Fagaras (176) Oradea (380) Rimnicu (193)

Sibiu (253) Bucareste (0)

 Exemplo
 Comprimento da rota: 140 + 99 + 211 = 450

Arad (366)

Sibiu (253) Timisoara (329) Zerind (374)

Arad (366) Fagaras (176) Oradea (380) Rimnicu (193)

Sibiu (253) Bucareste (0)

Exemplo

 Encontrou solução sem expandir nenhum nó que não estivesse

no caminho da solução
 Custo de busca minimizado

 Contudo, a solução não é ótima

 No exemplo, se escolhe o caminho que é mais econômico à
primeira vista, via Fagaras.
 Porém, existe um caminho mais curto via Rimnicu Vilcea e Pitesti
(80 + 97 +101 = 278) ao invés de (99 + 211 = 310) -> 32 km mais
curto

 Nomenclatura guloso
 Em cada passo, tenta chegar o mais perto possível do objetivo
Exemplo
 Ir de Arad a Bucareste
 Heurística da distância em linha reta hDLR
 Experiência – hDLR está relacionada com as distâncias percorridas
nas estradas
Busca gulosa

 Semelhante à busca em profundidade

 Prefere seguir em um único caminho
 Mesmos defeitos

 É incompleta
 Pode entrar em um caminho infinito e ficar presa em um loop

 Não é ótima
 Só olha para o futuro
2.1 - Busca gulosa

 Complexidade de tempo e espaço pior caso: O(bm)

 m é a profundidade máxima do espaço de busca

 Mantém todos os nós na memória

 Mas com uma boa função heurística, pode ter redução

substancial
2.2 - Busca A*
 Técnica de busca mais utilizada

 Minimiza o custo total estimado da solução

 Avalia os nós combinando:
 g(n): custo para alcançar cada nó
 Custo do nó inicial até o nó n
 h(n): custo para ir do nó n até o objetivo
 Custo estimado de n ao final

 Expande nó n de menor f(n) na fronteira

f(n) = g(n) + h(n)

Custo estimado total do caminho de n ao objetivo

(do início até ele + estimativa dele até o objetivo)
2.2 - Busca A*

 Combina:

 Busca Gulosa
 Se baseia em h
 Olha só para o futuro
 Econômica, pois só expande nós nos caminhos que escolher
 Porém, não é completa nem ótima

 Busca de Custo Uniforme

 Se baseia em g
 Olha só para o passado
 Ineficiente
 Porém, completa e ótima
2.2 - Busca A*

 Encontra solução de custo mais baixo

 Escolhe o primeiro nó com menor valor f(n) na fronteira
 Olha o futuro sem esquecer o passado

f(n) = g(n) + h(n)

 Algoritmo:
função Busca-A* (problema) retorna uma solução ou falha
Busca-Melhor-Escolha (problema, g+h)
2.2 - Busca A*

 Se a função heurística h(n) satisfaz algumas condições, A* é completa

e ótima
 Em busca em árvore, A* é ótima se h(n) for uma heurística admissível

 Nunca superestima o custo para alcançar o objetivo

 Para todo nó n, h(n) ≤ h*(n)

 h*(n) = custo real para atingir o objetivo a partir de n

 Se h é admissível, f(n) nunca irá superestimar o custo real da

melhor solução através de n
 (já que f(n) = g(n) + h(n))

 Heurística otimista
 Supõe que o custo da resolução do problema é menor do que ele
é na realidade
2.2 - Busca A*
 Ida de Arad a Bucareste
 hDLR é admissível
 Caminho mais curto entre dois pontos quaisquer é uma linha reta
 Logo, nunca vai superestimar a distância real a ser percorrida pela
estrada selecionada
 Usando:
 g(n) = distâncias na figura
 h(n) = hDLR
Exemplo
 Ir de Arad a Bucareste
Exemplo

 (a) Estado inicial

Arad (366)

0+366=366
Exemplo
 Ir de Arad a Bucareste
Exemplo

 (b) Expansão de Arad

Arad (366)

Sibiu (393) Timisoara (447) Zerind (449)

140+253=393 118+329=447 75+374=449
Exemplo

 (b) Expansão de Arad

Arad (366)

Sibiu (393) Timisoara (447) Zerind (449)

140+253=393 118+329=447 75+374=449
Exemplo
 Ir de Arad a Bucareste
 Exemplo
 (c) Expansão de Sibiu

Arad (366)

Sibiu (393) Timisoara (447) Zerind (449)

Arad (646) Fagaras (415) Oradea (671) Rimnicu (413)

280+366=646 239+176=415 291+380=671 220+193=413
 Exemplo
 (c) Expansão de Sibiu

Arad (366)

Sibiu (393) Timisoara (447) Zerind (449)

Arad (646) Fagaras (415) Oradea (671) Rimnicu (413)

280+366=646 239+176=415 291+380=671 220+193=413
Exemplo
 Ir de Arad a Bucareste

100
 Exemplo
 (d) Expansão de Rimnicu

Arad (366)

Sibiu (393) Timisoara (447) Zerind (449)

Arad (646) Fagaras (415) Oradea (671) Rimnicu (413)

Craiova (526) Pitesti (417) Sibiu (553)

366+160=546 317+100=417 300+253=553
 Exemplo
 (d) Expansão de Rimnicu

Arad (366)

Sibiu (393) Timisoara (447) Zerind (449)

Arad (646) Fagaras (415) Oradea (671) Rimnicu (413)

Craiova (526) Pitesti (417) Sibiu (553)

366+160=546 317+100=417 300+253=553
Exemplo
 Ir de Arad a Bucareste
 Exemplo
 (e) Expansão de Fagaras

Arad (366)

Sibiu (393) Timisoara (447) Zerind (449)

Arad (646) Fagaras (415) Oradea (671) Rimnicu (413)

Sibiu (591) Bucareste (450) Craiova (526) Pitesti (417) Sibiu (553)
338+253=591 450+0=450 366+160=546 317+100=417 300+253=553
 Exemplo
 (e) Expansão de Fagaras

Arad (366)

Sibiu (393) Timisoara (447) Zerind (449)

Arad (646) Fagaras (415) Oradea (671) Rimnicu (413)

Sibiu (591) Bucareste (450) Craiova (526) Pitesti (417) Sibiu (553)
338+253=591 450+0=450 366+160=546 317+100=417 300+253=553
Exemplo
 Ir de Arad a Bucareste
 Exemplo
 (f) Expansão de Pitesti

Arad (366)

Sibiu (393) Timisoara (447) Zerind (449)

Arad (646) Fagaras (415) Oradea (671) Rimnicu (413)

Sibiu (591) Bucareste (450) Craiova (526) Pitesti (417) Sibiu (553)

Bucareste (418) Craiova (615) Rimnicu (607)

418+0=418 455+160=615 414+193=607
2.2 - Busca A*

 É completa
 Tendo um número finito de nós com custo ≤ C* - custo da
solução ótima
 ou seja, a menos que haja infinitos nós com custo < C*
 Todos os custos de passos devem ser   finito
 b deve ser finito

 Eficiência ótima para qualquer função heurística

 Nenhum outro algoritmo ótimo tem a garantia de expandir um
número de nós menor que A*.
2.2 - Busca A*

 Complexidade de tempo ainda é exponencial na maioria

dos casos (O(bd))
 Exponencial com o comprimento da solução, porém boas
funções heurísticas diminuem significativamente esse custo

 Complexidade de espaço é exponencial

 Mantém todos os nós gerados na memória
 Para possibilitar o backtracking
 Natureza dos algoritmos BFS

 Em geral, A* esgota espaço bem antes de tempo

2.3 - Busca heurística limitada pela
memória
 Reduz requisitos de memória de A*
 A* de aprofundamento iterativo
• IDA* (Iterative Deepening A*)
 Corte usado é o custo de f em vez da profundidade

 Em cada iteração, o valor de corte é o menor custo (f) de

qualquer nó que excedeu o corte na iteração anterior.
 Se for gerado um nó com custo que excede o limite atual, ele é
descartado
 Completa e ótima

• SMA* (Simplified Memory-Bounded A*)

– O número de nós guardados em memória é fixado previamente
 Conforme vai avançando, descarta os piores nós (embora guarde
informações a respeito deles) e atualiza os melhores valores dos caminhos
 Não necessariamente completa e ótima

 Depende se o caminho caberá na memória disponível

3 - Funções heurísticas
 Exemplo do quebra-cabeças de 8 peças

 Custo da solução média para uma instância gerada ao acaso

é cerca de 22 passos.
 O fator de ramificação é cerca de 3:
 quando a peça branca estiver no meio, é possível quatro
movimentos;
 quando estiver em um canto, dois;
 quando estiver ao longo de uma borda, três.
3 - Funções heurísticas

 Busca exaustiva:

 Examina 322  3,1 x 1010 estados

 Fator de ramificação  3 e d  22 passos

 Uma busca em grafos (evitando estados repetidos) reduziria

isso de um fator de cerca de 170.000, porque apenas 9!/2 =
181.440 estados distintos são alcançáveis

 É um número melhor

 Porém, para 15 peças é próximo de 1013

 É necessário encontrar uma boa função heurística
3 - Funções heurísticas

 Exemplos de funções heurísticas admissíveis:

 h1 = número de blocos em posições erradas

 Admissível: qualquer bloco que esteja fora do lugar deve ser
movido ao menos uma vez
 h1(estado inicial) =
3 - Funções heurísticas

 Exemplos de funções heurísticas admissíveis:

 h1 = número de blocos em posições erradas

 Admissível: qualquer bloco que esteja fora do lugar deve ser
movido ao menos uma vez
 h1(estado inicial) = 8
3 - Funções heurísticas
 Exemplos de funções heurísticas admissíveis:

 h2 = soma das distâncias dos blocos em relação a suas

posições finais
 Soma das distâncias horizontal e vertical

 Admissível: resultado de movimento é deslocar um bloco para

uma posição mais próxima do objetivo

 h2(estado inicial) = 3 + …
3 - Funções heurísticas
 Exemplos de funções heurísticas admissíveis:

 h2 = soma das distâncias dos blocos em relação a suas

posições finais
 Soma das distâncias horizontal e vertical

 Admissível: resultado de movimento é deslocar um bloco para

uma posição mais próxima do objetivo

 h2(estado inicial) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18
3 - Funções heurísticas

 h1(estado inicial) = 8

 h2(estado inicial) = 3+1+2+2+2+3+3+2 = 18

 Nenhuma superestima o custo da solução verdadeira, que é 26

3.1 - Funções heurísticas

 h2 é sempre melhor que h1?

 Sim
 Para qualquer nó n, h2(n)  h1(n)
 h2 domina h1
 Dominância se traduz em eficiência
 A* com h2 nunca expandirá mais nós que A* com h1

É sempre melhor usar uma função heurística com valores mais

altos, desde que ela não superestime o custo e o seu tempo
de computação não seja muito grande
3.1 - Dominância de heurísticas

 Dadas duas funções heurísticas admissíveis h1 e h2

 Se h2(n) ≥ h1(n) para todo n

 Então h2 domina h1

 h2 é melhor para a busca

 Custos de busca típicos (números médios de nós expandidos):

 d = 12

 A*(h1) = 227 nós

A*(h2) = 73 nós
E se há várias h1,...,hm e
 d = 24 nenhuma domina?
 A*(h1) = 18.094 nós h(n) = max{h1(n),...,hm(n)}
A*(h2) = 1.219 nós
3.1 - Função heurística

 Como escolher uma boa função heurística h?

 h depende de cada problema particular

 h deve ser admissível

 não superestimar o custo real da solução
3.1 - Função heurística

 Existem estratégias genéricas para definir h:

(1) Relaxar restrições do problema
 Problema Relaxado:
– versão simplificada do problema original, onde os operadores
são menos restritivos

(2) Usar informação estatística

(3) Identificar os atributos mais relevantes do problema

Algoritmos de Busca
 Até agora, os algoritmos de busca:

 faziam uma exploração sistemática do espaço de busca

 mantendo um ou mais caminhos na memória
 registrando alternativas exploradas e não exploradas

 No entanto, em muitos problemas, o caminho até o objetivo é

irrelevante, como nos seguintes problemas:

 escalonamento de tarefas
 roteamento de veículos
 otimização de rede
 8 rainhas.
4 - Busca Local

 A idéia é começar com o estado inicial e melhorá-lo iterativamente

 Os estados estão representados sobre uma superfície

 a altura de qualquer ponto na superfície corresponde à função de
avaliação do estado naquele ponto

 O algoritmo se “move” pela superfície em busca de pontos mais

altos/baixos
 o ponto (nó) cujo valor da função de avaliação é mais alto/baixo
(máximo/mínimo global) corresponde à solução ótima
Espaço de busca
 Topologia de espaço de estados

 Algoritmo completo sempre encontra um objetivo, caso ele exista

 Algoritmo ótimo sempre encontra o mínimo/máximo global
4 - Busca Local
 Esses algoritmos guardam apenas o estado atual, e não vêem além
dos vizinhos imediatos do estado

 Contudo, muitas vezes são os melhores métodos para tratar

problemas reais muito complexos

 Duas classes de algoritmos:

 Hill-Climbing: Subida de Encosta
 Só faz modificações que melhoram o estado atual

 Simulated Annealing: Recozimento Simulado/ Têmpera Simulada

 Pode fazer modificações que pioram o estado temporariamente, para
possivelmente melhorá-lo no futuro
4.1 - Subida de Encosta
 Topologia de espaço de estados

 O objetivo é encontrar o máximo global.

 A busca de subida de encosta modifica o estado atual para tentar melhorá-
lo, como mostra a seta.
4.1 - Subida de Encosta

 Máximos Locais:
– em contraste com máximos globais, são picos mais baixos do que
o pico mais alto no espaço de estados (solução ótima)
– a função de avaliação leva a um valor máximo para o caminho
sendo percorrido: essa função utiliza informação “local”
– porém, o nó final está em outro ponto mais “alto”
– isto é uma consequência das decisões irrevogáveis do método
• e.g., Xadrez: eliminar a Rainha do adversário
pode levar o jogador a perder o jogo.
4.1 - Subida de Encosta

• Platôs:
– uma região do espaço de estados onde a função de avaliação dá
o mesmo resultado.
4.1 - Subida de Encosta

 Hill-climbing
 Se move de forma contínua em valor crescente
 Encosta acima
 Termina quando alcança um pico
 Em que nenhum vizinho tem valor mais alto
 Examina vizinhos imediatos
 Não precisa manter a árvore de busca
 Guarda só o estado atual e tenta melhorá-lo

Como tentar alcançar o cume do

Everest em meio a um nevoeiro denso,
durante uma crise de amnésia
 Algoritmo

Subida_em_encosta(problema)

Nó_atual = Estado_inicial(problema)
Repita
Nó_vizinho = sucessor de nó_atual com o melhor
valor de avaliação
Se aval(nó_vizinho) <= aval(nó_atual) então
retorne como solução o estado do nó corrente
Nó_atual = nó_vizinho
Fim_repita
4.1 - Subida de Encosta

 Chamada de busca gulosa local

 Captura um bom estado vizinho
 Porém, pode ficar paralisada:
 Em máximos/mínimos locais
 Em platôs
4.1 - Subida de Encosta
 Exemplo para problema das 8 rainhas:

 Formulação de estados completos

 Cada estado tem 8 rainhas no tabuleiro, uma por coluna

 Novos estados são gerados movendo uma rainha para outro quadrado na
mesma coluna
 Cada estado tem 8 x 7 = 56 sucessores

 Os sucessores de um estado são todos os

estados possíveis gerados pela movimentação
de uma única rainha para outro quadrado na
mesma coluna
4.1 - Subida de Encosta
 Exemplo para problema das 8 rainhas:

 Função de custo (heurística) h

 h = número de pares de rainhas atacando

umas às outras,direta ou indiretamente
 Neste caso, quanto menor, melhor

 Mínimo global = 0 (soluções perfeitas)

 Escolhe melhor sucessor atual

 Se houver vários, escolhe um deles
aleatoriamente

h = 17 nesse estado
melhor sucessor h = 12
4.1 - Subida de Encosta

 Um estado de oito rainhas com estimativa de custo de heurística h =

17, mostrando o valor de h para cada sucessor possível obtido pela
movimentação de uma rainha dentro de sua coluna.

 Os melhores movimentos (h = 12) estão marcados.

4.1 - Subida de Encosta

 Mínimo local com h = 1

 Todo sucessor tem um custo mais alto
 Alcançado em 5 passos a partir do estado com h = 17
4.1 - Subida de Encosta

 Problema das 8 rainhas

 Estados iniciais aleatórios

 86% do tempo a busca fica paralisada

 Resolve apenas 14% das instâncias do problema

 Mas é rápida
 4 passos em média quando tem sucesso

 3 passos em média quando fica paralisada

 Em um espaço que tem cerca de 88 = 17 milhões de estados

4.1 - Subida de Encosta

 Permitir movimentos laterais? Em geral, sim

 Mudar de estado em platôs (estados com avaliações iguais)
 Colocando um limite de vezes

 Problema das 8 rainhas

 Estados iniciais aleatórios e o limite de 100 movimentos laterais
consecutivos no platô
 Passa a resolver 94% das instâncias do problema (antes eram
14%)

 Mas demora mais

 21 passos em média quando tem sucesso

 64 passos em média quando falha

4.1 - Subida de Encosta

 Variantes:

 Subida de encosta estocástica

 Escolhe entre movimentos encosta acima
 Probabilidade dependente da declividade do movimento
 Em geral, converge mais lentamente
 Mas encontra melhores soluções em algumas topologias de
estados

 Subida de encosta pela primeira escolha

 Subida de encosta estocástica gerando sucessores ao acaso
 Até gerar um sucessor melhor que o estado atual
 Boa estratégia quando estado tem muitos sucessores
 Ex. milhares
4.1 - Busca de subida em encosta

 Subida de encosta com reinício aleatório

 “Se não tiver sucesso na primeira vez, continue tentando.”

 Várias buscas com estados iniciais diferentes

 Até encontrar um objetivo ou
 Até que um número máximo de iterações estipulado seja atingido ou
 Até que os resultados encontrados não apresentem melhora significativa

 O algoritmo escolhe, então, o melhor resultado obtido com as diferentes

buscas
4.1 - Busca de subida em encosta

 Subida de encosta com reinício aleatório

 Pode chegar a uma solução quando iterações suficientes forem

permitidas

 Bastante eficiente no exemplo das 8 rainhas

 Mesmo para 3 milhões de rainhas, pode encontrar soluções em menos de
um minuto
4.1 - Busca de subida em encosta

 Sucesso depende da topologia do espaço de estados

 Se houver poucos máximos/mínimos locais e platôs

 Subida de encosta com reinício aleatório encontrará uma boa
solução com rapidez
 Mesmo para problemas mais complexos, pode encontrar um
máximo local razoavelmente bom
 Com poucos reinícios

 Mas, o custo de tempo é exponencial para problemas NP-

completos
4.2 - Recozimento Simulado

 Simulated annealing

 Combinação de princípios de:

 Subida de encosta
 Incompleto, pode ficar paralisado

 Percurso aleatório
 Completo, mas ineficiente

 Para obter eficiência e ser completa

4.2 - Recozimento Simulado

 Recozimento

 Metalurgia

 Processo para endurecer metais/vidro

 Aquece a alta temperatura e esfria gradualmente
 Material é misturado em estado cristalino de baixa energia

• Algoritmo utiliza um mapeamento de resfriamento de instantes de

tempo (t) em temperaturas (T)
4.2 - Recozimento Simulado

 Para explicar a Têmpera Simulada, vamos mudar nosso ponto de vista

de subida de encosta para descida de gradiente (isto é, minimização do
custo).

 E imaginar a tarefa de colocar uma bola de pingue-pongue na fenda

mais profunda em uma superfície acidentada.
4.2 - Recozimento Simulado

 Se simplesmente deixarmos a bola rolar, ela acabará em um mínimo

local.

 Se agitarmos a superfície, poderemos fazer a bola quicar para fora do

mínimo local.
4.2 - Recozimento Simulado

 O artifício é agitar com força suficiente para fazer a bola sair dos
mínimos locais, mas não o bastante para desalojá-la do mínimo global.

 A solução de têmpera simulada é começar a agitar com força (isto é, em

alta temperatura) e depois reduzir gradualmente a intensidade da
agitação (ou seja, baixar a temperatura).
4.2 - Recozimento Simulado

 Em vez de escolher o melhor movimento, escolhe um movimento

aleatório
 Se o movimento melhorar a situação, é aceito

 Senão, é aceito com alguma probabilidade < 1

 Essa probabilidade é ajustada, de acordo com a qualidade do
movimento
 Decresce exponencialmente com a piora causada pelo movimento

 Probabilidade também diminui à medida que a temperatura T reduz

 Permite mais movimentos ruins no início (T alta)
 Eles ficam mais improváveis com a diminuição de T

Idéia: escapar de máximos/mínimos locais permitindo alguns movimentos

“ruins”, mas diminuir gradualmente a frequência deles
 Algoritmo
Têmpera_simulada(problema)
 T controla probabilidade de passos descendentes

1. nó_atual = Estado_inicial(problema)
2. Para t = 1 a ntemp faça
2.1 T = fator * t // controla os tamanhos dos
passos de resfriamento
2.2 Se T = 0 então retorne nó_atual
2.3 próx_nó <- um sucessor de atual selecionado
aleatoriamente
2.4 D E = aval[próx_nó] – aval[nó_atual]
2.5 Se D E <= 0 então nó_atual = próx_nó
2.6 Senão nó_atual = próx_nó somente com
probabilidade eDE/T

Se a avaliação do próximo nó é melhor, automaticamente vou para ele.

Senão, vou de acordo com uma probabilidade
 4.2 - Recozimento simulado

Transições muito ruins (ou seja, com Δ grande) são menos prováveis que as “pouco
ruins”.

 Quanto menor a temperatura, é menos provável que uma transição ruim seja aceita.
4.2 - Recozimento simulado

 O algoritmo é ótimo e completo se T diminui suficientemente

devagar no tempo

 O algoritmo vai encontrar um máximo/mínimo global com probabilidade

próxima de 1 (provado).

 A têmpera simulada foi usada inicialmente de forma extensiva para

resolver problemas de leiaute de VLSI no começo dos anos 1980.

 Ela foi amplamente aplicada ao escalonamento industrial e a outras

tarefas de otimização em grande escala.
6 - Referências

 Livro Russel e Norvig, Cap. 4 (4.1 a 4.3)

 Slides de:
 Profa Ana Carolina Lorena, UFABC
 Prof. Russel