Commonalities in local search (Q2711197)

In this thesis the author proposes a restart mechanism for improving the performance of local search in combinatorial optimization. His aim is to reduce the time spent in `unpromising parts' of the search space. He proposes a general improvement scheme that could work for local search heuristics. He identifies several `building elements' (called commonalities) which are common in the good solutions obtained. Instead of a long run he performs many short runs with initial solutions obtained by perturbing the best solution found so far in such a way that many commonalities of the solutions in the list are preserved. The author performed extensive experiments for several combinatorial optimization problems (e.g. traveling salesman, job shop scheduling etc.) and concludes that his restart mechanism is quite successful.