¿Cuáles son las limitaciones del algoritmo de escalada y cómo superarlas?

¿Cuáles son las limitaciones del algoritmo de escalada ? ¿Cómo podemos superar estas limitaciones?

Como @nbro ya ha dicho que Hill Climbing es una familia de algoritmos de búsqueda locales . Entonces, cuando dijiste Hill Climbing en la pregunta, asumí que estás hablando de la escalada estándar. La versión estándar de la escalada tiene algunas limitaciones y a menudo se atasca en el siguiente escenario:

• Máxima local: algoritmo de escalada que alcanza en las proximidades un valor máximo local, se dibuja hacia el pico y se queda atascado allí, sin tener otro lugar a donde ir .
• Crestas: son secuencias de máximos locales , lo que dificulta la navegación del algoritmo.
• Mesetas: Esta es una región plana de espacio de estado . Como no hay que ir cuesta arriba, el algoritmo a menudo se pierde en la meseta.
  

Para resolver estos problemas, se han desarrollado muchas variantes de algoritmos de escalada. Estos son los más utilizados:

• Stochastic Hill Climbing selecciona al azar de los movimientos cuesta arriba. La probabilidad de selección varía con la inclinación del movimiento cuesta arriba.
• Escalada de primera elección implementa el anterior generando sucesores al azar hasta que se encuentre uno mejor.
• Reinicio aleatorio de ascensiones en pendientes desde movimientos iniciales generados aleatoriamente hasta alcanzar el estado objetivo.

El éxito de los algoritmos de subida de colinas depende de la arquitectura del paisaje del estado-espacio. Siempre que haya pocos máximos y mesetas, las variantes de los algoritmos de búsqueda de ascenso en pendientes funcionan muy bien. Pero en el mundo real, los problemas tienen un paisaje que se parece más a una familia ampliamente dispersa de puercoespines calvos en un piso plano, con puercoespines en miniatura que viven en la punta de cada aguja de puercoespín (como se describe en el 4to Capítulo del libro Inteligencia Artificial: A Enfoque moderno). Los problemas NP-Hard generalmente tienen un número exponencial de máximos locales para atascarse.
Se han desarrollado algoritmos dados para superar este tipo de problemas:

• Recocido Estimulado
• Búsqueda de haz local
• Algoritmos genéticos

Libro de referencia - Inteligencia artificial: un enfoque moderno

La escalada no es un algoritmo, sino una familia de algoritmos de "búsqueda local". Los algoritmos específicos que entran en la categoría de algoritmos de "escalada" son 2-opt, 3-opt, 2.5-opt, 4-opt o, en general, cualquier N-opt. Consulte el capítulo 3 del documento " El problema del vendedor ambulante: un estudio de caso en optimización local " (por David S. Johnson y Lyle A. McGeoch) para obtener más detalles sobre algunos de estos algoritmos de búsqueda locales (aplicados al TSP).

Lo que diferencia a un algoritmo en esta categoría de otro es la "función de vecindario" que usan (en palabras simples, la forma en que encuentran soluciones vecinas a una solución dada). Tenga en cuenta que, en la práctica, este no es siempre el caso: a menudo estos algoritmos tienen varias implementaciones diferentes.

La limitación más evidente de los algoritmos de escalada es debido a su naturaleza, es decir, son algoritmos de búsqueda locales. Por lo tanto, generalmente solo encuentran máximos locales (o mínimos). Entonces, si alguno de estos algoritmos ya ha convergido a un mínimo local (o máximo) y, en la solución o en el espacio de búsqueda, existe, cerca de esta solución encontrada, una solución mejor, ninguno de estos algoritmos podrá encontrar esto Mejor solución. Básicamente estarán atrapados.

Los algoritmos de búsqueda locales generalmente no se usan solos. Se usan como subrutinas de otros algoritmos metaheurísticos, como el recocido simulado, la búsqueda local iterada o en cualquiera de los algoritmos de colonias de hormigas. Entonces, para superar sus limitaciones, generalmente no los usamos solos, sino que los usamos junto con otros algoritmos, que tienen una naturaleza probabilística y pueden encontrar mínimos o máximos globales (por ejemplo, cualquiera de los algoritmos de colonias de hormigas).