DAA - Algoritmo de escalada

Os algoritmos discutidos nos capítulos anteriores são executados sistematicamente. Para atingir o objetivo, um ou mais caminhos previamente explorados em direção à solução precisam ser armazenados para encontrar a solução ideal.

Para muitos problemas, o caminho para a meta é irrelevante. Por exemplo, no problema de N-Rainhas, não precisamos nos preocupar com a configuração final das rainhas, bem como em que ordem as rainhas são adicionadas.

Hill Climbing

Hill Climbing é uma técnica para resolver certos problemas de otimização. Nesta técnica, começamos com uma solução subótima e a solução é melhorada repetidamente até que alguma condição seja maximizada.

A ideia de começar com uma solução abaixo do ideal é comparada a começar da base da colina, melhorar a solução é comparada a subir a colina e, finalmente, maximizar algumas condições é comparada a alcançar o topo da colina.

Assim, a técnica de hill climbing pode ser considerada nas seguintes fases -

• Construir uma solução abaixo do ideal obedecendo às restrições do problema
• Melhorando a solução passo a passo
• Melhorar a solução até que nenhuma melhoria seja possível

A técnica de Hill Climbing é usada principalmente para resolver problemas computacionalmente difíceis. Ele olha apenas para o estado atual e o estado futuro imediato. Conseqüentemente, essa técnica é eficiente em termos de memória, pois não mantém uma árvore de pesquisa.

Algorithm: Hill Climbing 
Evaluate the initial state. 
Loop until a solution is found or there are no new operators left to be applied: 
   - Select and apply a new operator 
   - Evaluate the new state: 
      goal -→ quit 
      better than current state -→ new current state

Melhoria Iterativa

No método de melhoria iterativa, a solução ideal é alcançada progredindo em direção a uma solução ideal em cada iteração. No entanto, esta técnica pode encontrar máximos locais. Nesta situação, não há estado próximo para uma solução melhor.

Este problema pode ser evitado por diferentes métodos. Um desses métodos é o recozimento simulado.

Reinício Aleatório

Este é outro método de resolver o problema de ótimos locais. Essa técnica realiza uma série de pesquisas. Cada vez, ele começa a partir de um estado inicial gerado aleatoriamente. Conseqüentemente, a solução ótima ou quase ótima pode ser obtida comparando as soluções das pesquisas realizadas.

Problemas da técnica de escalada

Máxima Local

Se a heurística não for convexa, Hill Climbing pode convergir para máximos locais, em vez de máximos globais.

Cordilheiras e becos

Se a função de destino criar uma crista estreita, o alpinista só poderá subir a crista ou descer o beco em zigue-zague. Nesse cenário, o escalador precisa dar passos muito pequenos, exigindo mais tempo para atingir a meta.

Platô

Um platô é encontrado quando o espaço de busca é plano ou suficientemente plano para que o valor retornado pela função de destino seja indistinguível do valor retornado para regiões próximas, devido à precisão usada pela máquina para representar seu valor.

Complexidade da técnica de escalada

Esta técnica não apresenta problemas relacionados ao espaço, visto que analisa apenas o estado atual. Caminhos explorados anteriormente não são armazenados.

Para a maioria dos problemas na técnica de Hill Climbing de reinício aleatório, uma solução ótima pode ser alcançada em tempo polinomial. No entanto, para problemas NP-Completos, o tempo computacional pode ser exponencial com base no número de máximos locais.

Aplicações da técnica de escalada

A técnica de escalada pode ser usada para resolver muitos problemas, onde o estado atual permite uma função de avaliação precisa, como fluxo de rede, problema do caixeiro viajante, problema de 8 Rainhas, projeto de circuito integrado, etc.

O Hill Climbing também é usado em métodos de aprendizagem indutiva. Esta técnica é usada em robótica para coordenação entre vários robôs em uma equipe. Existem muitos outros problemas quando essa técnica é usada.

Exemplo

Essa técnica pode ser aplicada para resolver o problema do caixeiro viajante. Primeiro é determinada uma solução inicial que visita todas as cidades exatamente uma vez. Portanto, essa solução inicial não é ótima na maioria dos casos. Mesmo esta solução pode ser muito pobre. O algoritmo Hill Climbing começa com essa solução inicial e faz melhorias de forma iterativa. Eventualmente, uma rota muito mais curta provavelmente será obtida.