En optimización matemática e informática , 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 optimización, integridad, 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 bifurcación en función de la información disponible para decidir qué rama seguir. Por ejemplo, puede aproximarse a la solución exacta. [1]
El objetivo de una heurística es producir una solución en un plazo de tiempo razonable que sea lo suficientemente buena para resolver el problema en cuestión. Es posible que esta solución no sea la mejor de todas las soluciones a este problema o que simplemente se aproxime 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 semilla).
Los resultados sobre la dureza NP en informática teórica hacen de la heurística 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.
Las heurísticas son la base de todo el campo de la Inteligencia Artificial y la simulación del pensamiento por computadora, ya que pueden usarse en situaciones en las que no existen algoritmos conocidos . [2]
Los criterios de compensación para decidir si se utiliza una heurística para resolver un problema determinado incluyen los siguientes:
En algunos casos, puede resultar 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 (TSP):
para seleccionar el orden a dibujar usando un trazador de lápiz . Se sabe que TSP es NP-duro , por lo que es difícil encontrar una solución óptima incluso para un problema de tamaño moderado. 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 se debe elegir el siguiente mejor paso en ese momento, independientemente de si eso impide (o incluso imposibilita) dar buenos pasos más adelante. 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 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 buenas opciones primero, de modo que los malos caminos puedan eliminarse tempranamente (ver poda alfa-beta ). En el caso de los algoritmos de búsqueda "mejor primero" , como la búsqueda A* , la heurística mejora la convergencia del algoritmo manteniendo su corrección siempre que 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 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 tengan menos probabilidades de completar 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 ramas de solución posibles, una heurística selecciona ramas con más probabilidades de producir resultados que otras ramas. Es selectivo en cada punto de decisión, seleccionando ramas que tienen más probabilidades de producir soluciones. [4]
El software antivirus suele utilizar 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 descubre 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 automodificantes/mutantes ( polimórficos ) altamente aleatorios 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 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 fuerte teoría subyacente; o se derivan de arriba hacia abajo de la teoría o se llega a ellos basándose en datos experimentales o del mundo real. Otros son sólo reglas generales basadas en observaciones o experiencias del mundo real sin siquiera un atisbo de teoría. Estos últimos están expuestos a un mayor número de peligros.
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 determinado, 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.
Se puede realizar un análisis estadístico 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 verdadera distancia óptima al nodo objetivo en un gráfico dirigido que contiene un total de nodos o vértices etiquetados , "admisible" significa aproximadamente que la heurística subestima el costo para el objetivo o formalmente el de todos los lugares .
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 .
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)
