artificial intelligence - subiendo - Ejemplo simple de algoritmo de escalada
inteligencia artificial hill climbing (7)
Aquí está la solución:
A -> F, con el menor costo posible F -> G con costo 3 pero no hay camino.
Reinicie desde el menor costo posible que no sea G, bueno, es E porque E ya se insertó en la cola / pila / cola de prioridad o en la estructura de datos que use.
Por lo tanto, E -> I, pero tengo un costo mayor que E, por lo tanto, estás atascado: S
Reinicie desde el menor costo que no sea FE & G, por lo tanto elegimos J porque J tiene un costo menor que B con una diferencia de 2, es decir, J = 8 B = 10
J-> K con costo 0 entonces K es la meta
NOTA: la variación propuesta de escalar colinas para elegir un punto al azar, pero elegir el menor costo que no sea el de los nodos ya visitados es mejor que elegir al azar.
OTRA NOTA: es que cuando el nodo E no visitó I porque tengo un valor más alto que E, el algoritmo ya lo insertó en la estructura de datos, por lo que elegir el menor costo que el ya visitado crearía una nueva ruta desde I porque I nunca fue visitado y, por lo tanto, tiene un valor menor que J, este es el único camino que he omitido.
Estoy un poco confundido con el algoritmo de escalada. Quiero "ejecutar" el algoritmo hasta que encuentre la primera solución en ese árbol ("a" es inicial y hyk son estados finales) y dice que los números cerca de los estados son los valores heurísticos. Aquí está el árbol:
Mi pregunta: estoy tratando de correr la escalada de la colina en el árbol, así que bien, empezamos a-> f-> g y luego qué acabamos (sin resultado), pero leí que la escalada de la colina no puede volver y hacer una nueva elección (ejemplo j o e)? Es esto correcto ? Si puedo volver entonces, ¿cómo? Me refiero a dónde cambiamos nuestro ejemplo de elección inicial, elegimos e en lugar de g o j en lugar de f
Lo siento si mi pregunta es demasiado simple.
En realidad, en Hill Climbing, por lo general no retrocede, porque no está haciendo un seguimiento del estado (es una búsqueda local) y se alejaría de un máximo. Tampoco el retroceso o la búsqueda de tabú ayudan a responder la pregunta: el primero simplemente lo aleja de un máximo local y el segundo evita que vuelva a visitar los mismos máximos locales. Tampoco te ayudaría a alcanzar un máximo global. - Tyson Oct 16 ''12 a las 22:59
"donde recuerde los malos resultados anteriores y evítelos a propósito" No estoy de acuerdo, marca como tabú también buenas soluciones, pero no quiere seguir el mismo camino de nuevo. -
La escalada en una colina no tiene ninguna garantía contra quedarse atrapado en un mínimo / máximo local. Sin embargo, solo la forma más pura de escalar montañas no te permite retroceder.
Un simple riff en escalada que evitará el problema de los mínimos locales (a expensas de más tiempo y memoria) es una búsqueda tabú, donde se recuerdan los malos resultados anteriores y se los evita a propósito.
Una forma común de evitar atascarse en los máximos locales con la escalada en colina es usar reinicios aleatorios. En su ejemplo, si G es un máximo local, el algoritmo se detendría allí y luego seleccionaría otro nodo aleatorio para reiniciar. Entonces, si J o C fueron seleccionados (o posiblemente A, B o D), encontraría los máximos globales en H o K. Enjuague y repita suficientes veces y encontrará los máximos globales o algo cercano; Dependiendo de las limitaciones de tiempo / recursos y el espacio del problema.
Tenga en cuenta que la búsqueda local como Hill Climbing no está completa y no puede garantizar encontrar los máximos globales. El beneficio, por supuesto, es que requiere una fracción de los recursos. En la práctica y aplicada a los problemas correctos, es una solución muy efectiva.
el camino de acuerdo con la escalada pura será a-> J -> k si expande a los niños de izquierda a derecha, si los expande de derecha a izquierda, entonces obtendrá estos mínimos locales A -> F -> G, pero Generalmente nos expandimos de izquierda a derecha.
uno de los problemas con la escalada es quedarse atascado en los mínimos locales y esto es lo que sucede cuando alcanza F. Una versión mejorada de la escalada (que en realidad se usa prácticamente) es reiniciar todo el proceso seleccionando un nodo aleatorio en el buscar árbol y nuevamente continuar hacia la búsqueda de una solución óptima. Si una vez más te quedas atascado en algún mínimo local, tienes que reiniciar de nuevo con algún otro nodo aleatorio. Generalmente hay un límite en el no. Con el tiempo, puede volver a realizar este proceso de búsqueda de la solución óptima. Una vez que alcanza este límite, selecciona el mínimo entre todos los mínimos locales que alcanzó durante el proceso. A pesar de que aún no está completo, este tiene mejores posibilidades de encontrar la solución óptima global.
Puede intentar usar una técnica llamada recocido simulado para evitar que su búsqueda se quede atascada en los mínimos locales. Esencialmente, en el recocido simulado, hay un parámetro T que controla su probabilidad de hacer un movimiento a estados vecinos subóptimos. Si T es alto, es más probable que realice un movimiento subóptimo a un estado vecino y, por lo tanto, podría escapar a un mínimo local cuando se quede atascado allí, lo cual no haría si usara una escalada normal.