DAA - Algoritmo de escalada

Los algoritmos discutidos en los capítulos anteriores se ejecutan sistemáticamente. Para lograr el objetivo, es necesario almacenar uno o más caminos explorados previamente hacia la solución para encontrar la solución óptima.

Para muchos problemas, el camino hacia la meta es irrelevante. Por ejemplo, en el problema N-Queens, no necesitamos preocuparnos por la configuración final de las reinas ni por el orden en que se agregan.

Montañismo

Hill Climbing es una técnica para resolver ciertos problemas de optimización. En esta técnica, comenzamos con una solución subóptima y la solución se mejora repetidamente hasta que se maximiza alguna condición.

La idea de comenzar con una solución subóptima se compara con comenzar desde la base de la colina, mejorar la solución se compara con caminar cuesta arriba y, finalmente, maximizar alguna condición se compara con llegar a la cima de la colina.

Por lo tanto, la técnica de escalada se puede considerar como las siguientes fases:

  • Construir una solución subóptima que obedezca a las limitaciones del problema
  • Mejorando la solución paso a paso
  • Mejorar la solución hasta que no sea posible ninguna mejora

La técnica Hill Climbing se utiliza principalmente para resolver problemas computacionalmente difíciles. Solo mira el estado actual y el estado futuro inmediato. Por lo tanto, esta técnica es eficiente en la memoria ya que no mantiene un árbol de búsqueda.

Algorithm: Hill Climbing 
Evaluate the initial state. 
Loop until a solution is found or there are no new operators left to be applied: 
   - Select and apply a new operator 
   - Evaluate the new state: 
      goal -→ quit 
      better than current state -→ new current state

Mejora iterativa

En el método de mejora iterativa, la solución óptima se logra al avanzar hacia una solución óptima en cada iteración. Sin embargo, esta técnica puede encontrar máximos locales. En esta situación, no hay un estado cercano para una mejor solución.

Este problema puede evitarse con diferentes métodos. Uno de estos métodos es el recocido simulado.

Reinicio aleatorio

Este es otro método para resolver el problema de los óptimos locales. Esta técnica realiza una serie de búsquedas. Cada vez, comienza desde un estado inicial generado aleatoriamente. Por tanto, se puede obtener una solución óptima o casi óptima comparando las soluciones de las búsquedas realizadas.

Problemas de la técnica de escalada

Máximos locales

Si la heurística no es convexa, Hill Climbing puede converger a máximos locales, en lugar de máximos globales.

Crestas y callejones

Si la función de destino crea una cresta estrecha, entonces el escalador solo puede ascender la cresta o descender el callejón en zig-zag. En este escenario, el escalador necesita dar pasos muy pequeños que requieren más tiempo para alcanzar la meta.

Meseta

Se encuentra una meseta cuando el espacio de búsqueda es plano o lo suficientemente plano como para que el valor devuelto por la función de destino sea indistinguible del valor devuelto para las regiones cercanas, debido a la precisión utilizada por la máquina para representar su valor.

Complejidad de la técnica de escalada

Esta técnica no adolece de problemas relacionados con el espacio, ya que solo analiza el estado actual. Las rutas previamente exploradas no se almacenan.

Para la mayoría de los problemas de la técnica Hill Climbing con reinicio aleatorio, se puede lograr una solución óptima en tiempo polinomial. Sin embargo, para problemas NP-Complete, el tiempo de cálculo puede ser exponencial en función del número de máximos locales.

Aplicaciones de la técnica de escalada

La técnica Hill Climbing se puede utilizar para resolver muchos problemas, donde el estado actual permite una función de evaluación precisa, como flujo de red, problema de viajante de ventas, problema de 8 reinas, diseño de circuito integrado, etc.

Hill Climbing también se utiliza en métodos de aprendizaje inductivo. Esta técnica se utiliza en robótica para la coordinación entre varios robots en un equipo. Hay muchos otros problemas en los que se utiliza esta técnica.

Ejemplo

Esta técnica se puede aplicar para resolver el problema del viajante. Primero se determina una solución inicial que visita todas las ciudades exactamente una vez. Por tanto, esta solución inicial no es óptima en la mayoría de los casos. Incluso esta solución puede resultar muy pobre. El algoritmo Hill Climbing comienza con una solución inicial de este tipo y la mejora de manera iterativa. Eventualmente, es probable que se obtenga una ruta mucho más corta.