Heurística (informática) - Heuristic (computer science)

En optimización matemática y ciencias de la computación , la heurística (del griego εὑρίσκω "encuentro, descubro") es una técnica diseñada para resolver un problema más rápidamente cuando los métodos clásicos son demasiado lentos, o para encontrar una solución aproximada cuando los métodos clásicos no logran encontrar una solución exacta. solución. Esto se logra intercambiando la optimización, la integridad, la precisión o la precisión por velocidad. En cierto modo, puede considerarse un atajo.

Una función heurística , también llamada simplemente heurística , es una función que clasifica las alternativas en los algoritmos de búsqueda en cada paso de bifurcación en función de la información disponible para decidir qué bifurcación seguir. Por ejemplo, puede aproximarse a la solución exacta.

Definición y motivación

El objetivo de una heurística es producir una solución en un marco de tiempo razonable que sea lo suficientemente bueno para resolver el problema en cuestión. Esta solución puede no ser la mejor de todas las soluciones a este problema, o puede simplemente aproximarse a la solución exacta. Pero sigue siendo valioso porque encontrarlo no requiere un tiempo prohibitivamente largo.

Las heurísticas pueden producir resultados por sí mismas o pueden usarse junto con algoritmos de optimización para mejorar su eficiencia (por ejemplo, pueden usarse para generar buenos valores de semilla).

Los resultados sobre la dureza NP en la informática teórica hacen que la heurística sea la única opción viable para una variedad de problemas de optimización complejos que deben resolverse de forma rutinaria en aplicaciones del mundo real.

La heurística es la base de todo el campo de la inteligencia artificial y la simulación informática del pensamiento, ya que pueden utilizarse en situaciones en las que no existen algoritmos conocidos .

Compensación

Los criterios de compensación para decidir si utilizar una heurística para resolver un problema determinado incluyen los siguientes:

  • Optimidad: cuando existen varias soluciones para un problema dado, ¿la heurística garantiza que se encontrará la mejor solución? ¿Es realmente necesario encontrar la mejor solución?
  • Integridad: cuando existen varias soluciones para un problema dado, ¿puede la heurística encontrarlas todas? ¿Necesitamos realmente todas las soluciones? Muchas heurísticas solo están destinadas a encontrar una solución.
  • Exactitud y precisión: ¿Puede la heurística proporcionar un intervalo de confianza para la supuesta solución? ¿Es la barra de error de la solución excesivamente grande?
  • Tiempo de ejecución : ¿Es esta la heurística más conocida para resolver este tipo de problemas? Algunas heurísticas convergen más rápido que otras. Algunas heurísticas son solo marginalmente más rápidas que los métodos clásicos, en cuyo caso la "sobrecarga" en el cálculo de la heurística podría tener un impacto negativo.

En algunos casos, puede ser difícil decidir si la solución encontrada por la heurística es suficientemente buena, porque la teoría subyacente a la heurística no es muy elaborada.

Ejemplos de

Problema más simple

Una forma de lograr la ganancia de rendimiento computacional esperada de una heurística consiste en resolver un problema más simple cuya solución es también una solución al problema inicial.

Problema del vendedor ambulante

Jon Bentley describe un ejemplo de aproximación para resolver el problema del viajante de comercio (TSP):

  • "Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad y regresa a la ciudad de origen?"

para seleccionar el orden a dibujar usando un trazador de lápiz . Se sabe que TSP es NP-Hard, por lo que una solución óptima incluso para un problema de tamaño moderado es difícil de resolver. En cambio, el algoritmo codicioso se puede utilizar para dar una solución buena pero no óptima (es una aproximación a la respuesta óptima) en un período de tiempo razonablemente corto. La heurística del algoritmo codicioso dice que elija el que sea actualmente el mejor paso siguiente, independientemente de si eso impide (o incluso imposibilita) buenos pasos más adelante. Es una heurística en el sentido de que la práctica dice que es una solución suficientemente buena, la teoría dice que hay mejores soluciones (e incluso puede decir cuánto mejor en algunos casos).

Búsqueda

Otro ejemplo de heurística que hace que un algoritmo sea más rápido ocurre en ciertos problemas de búsqueda. Inicialmente, la heurística prueba todas las posibilidades en cada paso, como el algoritmo de búsqueda de espacio completo. Pero puede detener la búsqueda en cualquier momento si la posibilidad actual ya es peor que la mejor solución ya encontrada. En tales problemas de búsqueda, se puede utilizar una heurística para probar las buenas opciones primero, de modo que las rutas incorrectas puedan eliminarse pronto (consulte la poda alfa-beta ). En el caso de los mejores algoritmos de búsqueda , como la búsqueda A * , la heurística mejora la convergencia del algoritmo mientras mantiene su exactitud siempre que la heurística sea admisible .

Newell y Simon: hipótesis de búsqueda heurística

En su discurso de aceptación del Premio Turing , Allen Newell y Herbert A. Simon discuten la hipótesis de búsqueda heurística: un sistema de símbolos físicos generará y modificará repetidamente estructuras de símbolos conocidas hasta que la estructura creada coincida con la estructura de la solución. Cada paso siguiente depende del paso anterior, por lo que la búsqueda heurística aprende qué caminos seguir y cuáles ignorar midiendo qué tan cerca está el paso actual de la solución. Por lo tanto, algunas posibilidades nunca se generarán ya que se miden para que sea menos probable que completen la solución.

Un método heurístico puede realizar su tarea utilizando árboles de búsqueda. Sin embargo, en lugar de generar todas las posibles ramas de solución, una heurística selecciona las ramas con más probabilidades de producir resultados que otras ramas. Es selectivo en cada punto de decisión, eligiendo las ramas que tienen más probabilidades de producir soluciones.

Software antivirus

El software antivirus a menudo utiliza reglas heurísticas para detectar virus y otras formas de malware. El escaneo heurístico busca códigos y / o patrones de comportamiento comunes a una clase o familia de virus, con diferentes conjuntos de reglas para diferentes virus. Si se encuentra que un archivo o proceso en ejecución contiene patrones de código coincidentes y / o realiza ese conjunto de actividades, entonces el escáner infiere que el archivo está infectado. La parte más avanzada del análisis heurístico basado en el comportamiento es que puede funcionar contra virus altamente aleatorizados que se modifican / mutan ( polimórficos ) y que no pueden detectarse fácilmente mediante métodos de análisis de cadenas más simples. El escaneo heurístico tiene el potencial de detectar virus futuros sin necesidad de que el virus se detecte primero en otro lugar, se envíe al desarrollador del escáner de virus, se analice y se proporcione una actualización de detección para el escáner a los usuarios del escáner.

Trampas

Algunas heurísticas tienen una teoría subyacente sólida; se derivan de la teoría de arriba hacia abajo o se llega a ellos basándose en datos experimentales o del mundo real. Otras son solo reglas empíricas basadas en la observación o la experiencia del mundo real sin siquiera un atisbo de la teoría. Estos últimos están expuestos a un mayor número de trampas.

Cuando una heurística se reutiliza en varios contextos porque se ha visto que "funciona" en un contexto, sin que se haya demostrado matemáticamente que cumple con un conjunto de requisitos dado, es posible que el conjunto de datos actual no represente necesariamente conjuntos de datos futuros ( ver: sobreajuste ) y que las supuestas "soluciones" resultan ser similares al ruido.

El análisis estadístico se puede realizar cuando se emplean heurísticas para estimar la probabilidad de resultados incorrectos. Para usar una heurística para resolver un problema de búsqueda o un problema de mochila , es necesario verificar que la heurística sea admisible . Dada una función heurística destinada a aproximar la verdadera distancia óptima al nodo objetivo en un gráfico dirigido que contiene el total de nodos o vértices etiquetados , "admisible" significa aproximadamente que la heurística subestima el costo para el objetivo o formalmente para todos los casos .

Si una heurística no es admisible, es posible que nunca encuentre el objetivo, ya sea terminando en un callejón sin salida del gráfico o saltando de un lado a otro entre dos nodos y dónde .

Etimología

La palabra "heurística" entró en uso a principios del siglo XIX. Se forma irregularmente a partir de la palabra griega heuriskein , que significa "encontrar".

Ver también

Referencias