4.2.3 Guided Local Search

Búsqueda local guiada (GLS) es una alternativa a búsqueda local para hacerla más efectiva.

La idea básica de GLS es aumentar la función objetivo con penalizaciones.

Dada una función objetivo $g$ que mapea una solución candidata $s$ a un valor numérico, GLS define una función $h$ (que reemplaza a $g$) y que es usada por búsqueda local de la siguiente forma:

$$h(s) = g(s) + \lambda \times \sum (p_i \times I_i(s))$$

donde $s$ es la solución candidata, $\lambda$ es un parámetro de GLS, $i$ varía sobre todos los atributos, $p_i$ es la penalización para el $i$-ésimo atributo (las $p_i$s se inicializan a 0) e $I_i$ indica si $s$ tiene el $i$-ésimo atributo (ver tabla 4.3):

$$I_i(s) = \left\{ \begin{array}{rl} 1 & \mbox{ si } s \mbox{... ...mo atributo} \\ 0 & \mbox{ de otra forma} \end{array}\right.$$

Para que búsqueda local pueda salir de óptimos locales, GLS añade penalizaciones a ciertos atributos.

La utilidad de penalizar un atributo $i$ dado un óptimo local $s^*$ es:

$$util_i(s^*) = I_i(s^*) \times \frac{c_i}{1 + p_i}$$

donde $c_i$ es el costo del atributo y $p_i$ es la penalización actual del atributo $i$.

El atributo de mayor utilidad es el penalizado (se incrementa su penalización actual).

Tabla 4.3: Guided Local Search

Veamos primero como prodría aplicarse al TSP antes de ver algunas variantes.