Hill Climbing

O Hill Climbing é um algoritmo de busca local simples que começa com uma solução inicial e tenta iterativamente melhorá-la, movendo-se para uma solução vizinha com um melhor valor objetivo. Continua até que nenhum vizinho melhor possa ser encontrado (ótimo local).

Como Funciona

O algoritmo avalia a solução atual e seus vizinhos, selecionando sempre o vizinho que oferece a maior melhoria na função objetivo. Este processo continua até não ser possível encontrar qualquer melhoria adicional, indicando que um ótimo local foi atingido.

Pontos Fortes e Fracos

Pontos Fortes

• ✅ Simplicidade conceitual e de implementação
• ✅ Baixo custo computacional por iteração
• ✅ Convergência rápida para um ótimo local

Pontos Fracos

• ❌ Propensão a ficar preso em ótimos locais
• ❌ Inadequado para espaços de busca complexos e multimodais como a otimização semafórica
• ❌ O desempenho depende fortemente da solução inicial
• ❌ Sem mecanismo para escapar de ótimos locais

Aplicabilidade à Otimização Semafórica

Dado a complexidade da otimização semafórica e a probabilidade de múltiplos ótimos locais, o Hill Climbing básico é improvável que encontre soluções globalmente ótimas ou mesmo muito boas. Poderá ser útil para problemas muito simples ou como um componente em algoritmos híbridos mais avançados (por exemplo, Hill Climbing com reinício aleatório, ou como parte do modo Sequencial).

Limitação Fundamental

O espaço de parâmetros semafóricos provavelmente terá muitas "colinas" (ótimos locais) onde uma pequena alteração nos parâmetros poderá melhorar o desempenho, mas um conjunto de parâmetros muito melhor poderá existir noutro lugar. O Hill Climbing, ao observar apenas os vizinhos imediatos, provavelmente ficaria preso numa destas colinas menores e nunca alcançaria o verdadeiro "pico" (ótimo global).