¿Cuál es la diferencia entre escalada estocástica y recocido simulado?
Estoy leyendo sobre la búsqueda local: escalada y sus tipos, y recocido simulado
Una de las versiones de escalada es "escalada estocástica", que tiene la siguiente definición:
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 elegirlo como estado actual o examinar otro estado.
Algunas fuentes mencionaron que se puede utilizar para evitar los óptimos locales.
Luego estaba leyendo sobre el recocido simulado y su definición:
En cada iteración, se elige un movimiento aleatorio. Si mejora la situación, entonces se acepta el movimiento; de lo contrario, se acepta con alguna probabilidad inferior a 1
Entonces, ¿cuál es la principal diferencia entre los dos enfoques? ¿El estocástico elige solo un sucesor aleatorio (cuesta arriba)? Si elige solo (sucesores cuesta arriba), ¿cómo evita los óptimos locales?
Respuestas
El libro de Russell y Norvig (tercera edición) describe estos dos algoritmos (sección 4.1.1., P. 122) y este libro es la referencia que generalmente debe utilizar al estudiar algoritmos de búsqueda en inteligencia artificial. Estoy familiarizado con el recocido simulado (SA), dado que lo implementé en el pasado para resolver un problema combinatorio, pero no estoy muy familiarizado con la escalada estocástica (SHC), así que permítanme citar las partes del libro que describen SHC .
La escalada estocástica elige al azar entre los movimientos cuesta arriba; la probabilidad de selección puede variar con la inclinación del movimiento cuesta arriba. Esto generalmente converge más lentamente que el ascenso más empinado, pero en algunos paisajes estatales, encuentra mejores soluciones.
Entonces, SHC elige al azar un "movimiento cuesta arriba", es decir, un movimiento que mejora la función objetivo (por ejemplo, si está tratando de resolver el problema del vendedor ambulante , un "movimiento cuesta arriba" podría ser cualquier cambio en el ciclo hamiltoniano actual , una solución, para que el nuevo ciclo halmitoniano tenga un costo menor) entre los movimientos cuesta arriba (es decir, entre algunos conjuntos de movimientos que mejoran el objetivo).
En el recocido simulado , realiza algún movimiento. Si ese movimiento conduce a una mejor solución, siempre se queda con la mejor solución. Si conduce a una peor solución, acepta esa peor solución con cierta probabilidad. Hay otros detalles, como cómo acepta la peor solución (que puede encontrar en el libro de Russell y Norvig), pero esto ya debería aclarar que SA es diferente de SHC: SA puede aceptar peores soluciones para escapar de los mínimos locales, mientras que SHC acepta solo movimientos cuesta arriba.