Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What are some "cookbook" methods for neighborhood structure design in simulated annealing for combinatorial optimization?

Are some reviews or books that contain some "cookbook" methods for neighborhood structure design?


share|cite|improve this question
That's rather broad. Useful state transitions tend to take into account specifics of the problem at hand. Are there any particular optimization problems that you want state transitions for? – joriki Aug 8 '12 at 5:49
What I'm thinking about is a review of some more used methods for state transition so I can get some ideas how to do state transition for my specific problem. – Tianyang Li Aug 8 '12 at 5:52

Useful state transition tend to be such that parts of the solution can be preserved while rearranging the relationships between the parts. For instance, for TSP, a state transition should preserve large parts of the tour and only modify a handful of edges; a typical transition chooses two random edges and swaps their endpoints, i.e. turns $AB$ and $CD$ into $AD$ and $BC$ (taking care to match the endpoints such that the tour remains connected). For spin models, a useful state transition flips entire blocks of spins to keep the relative orientations inside the block intact. There are nifty methods for selecting the blocks such that the boundary includes many mismatched spin pairs without disturbing detailed balance; you can find information on these by searching e.g. for "cluster algorithm" and "spin model".

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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