Montañismo
En el análisis numérico, la escalada es una técnica de optimización matemática que pertenece a la familia de búsqueda local . Es un algoritmo iterativo que comienza con una solución arbitraria a un problema, luego intenta encontrar una mejor solución haciendo un cambio incremental en la solución. Si el cambio produce una mejor solución, se realiza otro cambio incremental a la nueva solución, y así sucesivamente hasta que no se puedan encontrar más mejoras.
Por ejemplo, la escalada de colinas se puede aplicar al problema del viajante de comercio . Es fácil encontrar una solución inicial que visite todas las ciudades, pero probablemente será muy pobre en comparación con la solución óptima. El algoritmo comienza con una solución de este tipo y le hace pequeñas mejoras, como cambiar el orden en que se visitan dos ciudades. Eventualmente, es probable que se obtenga una ruta mucho más corta.
La escalada de colinas encuentra soluciones óptimas para problemas convexos ; para otros problemas, encontrará solo óptimos locales (soluciones que no pueden ser mejoradas por ninguna configuración vecina), que no son necesariamente la mejor solución posible (el óptimo global ) de todas las soluciones posibles ( el espacio de búsqueda ). Los ejemplos de algoritmos que resuelven problemas convexos al escalar colinas incluyen el algoritmo simplex para programación lineal y búsqueda binaria . [1] : 253 Para intentar evitar quedarse atascado en los óptimos locales, se podrían usar reinicios (es decir, búsqueda local repetida) o esquemas más complejos basados en iteraciones (comobúsqueda local iterada ), o en memoria (como optimización de búsqueda reactiva y búsqueda tabú ), o en modificaciones estocásticas sin memoria (como recocido simulado ).
La relativa simplicidad del algoritmo lo convierte en una primera opción popular entre los algoritmos de optimización. Se usa ampliamente en inteligencia artificial , para alcanzar un estado objetivo desde un nodo de partida. En los algoritmos relacionados se utilizan diferentes opciones para los nodos siguientes y los nodos iniciales. Aunque los algoritmos más avanzados, como el recocido simulado o la búsqueda tabú , pueden dar mejores resultados, en algunas situaciones, la escalada funciona igual de bien. La escalada de colinas a menudo puede producir un mejor resultado que otros algoritmos cuando la cantidad de tiempo disponible para realizar una búsqueda es limitada, como con los sistemas en tiempo real, siempre que una pequeña cantidad de incrementos generalmente converja en una buena solución (la solución óptima). o una aproximación cercana). En el otro extremo,La ordenación de burbujas se puede ver como un algoritmo de escalada (cada intercambio de elementos adyacentes disminuye el número de pares de elementos desordenados), sin embargo, este enfoque está lejos de ser eficiente incluso para N modesto, ya que el número de intercambios requeridos crece cuadráticamente.
La escalada es un algoritmo en cualquier momento : puede devolver una solución válida incluso si se interrumpe en cualquier momento antes de que finalice.
