Heurística

Ciencia que estudia los procesos de decisión respecto a un campo de conocimiento concreto, como son
las estrategias cognitivas. Su contrapartida formal en computación es el algoritmo.

La palabra heurística proviene de la palabra griega heuriskein que significa descubrir, encontrar. Por
heurística entendemos una estrategia, método, criterio o truco usado para hacer más sencilla la solución
de problemas difíciles. El conocimiento heurístico es un tipo especial de conocimiento usado por los
humanos para resolver problemas complejos. En este caso el adjetivo heurístico significa medio para
descubrir.

Debido a la existencia de algunos problemas importantes con un gran interés práctico difíciles de
resolver, comienzan a surgir algoritmos capaces de ofrecer posibles soluciones que aunque no
consiguen el resultado óptimo, si que se acercan en un tiempo de cálculo razonable. Estos algoritmos
están basados en el conocimiento heurístico y por lo tanto reciben el nombre de algoritmos heurísticos.

Por lo general, los algoritmos heurísticos encuentran buenas soluciones, aunque a veces no hay pruebas
de que la solución pueda hallarse en un tiempo razonablemente corto o incluso de que no pueda ser
errónea. Frecuentemente pueden encontrarse casos particulares del problema en los que la heurística
obtendrá resultados muy malos o que tarde demasiado en encontrar una solución.

Un método heurístico es un conjunto de pasos que deben realizarse para identificar en el menor tiempo
posible una solución de alta calidad para un determinado problema.

Al principio esta forma de resolver problemas no fue bien vista en los círculos académicos, debido
fundamentalmente a su escaso rigor matemático. Sin embargo, gracias a su interés práctico para
solucionar problemas reales fue abriendo poco a poco las puertas de los métodos heurísticos, sobre todo
a partir de los años 60. Actualmente las versiones matemáticas de métodos heurísticos están creciendo
en su rango de aplicaciones, así como en su variedad de enfoques.

Nuevas técnicas heurísticas son utilizadas a diario por científicos de computación, investigadores
operativos y profesionales, para resolver problemas que antes eran demasiado complejos o grandes para
las anteriores generaciones de este tipo de algoritmos.

LA HEURÍSTICA

La heurística es el análisis y la extrapolación de datos basados en experiencias pasadas y en sus

consecuencias, este apartado es de una importancia vital para la IA interna en los juegos de ordenador.

Por ejemplo, un enemigo podrá intentar una aproximación, grabando los resultados de esa
aproximación en su memoria. Si fracasa en su intento de eliminar al jugador, la próxima vez que
intente algo parecido sabrá que, bajo las mismas circunstancias, ha fracasado una vez e intentará otra
ruta de aproximación al jugador. Si por el contrario tiene éxito, aún podrá obtener un aprendizaje de sus
actos, y extrayendo aquellas acciones que más han contribuido a la consecución del fin, que es eliminar
al jugador; así la próxima vez que el ordenador se encuentre en semejante situación. La heurística, por
tanto, permite tener enemigos con memoria.
Heurística e Inteligencia Artificial
Los procesos que se llevan a cabo en el cerebro pueden ser analizados, a un nivel de abstacción dado,
como procesos computacionales de algún tipo.

En cierto sentido, el enfoque heurístico es el característico de la IA. Newell y Simon asociaban el

"método de búsqueda heurística" con el tipo de representación de soluciones parciales. Nosotros nos
vamos a limitar a explicar qué significa el término "heurística" en el ambito de la inteligencia artificial.

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.
Osman y Kelly (1996) describen la metaheurística del siguiente modo: "Estas familias de enfoques
incluyen pero no se limitan a procedimientos adaptativos aleatorios golosos, algoritmos genéticos,
búsqueda de umbral y sus híbridos. Incorporan conceptos basados en la evolución biológica, la
resolución inteligente de problemas, las ciencias matemáticas y físicas, el estudio del sistema nervioso
y la mecánica estadística". Un poco más adelante los autores describen a la disciplina de la siguiente
forma: "Las metaheurísticas son una clase de métodos aproximados, que están diseñados para atacar
problemas de optimización combinatoria difíciles para los que las heurísticas clásicas fracasaron en ser
efectivas y eficientes. Las metaheurísticas proporcionan marcos generales que permiten crear nuevos
híbridos combinando diferentes conceptos de: heurísticas clásicas; inteligencia artificial; evolución
biológica; sistemas neuronales y mecánica estadística".

Finalmente, Osman y Kelly comentan: "Debe notarse que existen convergencias teóricas para algunas
de las metaheurísticas bajo algunos supuestos. Sin embargo, estos supuestos no pueden satisfacerse o
aproximarse en la mayoría de las aplicaciones prácticas. Por lo tanto, se pierde la capacidad para
demostrar optimalidad y se obtienen soluciones aproximadas. A pesar de este inconveniente, las
metaheurísticas han sido altamente exitosas en encontrar soluciones óptimas o cuasi óptimas en muchas
aplicaciones prácticas de optimizaciones en diversas áreas, más que sus heurísticas subordinadas".

Yagiura e Ibaraki (1996) mencionan la combinación de herramientas heurísticas en marcos más

sofisticados como característica distintiva de las metaheurísticas y consideran que dos de sus
propiedades atractivas son la simplicidad y la robustez.

Finalmente y para que conste la estrecha relación entre heurística e inteligencia artificial presentamos
algunas definiones clásicas de Inteligencia Artificial:

 Systems that can demonstrate human-like reasoning capability to enhance the quality of life and
improve business competitiveness. (Japan-S’pore AI Centre)

 La Inteligencia Artificial es el estudio de técnicas de resolución de problemas con complejidad

exponencial a partir del conocimiento del campo de aplicación del problema. (Rich)
Tipos de Algoritmos Heurísticos

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. (Glover).

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.

Introducción a la Verificación en la Ingeniería del Conocimiento

Al igual que la ingeniería del software, la ingenieria del conocimiento cuenta entre sus fases con una
destinada a la evaluacion del sistema desarrollado.

Fases habituales en la ingenieria del conocimiento:

1. Estudio de viabilidad
2. Adquisición del conocimiento
3. Conceptualización (análisis)
4. Formalización (diseño)
5. Implementación
6. Evaluación

La fase de evaluación en la ingenieria del conocimiento se caracteriza por los siguientes aspectos a
tener en cuenta

 Verificación
o Sintaxis y estructura adecuada (no redundante, completa, consistente)
o Se realiza en modelos conceptuales, formales y computables
 Validación
o Semántica adecuada [experto]
o Se realiza en modelos conceptuales, formales y computables
Por lo tanto podemos considerar como un proceso fundamental en la evaluacion de "software
inteligente" la creación de modelos matematicos.

Modelos Matemáticos

Una de las fases del método heurístico se basa en construir modelos.

Aunque existen muchas definiciones de modelo, una de las más interesantes es la de Aracil: "Un
modelo constituye una representación abstracta de un cierto aspecto de la realidad, y tiene una
estructura que está formada por los elementos que caracterizan el aspecto de la realidad modelada y por
las relaciones entre estos elementos".

Nosotros estamos interesados en modelos formales basados en la lógica matemática, y estos están
basados en un conjunto de relaciones matemáticas (relaciones lógicas, ecuaciones, inecuaciones, etc)
que representan las relaciones existentes en el mundo real. Un modelo queda por lo tanto definido por
las relaciones que contiene.

Podemos clasificar los modelos matemáticos según su función:

 Modelos predictivos: Son aquellos que nos informan sobre el comportamiento de la variable en el
futuro, esto es, lo que debería ser. Los modelos basados en técnicas estadísticas se corresponden con
este tipo.
 Modelos evaluativos: Se basan en medir las diferentes alternativas para comparar los resultados de
ellas. Este es el caso de los árboles de decisión.
 Modelos de optimización: Estos modelos tratan de localizar un optimo del problema (generalmente el
óptimo global), es decir, buscan la mejor alternativa posible. Están basados en técnicas de
programación matemática.

Una vez se ha mostrado una breve clasificación de los modelos, es necesario aportar una medida de su
solución, puesto que el objetivo de definir un modelo es, resolverlo "cómodamente" y extraer los
resultados necesarios para tomar alguna decisión.

La resolubilidad de los problemas depende de tres características:

1. El tamaño del problema: La variables y ecuaciones que contiene. para un mayor número de éstas
resultará más dificil resolver el problema.
2. El tipo del problema: entero, lineal y no lineal. Los problemas lineales son "fáciles" de resolver,
mientras que los no lineales son muy difíciles.
3. El tipo de instancias: Deterministas o ciertas, con riesgo (conociendo la probabilidad de ocurrencia),
con incertidumbre (se conocen los posibles resultados pero no la probabilidad de que ocurran) y
turbulencia (no conocemos ninguna cosa).
J. Marcos Moreno Vega, José A. Moreno Pérez. Heurísticas en Optimización . Colección Textos
Universitarios. Consejería de Educación, Cultura y Deportes (2000)

Se tratan gran parte de los tópicos recogidos en los descriptores y contenidos de la asignatura.
Asimismo, se relacionan éstos con los que se tratan en diversas asignaturas del plan de estudio.
El texto consta de seis capítulos que se dedican, respectivamente, a introducir la materia,
describir representaciones y estructuras de entorno y estudiar diferentes búsquedas por entornos,
Algoritmos Genéticos y Optimización por medio de Colonias de Hormigas.

Adenso Díaz. Optimización heurística y redes neuronales. Editorial Paraninfo (1996)

Primer libro en español que trató sobre heurísticas de optimización. Aborda el estudio de
diferentes heurísticas: Recocido Simulado, Algoritmos Genéticos, Búsqueda Tabú, GRASP, ...

Colin R. Reeves (editor). Modern Heuristic Techniques for Combinatorial Problems. Backwell
Scientific Publications (1993)

Se describen los procedimientos heurísticos más importantes aparecidos en la literatura: Recocido

Simulado, Búsqueda Tabú, Algoritmos Genéticos, Redes Neuronales Artificiales y Relajación
Lagrangiana. La descripción de cada uno de estos algoritmos es realizada por algunos de los más
prestigiosos investigadores en cada procedimiento. Además de describir el procedimiento, se
aporta una valiosísima bibliografía y líneas de investigación futuras. Asimismo, se profundiza en la
idea de que estos algoritmos pueden ser integrados en un mismo procedimiento para mejorar la
eficiencia de la búsqueda.

Gilbert Laporte, Ibrahim H. Osman (editores) Metaheuristics in Combinatorial Optimization. Annals

of Operations Research, Vol. 63. Baltzer Science Publishers (1996)

Se encuentran trabajos de investigación recientes sobre Recocido Simulado, Búsqueda Tabú,

Algoritmos Genéticos y Técnicas Híbridas. Asimismo, se suministra una amplia bibliografía con
1380 referencias bibliográficas catalogadas de acuerdo a la heurística que estudian o aplican.

Fred Glover, Manuel Laguna. Tabu Search Kluwer Academic Publishers (1997).

Monografía en la que se presenta un estudio amplio y detallado de las características,

propiedades, perspectivas y aplicaciones de la Búsqueda Tabú. Es muy interesante, aunque sólo
trata del uso de la memoria en el proceso de búsqueda. Recientemente se ha publicado la
segunda edición en la que se actualizan las referencias y se clarifican algunas partes del texto.
Zbigniew [Link] Algorithms + Data Structures = Evolution Programs. Springer
(1996).

Trata en detalle el paradigma de los Algoritmos Genéticos y su uso como herramienta para
resolver diversos problemas combinatorios y numéricos. Su uso está recomendado para quienes
deseen adquirir sólidos conocimientos en este tópico.

Emile Aarts, Jan Karel Lenstra (editores). Local Search in Combinatorial Optimization. John Wiley
& Sons (1997).

Este libro consta de varios capítulos escritos por algunos de los más importantes investigadores
en el campo de las Heurísticas aplicadas a Problemas Combinatorios. Entre los capítulos más
interesantes para la asignatura se encuentran los dedicados a Recocido Simulado, Búsqueda Tabú
y Algoritmos Genéticos. Cabe destacar también el capítulo de Introducción en el que, entre otras
cosas, se encuentra una pequeña reseña histórica de la aplicación de técnicas heurísticas a
problemas combinatorios, se enumeran estructuras de entorno para diferentes problemas y se
describen brevemente algunas de las principales heurísticas.

Eric Bonabeau, Marco Dorigo, Guy Theraulaz Swarm Intelligence. From Natural to Artificial
Systems. Oxford University Press, 1999

C.C. Ribeiro, P. Hansen. Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, 2001

David Corne, Marco Dorigo, Fred Golver. New Ideas in Optimization. McGraw Hill, 1999

Manuel Laguna, José Luis Gonzalez Velarde. Computing Tools for Modeling: Optimization and
Simulation. Kluwer Academic Publishers, 2000

P.M. Pardalos, M.G.C. Resende (eds.). Handbook of Applied Optimization. Oxford University Press,
2001.

Rafael Bello, Métodos de Solución de Problemas de la Inteligencia Artificial, Universidad Central de

Las Villas, 2007.

Ivan Bratko, Prolog programming for Artificial Intelligence. Addison-Wesley Publishing Company,
Reading, Mass, 1986.