SA is not a magic answer to problems although it may seem such, and although it is often presented with a touch of mysterious glory. Since SA has no memory, and since not even a nearly full search can be performed during the algorithm, there must exist another way within its operation to help it find its way. This is what the design of the state space and transitions achieves, and with which SA rises and falls. In some problems the original intuitive problem formulation is naturally suitable for SA, but in others the problem should be translated into a suitable representation, requiring good understanding of both the implementation area and SA itself.
Although the theory of simulated annealing does not pose any constraints or restrictions on the shape of the state space, in practice some state spaces do behave much better than others during annealing. For annealing to function properly, either the system must reach thermal equilibrium at each temperature and the temperatures must be lowered slowly enough, as described by the theory of SA, or the energy function of the state space must be locally rather smooth. The latter condition depends on the problem formulation, in particular on the states and the transitions. The first condition can almost never be satisfied adequately, and therefore the problem representation is essential. To be able to transform any problem into one suitable for SA, a thorough understanding of the application area is important. The importance of the appropriate problem formulation does not seem to be adequately stressed in the literature on application of SA.
In future, theoretical work is needed on SA to define in exact mathematical terms what properties does a successful implementation of SA have. So far the situation has been somewhat amusing: theoretical grounds that determine the success have indeed been defined but the conditions are impossible to fulfill in practice due to time constraints. Therefore there is no general awareness of why the current implementations actually do work despite that they do not follow the theoretical limits.
Empirical guidelines (if not even mathemathical analysis) could perhaps be defined for the relationship between annealing times and the ratio of search space vs. the longest transition paths required to cover it. The optimal value necessarily resides between 1:N and N:N but it remains to be seen whether an optimum independent of any particular implementation exists.
If criteria for a successful state space connectivity can be found, also a method for constructing such state spaces would be useful. Similar methods guiding the selection of good annealing schedules have already been studied both empirically and theoretically. Now the same remains to be done for the design of the state space and the selection of transitions.