The Guided Local Search Project

Chris Voudouris	Edward Tsang	Qingfu Zhang	Patrick Mills	Tung-Leng Lau	Abdullah Alsheddy	Ahmad Alhindi

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:

• The travelling salesman problem (TSP) (demo available)
• The radio length frequency assignment problem (RLFAP)
• British Telecom's workforce scheduling problem
• The quadratic assignment problem
• F6, an artificial optimization problem
• The vehicle routing problem (GreenTrip Project, involving ILOG and Strathclyde University)
• Staff empowerment in flexible workforce management

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:

• Chang Wang and Edward Tsang first reported GENET for binary problems in 1991; it was extended it to non-binary problems in 1992.
• James Borrett thoroughly studied possible extensions of GENET.
• Andrew Davenport substantially studied and extended GENET (PhD thesis 1996).
• Chris Voudouris generalized GENET to GLS (PhD thesis 1997).
• Patrick Mills characterised and extended GLS (PhD thesis 2002).
• Nathan Barnes attempted to apply Guided Local Search to the vehicle routing problem at Essex.
• Tung-Leng Lau developed Guided Genetic Algorithm (GGA), which is a hybrid system between Genetic Algorithm and GLS (PhD thesis 1999).
• Abdullah Al-Sheddy applies GLS to workforce scheduling (from 2007)
• Ahmad Alhindi added various local search methods, including GLS, to Qingfu Zhang's state-of-the-art multi-objective optimization algorithm MOEA/D

	Publications		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.

Constraint Satisfaction Home Page