5
$\begingroup$

Simulated annealing is a useful technique for finding near-optimal solutions to combinatorial problems. I have found a lot of tutorials on implementing the basic algorithm, but miss a general guide as to how constraints are incorporated into the optimization.

I wonder if anyone knows any sources for advice or algorithms for incorporating constraints into simulated annealing applications.

NB: I have constructed some algorithms for generating feasible permutations of the solutions, but would like to see more general results.

Any help is greatly appreciated

$\endgroup$
  • $\begingroup$ Just a suggestion: Instead of constraints, would a penalty-term added to the objective function be feasible? $\endgroup$ – André Dec 28 '17 at 21:22
  • $\begingroup$ Yes. The question is then how the penalty term should be weighed against the function to be minimized. $\endgroup$ – user3124074 Dec 29 '17 at 5:07
2
$\begingroup$

Simulated annealing comes from computations in statistical mechanics. When I think of simulated annealing, I very much think in terms of physics: I want to minimize some potential energy function that depends on the configuration, and whose global minimum corresponds to an optimal solution of your problem. At high temperature, there is enough kinetic energy available to go against the potential gradient, i.e. you are more likely to move toward a configuration of higher potential energy than when the temperature is low. If you think about a mountainous landscape with some marbles in it, and you shake it like crazy, the marbles may move in all directions, often uphill. If you only slightly shake it, marbles in local minima will slightly move around the minimum, only when the minimum is very shallow it may move out and roll down to further lower the potential energy. If you start at high temperature and slowly go down, the marbles will initially be shaken out of (and into) even very deep local minima, but later on they will not return to minima for which a high potential barrier has to be overcome.

In simulated annealing this time factor is absent, but otherwise the idea is the same. Instead of the next configuration in terms of the system's time evolution, a general nearby configuration (in any sense) is considered and accepted or rejected with the appropriate, temperature dependent, probability. When the ergodic hypothesis is assumed for the system, in the long run you will, roughly speaking, find the same configurations, but for practical applications you don't need to bother with such technicalities.

In statistical mechanics, the transition probability would be based on the Boltzmann distribution of configurations, but again, if you just want to optimize a wide range of transition probabilities will do the trick for you.

After all these digressions, let's assume that your transition probability as a function of the energies of the two configurations and the temperature is given. Then there are two steps left where you can deal with your particular constraints: the generation of neighboring states, and the definition of the energy function. If you have a hard constraint on state, i.e. some states are strictly forbidden, you could directly exclude their generation as candidate neighbors. You may even find a way to directly generate random neighboring states following a distribution that takes their energy into account.

Rather than the sampling of neighbors, the obvious step in which to take care of your constraints is in the definition of the energy function, as André said in his comment. Here you can exclude configurations in a straightforward way, by assigning an infinite energy to them; if you assign a very high energy, they will be essentially inaccessible except at very high temperature, allowing you to essentially "tunnel" through them (if you need to allow that).

As a reference for algorithms in statistical mechanics, which explains the context of simulated annealing in an excellent way, I recommend this book by Werner Krauth and the companion online course. If you have a physical analogue for your optimization problem, then this can directly guide you in assigning energies to configurations.

I am not sure if this addresses your question, but I hope it is helpful anyway.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.