How important is initial state for local search optimisation? I have been enjoying Pascal van Hentenryck's Discrete Optimisation course and we're in Week 4 on the wonders of Local Search algorithms for combinatorial optimisation.
I'm wondering how important the initial configuration is to the quality of solution achievable in a fixed time or, somewhat equivalently, how quickly a solution of a given quality can be reached.
So if I have a good heuristic or intuition for how to arrange things in the first place, is it helpful to devote some processing time to setting that up or is it all dominated by the effect of the local search process?
For example, in the Cartesian Travelling Salesman Problem (where we're working in a 2D plane and the cost of a journy is simply the straight-line distance) I might &quot;feel&quot; that a good route could roughly follow a clockwise sweep from the centre of the space.  So I could use this to set my initial tour (i.e. order the nodes by their angle from the mean of all points).  This intuition might be rubbish for certain instances and great for others, I was hoping to see a study where (let's say random TSP) instances had been solved by following a heuristic first state as opposed to a completely random (but legal) first state.
A good initial state can often be helpful.  I would guess that there is a significant chance that spending extra time to find a good initial state will be useful.
All we can say in general is that &quot;it depends&quot;.  It depends on the specific problem and the shape of the fitness landscape.  If the problem has few or no local minima, the search might not be very sensitive to the initial state.  If it has many local minima, the search might be very sensitive to the start state, and a good start state might help again.  There are no universal answers that can be supplied.
Usually the only way to answer these questions is to try it and see.  With heuristics, there aren't any provable guarantees and it's often hard to make many predictions based on theory or analysis.