martes

HEURISTICA

La heurística es un rasgo de los humanos, desde cuyo punto de vista puede describirse como el arte y la ciencia del descubrimiento y de la invención o de resolver problemas mediante la creatividad y el pensamiento lateral o pensamiento divergente.

En computación, dos objetivos fundamentales son encontrar algoritmos con buenos tiempos de ejecución y buenas soluciones, usualmente las óptimas (tiempo de ejecucion y espacio). Una heurística es un algoritmo que abandona uno o ambos objetivos; por ejemplo, normalmente encuentran buenas soluciones, aunque no hay pruebas de que la solución no pueda ser arbitrariamente errónea en algunos casos; o se ejecuta razonablemente rápido, aunque no existe tampoco prueba de que siempre será así. Las heurísticas generalmente son usadas cuando no existe una solucion óptima bajo las restricciones dadas (tiempo,espacio,etc.), o cuando no existe del todo.

Desde el inicio de la IA, el término "heurística" osciló entre dos sentidos
fundamentales vinculados a la utilización de información del dominio de problemas (con el fin de hacer una búsqueda más eficiente) y a la imposibilidad de garantizar
encontrar la solución de un problema.
Estas definiciones se refieren, a dos conjuntos diferentes de métodos: dispositivos que mejoran la eficiencia y dispositivos que no garantizan obtener un resultado. El paradigma metaheurístico consiste en una familia de métodos de búsqueda que comenzó a desarrollarse con ese nombre a partir de la década del 80. Estrictamente no se lo considera un paradigma sino simplemente un conjunto de métodos o herramientas de búsqueda, pero es posible que tarde o temprano entre en esta categoría.






SISTEMAS HEURISTICOS



En una primera clasificación podemos decir que los algoritmos heurísticos pueden ser simples o complejos. Los algoritmos simples tienden a tener reglas de terminación bien definidas, y se detienen en un óptimo local, mientras que los algoritmos más complejos pueden no tener reglas de terminación estándar, y buscan soluciones mejores hasta alcanzar un punto de parada arbitrario.

Dentro de los algoritmos heurísticos complejos podemos hacer una segunda clasificación, esta vez orientada a la funcionalidad de los mismos. En primer lugar podemos encontrarnos con algoritmos que fueron diseñados para dar solución a problemas de búsqueda de óptimos o clasificación y por otro lado tenemos los algoritmos que tratan de deducir conocimiento a partir de un conjunto de axiomas, estos últimos conocidos como sistemas basados en el conocimiento.

Entre los algoritmos de busqueda de óptimos se encuentran los siguientes métodos:



Busqueda Tabú

Temple Simulado

Algoritmos Genéticos

Redes Neuronales

Los sistemas basados en el conocimiento definen un área muy concreta dentro de la inteligencia artificial, conocida como Ingeniería del conocimiento. Los sistemas desarrollados en este campo siguen un patrón heurístico similar al razonamiento humano.




Busqueda Tabú



La búsqueda tabú es un procedimiento o estrategia dado a conocer en los trabajos de Glover, y que esta teniendo grandes exitos y mucha aceptación en los últimos años. Según su creador, es un procedimiento que "explora el espacio de soluciones más alla del óptimo local", (Glover y Laguna). Se permiten cambios hacia arriba o que empeoran la solución, una vez que se llega a un óptimo local. Simultáneamente los ultimos movimientos se califican como tabús durante las siguientes iteraciones para evitar que se vuelvan a soluciones anteriores y el algoritmo cicle. El termino tabú hace referencia a un tipo de inhibición a algo debido a connotaciones culturales o historicas y que puede ser superada en determinadas condiciones.



Temple Simulado



El uso del temple simulado en problemas de Optimización se ha extendido desde mediados de los ochenta hasta ahora, a partir de los trabajos de Kirpatrick, Gelatt & Vecchi. Los algoritmos Temple Simulado están basados en una estrecha analogía entre los procesos físicos termodinámicos y los elementos de un problema de optimización combinatoria. Aunque asintóticamente estos algoritmos se comportan como exactos, (un análisis exhaustivo de esta afirmación se puede encontrar en el trabajo de Aarts & Korst), en la práctica se diseñan como heurísticos. El campo de aplicaciones se ha extendido durante estos años. En problemas de rutas destacan las aportaciones de Osman, para el VRP; y Aarts y otros, para el problema del viajante de comercio.



Algoritmos Genéticos



En los años setenta, de la mano de John Holland surgió una de las líneas más prometedoras de la inteligencia artificial, la de los algoritmos genéticos. Son llamados así porque se inspiran en la evolución biológica y su base genético-molecular. Estos algoritmos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica (mutaciones y recombinación genética), así como también a una selección de acuerdo con algún criterio, en función del cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos, que son descartados.



Redes Neuronales



En inteligencia artificial las redes de neuronas artificiales (RNA) son un ejemplo de aprendizaje y procesamiento automático basado en el funcionamiento del sistema nervioso animal. Se trata de simular el comportamiento observado en las redes neuronales biológicas a través de modelos matemáticos mediante mecanismos artificiales (circuitos integrados, ordenadores...). Con las RNA se pretende conseguir que las máquinas den repuestas similares a las del cerebro humano, caracterizadas por su generalización y robustez.



Sistemas expertos



Los sistemas expertos se basan en simular el razonamiento humano con un doble interés: en primer lugar el del analizar el razonamiento de un experto en la materia para poder codificarlo con la ayuda de un determinado lenguaje informático; por otra parte, la síntesis artificial de los razonamientos para que se parezcan a los del experto humano en la resolución de un determinado problema. Estos dos intereses han hecho que los investigadores del campo de la IA intenten establecer una metodología que les permita verificar la "comunicación" con los expertos y separar los distintos tipos de razonamiento (formal, deductivo, inductivo...), además de construir los elementos necesarios para modelizarlos.

Mientras que en la programación clásica se diferencia solamente entre el programa y los datos, en los sistemas expertos se diferencian tres componentes:

Una base de conocimientos
Una base de hechos
Un motor de inferencia

La base de conocimientos almacena toda la información específica relativa al campo de conocimiento deseado. Para ello se hace uso de un lenguaje específico para representar los conocimientos y que permite definir al experto su propio vocabulario técnico.

En la base de hechos se encuentran los datos relativos a los problemas que se quieren resolver con la ayuda del sistema. La memoria de trabajo almacena los resultados intermedios, pudiendo guardar el rastro de las inferencias realizadas. Es por eso que puede utilizarse para explicar la forma en la que el sistema ha deducido la información durante una sesión de trabajo o describir el comportamiento del propio sistema. Al comienzo del período de trabajo, en la base de hechos sólo se encuentran los datos introducidos por el usuario del sistema, pero a medida que actúa el motor de inferencia, almacena las inducciones y deducciones que ha llevado a cabo el sistema para conseguir las conclusiones.

El motor de inferencia, es un programa que a partir del "conocimiento" puede resolver el problema especificado. Esto se consigue gracias a los datos de la base de hechos del sistema. Por lo general, las reglas de la base de conocimiento son silogismos demostrativos (si A es cierto entonces deducimos B). En este caso, el motor de inferencias selecciona, valida y activa las reglas que permiten obtener la solución correspondiente al problema en cuestión.

Existen dos tipos de motor de inferencia: los que emplean el razonamiento aproximado (cuyo resultado puede ser erróneo) y los que usan un tipo de razonamiento a partir del que se puede obtener resultado verdadero.



http://eduardo-aceves.blogspot.com/2010/02/heuristica.html