I've been trying to understand the stochastic hill climber for a while, bu开发者_如何转开发t not having any luck with it. I've looked through a book on heuristics and got a pseudo code. I don't understand what the probability function should look like. I understand that the new solution is piked randomly and accepted based on some probability, what I don't get is how to program this probability. Thanks
PSUEDO-CODE - from How to Solve it: Modern Heuristics - Zbugniew Michalewicz, David Fogel
procedure stochastic hill-climber
begin
t <- 0
select a current string vc at random
evaluate vc
repeat
select the string vn from the neighbourhood of vc
select vn with probability 1/(1+(e^(evaluation(vc) - evaluation(vn))/T))
t <- t + 1
until t=MAX
end
This is a form of Genetic algorithm which has a fitness function called evaluation. It chooses a neighbor with a large positive difference between the current and neighbor. It has a sigmoid activation function 1/(1 + e^(something)) which means that it will map to the interval (0,1). I believe that the T is to reduce the size of the differences over time to allow the answer to eventually converge to a limit. t is just a counter which represents a generation in the algorithm. The algorithm will end as soon as t reaches the max generation. Hope this helps.
精彩评论