Guided local search

The method in its current form was developed by Dr Christos Voudouris and detailed in his PhD Thesis.

[1] GLS was inspired by and extended GENET, a neural network architecture for solving Constraint Satisfaction Problems, which was developed by Chang Wang, Edward Tsang and Andrew Davenport.

Both GLS's and GENET's mechanism for escaping from local minima resembles reinforcement learning.

To apply GLS, solution features must be defined for the given problem.

The choice of solution features depends on the type of problem, and also to a certain extent on the local search algorithm.

(initially set to 0) to record the number of occurrences of the feature in local minima.

In the SAT and weighted MAX-SAT problems, the features can be “whether clause C satisfied by the current assignments”.

When the local search algorithm returns a local minimum x, GLS penalizes all those features (through increments to the penalty of the features) present in that solution which have maximum utility,

The idea is to make the local minimum more costly than the surrounding search space, where these features are not present.

is simply to record the average change in objective function up until the first local minimum, and then set

to this value divided by the number of GLS features in the problem instance.

Mills (2002) has described an extended guided local search (EGLS) which utilises random moves and an aspiration criterion designed specifically for penalty based schemes.

The resulting algorithm improved the robustness of GLS over a range of parameter settings, particularly in the case of the quadratic assignment problem.

A general version of the GLS algorithm, using a min-conflicts based hill climber (Minton et al. 1992) and based partly on GENET for constraint satisfaction and optimisation, has also been implemented in the Computer-Aided Constraint Programming project.

Alsheddy (2011) extended guided local search to multi-objective optimization, and demonstrated its use in staff empowerment in scheduling [citation needed].

GLS was built on GENET, which was developed by Chang Wang, Edward Tsang and Andrew Davenport.