Algoritmos de búsqueda local son estrategias de optimización que buscan mejorar una solución dada en un espacio de búsqueda, sin necesidad de explorar todos los caminos posibles. Estos algoritmos son eficientes y ahorrativos en términos de memoria y tiempo, pero pueden quedar atrapados en óptimos locales. Este tipo de algoritmo se caracteriza por operar iterativamente, realizando pequeños cambios en la solución actual para mejorarla gradualmente.
En lugar de explorar todo el espacio de búsqueda de posibles soluciones, como lo hacen algunos algoritmos de búsqueda exhaustiva, los algoritmos de búsqueda local comienzan con una solución inicial y luego exploran su vecindad inmediata para encontrar una solución mejor. Este proceso se repite hasta que ya no se pueda mejorar la solución actual, momento en el que se considera que el algoritmo ha convergido a una solución aceptable. Los algoritmos de búsqueda local son particularmente útiles cuando el espacio de búsqueda es grande y la solución óptima no es conocida o no es práctico buscarla exhaustivamente.
Los algoritmos de búsqueda local se centran en mejorar la solución actual, explorando el entorno inmediato de la solución actual. Esto contrasta con los algoritmos de búsqueda informada, que exploran el espacio de búsqueda de manera sistemática
Es el conjunto de soluciones posibles en un problema de búsqueda local. Este concepto ayuda a comprender mejor la búsqueda local.
Es el conjunto de soluciones vecinas a la solución actual. Los algoritmos de búsqueda local exploran el entorno de la solución actual para encontrar soluciones mejoradas.
Algunos algoritmos básicos de búsqueda local incluyen el algoritmo de búsqueda local del mejor y el algoritmo de búsqueda local del primer mejor.
Los algoritmos de búsqueda local pueden quedar atrapados en óptimos locales, lo que significa que pueden encontrar soluciones localmente óptimas, pero no necesariamente la solución global más óptima.
Pseudocódigo:
Función BúsquedaPorMejorMejora(inicio):
solución_actual = inicio
mientras haya mejora en la solución actual:
mejor_vecino = NULL
mejor_valor = valor(solución_actual)
para cada vecino en vecindad(solución_actual):
si valor(vecino) > mejor_valor:
mejor_vecino = vecino
mejor_valor = valor(vecino)
si mejor_vecino != NULL:
solución_actual = mejor_vecino
devolver solución_actual
Pseudocódigo:
Función BúsquedaPorPrimerMejora(inicio):
solución_actual = inicio
mientras haya mejora en la solución actual:
mejor_vecino = NULL
para cada vecino en vecindad(solución_actual):
si valor(vecino) > valor(solución_actual):
mejor_vecino = vecino
romper
si mejor_vecino != NULL:
solución_actual = mejor_vecino
devolver solución_actual
Pseudocódigo:
Función BúsquedaTabú(inicio):
solución_actual = inicio
solución_mejor = inicio
tabú_lista = lista vacía
mientras criterio_de_parada_no_alcanzado:
mejores_vecinos = generar_vecinos_no_tabú(solución_actual, tabú_lista)
mejor_vecino = seleccionar_mejor_vecino(mejores_vecinos)
si valor(mejor_vecino) > valor(solución_mejor):
solución_mejor = mejor_vecino
tabú_lista = actualizar_tabú(tabú_lista)
solución_actual = mejor_vecino
devolver solución_mejor
Pseudocódigo:
Función RecocidoSimulado(inicio, temperatura_inicial, factor_enfriamiento, iteraciones_por_temperatura):
solución_actual = inicio
temperatura_actual = temperatura_inicial
mientras temperatura_actual > 0:
para i en rango(iteraciones_por_temperatura):
nuevo_estado = generar_estado_aleatorio(solución_actual)
delta = valor(nuevo_estado) - valor(solución_actual)
si delta > 0 o probabilidad(e^(-delta / temperatura_actual)) > aleatorio():
solución_actual = nuevo_estado
temperatura_actual = temperatura_actual * factor_enfriamiento
devolver solución_actual
Recursos: Información no disponible
Duración: Información no disponible
Departamento de Sistemas e Informatica
sistemas@itistmo.edu.mx
“Por una tecnología propia como principio de libertad®️”