Difference between exploration and exploitation in Simulated Annealing algorithm

Question

In evolutionary algorithms, two main abilities maintained which are Exploration and Exploitation.

In Exploration the algorithm searching for new solutions in new regions, while Exploitation means using the already existing solution and make refinements to it so its fitness will improve.

In Simulated Annealing, I don't understand when the Exploration and the Exploitation happen.

For example in Genetic algorithm: the Exploration is happened in the Crossover and Mutation steps, while the selection in Exploitation step.

Answer 1

I personally see it as follows. In simulated annealing the likelihood of choosing a solution from the neighborhood is quite high at the beginning. This phase could be regarded as exploration as the algorithm usually takes relatively big steps in the solution space. Later the likelihood decreases and by doing so the algorithm stays within a certain region of the solution space and just moves with small steps towards the end solutions. This can be regarded as exploitation.

Answer 2

Those two are also called Diversification (Exploration) and Intensification (Exploitation).

In SA, Diversification relates to the larger values of the probability of accepting an inferior neighbor solution, while Intensification relates to the smaller values.

Since the probability is dependent to the difference between the objective of the current and neighbor solutions, it means a bad neighbor is less likely to be chosen when the probability is small.

Note that you can have an adaptive scheme, that is increasing the temperature when there are a number of consecutive iterations with no improving solution. With that, you diversify the search when the intensified area does not yield to a good solution.

BTW, I would suggest you have a look at the threshold accepting (TA) version as well, since there are many researches showing that TA has same or superior solutions than SA, and so there is no need to compute the sophisticated Metropolis probabilities.