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 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:
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.
|Constraint Satisfaction Home Page|