A new approach to choosing initial points in local search (Q1116345)

Local search algorithms for global combinatorial optimization are usually initialized with multiple random solutions. We show that for an arbitrary problem, the use of a systematic initial point procedure based on an arbitrary partitioning of the state space typically outperforms the random initial point procedure. We further show that for one class of search operators it is possible to partition the search space into u- spheres. The use of u-spheres to initialize the search process is then investigated experimentally and shown to be capable of yielding a computational advantage at no added computational cost.