Diferencias

Muestra las diferencias entre dos versiones de la página.

--- ai:techniques:search_algorithms [2010/10/17 09:12]
alfred
+++ ai:techniques:search_algorithms [2020/05/09 09:25] (actual)
@@ Línea 28: / Línea 28: @@
     - De todos los nodos de la lista de nodos cerrados escogemos el de //f// más baja.
   - Si el estado actual es el estado objetivo ya hemos acabado. Si no, volvemos al paso 1.
@@ Línea 82: / Línea 83: @@
-===== Hill Climbing =====
+===== IDA* =====
-El ''hill climbing'' (también llamado ''rather descent'' si su función evalua el coste en vez de la calidad) intenta, en una solución ya existente al problema (que podría haber sido creada de forma aleatoria), hacer cambios hasta conseguir soluciones mejores. \\
+  - Realizamos el cálculo de coste para el nodo 1, ese será el coste (o profundidad) inicial y máximo permitido.
-Representa la búsqueda como un escalador que busca la cima de un monte sólo que no sabe cual es esta. Un monte puede tener varios picos y el escalador puede tomar un pico como la cima. \\
+  - Nos ponemos en el primer nodo.
-Consiste en un bucle que busca incrementar la calidad de una situación, no depende de un árbol de búsqueda (nodos) por lo que ha de poder evaluar dichos nodos (o estados) independientemente. Cuando los estados a los cuales se puede acceder desde el estado actual tienen un valor equivalente el siguiente que se evaluará se seleccionará aleatoriamente. En este algoritmo se distinguen los siguientes conceptos:
+  - Vamos al siguiente nodo (moviéndonos siempre en profundidad, es decir, siempre abriremos el último nodo.
-  * Máxima local: Consiste en un "pico" que puede ser más bajo que el pico más alto y es a la que se ha de llegar ya que, aún no siendo la mejor solución es una satisfactoria.
+  - Si el siguiente nodo no pasa del coste máximo actual lo cogemos como nodo actual y hacemos el paso 3.
-  * Plateaux: Un area en el que al evaluar los siguientes pasos tenemos un valor equivalente. La búsqueda seguirá un camino aleatorio.
+  - Miramos el siguiente que toque (desde un nodo anterior).
-  * Colinas:
+  - Si ningún nodo puede expandirse por superar todos el coste máximo, incrementamos este y vamos al paso 2.
+{{ ai:ida.png |}}
+===== Hill-Climbing =====
+El ''hill-climbing'' (también llamado ''rather descent'' si su función evalua el coste en vez de la calidad, aunque también podríamos convertir el valor de coste a negativo) intenta, sobre una solución ya existente del problema qué cambios hay que hacer hasta conseguir una solución mejor. \\
+Representa la búsqueda que realiza como si fuese un escalador que, en medio de una densa niebla, busca la cima de un monte pero este no sabe cual es, ya que un monte puede tener varios picos y el escalador puede creer que un pico es la cima debido a la niebla. \\
+El algoritmo consiste en un bucle que busca incrementar la calidad de una situación. Empieza con una solución inicial (generada aleatoriamente) y de forma iterativa va haciendo pequeños cambios hasta llegar a la mejor solución que pueda encontrar, entonces usa dicha solución como solución inicial y así continúa. Por lo tanto no depende de un árbol de búsqueda (nodos), es por eso que el problema le ha de permitir evaluar dichos nodos (o estados) de forma independiente. Cuando los estados a los cuales se puede acceder desde el estado actual tienen un valor equivalente el siguiente que se evaluará se seleccionará aleatoriamente. En este algoritmo se distinguen los siguientes conceptos:
+  * Máxima local: Consiste en un "pico" que puede ser más bajo que el pico más alto (óptimo) y es al que ha de llegar ya que, aún no siendo la mejor solución es una satisfactoria.
+  * Explanada: Un area en el que al evaluar los siguientes pasos tenemos un valor equivalente. La búsqueda seguirá un camino aleatorio.
+  * Colinas: Hay máximas locales muy próximas y la búsqueda oscila entre ellas haciendo mínimo o ningún progreso. Si esto ocurre lo mejor que puede hacerse es reiniciar en otro punto aleatorio.
+{{ai:hill_climbing.png?400|}} \\
+Realmente el algoritmo lo que hace es iniciar en una solución aleatoria y busca una mejor y próxima solución hasta encontrar una que no pueda mejorar. Puede restringirse el número de iteraciones en las que permitiremos en las que no se haga un avance, así si hay un máximo restricción de iteraciones permitidas un reinicio aleatorio puede llegar a encontrar la solución óptima. El éxito depende de la diversidad de estados "picos", si sólo existen pocas máximas locales un reinicio aleatorio encontrará una solución óptima bastante rápido, pero por desgracia los problemas reales tienen una superficie parecida a la de un puercoespín, muchas máximas locales. Aún así, y debido a esto, es fácil encontrar rápidamente una buena solución a pesar de que esta no sea la óptima.
 <code>
-http://en.wikipedia.org/wiki/Hill_climbing
+function Hill-Climbing (problema) retorna una posible solución
-    <) Ridges: a ridge may have steeply sloping sides, so that the search reaches the top of the
+  entrada:
-    ridge with ease, but the top may slope only very gently toward a peak. Unless there happen
+    problema
-    to be operators that move directly along the top of the ridge, the search may oscillate from
+  utiliza:
-    side to side, making little progress.
+    currentNode
-    In each case, the algorithm reaches a point at which no progress is being made. If this happens, an
+    nextNode
-    obvious thing to do is start again from a different starting point. Random-restart hill-climbing
+  ejecución:
-    does just this: it conducts a series of hill-climbing searches from randomly generated initial
+    currentNode = getInitialState (problem)
-    states, running each until it halts or makes no discernible progress. It saves the best result found
+    loop do
-    so far from any of the searches. It can use a fixed number of iterations, or can continue until the
+      nextNode = currentNode.getSuccessors().getNodeWithMaximumValue()
-    best saved result has not been improved for a certain number of iterations
+      if (nextNode.value < currentNode.value)
+        return current
+      currentNode = nextNode
+    end loop
+</code>
-Clearly, if enough iterations are allowed, random-restart hill-climbing will eventually find
-the optimal solution. The success of hill-climbing depends very much on the shape of the state-
+==== Variantes ====
-space "surface": if there are only a few local maxima, random-restart hill-climbing will find a
+  * **Stochastic hill climbing**, escoge aleatoriamente entre los siguientes pasos que mejoran la solución actual. Esto generalmente es un ascenso lento pero en algunos problemas puede dar mejores soluciones.
-good solution very quickly. A realistic problems has surface that looks more like a porcupine.
+  * **First-Choice hill climbing** es un stochastic hill climbing pero en la generación de futuros estados. Va generando pasos siguientes hasta que encuentra uno mejor, es decir, será el primer estado mejor el que escoja. Es una buena estrategia cuando el estado tiene muchos sucesores.
-If the problem is NP-complete, then in all likelihood we cannot do better than exponential time.
+  * **Random-restart hill climbing**, genera varios estados iniciales de forma aleatoria (en sí ya es un problema ya que no es trivial), a partir de estos inicia distintas soluciones.
-It follows that there must be an exponential number of local maxima to get stuck on. Usually,
-however, a reasonably good solution can be found after a small number of iterations.
+===== Simulated annealing =====
+Es un hill climbing pero que permite la bajada. El hill climbing tiene el el inconveniente que puede quedarse atascado en una máxima local, pero si, al contrario de esto, realizasemos un movimiento puramente aleatorio sería extremadamente ineficiente a pesar de que podría alcanzar el problema óptimo en algún momento. En metalurgia "annealing" es el proceso para calentar metales y vídrios, moldearlos y luego enfriarlos. Simulated annealing consiste en eso, en subir y bajar la temperatura o, en el caso de un hill climbing, la colina.
+<code>
+función SimulatedAnnealing (problema, organización) retorna un estado solución
+  entrada:
+    problema
+    organización, asigna la relación tiempo\temperatura
+  ejecución:
+    current = getInitialState (problem)
+    for t = 1 hasta infinito hacer:
+      T = organización (t)
+      if T = 0:
+        return current
+      next = current.getRandomSuccessors()
+      ∧E = next.Value - current.Value
+      if ∧E > 0:
+        current = next
+      else if getProbability(∧E, T) > random(0,1):
+        current = next
 </code>
+El loop interno es similar al del hill climbing, pero en vez de escoger el mejor movimiento escoge uno aleatorio, si dicho movimiento mejora la situación será siempre aceptado pero si no a cada paso que se haga será, por probabilidad, más difícil que se siga. Es decir, la mala calidad de la solución hace que la temperatura (//T//) baje y, por lo tanto, la cantidad de evaluación (//∧E//) menor.

Programming

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página