- El algoritmo de escalada es un algoritmo de búsqueda local que se mueve continuamente en la dirección de elevación/valor creciente para encontrar el pico de la montaña o la mejor solución al problema. Termina cuando alcanza un valor máximo donde ningún vecino tiene un valor más alto.
- El algoritmo de escalada es una técnica que se utiliza para optimizar los problemas matemáticos. Uno de los ejemplos ampliamente discutidos del algoritmo de escalada es el problema del viajante en el que necesitamos minimizar la distancia recorrida por el vendedor.
- También se le llama búsqueda local codiciosa, ya que sólo mira a su buen estado vecino inmediato y no más allá de eso.
- Un nodo del algoritmo de escalada tiene dos componentes que son estado y valor.
- Hill Climbing se utiliza principalmente cuando se dispone de una buena heurística.
- En este algoritmo, no necesitamos mantener ni manejar el árbol o gráfico de búsqueda, ya que solo mantiene un único estado actual.
Características de la escalada:
A continuación se detallan algunas características principales del algoritmo de escalada de colinas:
Diagrama de espacio de estados para escalar colinas:
El paisaje del espacio de estados es una representación gráfica del algoritmo de escalada que muestra un gráfico entre varios estados del algoritmo y la función objetivo/costo.
En el eje Y hemos tomado la función que puede ser una función objetivo o una función de costos, y el espacio de estados en el eje x. Si la función en el eje Y tiene un costo, el objetivo de la búsqueda es encontrar el mínimo global y el mínimo local. Si la función del eje Y es la función objetiva, entonces el objetivo de la búsqueda es encontrar el máximo global y el máximo local.
Diferentes regiones en el paisaje del espacio estatal:
Máximo local: El máximo local es un estado que es mejor que sus estados vecinos, pero también hay otro estado que es más alto que él.
Máximo global: El máximo global es el mejor estado posible del paisaje del espacio estatal. Tiene el valor más alto de función objetivo.
Estado actual: Es un estado en un diagrama de paisaje donde un agente está presente actualmente.
Máximo local plano: Es un espacio plano en el paisaje donde todos los estados vecinos de los estados actuales tienen el mismo valor.
Hombro: Es una región de meseta que tiene un borde cuesta arriba.
Tipos de algoritmo de escalada:
- Escalada de colinas sencilla:
- Escalada de colinas con el ascenso más pronunciado:
- Escalada de colinas estocástica:
1. Escalada de colinas sencilla:
La escalada simple es la forma más sencilla de implementar un algoritmo de escalada. Solo evalúa el estado del nodo vecino a la vez y selecciona el primero que optimiza el costo actual y lo establece como estado actual. . Solo verifica su estado sucesor y, si encuentra un estado mejor que el actual, se mueve para estar en el mismo estado. Este algoritmo tiene las siguientes características:
- Menos tiempo
- Solución menos óptima y la solución no está garantizada.
Algoritmo para escalar colinas simples:
- Si es el estado objetivo, entonces regresa al éxito y abandona.
- De lo contrario, si es mejor que el estado actual, asigne un nuevo estado como estado actual.
- De lo contrario, si no es mejor que el estado actual, regrese al paso 2.
2. Escalada de colinas con el ascenso más pronunciado:
El algoritmo de ascenso más pronunciado es una variación del algoritmo simple de escalada de colinas. Este algoritmo examina todos los nodos vecinos del estado actual y selecciona el nodo vecino que esté más cerca del estado objetivo. Este algoritmo consume más tiempo ya que busca múltiples vecinos.
Algoritmo para escalar colinas con el ascenso más pronunciado:
- Dejemos que SUCC sea un estado tal que cualquier sucesor del estado actual será mejor que él.
- Para cada operador que aplica al estado actual:
- Aplique el nuevo operador y genere un nuevo estado.
- Evaluar el nuevo estado.
- Si es el estado objetivo, devuélvalo y salga; de lo contrario, compárelo con el SUCC.
- Si es mejor que SUCC, establezca el nuevo estado como SUCC.
- Si SUCC es mejor que el estado actual, establezca el estado actual en SUCC.
3. Escalada de colinas estocástica:
La escalada estocástica no examina a todos sus vecinos antes de moverse. Más bien, este algoritmo de búsqueda selecciona un nodo vecino al azar y decide si lo elige como estado actual o examina otro estado.
comentario css
Problemas en el algoritmo de escalada de colinas:
1. Máximo local: Un máximo local es un estado pico en el paisaje que es mejor que cada uno de sus estados vecinos, pero también hay otro estado presente que es más alto que el máximo local.
Solución: La técnica de retroceso puede ser una solución del máximo local en el paisaje del espacio estatal. Cree una lista de rutas prometedoras para que el algoritmo pueda retroceder en el espacio de búsqueda y explorar otras rutas también.
2. Meseta: Una meseta es el área plana del espacio de búsqueda en la que todos los estados vecinos del estado actual contienen el mismo valor, debido a que este algoritmo no encuentra la mejor dirección para moverse. Una búsqueda de escalada podría perderse en la zona de la meseta.
Solución: La solución para la meseta es dar pasos grandes o muy pequeños mientras se busca, para resolver el problema. Seleccione aleatoriamente un estado que esté lejos del estado actual para que sea posible que el algoritmo pueda encontrar una región que no sea una meseta.
3. Crestas: Una cresta es una forma especial del máximo local. Tiene un área más alta que las áreas circundantes, pero en sí misma tiene una pendiente y no se puede llegar con un solo movimiento.
Solución: Con el uso de la búsqueda bidireccional, o moviéndonos en diferentes direcciones, podemos mejorar este problema.
Recocido simulado:
Un algoritmo de escalada que nunca avanza hacia un valor más bajo garantiza que será incompleto porque puede quedarse atascado en un máximo local. Y si el algoritmo aplica un paseo aleatorio, moviendo un sucesor, entonces puede completarse pero no ser eficiente. Recocido simulado es un algoritmo que produce eficiencia e integridad.
En termino mecanico Recocido Es un proceso que consiste en endurecer un metal o vidrio a una temperatura alta y luego enfriarlo gradualmente, lo que permite que el metal alcance un estado cristalino de baja energía. El mismo proceso se utiliza en el recocido simulado en el que el algoritmo elige un movimiento aleatorio, en lugar de elegir el mejor movimiento. Si el movimiento aleatorio mejora el estado, entonces sigue el mismo camino. De lo contrario, el algoritmo sigue el camino que tiene una probabilidad menor que 1 o se mueve cuesta abajo y elige otro camino.