4

Russell and Norvig's book (3rd edition) describe these two algorithms (section 4.1.1., p. 122) and this book is the reference that you should generally use when studying search algorithms in artificial intelligence. I am familiar with simulated annealing (SA), given that I implemented it in the past to solve a combinatorial problem, but I am not very ...


3

Tabu search uses memory to rule out parts of the neighborhood for local search, allowing the trajectory to typically pass through local optima instead of getting stuck in them.


3

You could parallelize the search by dividing the global space in distinct regions/subsets. Then apply in each region a local search. This way you can search the global space systematically, more exhaustively and perhaps in different ways (e.g by applying a different local search method to each region). Finally you can compare the results and choose the best ...


2

In the least technical, most intuitive way possible: Simulated Annealing can be considered as a modification of Hill Climbing (or Hill Descent). Hill Climbing/Descent attempts to reach an optimum value by checking if its current state has the best cost/score in its neighborhood, this makes it prone to getting stuck in local optima. Simulated Annealing ...


1

Note that you can't really predict whether your escape from a local minimum will work or not - you might just wind up in another, worse local minimum. The probability function you describe increases the likelihood of this happening. By upweighting the likelihood of allowing small energy differences, you allow for the possibility of escaping local minima, ...


1

After diving deeper into the material I am able to answer my own question: Simulated Annealing tries to optimize a energy (cost) function by stochastically searching for minima at different temparatures via a Markov Chain Monte Carlo method. The stochasticity comes from the fact that we always accept a new state $c'$ with lower energy ($\Delta E < 0$), ...


1

Simulated annealing is just one of the approaches for an optimization problem: Given a function f(X), you want to find an X where f(X) is optimal (has maximum or minimum value). Shaking (a methaphor for introducing a degree of randomness to annealing process) is used to prevent the algorithm from stopping prematurely, when only a sub-optimal solution (...


Only top voted, non community-wiki answers of a minimum length are eligible