Mechanisms for local search

Local search methods for combinatorial optimization make a series of steps, at each stage improving the current solution by moving to a neighbouring solution. This is usually done by considering the neighbouring solutions one at a time and moving to the first one which gives an improvement (a first improving method). In this paper we consider whether there are circumstances in which some other strategy will have better performance. In exploring this question we begin by giving a theoretical treatment of a simple model with random objective values at each solution point. We carry out some experiments on the Travelling Salesman Problem and the Quadratic Assignment Problem using varying values of a spread parameter, kappa. The value of kappa corresponds to the number of improving solutions looked at before making a move. We also make some conjectures relating the overall performance of the local search method to the average number of solutions which are evaluated before a local minimum is reached.