Guided local search

Guided local search

The strategy of the guided local search algorithm is to use penalties to encourage a local search technique to escape local optima and discover global optima. A local search algorithm is executed until it gets stuck in a local optima. The characteristics of the local optima are evaluated and penalized, the results of which are used in an increased cost function used by the local search procedure. The local search is repeated several times using the last discovered local optima and the increased cost function which guides exploration away from solutions with functionality present in the discovered local optima.

The guided local search procedure is independent of the integrated local search procedure. A research procedure appropriate to the field should be identified and used.

The guided local search procedure may need to be performed for thousands to hundreds of thousands of iterations, each iteration of which involves running a local search algorithm to converge.

The algorithm was designed for discrete optimization problems where a solution is composed of independently evaluable "features" such as combinatorial optimization, although it has been applied to continuous function optimization modeled as strings. binaries.

The parameter λ is a scaling factor for the functionality penalty which must be in the same proportion to the costs of the candidate solution of the specific problem instance to which the algorithm is applied. As such, the value of λ should be significant when it is used in the augmented cost function (such as when it is added to a candidate solution cost in minimization and subtracted from a cost in the case of a maximization problem).

guided local search


To share
%d bloggers like this: