A Escalada Estocástica em Colinas geralmente apresenta desempenho pior do que a Escalada em Colina Mais Íngreme , mas quais são os casos em que a primeira apresenta melhor desempenho?
Os algoritmos de subida mais íngreme funcionam bem para otimização convexa. No entanto, problemas do mundo real são tipicamente do tipo de otimização não convexa: existem vários picos. Nesses casos, quando esse algoritmo inicia em uma solução aleatória, a probabilidade de atingir um dos picos locais, em vez do pico global, é alta. Melhorias como o Simulated Annealing melhoram esse problema, permitindo que o algoritmo se afaste de um pico local e, assim, aumentando a probabilidade de encontrar o pico global.
Obviamente, para um problema simples com apenas um pico, a subida mais íngreme é sempre melhor. Também pode usar a parada antecipada se um pico global for encontrado. Em comparação, um algoritmo simulado de recozimento realmente saltaria para longe de um pico global, retornaria e voltaria a se afastar. Isso repetiria até que esfriasse o suficiente ou que um certo número predefinido de iterações fosse concluído.
Problemas do mundo real lidam com dados barulhentos e ausentes. Uma abordagem estocástica de escalada, embora mais lenta, é mais robusta para esses problemas, e a rotina de otimização tem uma probabilidade maior de atingir o pico global em comparação com o algoritmo mais íngreme.
Epílogo: Essa é uma boa pergunta que levanta uma questão persistente ao projetar uma solução ou escolher entre vários algoritmos: o trade-off custo-desempenho-computacional. Como você deve ter suspeitado, a resposta é sempre: depende das prioridades do seu algoritmo. Se fizer parte de algum sistema de aprendizado on-line que esteja operando em um lote de dados, haverá uma forte restrição de tempo, mas uma fraca restrição de desempenho (os próximos lotes de dados corrigirão o viés incorreto introduzido pelo primeiro lote de dados). Por outro lado, se for uma tarefa de aprendizado offline com todos os dados disponíveis, o desempenho é a principal restrição e as abordagens estocásticas são recomendáveis.
Vamos começar com algumas definições primeiro.
A escalada é um algoritmo de busca que simplesmente executa um loop e se move continuamente na direção de aumentar o valor - ou seja, subindo a colina. O loop termina quando atinge um pico e nenhum vizinho tem um valor mais alto.
A escalada de montanha estocástica , uma variante da escalada, escolhe aleatoriamente dentre os movimentos de subida. A probabilidade de seleção pode variar de acordo com a inclinação da subida. Dois métodos conhecidos são:
Escalada de primeira escolha: gera sucessores aleatoriamente até que seja gerado um que seja melhor que o estado atual. * Considerado bom se o estado tiver muitos sucessores (como milhares ou milhões).
Escalada de reinício aleatório:Trabalha com a filosofia de "Se você não conseguir, tente, tente novamente".
Agora a sua resposta. A subida estocástica de montanhas pode realmente ter um desempenho melhor em muitos casos . Considere o seguinte caso. A imagem mostra a paisagem do espaço de estado. O exemplo presente na imagem é retirado do livro Inteligência Artificial: Uma Abordagem Moderna .
Suponha que você esteja no ponto mostrado pelo estado atual. Se você implementar um algoritmo simples de subida, atingirá o máximo local e o algoritmo será encerrado. Mesmo que exista um estado com um valor de função objetivo mais ideal, o algoritmo falha ao chegar lá, pois ficou preso no máximo local. O algoritmo também pode ficar preso em máximos locais planos .
A reinicialização aleatória em subidas de montanha realiza uma série de pesquisas em subidas de montanha a partir de estados iniciais gerados aleatoriamente até que um estado de objetivo seja encontrado.
O sucesso da escalada depende da forma da paisagem do espaço de estados. Caso haja apenas alguns máximos locais, planaltos planos; A subida aleatória de reinício encontrará uma boa solução muito rapidamente. A maioria dos problemas da vida real tem uma paisagem do espaço de estado muito aproximada, tornando-os inadequados para o uso do algoritmo de escalada em montanhas ou qualquer uma de suas variantes.
NOTA: O algoritmo Hill Climb também pode ser usado para encontrar o valor mínimo , e não apenas os valores máximos. Eu usei o termo máximo na minha resposta. Caso esteja procurando valores mínimos, tudo será inverso, incluindo o gráfico.
Também sou novo nesses conceitos, mas do jeito que eu entendi, a escalada estocástica teria um melhor desempenho nos casos em que o tempo de computação é precioso (inclui o cálculo da função de condicionamento físico), mas não é realmente necessário alcançar o melhor solução possível. Atingir até um ótimo local seria aceitável. Os robôs que operam em um enxame seriam um exemplo em que isso poderia ser usado.
A única diferença que vejo na subida mais íngreme é o fato de que ele pesquisa não apenas os nós vizinhos, mas também os sucessores dos vizinhos, bem como o algoritmo de xadrez busca mais movimentos adiante antes de selecionar a melhor jogada.
fonte
fonte