Neighbor selection in simulated annealing algorithm

Question

When choosing a neighbor should you consider the temperature of the algorithm? So, for example, if the heat during the assembly of a neighbor must be rearranged? Or does temperature only affect the likelihood of acceptance?

Answer 1

The latter is true: only the probability of acceptance depends on the temperature. The higher the temperature, the more “bad” movements are taken to escape from local optima. If you pre-select neighbors with low energy values, you basically contradict the idea of ​​Simulated Annealing and turn it into a greedy search.

Pseudocode from Wikipedia :

s ← s0; e ← E(s) // Initial state, energy. sbest ← s; ebest ← e // Initial "best" solution k ← 0 // Energy evaluation count. while k < kmax and e > emax // While time left & not good enough: T ← temperature(k/kmax) // Temperature calculation. snew ← neighbour(s) // Pick some neighbour. enew ← E(snew) // Compute its energy. if P(e, enew, T) > random() then // Should we move to it? s ← snew; e ← enew // Yes, change state. if enew < ebest then // Is this a new best? sbest ← snew; ebest ← enew // Save 'new neighbour' to 'best found'. k ← k + 1 // One more evaluation done return sbest // Return the best solution found. 

Answer 2

I also had the same question, but I think the answer from another post of the basics of simulated annealing in Python suggests that T might be related to the choice of neighbors is quite reasonable.

The choice of neighbors will also depend on your problem. The main reason to limit your neighborhood is that as soon as you find a decent solution, even if you later move on to a worse solution, you will at least stay in that area. The intuition is that most objective functions are somewhat smooth, so good decisions will be next to other good ones. So you need an area that is small enough to keep you close to good solutions, but big enough for you to quickly find them. One thing you can try is to reduce time over time (for example, make it proportional to temperature). - hunse Nov 4 '13 at 20:58

Answer 3

Here is a description from Wikipedia that says that the temperature should actually be calculated for some problems.

Effective Candidate Generation

A more accurate heuristic formulation is that one needs to try the first states of the candidate s 'for which P (E (s), E (s'), T) is large. For the "standard" receiving function P above, this means that E (s') - E (s) is of order T or less. Thus, in the traveling salesman example above, you can use the neighbor function (), which swaps two random cities, where the probability of choosing a pair of cities disappears as their distance increases beyond T.

This means that when determining a neighbor, temperature can be a significant factor.

A more useful reading on how to write a neighbor function: How to efficiently select a neighbor in one-dimensional and n-dimensional space for simulated annealing