Seu próximo nível começa aqui
Seu desenvolvimento não pode ter limites. Garanta sua Assinatura Ilimitada e libere uma preparação completa com os melhores professores do Brasil.
Existem algoritmos de busca local estocástica em que a...
Existem algoritmos de busca local estocástica em que
a função passo está implementada em dois estágios.
No primeiro estágio, uma solução vizinha s’ da solução
candidata corrente s é selecionada uniformemente e
depois é aceita, ou não, de acordo com a função de
probabilidade: p(T,s,s’) = 1, se f(s’) f(s); ou p(T,s,s’) =
exp( (f(s)-f(s’))/T ), caso contrário, onde T é um parâmetro
denominado temperatura e f é a função avaliação. Quanto
ao emprego desse critério, conhecido como condição de
Metropolis, tem-se que
A
quando T diminui, a aceitação fica mais rigorosa, ou
seja, uma solução s’ com função avaliação pior que s
tem pouca chance de ser aceita como nova solução
candidata.
B
à medida que T aumenta, menos chance tem uma solução
pior que a solução candidata corrente em ser
aceita como nova solução candidata.
C
existe a possibilidade de uma solução selecionada s’
que melhora a função avaliação ser rejeitada.
D
o algoritmo Simulated Annealing usa o critério de
Metropolis que é parametrizado por um valor fixo de T
E
são exemplos de algoritmos de busca local estocástica
que utilizam esse critério Simulated Annealing, Melhoria
Iterativa Probabilística e Busca Tabu.