# “Cookbook” methods for neighborhood structure design in simulated annealing for combinatorial optimization?

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?

Thanks!

-
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".