GUIDED LOCAL SEARCH AND ITS APPLICATIONS
Dr Edward Tsang, Department of Computer Science, University of Essex

Abstract: In this talk, I describe a search strategy called Guided Local Search and its applications. Guided Local Search is a general meta-heuristic search strategy for solving constraint satisfaction and optimization problems. It is a control strategy designed to sit on top of hill-climbing algorithms to help them to escape local optima. It has been applied to a number of problems, including artificial problems (including constraint satisfaction), standard optimization problems (such as the travelling salesman problem and the quadratic assignment problem) and real life problems (such as British Telecom's workforce scheduling problem, the radio length frequency assignment problem, vehicle routing, etc.) and has achieved outstanding results in both efficiency (in terms of speed) and effectiveness (in terms of quality of solutions).

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 11 March 1998.

back