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

  • $\begingroup$ Given a lack of details in the question, I can only give a broad answer: in general, an initial configuration can be extremely important. Local search is often used for NP-hard problems, some even without any finite polynomial-time approximation (assuming $P \ne NP$). Of course, if you start directly from the optimal solution, you'll get a much better answer than if you start from a random configuration. $\endgroup$ – Dmitry Sep 11 '20 at 11:17
  • $\begingroup$ Thank you @Dmitry; you're right, my question is a little vague. I guess I was hoping that some studies had been done on specific problems - I've search Google Scholar, but not found anything that fits. I will amend my problem question with a slightly more concrete example. $\endgroup$ – Mr Felix U Sep 11 '20 at 11:39
  • $\begingroup$ I don't know about TSP, but maybe the following somehow answers your general question: 1) One advantage of local search is that it can be applied after any other algorithm. Since a) it can only improve a solution and b) some solutions often outperform randomly initialized local search, one can say that initialization is important. (Note however, that local search probably won't improve a good solution too much). 2) One may think about k-means as a local search algorithm In this case, en.wikipedia.org/wiki/K-means%2B%2B initialization provides some guarantees, why a random one don't. $\endgroup$ – Dmitry Sep 11 '20 at 13:43
  • 1
    $\begingroup$ The initial state is of utmost importance. For example, if the initial state is a global optimum, then the algorithm is guaranteed to perform optimally. In practice, one often tries many different initial states. $\endgroup$ – Yuval Filmus Sep 11 '20 at 19:35

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


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.