Búsqueda local guiada

Búsqueda local guiada

La estrategia del algoritmo busqueda local guiado es usar penalizaciones para alentar una técnica de búsqueda local para escapar de los óptimos locales y descubrir los óptimos globales. A algoritmo la búsqueda local se ejecuta hasta que se atasca en un óptimo local. Se evalúan y penalizan las características de los óptimos locales, cuyos resultados se utilizan en una función de coste aumentada utilizada por el procedimiento de búsqueda local. La búsqueda local se repite varias veces usando los últimos óptimos locales descubiertos y la función de costo incrementado que aleja la exploración de soluciones con características presentes en los óptimos locales descubiertos.

El procedimiento de búsqueda local guiada es independiente del procedimiento de búsqueda local integrado. Debe identificarse y utilizarse un procedimiento de investigación apropiado para el campo.

Es posible que sea necesario realizar el procedimiento de búsqueda local guiada durante miles a cientos de miles de iteraciones, cada una de las cuales implica ejecutar un algoritmo de búsqueda local para converger.

El algoritmo fue diseñado para problemas de optimización discreta donde una solución se compone de "características" evaluables de forma independiente, como la optimización combinatoria, aunque se ha aplicado a la optimización de funciones continuas modeladas como cadenas binarias.

El parámetro λ es un factor de escala para la penalización de características que debe estar en la misma proporción con los costos de la solución candidata de la instancia específica del problema al que se aplica el algoritmo. Como tal, el valor de λ debe ser significativo cuando se usa en la función de costo aumentada (como cuando se agrega al costo de una solución candidata en minimización y restado de un costo en el caso de un problema de maximización).

búsqueda local guiada