1
Buscando Soluções
Busca iterativa (otimização)
CIn- UFPE
2
Problemas de Otimização
 Definição
• Problema onde se busca a melhor de todas soluções segundo
uma dada função de avaliação ou função objetivo
 “Busca clássica” ou planejamento
• Qual é a solução?
• É difícil achar uma mas assim que se acha pára-se de buscar
– Ex. encontrar uma rota entre duas cidades
 Otimização
• Qual é a melhor solução?
• É fácil achar uma mas difícil saber se é a melhor pois a função de
avaliação só permite comparações entre soluções...
– Ex. Girar a antena para melhorar a imagem da TV
CIn- UFPE
3
Problemas de Otimização
 Como resolvê-los?
• Começar com o estado inicial (configuração completa, solução
aceitável), e melhorá-la iterativamente.
• Não interessa o caminho percorrido!!! A SOLUÇÃO É UM NÓ!!
 1001 problemas práticos (comércio, indústria, etc.)
CIn- UFPE
4
Problemas de Otimização
 Localização de Facilidades
• Distribuir facilidades maximizando a satisfação dos demandantes
– Escolher localização de torres de celular em uma cidade de forma a
minimizar o risco de algum telefone ficar descoberto
– Escolher localização de armazéns de forma a minimizar o
deslocamento dos caminhões de entrega até os clientes
 Coloração de grafos:
• colorir mapas usando o mínimo de cores e sem usar mesmas
cores em países vizinhos
– distribuir freqüências Estações de Rádio Base (ERB) de forma a
aumentar as possibilidades de conexão entre telefones celulares
sem permitir interferências
CIn- UFPE
5
Problemas de Otimização
 Job shop
• agendar tarefas de forma a minimizar o tempo ajuste entre elas
– Linhas de montagem
 Caxeiro Viajante
• Visitar cidades uma única vez minimizando a rota total percorrida
– redes de computadores, ...
 Mochila (knapsack)
• Dado um conjunto de objetos, cada qual com um preço e uma
utilidade, determinar um subconjunto com preço total igual a P
que tenha uma utilidade total máxima.
– Alocação de recursos com restrições financeiras
CIn- UFPE
6
Problemas de Otimização
 Os estados podem ser representados sobre uma
superfície (= a função de avaliação)
• a altura de qualquer ponto na superfície corresponde a sua
avaliação
 O algoritmo se “move” pela superfície em busca de
pontos mais altos/baixos
• o ponto mais alto/baixo (máximo/mínimo global) corresponde à
solução ótima
CIn- UFPE
7
Técnicas de Otimização
 Matemáticas ou exatas
•
•
•
•
•
•
Branch and bound
Programação Dinâmica
Programação Linear
Algoritmos gulosos
Indução Matemática
...
 Heurísticas
•
•
•
•
•
•
Hill-Climbing
Simulated Annealing
Busca tabu
Algoritmos Genéticos
Redes neurais
...
CIn- UFPE
8
Algoritmos de (locais) Melhorias Iterativas
 Guardam apenas o estado atual (o local), 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 complexos.
 Hill-Climbing: Subida da Encosta ou Gradiente
Ascendente
• só faz modificações que melhoram o estado atual.
 Simulated Annealing: Resfriamento Simulado
• pode fazer modificações que pioram o estado temporariamente,
para possivelmente melhorá-lo no futuro.
CIn- UFPE
9
Subida da Encosta: algoritmo
 O algoritmo não mantém uma árvore de busca:
• guarda apenas o estado atual e sua avaliação
• É simplesmente um “loop” que se move na direção crescente
(para maximizar) ou decrescente (para minimizar) da função de
avaliação.
 Algoritmo:
função Hill-Climbing (problema) retorna uma solução
variáveis locais: corrente (o nó atual), próximo (o próximo nó)
corrente  Faz-Nó(Estado-Inicial[problema])
loop do
próximo  sucessor de corrente de maior valor (expande
nó corrente e seleciona seu melhor filho)
se Valor[próximo] < Valor[corrente] (ou >, para minimizar)
então retorna corrente (o algoritmo pára)
corrente  próximo
end
CIn- UFPE
Exemplo de Subida da Encosta:
TSP (travel salesman problem)
10
 Cálculo da menor rotas com 5 nós:
• estado inicial = (N1, N2, N3, N4, N5)
• f = soma das distâncias diretas entre cada nó, na ordem escolhida
• operadores = permutar dois nós quaisquer do caminho
• restrição = somente caminhos conectados são estados válidos
• estado final = nó onde valor de f é mínimo
E1 = {N1, N2, N3, N4, N5}
f(e1) = 10
e2 = {N2, N1, N3, N4, N5}
f(e2) = 14
e3 = {N1, N2, N4, N3, N5}
f(e3) = 9
e5 = {N4, N2, N1, N3, N5}
f(e5) = 10
e4 = {N1, N2, N3, N5, N4}
f(e4) = 12
e6 = {N5, N2, N4, N3, N1}
f(e6) = 11
CIn- UFPE
11
Subida da Encosta
 O algoritmo move-se sempre na direção que apresenta
maior taxa de variação para f
 Isso pode acarretar em 3 problemas:
1. Máximos locais
2. Planícies (platôs)
3. Encostas e picos
CIn- UFPE
12
Máximos locais
 Definição
• 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)
 O algoritmo pára no máximo local
• a função de avaliação é menor para todos os estados filhos do
estado atual, apesar de o objetivo estar em um ponto mais alto
– essa função utiliza informação “local”
• só é permitido movimento com taxa crescente de variação
CIn- UFPE
13
Platôs (Planícies)
 Definição
• Uma região do espaço de estados onde a função de avaliação
dá o mesmo resultado
– f(n) = f(filhos(n))
 o algoritmo pára depois de algumas tentativas
CIn- UFPE
14
Encostas e Picos
 Apesar de existir uma direção que leva ao pico, nenhum
dos operadores válidos sozinhos conduz o algoritmo
nessa direção
• os movimentos possíveis têm taxa de variação zero ou negativa
• seria preciso encadear operadores para melhorar a avaliação
CIn- UFPE
15
Subida da Encosta Iterativa
 Nos casos acima, o algoritmo chega a um ponto de onde
não faz mais progresso.
 Solução: reinício aleatório (random restart)
• O algoritmo realiza uma série de buscas a partir de estados
iniciais gerados aleatoriamente.
 Cada busca é executada
• até que um número máximo estipulado de iterações seja
atingido, ou
• até que os resultados encontrados não apresentem melhora
significativa.
 O algoritmo escolhe o melhor resultado obtido com as
diferentes buscas.
CIn- UFPE
16
Subida da Encosta: análise
 O algoritmo é completo?
• SIM, uma vez que cada nó tratado pelo algoritmo é sempre um
estado completo (uma solução)
 O algoritmo é ótimo?
• TALVEZ, quando iterações suficientes forem permitidas... Mas
custa caro!
 O sucesso deste método depende muito do formato da
superfície do espaço de estados:
• se há poucos máximos locais, o reinício aleatório encontra uma
boa solução rapidamente
• caso contrário, o custo de tempo é exponencial.
CIn- UFPE
Resfriamento/Recozimento Simulado
(ou Moqueca Simulada)
17
 Este algoritmo é semelhante à Subida da Encosta, porém
sem reiniciar a busca
• o algoritmo admite retroceder para situações piores com certa
probabilidade que diminui com o tempo
• esses retrocessos são chamados de passos indiretos
 Apesar de aumentar o tempo de busca, essa estratégia
consegue escapar dos máximos locais
 Analogia com cozimento de vidros ou metais:
• processo de resfriar um líquido gradualmente até ele se solidificar
CIn- UFPE
18
Resfriamento Simulado
 O algoritmo utiliza um mapeamento de resfriamento de
instantes de tempo (t) em temperaturas (T)
• pode ser uma função ou pares (t,T)
 Nas iterações iniciais, não escolhe necessariamente o
“melhor” passo, e sim um movimento aleatório:
• se a situação melhorar, esse movimento é escolhido;
• caso contrário, associa a esse movimento uma probabilidade de
escolha menor do que 1.
 Essa probabilidade depende de dois parâmetros, e
decresce exponencialmente com a piora causada pelo
movimento, e-DE/T, onde:
DE = Valor[próximo-nó] - Valor[nó-atual]
T = Temperatura
CIn- UFPE
19
Resfriamento Simulado: algoritmo
 função Resfriamento-Simulado (problema,mapeamento)
retorna uma solução
variáveis locais: corrente, próximo, T (temperatura que controla a
probabilidade de passos para trás)
corrente  Faz-Nó(Estado-Inicial[problema])
for t  1 to  do
T  mapeamento[t]
Se T = 0
então retorna corrente
próximo  um sucessor de corrente escolhido aleatoriamente
DE  Valor[próximo] - Valor[corrente]
Se DE > 0
então corrente  próximo
senão corrente  próximo com probabilidade = eDE/T
CIn- UFPE
20
Resfriamento Simulado
 Com o tempo (diminuição da temperatura), este algoritmo
passa a funcionar como Subida da Encosta.
 O algoritmo é ótimo e completo se o mapeamento de
resfriamento variar suavemente
• isto é, se o mapeamento diminui T suficientemente devagar no
tempo, o algoritmo vai encontrar um máximo global ótimo.
CIn- UFPE
21
Otimização
 Espaço contínuo?
 Dados n computadores num plano, determinar onde
colocar um hub de forma que todos os computadores
fiquem ligados ao hub utilizando o mínimo possível de
fio. (http://acm.uva.es/p/v102/10228.html)
CIn- UFPE
22
Críticas à Busca Heurística
 Solução de problemas usando técnicas de busca
heurística:
• dificuldades em definir e usar a função de avaliação
• não consideram conhecimento genérico do mundo (ou “senso
comum”)
 Função heurística: compromisso (conflito) entre
• tempo gasto na seleção de um nó e
• redução do espaço de busca
• Achar o melhor nó a ser expandido a cada passo pode ser tão
difícil quanto o problema da busca em geral.
CIn- UFPE