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?

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.

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