MECHANISMS FOR LOCAL SEARCH

Local search methods for combinatorial optimization make a series of s teps, at each stage improving the current solution by moving to a neig hbouring solution. This is usually done by considering the neighbourin g solutions one at a time and moving to the first one which gives an i mprovement (a first improving method). In this paper we consider wheth er there are circumstances in which some other strategy will have bett er performance. In exploring this question we begin by giving a theore tical treatment of a simple model with random objective values at each solution point. We carry out some experiments on the Travelling Sales man Problem and the Quadratic Assignment Problem using varying values of a spread parameter, kappa. The value of kappa corresponds to the nu mber of improving solutions looked at before making a move. We also ma ke some conjectures relating the overall performance of the local sear ch method to the average number of solutions which are evaluated befor e a local minimum is reached.