Inteligencia artificial

Heurística

Heurística admisible

En ciencias de la computación, específicamente en algoritmos relacionados con búsqueda de caminos, se dice que una heurística (informática) es admisible si nunca sobreestima el costo de alcanzar el objetivo, o sea, que en el punto actual la estimación del costo de alcanzar el objetivo nunca es mayor que el menor costo posible.- ................................:https://es.wikipedia.org/w/index.php?title=Heur%C3%ADstica_admisible&printable=yes

La familia de los algoritmos informados, frente a los desinformados o por fuerza bruta, son aquellos que poseen una información extra sobre la estructura a objeto de estudio, la cual explotan para alcanzar más rápidamente su objetivo final, con un camino de costo mínimo desde el punto inicial al final.

La búsqueda informada es aquella que utiliza el conocimiento específico del problema más allá de la definición del problema en sí mismo, la cual puede encontrar soluciones de una manera más eficiente que una estrategia no informada, increíblemente ineficiente en la mayoría de los casos.

El problema de algunos algoritmos de búsqueda informada en estructuras de relativa complejidad, como puede ser el algoritmo voraz, es que se guían en exclusiva por la función heurística, la cual puede no indicar el camino de coste más bajo, o por el coste real de desplazarse de un nodo a otro (como los algoritmos de escalada), pudiéndose dar el caso de que sea necesario realizar un movimiento de coste mayor para alcanzar la solución. Es por ello bastante intuitivo el hecho de que un buen algoritmo de búsqueda informada debería tener en cuenta ambos factores, el valor heurístico de los nodos y el coste real del recorrido.

A la forma más ampliamente conocida de la búsqueda primero el mejor se le llama búsqueda A* (“búsqueda A estrella”). Evalúa los nodos combinando g(n), el coste para alcanzar el nodo, y h*(n), el coste estimado de ir al nodo objetivo: f*(n) = g(n) + h*(n)

Ya que la g(n) nos da el coste del camino desde el nodo inicio al nodo n, y la h*(n) el coste estimado del camino más barato desde n al objetivo, tenemos:

f*(n) = coste más barato estimado de la solución a través de n.

Así, si tratamos de encontrar la solución más barata, es razonable intentar primero el nodo con el valor más bajo de g(n) + h*(n). Resulta que esta estrategia es más razonable: con tal de que el valor heurístico h*(n) satisfaga ciertas condiciones, la búsqueda A* es tanto completa como óptima.

La optimalidad de A* es sencilla de analizar si se usa con la BÚSQUEDA-ÁRBOLES. En esta caso, A* es óptima si h*(n) es una heurística admisible, es decir, con tal de que la h*(n) nunca sobrestime el coste de alcanzar el objetivo. Las heurísticas admisibles son por naturaleza optimistas, porque piensan que el coste de resolver el problema es menor que el que es en realidad. Ya que g(n)  es el coste exacto para alcanzar n, tenemos como consecuencia inmediata que la g(n) nunca sobrestima el coste verdadero de una solución a través de n.

Un ejemplo obvio de una heurística admisible es la distancia en línea recta h* que usamos para ir a una estación destino de nuestro viaje. La distancia en línea recta es admisible porque el camino más corto entre dos puntos cualesquiera es una línea recta, entonces la línea recta no puede ser una sobrestimación.

El rendimiento de los algoritmos de búsqueda heurística depende de la calidad de la función heurística. Las heurísticas buenas pueden construirse a veces relajando la definición del problema, por costos de solución precalculados para sub-problemas en un modelo de bases de datos, o aprendiendo de la experiencia con clases de problemas.

Particularizando sobre este algoritmo,

Idea:

• Minimizar el coste estimado total de un camino en el árbol de búsqueda.
• Combinar:

– El coste para llegar al nodo n (se conoce exactamente: g), y

– El coste aproximado para llegar a un nodo meta desde el nodo n (estimado por el valor heurístico h*)

Función heurística de A*:

• f (n) = g(n) + h(n): Coste real del plan (camino) de mínimo coste que pasa por n.

• f* (n) = g(n) + h*(n): estimación de f.

Estrategia A*:

• Entre las hojas del árbol de búsqueda, elegir el nodo de valor f* mínimo.

Interpretación fuerte de A*:

• Una heurística suele facilitar la resolución de un problema, pero no garantiza que se resuelva.
• Una heurística es una “regla de tres” para un problema.
• Búsqueda: Optimalidad o incluso completitud no garantizados.

Algoritmo A* – Esquematización –:

• Se basa en la búsqueda general.
• Almacenar el valor g de cada nodo expandido.
• Mantener la estructura abierta ordenada por valores crecientes de f*.
• Insertar nuevos nodos en la estructura abierta según sus valores de f*.

Algoritmo A* – Implementación del algoritmo genérico en pseudocódigo -:

A* (Nodo S0)

abierta <- s="" span="" style="border: 0px; font-family: inherit; font-size: 10px; font-style: inherit; font-weight: inherit; height: 0px; line-height: 1; margin: 0px; outline: 0px; padding: 0px; position: relative; top: 0.5ex; vertical-align: baseline;">0

Repetir

Si vacío? (abierta) entonces

devolver(negativo)

nodo <- abierta="" p="" primero="">

Si meta? (nodo) entonces

devolver(nodo)

sucesores <- expandir="" nodo="" p="">

Para cada n E sucesores hacer

n.padre <- nodo="" p="">

ordInsertar (n,abierta,f*)

Fin{Repetir}

en donde,

Abierta: Estructura dinámica, en nuestro caso a nivel de implementación cola con prioridad según valores de la estimación f*, de almacenamiento temporal del expansionamiento de los nodos intermedios de camino al nodo meta o fin, en este caso destino de nuestro recorrido por el plano del Metro de Madrid; a medida que el algoritmo vaya iterando, esta irá viendo cómo se introducen en el nodos hijos a consecuencia del expansionamiento de sus respectivos antecesores, los cuales se irán ordenando por mínimo f*, dando prioridad no garantiza a nuestra heurística, puesto que estará determinada por los patrones de costes reales asociados, número de paradas y transbordos realizados hasta el momento, y el coste estimado obtenido según rectitud en el camino al nodo meta.

Primero: Nodo que se extrae de la estructura abierta, el cual se somete a comprobaciones de si es nodo meta, factor que determina el comportamiento del algoritmo: si es que si, habrás obtenido el resultado, en caso contrario, expandiremos este y los procesaremos y ordenaremos nuevamente en nuestra estructura temporal.

Especificación del coste real g:

Tomaremos de partida y para relajar la toma de mediciones y las numerosas pruebas en la implementación del algoritmo, que el coste real asociado en cada avance en el cálculo de la mejor solución costará una unidad por movilidad de una estación n1 a otra n2, así como la adición de una unidad extra más para el caso de transbordos entre líneas, si fuera el caso de que n2 perteneciera a una línea con la que n1 no tuviera correspondencia, o en la particularidad de 3 estaciones que, por aspectos de infraestructura, aún encontrándose en la misma línea que sus estaciones antecesora y sucesora, resulta obligatorio un cambio de tren (Estadio Olímpico – línea 7 – , Tres Olivos – Línea 10 – y Puerta de Arganda – Línea 9 -).

Elección del coste estimado h*:

Precisamos que la heurística o coste estimado que tomaremos desde un nodo actual hasta el nodo meta y para todo nodo en el árbol de exploración de camino a la solución será en función de “cuanto de recto” se presenten los nodos; es decir, el coste estimado h* es la distancia en línea recta. En cada nodo hijo, el coste estimado es su distancia en línea recta con el nodo meta. Tomando como referencia que cada estación tiene un punto en el mapa, unas coordenadas en la imagen, y aplicando una escala más o menos aproximada, se logra la obtención de coordenadas reales (valores discretos, relativos) para todas las estaciones, y con ellas, escogiendo las coordenadas de una cualquiera y las de la destino, y haciendo uso de la distancia euclídea, distancia “ordinaria” entre dos puntos de un espacio euclídeo que se deduce a partir del teorema de Pitágoras, averiguar su distancia.

Simulated annealing (SA) (recocido simulado, cristalización simulada o enfriamiento simulado) es un algoritmo de búsqueda meta-heurística para problemas de optimización global; el objetivo general de este tipo de algoritmos es encontrar una buena aproximación al valor óptimo de una función en un espacio de búsqueda grande. A este valor óptimo se lo denomina "óptimo global"

El nombre e inspiración viene del proceso de recocido del acero y cerámicas, una técnica que consiste en calentar y luego enfriar lentamente el material para variar sus propiedades físicas. El calor causa que los átomos aumenten su energía y que puedan así desplazarse de sus posiciones iniciales (un mínimo local de energía); el enfriamiento lento les da mayores probabilidades de recristalizar en configuraciones con menor energía que la inicial (mínimo global).- .............................................:https://es.wikipedia.org/w/index.php?title=Algoritmo_de_recocido_simulado&printable=yes