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 problemas más rápidamente cuando los métodos clásicos son demasiado lentos para encontrar una solución exacta o aproximada, o cuando los métodos clásicos no logran encontrar ninguna solución exacta en un espacio de búsqueda . Esto se logra intercambiando optimalidad, completitud, exactitud o 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 ramificación en función de la información disponible para decidir qué rama seguir. Por ejemplo, puede aproximar la solución exacta. [1]
El objetivo de una heurística es producir una solución en un período de tiempo razonable que sea lo suficientemente buena para resolver el problema en cuestión. Esta solución puede no ser la mejor de todas las soluciones para este problema, o puede simplemente aproximarse a la solución exacta. Pero aun así es valiosa porque encontrarla 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 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 rutinariamente en aplicaciones del mundo real.
Las heurísticas son 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 . [2]
Los criterios de compensación para decidir si se debe utilizar una heurística para resolver un problema determinado incluyen los siguientes:
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.
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 sea también una solución al problema inicial.
Jon Bentley describe un ejemplo de aproximación para resolver el problema del viajante de comercio (TSP):
para seleccionar el orden de dibujo utilizando un trazador de lápiz . Se sabe que TSP es NP-hard , por lo que es difícil resolver una solución óptima incluso para un problema de tamaño moderado. En cambio, se puede utilizar el algoritmo voraz para dar una solución buena pero no óptima (es una aproximación a la respuesta óptima) en un tiempo razonablemente corto. La heurística del algoritmo voraz dice que se debe elegir el mejor siguiente paso en ese momento, independientemente de si eso impide (o incluso hace imposible) buenos pasos posteriores. Es una heurística en el sentido de que la práctica indica que es una solución suficientemente buena, mientras que la teoría indica que hay mejores soluciones (e incluso indica cuánto mejores, en algunos casos). [3]
Otro ejemplo de heurística que hace que un algoritmo sea más rápido se da en ciertos problemas de búsqueda. Inicialmente, la heurística prueba cada posibilidad 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, una heurística se puede utilizar para probar buenas opciones primero, de modo que los malos caminos se puedan eliminar pronto (ver poda alfa-beta ). En el caso de los algoritmos de búsqueda de mejor primero , como la búsqueda A* , la heurística mejora la convergencia del algoritmo mientras mantiene su corrección mientras la heurística sea admisible .
En su discurso de aceptación del premio Turing , Allen Newell y Herbert A. Simon analizan la hipótesis de la 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 descartar midiendo qué tan cerca está el paso actual de la solución. Por lo tanto, algunas posibilidades nunca se generarán porque se mide que tienen menos probabilidades de completar la solución.
Un método heurístico puede cumplir su tarea utilizando árboles de búsqueda. Sin embargo, en lugar de generar todas las ramas de solución posibles, un método heurístico selecciona ramas con mayor probabilidad de producir resultados que otras ramas. Es selectivo en cada punto de decisión, eligiendo ramas que tienen mayor probabilidad de producir soluciones. [4]
El software antivirus suele utilizar reglas heurísticas para detectar virus y otras formas de malware. El análisis heurístico busca códigos 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 un proceso en ejecución contiene patrones de código coincidentes o está realizando ese conjunto de actividades, 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 aleatorios que se modifican o mutan automáticamente ( polimórficos ) que no se pueden detectar fácilmente con métodos de análisis de cadenas más simples. El análisis heurístico tiene el potencial de detectar virus futuros sin necesidad de detectar primero el virus en otro lugar, enviarlo al desarrollador del escáner de virus, analizarlo y proporcionar una actualización de detección para el escáner a los usuarios del escáner.
Algunas heurísticas tienen una teoría subyacente sólida; se derivan de la teoría de arriba hacia abajo o se basan en datos experimentales o del mundo real. Otras son simplemente reglas generales basadas en la observación o la experiencia del mundo real sin siquiera un atisbo de teoría. Estas últimas están expuestas a un mayor número de obstáculos.
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 un conjunto dado de requisitos, es posible que el conjunto de datos actual no necesariamente represente conjuntos de datos futuros (ver: sobreajuste ) y que las supuestas "soluciones" resulten 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 utilizar una heurística para resolver un problema de búsqueda o un problema de mochila , es necesario comprobar que la heurística es admisible . Dada una función heurística destinada a aproximar la distancia óptima real al nodo objetivo en un gráfico dirigido que contiene nodos o vértices totales etiquetados como , "admisible" significa aproximadamente que la heurística subestima el costo para el objetivo o formalmente que para todos donde .
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 donde .
La palabra "heurística" se empezó a utilizar a principios del siglo XIX. Se forma de forma irregular a partir de la palabra griega heuriskein , que significa "encontrar". [5]
![{\displaystyle {i,g}\en [0,1,...,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21bac8fa995fcd566b257fa43410273f8c839b71)
