Chapter 4 - Busca local

A busca local se importa somente com o estado final, não com o trajeto que foi percorrido. Portanto não guarda os estados anteriores. Exemplo citado do problema de Bucharest, que o retorno esperado era o trajeto de Arad → Bucharest. Esse tipo de busca não é sistematica.

→ Algoritmos de busca local podem solucionar problemas de otimização

Duas grandes vantagens são:

1. Usa pouca memória
2. Pode encontrar uma solução bacana em espaços grandes e infinitos, nos quais os algoritmos sistematicos não performavam bem, praticamente inviáveis.

Problemas de busca/otimização

• Encontra pontos extremos de uma função (mínimo ou máximo): busca a melhor solução a partir de um espaço de busca
• Componentes de problemas de busca:
  • Função objetivo: avalia cada solução;
  • Restrições do problema;
  • Espaço de busca: o domínio da função objetivo.

[File: bc4b45ea-f205-43f0-a16e-6c74498fdca0]

• Um algoritmo de busca local é:
  • Completo: quando sempre encontra uma solução, se existir;
  • Ótimo: sempre encontra o máximo/mínimo global.

Hill climbing

→ Também é conhecido como busca gulosa local

Guarda somente o estado atual e se move em direção ao vizinho que tenha o estado com maior valor. Ele para quando não encontra nenhum vizinho com valor maior que o atual.

O que pode acontecer com o Hill climbing, é que dependendo do estado atual que eu inicio minha busca, ao olhar meus vizinhos e ir para o que tenha maior valor, pode ser que eu não ache a melhor solução, pois caio no máximo local ao invés do máximo global.

Exemplo citado em aula foi o do 8 rainhas.

Esse problema das 8 rainhas, é que se quer uma solução em que as 8 rainhas estejam posicionadas e que nenhuma ataque a outra.

Os movimentos de ataque permitidos são:

• vertical
• horizontal
• diagonal

[File: 501e50b2-5b18-4948-87b3-c2e6db93bad2]

Na imagem acima, esta é a posição inicial do problema das 8 rainhas, gerada aleatoriamente.

O único problema é que a rainha da coluna 4, pode atacar a da coluna 7 e vice versa.

Os estados sucessores são todos os possíveis estados que são gerados ao mover uma peça na mesma coluna. Portanto para uma coluna, temos 7 possibilidades de movimento; Como temos 8 peças, temos a seguinte multiplicação 8x7 = 56 sucessores.

O Hill-climbing pode ficar travado em algumas situações:

→ Como o estado inicial é aleatório pode ser que iniciamos num estado que ficamos no máximo local, no caso que queremos maximizar a função.

→ Problema de ficar preso no Ridge (Crista). Imagem abaixo exemplifica um pouco esta questão. Basicamente o algoritmo fica preso num pico que as próximas opções são piores (no caso andando no eixo X), mas tem opções melhores caso ele ande verticalmente (pelo eixo Y), mas o Hill-Climbing não enxerga esta possibilidade e fica preso.

[File: 9460c902-cb2b-4374-8385-e4a2affcd780]

[File: df64cb14-6b05-4ab1-b5cb-9d33d0539a86]

→ Platôs. O algoritmo pode ficar preso num platô, ou máximo local "flat", a partir deste momento ele não consegue encontrar vizinhos melhores, somente iguais a ele, portanto fica sem saída.

→ Shoulder. Shoulder ou cotovelo, é quando até existe uma saída para o algoritmo, ele tá bem no início e pode encontrar tanto um máximo global ou o máximo local.

[File: f2fab845-1e95-4887-bffe-63083c9e390c]

No Hill-Climbing iniciando num estado aleatório, ele fica travado 86% do tempo, encontrando a solução somente 14% das vezes. Mas ele é mais rápido.

Para ter uma porcentagem de solução melhor, podemos ao encontrar um Platô, considerar se movimentar lateralmente. Neste caso iremos torcer para que este platô seja um cotovelo (shoulder) e com isso encontrar um máximo global ou máximo local. Caso estejamos no platô local máximo, iremos ficar pra sempre neste local, rodando o algoritmo em looping infinito.

Para evitar este problema, podemos delimitar a quantidade de movimentos laterais que iremos realizar. Neste caso conseguimos aumentar a porcentagem de resolução de 14% para 94%. Mas um contratempo desta abordagem é que elevamos a média de quantidade de passos para encontrar uma solução, tornando o algoritmo mais custoso para ser executado.

Variantes do Hill-Climbing

• Hill-Climbing Estocástico:
  • Dentre os vizinhos que melhoram o estado atual, escolhe um aleatoriamente ( ao invés de escolher necessariamente o melhor);
  • A escolha pode ser proporcional a melhora.
• Hill-Climbing Primeira escolha:
  • Ele implementa o estocástico gerando sucessores randomicamente até que o gerado seja melhor que o atual estado.
• Hill-Climbing com Reinício Aleatório:
  • Executa o Hill-Climbing para diversos estados iniciais gerados aleatoriamente. Até que encontre uma solução.
  • É completo
  • Para o exemplo das 8 rainhas ele até que executa rapidamente, mas para casos em que se tenha muitos platôs e máximos locais, ele não é uma boa solução, acaba sendo ineficiente.

Simulated Annealing

• Algoritmo similar ao Hill-Climbing
  • Ao invés de escolher sempre o melhor vizinho, escolhe um vizinho aleatório
• Se o vizinho melhora o valor da função objetivo, então o algoritmo escolhe esse caminho. (Sempre é aceito este movimento)
• O simulated annealing usa analogia da metalurgia / termodinâmica.

A grande diferença pro hill-climbing comum, é que o simulated annealing aceita movimentos que seriam desconsiderados por serem movimentos piores; Mas não é sempre que ele aceita, existe um cálculo de probabilidade para aceitar ou não o movimento proposto.

[File: a9281f1b-3edb-4e93-9eb8-6837263a8644]

No início essa probabilidade é maior (maior temperatura) e menor no final (menor temperatura);

A aceitação de movimentos para estados piores no início permite ao algoritmo escapar de mínimos locais e explorar mais amplamente o espaço de busca, aumentando a chance de encontrar a solução ótima global. Conforme a temperatura diminui, o algoritmo se comporta de maneira mais similar ao Hill-Climbing, tornando-se mais seletivo e refinando a busca para encontrar a melhor solução possível.

Local Beam Search

→ A busca em feixe (beam search) trabalha com k estados simultâneos, diferentemente dos algoritmos de busca local anteriores.

→ A cada iteração do algoritmo, são gerados os sucessores dos k estados:

- Se encontrar a solução, finaliza;
- Caso contrário, seleciona os k melhores sucessores para a próxima iteração.

→ Informações relevantes são passadas entre threads das buscas paralelas.

Este comportamento faz o algoritmo redirecionar os recursos para aonde pode obter melhores soluções.

A busca em feixe pode sofrer de falta de diversidade entre os estados k.

Stochastic Beam Search

• Similar à ideia do Hill-Climbing Estocástico;
• A Busca em Feixe Estocástica escolhe k vizinhos aleatoriamente, com probabilidade proporcional ao valor da função objetivo de cada vizinho.
  • Isto faz a busca estocástica em feixe ser mais diversificada do que a busca em feixe.
  • Sucessores com melhor desempenho têm maior chance de serem escolhidos, mas os piores ainda têm uma chance menor de serem selecionados.

A Busca em Feixe é mais determinística e focada nos melhores sucessores, enquanto a Busca em Feixe Estocástica é mais exploratória e aleatória, permitindo uma busca mais diversificada.