How important is initial state for local search optimisation?
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.