|
3
|
From what I can gather, there is not much theory behind local search methods like Tabu Search, Simulated Annealing, Large Neighborhood Search, etc. By theory I mean some mathematical argument as to why these methods work in the cases that they do. Despite that I feel there might exist some good theories about such methods that I would be interested in. If someone knows of a good set of such references (maybe survey papers for instance), I would be grateful. |
||
|
|
|
3
|
A list of textbooks and compilations (far from being complete or representative) discussing theoretical aspects -- as well as run-time behaviour and computational results -- of local search techniques ... Collections:
Monographs:
"Classics":
PhD Thesis:
Basics, Rationale and Bibliographies:
|
|||
|
|
|
3
|
There is a large body of work studying the finite-time convergence properties of Simulated Annealing, based on Markov chain models. You could start with the following paper:
There isn't as much theoretical study made into the convergence of deterministic methods like tabu search, even though they have been proven empirically to be more successful in general. |
||
|
|
|
2
|
If you look at something like "Game of life" there are some interesting theory on that (for example you can prove that in the limit your machine starts to make a highway regardless of initial conditions). Most of these methods fall under probabilistic algorithms so there is basically no argument about convergence or complexity. But you can use some of the results from stochastic systems for example we know that symmetric 3D random walks are transient while 2D random walks are null recurrent that explains why most of the agent based methods work nicely in 2D but fail in 3D. (basically a drunk ant will get back home eventually but a drunk bird gets lost forever) |
||
|
|
|
1
|
I liked Pascal Van Hentenryck.'s book on 'constraint-based local search'. |
||
|
|
