The Guided Local Search Project

Chris Voudouris photo
Edward Tsang photo
Patrick Mills photo
Tung Leng Lau photo
Abdullah Alsheddy photo
Chris
Voudouris
Edward
Tsang
Patrick
Mills
Tung-Leng
Lau
Abdullah
Alsheddy
Line break

Guided Local Search (GLS) is a general meta-stochastic 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 non-trivial number of problems, including: artificial problems, standard optimization problems and real life problems and achieved excellent results in both efficiency (in terms of speed) and effectiveness (in terms of quality of solutions).

Patrick Mills extended GLS by adding Aspiration and Randomness into the GLS. The resulting algorithm, EGLS (Extended GLS), is less less sensitive to the setting of the major parameter (Lamda-coefficient).

Alsheddy extended GLS to multi-objective optimization.

GLS_Solver is a solver that implements GLS in the SAT, Max-SAT and the QAP. A large number of measures are available (see details here) for the users to monitor and analyse the performance of GLS. This software enables the users to reproduce all the results that we have published in this project.

Some of the applications of GLS are:

GLS has been incorporated in ILOG Dispatcher, a commercial package for vehicle routing, which was featured in the February 2002 issue of OR/MS Today, a magazine published by INFORMS (the Institute for Operations Research and the Management Sciences). It is also used in various projects by British Telecom; it is part of their iOpt optimisation toolkit (cached).

GLS was extended from GENET, though it has a much larger scope than GENET, and has been demonstrated in more problems. It has now been followed up by researchers outside our group. Some of their publications known to us can be found in the GENET-related work page.

GENET and GLS Development History:


Publications icon Publications demos icon GLS Demos

Acknowledgements

This research originated as part of the GENET project, which was funded by EPSRC grant (GR/H75275) from 1st January 1993 to 30th September 1995. A three year EPSRC-funded project (GR/M46297) to characterise and extend GLS will start in mid-1999. Edward Tsang, Chang Wang, Jim Doran, James Borrett, Andrew Davenport, Kangmin Zhu and Chris Voudouris (in chronological order) have all contributed to the GENET project. Nathan Barns was sponsored by a BT Studentship. Tung-Leng Lau was sponsored by a University of Essex Scholarship, 1995-1998.

Line break
 

page maintained by: Chris Voudouris and Edward Tsang

Constraint Satisfaction Home Logo Constraint Satisfaction Home Page