30 ms·
Strange—ingenious. Hill climbing is bad for these sorts of problems since it gets stuck in local maxima—an as the charts in the evaluation show, there are often
by pavpanchekha 13y ago
Strange—ingenious. Hill climbing is bad for these sorts of problems since it gets stuck in local maxima—an as the charts in the evaluation show, there are often multiple maxima in the floating point precision of a program. So instead you need any of a variety of methods that guarantee finding a global maximum eventually. Luckily, MCMC gives you such a guarantee, with better asymptotic probabilistic bounds than simulated annealing. In the evaluation, they have a comparison of MCMC to annealing and hill climbing.
- thisisdave 13y ago>with better asymptotic probabilistic bounds than simulated annealing This seems unlikely to me. The Metropolis algorithm is just simulated annealing with a constant temperature. Which means that simulated annealing includes Metropolis MCMC as a special case. Also, while simulated annealing is guaranteed to find the global optimum given infinite time (almost sure convergence), I'm not aware of any such guarantees for Metropolis.
- jules 13y ago> In the evaluation, they have a comparison of MCMC to annealing and hill climbing. Where do you see that? Searching the document for "annealing" brings up 0 results. They don't do a comparison with hill climbing either.