Mechanisms for local search |
| |
Authors: | E.J. Anderson |
| |
Affiliation: | The Judge Institute of Management Studies, University of Cambridge, Cambridge CB2 1RX, UK |
| |
Abstract: | 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, k. The value of k 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. |
| |
Keywords: | Local search Optimisation Heuristics Travelling Salesman Problem Quadratic Assignment Problem |
本文献已被 ScienceDirect 等数据库收录! |