Neighbor selection in simulated annealing algorithm

Question

When picking a neighbor should the algorithm's temperature be considered? So for example if the temperature is high when picking a neighbor should be permutation be made? Or does the temperature only affect the acceptance probability?

Leader

Answer 1

The latter is true: Only the acceptance probability is influenced by the temperature. The higher the temperature, the more "bad" moves are accepted to escape from local optima. If you preselect neighbors with low energy values, you'll 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.

Johppa

Given that pseudo code, it is not defined how neighbor is calculated. Therefore, it is not shown that temperature is not part of the calculation. – Annihilation

Answer 2

Here is description from wikipedia which states that the temperature should be in fact calculated in for some problems.

Efficient candidate generation

A more precise statement of the heuristic is that one should try first candidate states s' for which P(E(s), E(s'), T) is large. For the "standard" acceptance function P above, it means that E(s') - E(s) is on the order of T or less. Thus, in the traveling salesman example above, one could use a neighbour() function that swaps two random cities, where the probability of choosing a city pair vanishes as their distance increases beyond T.

This does imply that Temperature can be relevant factor when determining neighbor.

More useful reading on how to write neighbor function: How to efficiently select neighbour in 1-dimensional and n-dimensional space for Simulated Annealing

Annihilation

Answer 3

I also had the same question, but I think the answer from another post Basics of Simulated Annealing in Python suggests T can be related to choosing neighbors is quite reasonable.

Choosing neighbors will also depend on your problem. The main reason to limit the neighborhood is so that once you've found a decent solution, even if you later move to a worse solution, you at least stay in the neighborhood. The intuition is that most objective functions are somewhat smooth, so good solutions will lie near other good solutions. So you need a neighborhood that's small enough to keep you near good solutions, but large enough to let you find them quickly. One thing you can try is decreasing the neighborhood over time (e.g. make it proportional to the temperature). – hunse Nov 4 '13 at 20:58

Squashy