Retos de la minería de datos

La revolución digital ha hecho posible que la información digitalizada sea fácil de capturar, procesar, almacenar, distribuir, y transmitir. En palabras de los investigadores Mitra y Acharya, en el libro publicado el año 2003 bajo el titulo “Minería de datos: Multimedia, computación blanda y bioinformática”, con el importante progreso en informática y en las tecnologías relacionadas y la expansión de su uso en diferentes aspectos de la vida, se continúa recogiendo y almacenando en bases de datos gran cantidad de información. Descubrir conocimiento de este enorme volumen de datos es un reto en sí mismo. La minería de datos es un intento de buscarle sentido a la explosión de información que actualmente puede ser almacenada. En los primeros años del siglo veintiuno, los datos no están restringidos a tuplas representadas únicamente con números o caracteres. El avance de la tecnología para la gestión de bases de datos hace posible integrar diferentes tipos de datos, tales como imagen, video, texto, y otros datos numéricos, en una base de datos sencilla, facilitando el procesamiento multimedia. Como resultado, la mezcla tradicional ad hoc de técnicas estadísticas y herramientas de gestión de datos no son adecuadas por más tiempo para analizar esta vasta colección de datos desiguales.

Según Riquelme y sus colegas, en el artículo escrito el año 2006 titulado “Minería de datos: Conceptos y tendencias”, la tecnología de Internet y su creciente demanda necesita el desarrollo de tecnologías de minería de datos más avanzadas para interpretar la información y el conocimiento de los datos distribuidos por todo el mundo. En este siglo la demanda continuará creciendo, y el acceso a grandes volúmenes de datos multimedia traerá la mayor transformación para el global de la sociedad. Por tanto, el desarrollo de la tecnología de minería de datos avanzada continuará siendo una importante área de estudio, y en consecuencia se espera gastar muchos recursos en esta área de desarrollo en los próximos años. Existen diversos dominios donde se almacenan grandes volúmenes de información en bases de datos centralizadas y distribuidas, como por ejemplo librerías digitales, archivos de imágenes, bioinformática, cuidados médicos, finanzas e inversión, fabricación y producción, negocios y marketing, redes de telecomunicación, etc. Es conocida la frase “los datos en bruto raramente son beneficiosos de manera directa”. Su verdadero valor se basa en: (a) la habilidad para extraer información útil la toma de decisiones o la exploración, y (b) la comprensión del fenómeno gobernante en la fuente de datos. En muchos dominios, el análisis de datos fue tradicionalmente un proceso manual. Uno o más analistas familiarizados con los datos, con la ayuda de técnicas estadísticas, proporcionaban resúmenes y generaban informes. En efecto, el analista hacía de procesador de preguntas sofisticado. Sin embargo, tal enfoque cambió como consecuencia del crecimiento del volumen de datos.

Según Vallejos, en el trabajo de adscripción escrito el año 2006 titulado “Minería de datos”, el nombre de minería de datos deriva de las similitudes entre buscar valiosa información de negocios en grandes bases de datos y minar una montaña para encontrar una veta de metales valiosos. Ambos procesos requieren examinar una inmensa cantidad de material, o investigar inteligentemente hasta encontrar exactamente donde residen los valores. Dadas bases de datos de suficiente tamaño y calidad, la tecnología de minería de datos puede generar nuevas oportunidades de negocios al proveer estas capacidades: (1) Predicción automatizada de tendencias y comportamientos. La minería de datos automatiza el proceso de encontrar información predecible en grandes bases de datos. Preguntas que tradicionalmente requerían un intenso análisis manual, ahora pueden ser contestadas directa y rápidamente desde los datos. La minería de datos utiliza datos en correos electrónicos promocionales anteriores para identificar posibles objetivos que maximicen los resultados de la inversión en futuros correos. Otros problemas predecibles incluyen pronósticos de problemas financieros futuros y otras formas de incumplimiento, e identificar segmentos de población que probablemente respondan similarmente a eventos dados. (2) Descubrimiento automatizado de modelos previamente desconocidos. Las herramientas de minería de datos barren las bases de datos e identifican modelos previamente escondidos en un sólo paso. Otros problemas de descubrimiento de modelos incluyen detectar transacciones fraudulentas de tarjetas de créditos e identificar datos anormales que pueden representar errores de transcripción en la carga de datos. Las técnicas de minería de datos pueden redituar los beneficios de automatización en las plataformas de hardware y software existentes y pueden ser implementadas en sistemas nuevos a medida que las plataformas existentes se actualicen y nuevos productos sean desarrollados. Cuando las herramientas de minería de datos son implementadas en sistemas de procesamiento paralelo de alto rendimiento, pueden analizar bases de datos masivas en minutos. Procesamiento más rápido significa que los usuarios pueden automáticamente experimentar con más modelos para entender datos complejos. Alta velocidad hace que sea práctico para los usuarios analizar inmensas cantidades de datos. Grandes bases de datos, a su vez, producen mejores predicciones. Las empresas suelen generar grandes cantidades de información sobre sus procesos productivos, desempeño operacional, mercados y clientes. Pero el éxito de los negocios depende por lo general de la habilidad para ver nuevas tendencias o cambios en las tendencias. Las aplicaciones de la minería de datos pueden identificar tendencias y comportamientos, no sólo para extraer información, sino también para descubrir las relaciones en bases de datos que pueden identificar comportamientos que no muy evidentes.

Kargupta y sus colegas, en el libro escrito el año 2004 titulado “Minería de datos: Desafíos para la siguiente generación y direcciones futuras”, además de los investigadores Yang y Wu, en el artículo escrito el año 2005 titulado “Problemas de cambio en la investigación en minería de datos”, mencionan que existen algunos retos que superar antes de que la minería de datos se convierta en una tecnología de masas. Se señalan algunos de tales retos: El primer reto relacionado con los aspectos metodológicos. Sería muy útil la existencia de una interfaz de programación de aplicaciones estándar, de forma que los desarrolladores puedan integrar sin dificultad los resultados de los diversos algoritmos de minería. Esto podría facilitar también la tarea de automatizar y simplificar todo el proceso, integrando aspectos como muestreo, limpieza productos de minería de datos estuvieran orientados al programador para fomentar su uso y ampliación. Sería asimismo necesario unificar la teoría sobre la materia: Así de datos, minería, visualización, etc. En este mismo sentido sería deseable que los se puede observar que los estados del arte no son generalizables, no existe un estándar para la validación de resultados y, en general, la investigación se realiza demasiado aislada. Asimismo se necesitaría mejorar la formación en esta área entre los titulados universitarios, que sería la mejor manera de expandir su uso, y finalmente, sigue siendo un asunto pendiente la integración del conocimiento del dominio en el algoritmo, y viceversa, es decir, mejorar la interpretabilidad y facilidad de uso del modelo hallado.

Kargupta, en el libro mencionado, señala que el segundo reto relacionado con la escalabilidad. La escalabilidad de la minería de datos hacia grandes volúmenes de datos es y será siempre una de las tendencias futuras, ya que el volumen de información que se ha de tratar crece de manera exponencial, con lo que los avances en esta área quedan siempre superados por las necesidades crecientes. Datos con miles de atributos es ya algo habitual, pero es probable que las técnicas no estén preparadas aún para centenares de miles o incluso millones de características. Dentro de esta línea también se localiza la minería de flujos de datos de muy alta velocidad con posibles cambios de estructura, dimensión o modelo de generación dinámico durante la fase de entrenamiento. Esto obliga a contar con un modelo de conocimiento en todo momento. El tercer reto está relacionado con la simulación, integración en la toma de decisiones y la minería de datos. Los modelos extraídos para un ámbito de interés de una organización. Básicamente se trata de utilizar las salidas de unos modelos como entradas de otros y maximizar el beneficio del conjunto de modelos. Además, pueden añadirse al modelo global restricciones de valores máximos o mínimos, saturación, etc. Las técnicas tradicionales de combinación de modelos, no pueden aplicarse directamente. Las técnicas de simulación en minería de datos, más relacionadas con el problema de una maximización global no han recibido la atención suficiente desde el área de la minería de datos.
TITULARES

Algoritmo evolutivo multiobjetivo

Segun Miettinen, en el libro escrito el año 1998 mencionado anteriormente, a finales del siglo veinte, existían más de treinta técnicas de programación matemática para resolver problemas de optimización multiobjetivo. Con todo, la complejidad de muchos problemas de optimización multiobjetivo del mundo real vuelve a estas técnicas inadecuadas o incluso inaplicables para resolverlos. La complejidad de estos problemas se debe, entre otras cosas: A la multimodalidad, a la alta dimensionalidad del espacio de búsqueda, a la discontinuidad de sus funciones objetivo, a desconexiones tanto en el espacio de las variables de decisión como en el de las funciones objetivo, o a que son NP-completos. Algunos investigadores, entre los que destacan Fogel, con el libro escrito el año 1999 titulado “Inteligencia artificial a través de la evolución simulada: Cuarenta años de programación evolutiva”, además de Michalewicz y Fogel, con el libro escrito el año 2000 titulado “Como resolverlo: Heurísticas modernas”, han identificado algunas dificultades que tienen las técnicas clásicas para resolver problemas de optimización multiobjetivo. A continuación se listan algunas de ellas: (1) Los algoritmos necesitan ejecutar varias veces para encontrar varias soluciones del conjunto de óptimos de Pareto. (2) La mayoría de los algoritmos requieren información sobre el dominio del problema que se trata. (3) Algunos algoritmos son sensibles a la forma o continuidad del frente de Pareto. (4) En los problemas que involucran incertidumbre o eventos estocásticos, los métodos clásicos son inadecuados. (5) La dispersión de las soluciones del frente de Pareto depende de la eficiencia del optimizador monoobjetivo.

La complejidad de los problemas de optimización multiobjetivo del mundo real ha conducido a la búsqueda de enfoques alternativos para resolver este tipo de problemas. Uno de esos enfoques lo encabezan los algoritmos evolutivos. A finales de los años 1960, Rosenberg, en la tesis doctoral escrita el año 1967 titulada “Simulación de poblaciones genéticas con propiedades bioquímicas”, plantea utilizar un método genético de búsqueda para resolver problemas de optimización multiobjetivo. No obstante, no fue hasta el año 1984 cuando David Schaffer, en la tesis doctoral titulada “Optimización de objetivos múltiples con algoritmos genéticos de vectores evaluados”, propone la primera implementación de lo que actualmente se conoce como algoritmo evolutivo multiobjetivo. A partir de ese momento, varios investigadores, entre los que destacan Coello y Toscano, con el artículo escrito el año 2001 titulado “Optimización multiobjetivo utilizando un algoritmo micro genético”, además de Zitzler y Thiele, con el artículo escrito el año 1999 titulado “Algoritmos evolucionarios multiobjetivo: Un caso de estudio comparativo y el enfoque del frente de Pareto”, han desarrollado su propio algoritmo evolutivo multiobjetivo. La publicación de los resultados de estos algoritmos mostró la superioridad de los algoritmos evolutivos multiobjetivo sobre las técnicas clásicas de programación matemática. Los algoritmos evolutivos son naturalmente adecuados para resolver problemas de optimización multiobjetivo gracias a que trabajan de manera simultánea con un conjunto de soluciones potenciales, es decir, la población. Esta característica permite encontrar varias soluciones del conjunto óptimo de Pareto en una sola ejecución. Asimismo, son menos sensibles a la forma o continuidad del frente de Pareto. Zitzler y Thiele mencionan que las características fundamentales, de un algoritmo evolutivo multiobjetivo, son las siguientes: Mantener un conjunto de soluciones potenciales, el cual es sometido a un proceso de selección y es manejado por operadores genéticos, generalmente la recombinación y la mutación. Los algoritmos evolutivos y los algoritmos evolutivos multiobjetivo son estructuralmente similares. La diferencia fundamental es que un algoritmo evolutivo multiobjetivo calcula muchas funciones de aptitud.

Aprendizaje supervisado

Según Basogain, en el libro digital escrito el año 2006 titulado “Redes neuronales artificiales y sus aplicaciones”, las redes neuronales artificiales están inspiradas en las redes neuronales biológicas del cerebro humano. Están constituidas por elementos que se comportan de forma similar a la neurona biológica en sus funciones más comunes. Estos elementos están organizados de una forma parecida a la que presenta el cerebro humano. Las redes neuronales artificiales al margen de “parecerse” al cerebro presentan una serie de características propias del cerebro. Por ejemplo las redes neuronales artificiales aprenden de la experiencia, generalizan de ejemplos previos a ejemplos nuevos y abstraen las características principales de una serie de datos. (1) Aprender. Adquirir el conocimiento de una cosa por medio del estudio, ejercicio o experiencia. Las redes neuronales artificiales pueden cambiar su comportamiento en función del entorno. Se les muestra un conjunto de entradas y ellas mismas se ajustan para producir unas salidas consistentes. (2) Generalizar. Extender o ampliar una cosa. Las redes neuronales artificiales generalizan automáticamente debido a su propia estructura y naturaleza. Estas redes pueden ofrecer, dentro de un margen, respuestas correctas a entradas que presentan pequeñas variaciones debido a los efectos de ruido o distorsión. (3) Abstraer. Aislar mentalmente o considerar por separado las cualidades de un objeto. Algunas redes neuronales artificiales son capaces de abstraer la esencia de un conjunto de entradas que aparentemente no presentan aspectos comunes o relativos.

En palabras de Chauvin y Rumelhart, en el libro escrito el año 1995 titulado “Backpropagation: Teoria, arquitectura y aplicaciones”, una vez diseñada la arquitectura de la red neuronal, compuesta por capas y número de neuronas por capa, además de las funciones que la regirán, se tiene que proceder a entrenar a la red para que “aprenda” el comportamiento que debe tener; es decir, para que aprenda a dar la respuesta adecuada a la configuración de estímulos o patrones de entrada que se le presenten. Una excepción a esta regla general la constituyen las redes de Hopfield, que no son entrenadas sino construidas, de modo que tengan ya inicialmente el comportamiento deseado. Por este motivo, se ha dicho que las redes de Hopfield simulan el comportamiento “instintivo” mientras que las demás redes simulan el comportamiento “aprendido”.

Según Gestal, en la tesis de doctorado escrita el año 2009 titulada “Computación evolutiva para el proceso de selección de variables en espacios de búsqueda multimodales”, con la técnica de aprendizaje supervisado el entrenamiento consiste en presentarle a la red repetitivamente patrones de estímulos de entrada pertenecientes a un juego de ensayo. El juego de ensayo está formado por parejas “patrón de estímulos - respuesta correcta” y debe de ser elegido cuidadosamente. Cada pareja se denomina hecho. En el juego de ensayo debe estar representada equilibradamente toda la información que la red necesite aprender. Al realizar el entrenamiento la respuesta que da la red a cada patrón se compara con la respuesta correcta ante dicho patrón y, en virtud de esa comparación, se reajustan los pesos sinápticos. El reajuste de los pesos sinápticos está orientado a que, ante el patrón de entrada, la red se acerque cada vez más a la respuesta correcta. Cuando ante un patrón de entrada la red de neuronas ya responde correctamente, se pasa al siguiente patrón del juego de ensayo y se procede de la misma manera. Cuando se termina con el último patrón del juego de ensayo, se tiene que volver a empezar con el primero, ya que los pesos se han seguido modificando. En casos sencillos, al cabo de unos pocos pasos de entrenamiento completos, con todos los elementos del juego de ensayo, los pesos sinápticos de todas las neuronas se estabilizan en torno a unos valores óptimos. Se dice entonces que el algoritmo de aprendizaje converge. Es decir, después de sucesivas presentaciones de todos los patrones estimulares del juego de ensayo, la red, responderá correctamente a todos ellos y se puede considerar entrenada y dar por terminada la fase de aprendizaje. El aprendizaje puede realizarse con tres técnicas diferentes: aprendizaje supervisado, aprendizaje no supervisado y aprendizaje parcialmente supervisado. Al interior de estas técnicas, el aprendizaje supervisado es la técnica de aprendizaje más sencilla, consiste en la presentación de los patrones de entrada y de las etiquetas de clase deseadas para cada patrón de entrada.

Control difuso

El concepto de lógica difusa es muy común, el mismo fue introducido por el gran investigador Lotfi Zadeh, en el artículo escrito el año 1965 titulado “Conjuntos difusos”. Este concepto está asociado con la manera en que las personas perciben el medio, por ejemplo ideas relacionadas con la altura de una persona, velocidad con la que se mueve un objeto, la temperatura dominante en una habitación, cotidianamente se formulan de manera ambigua y depende de quién percibe el efecto físico o químico. Una persona puede ser alta o baja, algo puede moverse rápido o lento, una temperatura puede ser baja o moderada o alta, se dice que estas afirmaciones acerca de una variable son ambiguas porque rápido, bajo, alto son afirmaciones del observador, y estas pueden variar de un observador a otro. Uno se puede preguntar cuándo algo es frío o caliente, que tan baja es la temperatura cuando se dice frío, o que tan alta es cuando se dice caliente. Los conjuntos difusos definen justamente estas ambigüedades, y son una extensión de la teoría clásica de conjuntos, donde un elemento pertenece o no a un conjunto, tal elemento tiene solo dos posibilidades, pertenecer o no, un elemento es bi-valuado y no se definen ambigüedades. Con conjuntos difusos se intenta modelar la ambigüedad con la que se percibe una variable. Los conjuntos difusos son la base para la lógica difusa. Con los conjuntos difusos se realizan afirmaciones lógicas del tipo si-entonces, definiéndose estas con lógica difusa. Este tema es propio de la inteligencia artificial, donde se intenta emular en pensamiento humano. Desde que Zadeh desarrolló el concepto de lógica difusa, en el artículo citado anteriormente, se ha trabajando en este tema, el principal centro de desarrollo es Japón, donde sus investigadores la han aplicado a muy diversos sistemas, principalmente electrodomésticos, sistemas más recientes están vinculados con la industria, la medicina y la actividad espacial.

Según Martínez y Sanz, en el libro publicado el año 2002 con el título “Redes neuronales y sistemas difusos”, la incorporación de la lógica difusa a los sistemas de control da lugar a lo que se denomina sistemas de control difuso. Al interior de los sistemas de control se encuentran dos grandes áreas, el modelado o identificación y el control propiamente dicho o control directo. Se realizara un enfoque inicial en el control de procesos suponiendo conocido el modelo de este. La idea es muy simple, se trata de determinar de manera lógica que se debe hacer para lograr los objetivos de control de mejor manera posible a partir de una base de conocimiento proporcionada por un operador humano, sin esta base no es posible desarrollar una aplicación y que esta funcione de manera correcta. Se utiliza el conocimiento y experiencia de un operador humano para construir un controlador que emule el comportamiento de tal persona. Comparado con el control tradicional, el control difuso tiene dos ventajas practicas, una es que no se requiere el modelo matemático del proceso a controlar y otra es que se obtiene un controlador no lineal desarrollado empíricamente sin complicaciones matemáticas, en realidad los desarrollos matemáticos de este tema todavía están en su infancia. En palabras de Cristian De Los Ríos, descritas en la tesis de grado publicada el año 2004 con el título “Evaluación de estructuras y métodos de ajuste de reguladores PID-Difusos”, la teoría de conjuntos difusos es utilizada en muchos campos técnicos como control, modelado, procesamiento de imágenes y señales, sistemas expertos, etc., pero es quizás en el campo del control su más frecuente y exitosa aplicación. Se debe tener en cuenta que los sistemas con controladores difusos son naturalmente no lineales, se los puede configurar para ajustarse a cualquier función, es decir que pueden emular funciones lineales pero en general se trabaja con configuraciones no lineales. En general, pues, se trabaja con configuraciones no lineales, por lo que las herramientas de diseño y análisis de control lineal no serán útiles en estos sistemas borrosos, de todos modos se hacen aproximaciones lineales para utilizar en alguna medida las herramientas bien conocidas del control lineal, se puede recurrir a esto ya que aún están en desarrollo las herramientas de diseño y análisis de sistemas borrosos.

Protección de Agentes

Desde el punto de vista del usuario final, según Lange y Oshima, en el libro escrito el año 1998 titulado “Programación e implementación de agentes móviles Java con aglets”, se menciona que los agentes pueden ser: “Programas que asisten y actúan a favor del usuario final”, en este caso se refuerza la idea de la delegación en los agentes de las tareas de usuario. Sobre el concepto de agente, se puede hablar de sus características, diciendo que un agente autónomo, para empezar, no es un programa, o al menos es algo más que un programa, al fin y al cabo, todo lo que se ejecuta en una computadora es un programa; es decir, no se suele llamar programa por el mismo motivo que un sistema operativo no se suele llamar un programa a pesar de que no pueda ser otra cosa. Una de las características que distingue los agentes de los programas sencillos es la autonomía de acción. Los agentes son más que activos, es decir, que no sólo actúan en respuesta a una acción directa del usuario, sino que también actúan siguiendo los objetivos que tienen marcados, bien por el usuario bien por su propia construcción. Además, son persistentes, aún cuando el usuario no interactúa con ellos siguen funcionando, recolectando información, aprendiendo y comunicándose con otros agentes.

Cuando se transfiere código ejecutable a través de la red, existe la posibilidad de un ataque. En palabras de los investigadores Jansen y Karygiannis, en el artículo escrito el año 2000 titulado “Seguridad en agentes móviles”, los agentes al igual que ocurre con los programas usados en redes, pueden ser susceptibles a alteraciones, ataques, espionaje, y clonaciones. Es importante ser conscientes de que siempre existe la posibilidad de que un intruso intente afectar la integridad de un sistema y por tanto llevar a cabo las medidas de prevención adecuadas ayuda a minimizar los riesgos. Algunos de los ataques que son ejecutados en contra de agentes son: Espionaje de código, espionaje de información, manipulación de código y de información, ejecución incorrecta del código, identidad falsa de un host y negación de ejecución. Un agente puede llevar consigo información confidencial, por lo que se debe prevenir en todo momento la modificación del código ejecutable. Es posible asegurar la integridad de un agente que proviene de otro host utilizando la firma digital o el cifrado. Sin embargo, es difícil detectar o prevenir los ataques que pueda realizar un host mientras se ejecuta un agente. Los hosts pueden intentar sacar provecho del agente modificando el código, los datos, las comunicaciones o incluso los resultados, ya que, como se mencionaba, tienen control total sobre la ejecución del agente. A este problema se le conoce como el de los “Hosts maliciosos”, este es considerado por muchos autores el más difícil de resolver en lo relacionado con la seguridad en sistemas de agentes móviles.

Para prevenir una alteración en el código y en la información, los agentes se pueden proteger, al igual que muchos programas informáticos, utilizando métodos criptográficos. De forma similar los agentes pueden ser autenticados con un host o incluso con otros agentes, mediante métodos de clave pública como es la firma digital. Según Chess, en el artículo escrito el año 1996 titulado “Consideraciones de seguridad en sistemas basados en agentes”, tomando en cuenta que los agentes se pueden ejecutar en hosts con diversos grados de confianza, sería ingenuo no esperar un comportamiento malicioso por su parte. Los hosts pueden sacar provecho del agente modificando el código, los datos, el modo de ejecución, el estado, las comunicaciones, el itinerario o incluso los resultados, ya que tienen control total sobre la ejecución. Precisamente esta es la razón por la cual no se pueden evitar ataques de denegación de servicio, puesto que el host tiene en sus manos el código del agente para ejecutarlo a placer, forzándolo a terminar antes de tiempo o incluso a migrar a otro destino. Para un agente móvil es imposible almacenar en claro una clave secreta, puesto que el host tiene acceso de lectura y modificación a la misma, para esto es imprescindible disponer de un entorno confiable para realizar las operaciones criptográficas.

Segunda parte Búsqueda heurística

En palabras de Fuentetaja, en la tesis doctoral escrita el año 2010 titulada “Búsqueda heurística en planificación basada en costes”, en planificación mediante búsqueda heurística se han aplicado heurísticas de muy diversos tipos y naturaleza. A grandes rasgos las heurísticas se pueden dividir en dos categorías: Heurísticas dependientes del dominio y heurísticas independientes del dominio. Con heurísticas independientes del dominio se hace referencia a aquellas cuyo proceso de cálculo es el mismo para todos los dominios. Las heurísticas dependientes del dominio, pueden ser muy útiles para guiar la búsqueda, sin embargo, no se pueden aplicar a problemas con estructura distinta a aquellos para los que se generaron. Estas heurísticas requieren de un trabajo adicional en cada dominio para generar la información, o la función, que permite calcular la heurística. Cuando este trabajo se puede realizar de forma automática, se acercan más a las heurísticas independientes del dominio, que son aquellas que no requieren de ninguna información adicional al propio dominio o problema. Estas últimas están acordes con la idea de la planificación como un proceso general de resolución de problemas y han tenido un gran auge en los últimos años. Las heurísticas independientes del dominio más comunes en planificación mediante búsqueda heurística se pueden clasificar en función de su objetivo como: (1) Heurísticas numéricas. Aquellas que estiman numéricamente la distancia entre dos estados, un estado fuente y un estado destino. (2) Heurísticas de poda u ordenación. Aquellas que sirven para podar el espacio de estados, o para ordenar ciertos nodos. (3) Heurísticas con vistas futuras. Aquellas que permiten generar rápidamente estados profundos mediante la aplicación, total o parcial, de una política.

Fuentetaja, en la tesis doctoral citada anteriormente, continúa mencionando que los algoritmos de búsqueda progresiva que se han venido utilizando en planificación clásica se pueden dividir en dos grupos: (1) Aquellos que aplican algoritmos de búsqueda local, y (2) Aquellos que aplican algoritmos de tipo mejor primero. La búsqueda local funciona de la siguiente forma: de entre la vecindad de un único nodo actual, elige un nodo que pasa a ser el nuevo nodo actual y el proceso se repite de forma iterativa hasta que se cumpla un criterio de terminación. La búsqueda local se caracteriza porque no tiene memoria y no revisa las decisiones una vez que estas se han tomado, es decir, es un procedimiento irrevocable. El criterio de terminación normalmente se cumple cuando se ha encontrado una solución, cuando se ha realizado un determinado número de iteraciones y aparentemente el proceso de búsqueda está estancado o cuando no se puede continuar a partir el nodo actual. A continuación se mencionan algunos tipos de búsqueda local que se han aplicado en planificación, como la búsqueda de ascenso de colinas y la búsqueda forzada de ascenso de colinas, complementándose esta descripción con el algoritmo de búsqueda mejor primero.

La búsqueda de ascenso de colinas o búsqueda en escalada, es uno de los procedimientos más conocidos de búsqueda local. En este caso, el siguiente nodo de cada iteración se elige de entre los que tienen una mejor evaluación heurística de entre todos los sucesores. En caso de que el nodo elegido tenga una evaluación heurística peor que el padre, la búsqueda termina. El funcionamiento de la búsqueda en escalada depende de la topología del espacio de búsqueda. Cuando se encuentra un óptimo local, es decir, un estado para el que todos los sucesores tienen peor evaluación, la búsqueda termina sin encontrar solución alguna. La búsqueda de ascenso de colinas forzada es una variante del ascenso de colinas en la que se generan sucesores utilizando búsqueda en amplitud, hasta encontrar un sucesor, que puede ser indirecto, con una evaluación heurística mejor que el nodo actual. En este caso el nuevo nodo actual es este sucesor. La búsqueda mejor primero constituye un esquema de búsqueda global, que se caracteriza por elegir el siguiente nodo a expandir basándose en una función de evaluación. Normalmente se consideran mejores los nodos con un menor valor para la función de evaluación. La búsqueda mejor primero se suele implementar utilizando una lista ordenada en orden creciente respecto a la función de evaluación, la lista abierta, de manera que el siguiente nodo a expandir es siempre el primer elemento de la lista. Cuando un nodo se expande, se generan todos sus sucesores, y éstos se introducen en la lista abierta. El nodo expandido se introduce en una lista cerrada. El algoritmo analiza cuando el nodo que se extrae de la lista abierta es un nodo solución.

Búsqueda heurística

Al interior de las nuevas teorías sobre el juicio humano y gracias, fundamentalmente, al trabajo realizado por Kahneman, Slovic y Twersky desde principios de la década de los setenta, reportados en el libro publicado el año 1982 titulado “Juicio bajo incertidumbre: Heurística y prejuicios”, se han reconocido una serie de reglas de decisión denominadas “heurísticas”. Una heurística puede definirse como la estrategia utilizada por las personas para emitir un juicio, realizar una estimación, tomar una decisión, etc., basándose en componentes limitados de la información disponible. De esta manera, estas reglas han recibido la denominación de “atajos mentales” o “reglas de sentido común”, dando origen a gran cantidad de investigaciones y experimentación. Realizar un juicio heurístico puede considerarse como una manera bastante eficiente de llegar a una solución a un problema debido fundamentalmente a su rapidez y consistencia con las propias creencias. Sin embargo, las soluciones ofrecidas pueden ser inexactas, pudiendo conducir a errores. A modo de ejemplo, un juicio consistente con una heurística de representatividad, sería “Juzgar un libro por su portada”. Las heurísticas han sido frecuentemente descritas como estrategias que la gente utiliza de manera deliberada en orden de simplificar los problemas, que de otra manera serían difíciles de solucionar por la mente humana. La discusión corriente en ámbito académicos argumenta que una descripción de ese tipo, conlleva a que los errores producidos por su uso tienen su origen en una mente no suficientemente atenta, lo cual es inconsistente con el planteamiento propuesto por Kahneman, Slovic y Twersky, que establecen que las heurísticas se acercan a la denominación de “juicios naturales”, pudiendo influir en la tarea de decisión o estimación sin ser usadas de manera estratégica o deliberada.

Por otra parte, en palabras de Ramos, en los apuntes escritos el año 2007 con el título “Heurísticas y problemas combinatorios”, con el fin de resolver problemas complicados con eficiencia, en ocasiones es necesario comprometer algunos requisitos de optimalidad y construir una estructura de control que no garantice encontrar la mejor respuesta pero que casi siempre encuentre una buena solución. De esta forma, surge la idea de heurística. La palabra heurística viene de la palabra griega heuriken que significa “descubrir”, que es también origen de eureka, derivado de la famosa exclamación de Arquímedes, heurika “lo encontré”. Los investigadores Bartholdi y Platzman, en el artículo escrito el año 1988 titulado “Heurística basada en curvas espaciales y compactas para problemas combinatorios en el espacio euclidiano”, definieron heurística de la siguiente manera: “Una heurística puede verse como un procesador de información que, deliberadamente, peor juiciosamente, ignora cierta información. Ignorando información, una heurística se libra de gran parte del esfuerzo que debió haberse requerido para leer los datos y hacer cálculos con ellos. Por otra parte, la solución producida por tal heurística, es independiente de la información ignorada, y de este modo no se ve afectada por cambios en tal información. Idealmente, se busca ignorar información que resulta muy caro colectar y mantener, esto es, computacionalmente caro de explotar y mantener, y que contribuye en poco a la precisión de la solución.” Se puede definir una heurística como una técnica que aumenta la eficiencia de un proceso de búsqueda, posiblemente sacrificando demandas de completitud. Las heurísticas son como los guías de turismo: Resultan adecuadas en el sentido de que generalmente suelen indicar las rutas interesantes; son malas en el sentido de que pueden olvidar puntos de interés para ciertas personas. Al usar buenas heurísticas se pueden expresar buenas, aunque posiblemente no óptimas, soluciones a problemas difíciles, como el problema del viajante de comercio. Una función heurística es una correspondencia entre las descripciones de estados del problema hacia alguna medida de deseabilidad, normalmente representada por números. Quiere decir que mensura cada estado del problema y dice qué tan cerca de la solución óptima está. El propósito de una función heurística es el de guiar el proceso de búsqueda en la dirección más provechosa sugiriendo qué camino tomar cuando hay más de uno disponible. Cuanto más exactamente estime la función heurística los méritos de cada nodo del grafo que representa al problema, más directo será el proceso de solución. En general, hay que hacer una ponderación entre el costo de evaluación de una función heurística y el ahorro de tiempo de búsqueda que proporciona la función.