I. INTRODUCCIÓN
Desde hace ya muchos años la inteligencia artificial busca encontrar métodos o búsquedas que permitan llegar a una solución factible de un problema, es así que en 1963 Newell investigó el proceso de resolución de un problema y para ello se inauguró el primer laboratorio de sistemas expertos, denominado Heuristic Programming Project.
Como ya he ido explicando a lo largo de las publicaciones, el objetivo de la inteligencia artificial es resolver problemas en los que no se tenga conocimiento suficiente para plantear una solución, sin embargo, en ocasiones podemos saber de qué se trata el problema y tener información sobre el mismo, y no saber cómo encontrar una solución, es por esto que se usan las denominadas estrategias de búsquedas informadas o búsquedas heurísticas, para lo cual se requieren funciones heurísticas de las que hablaré más adelante (Ramírez y Laureano. 2008)
La palabra Heurística en sí, viene del griego heuriskein y su significado es encontrar o descubrir algo, sin embargo de este algo se debe tener un previo conocimiento, la heurística busca encontrar una solución dado un estado inicial, siguiendo una secuencia de pasos que nos lleven a la meta.
II. OBJETIVO
Conocer cómo funcionan las funciones heurísticas.
III. MARCO TEÓRICO
Una vez entendido que las búsquedas con información son aquellas búsquedas quizá más complejas debido a que el agente debe tener previa información, pero a la vez sencillas debido a que se encuentra una solución de manera más rápida, se debe entender qué es lo que permite que una búsqueda informada se realizase y esto es: La función heurística.
3.1. ¿QUÉ ES UNA FUNCIÓN HEURÍSTICA?
La función heurística es denotada como h(n) que significa coste estimado del camino más barato desde el nodo n hasta el nodo objetivo, por ejemplo para la búsqueda voráz primero el mejor la función heurística es f(n) = h(n) mientras que para la búsqueda A* la función es: f(n) = g(n) + h(n).
Imagen 3.1: 8- Puzzle
En el caso del puzzle 8, de la imagen 3.1 existen 181.440 estados posibles a alcanzar debido a que el factor de ramificación es aproximadamente 3 ya que si la ubicación es una esquina existen 2 posibles movimientos, si está en medio existen 4 y si está en el borde de una línea existen 3 posibilidades por lo tanto la media es 3.
Imagen 3.2: 15- Puzzle
El puzzle 8 tiene una cantidad considerable de estados sin embargo manejable, lo cual no ocurre con el 15- puzzle de la imagen 3.2 el cual tiene una cantidad de estado posibles de 10^13, por lo tanto se requiere analizar una función heurística que permita encontrar el resultado , un ejemplo puede ser:
h1= Contar las piezas que están en una posición incorrecta, en el caso de la imagen 3.2 todas las piezas están en posición incorrecta.
h2= Las distancias son sumadas hasta llegar a un nodo objetivo y se suman los pasos horizontales y verticales.
3.2. LA PRECISIÓN DE LA HEURÍSTICA EN EL RENDIMIENTO.
Para saber si nuestra función heurística es la adecuada se evalúa el rendimiento mediante el factor de ramificación eficaz.
El factor de ramificación eficaz puede variar según el problema y es usado generalmente para problemas más difíciles, una función heurística adecuada sería aquella que tenga el valor de b* el cual es el factor de ramificación, en 1 o cerca de 1.
3.3 INVENTAR FUNCIONES HEURÍSTICAS ADMISIBLES.
Cuando un problema no tiene tantas restricciones que le permitan alcanzar una función objetivo, se denomina problema relajado, en este caso el 15-puzzle y el 8-puzzle no son problemas relajados debido a la restricción de sólo mover horizontal y verticalmente.
Cuando un problema es relajado el costo para la función óptima es una heurística admisible para el problema original, es decir admitidas por el mismo.
Un problema que no se relajado puede convertirse en esto, si se definen utilizando el lenguaje formal, por ejemplo: Una ficha puede moverse desde la casilla A hacia la casilla B.
3.3.1. ABSOLVER
Absolver es un programa creado con la finalidad de generar heurísticas a partir de un problema, este programa generó una función heurística para el 8-puzzle y encontró la mejor heurística para solucionar el cubo Rubik (Russell y Norvig. 2008).
3.4. APRENDIZAJE DE HEURÍSTICAS DESDE LA EXPERIENCIA
Una función heurística ve el costo de llegar a una solución que comienza desde el nodo n, una forma de aprender es a través de la experiencia ya que cada solución óptima propone ejemplos para aprender de la función heurística denotada como h(n) (Russell y Norvig. 2008).
El aprendizaje inductivo es aquel en el que se evalúa el costo de solución para los estados que pueden surgir a lo largo de la búsqueda de una solución.
Para que los métodos inductivos trabajen de mejor manera se deben proporcionar características más que solamente la descripción de los posibles estados, un ejemplo claro podría ser un agente que se encuentra perdido y tiene 3 caminos, esa sería una descripción pero las características de los caminos posibles serviría de mucha ayuda para determinar el camino objetivo mejor, por ejemplo analizar la distancia desde donde está ubicado hasta el final del camino.
IV. CONCLUSIÓN
Las búsquedas informadas o búsquedas heurísticas son utilizadas cuando se tiene cierta información de los estados a extender en un problema, sin embargo, para realizar una búsqueda correcta, se necesitan de funciones acordes al tipo de estrategia de búsqueda y el tipo de problema, estas son denominadas funciones heurísticas.
La heurística es utilizada desde tiempos remotos en la inteligencia artificial para ayudar a resolver un problema del que se tenga alguna información, es muy importante establecer funciones adecuadas como las establecidas en la búsqueda primero el mejor y en la búsqueda A*.
Se puede aprender sobre las funciones heurísticas evaluando el costo que corresponde moverse desde un estado hacia otro.