En informática , la algorítmica empírica (o algorítmica experimental ) es la práctica de utilizar métodos empíricos para estudiar el comportamiento de los algoritmos . La práctica combina el desarrollo de algoritmos y la experimentación: los algoritmos no solo se diseñan, sino que también se implementan y se prueban en una variedad de situaciones. En este proceso, se analiza un diseño inicial de un algoritmo para que el algoritmo pueda desarrollarse de manera gradual. [1]
Los métodos de la algorítmica empírica complementan los métodos teóricos para el análisis de algoritmos . [2] A través de la aplicación basada en principios de métodos empíricos, particularmente de la estadística , a menudo es posible obtener información sobre el comportamiento de algoritmos como algoritmos heurísticos de alto rendimiento para problemas combinatorios difíciles que son (actualmente) inaccesibles al análisis teórico. [3] Los métodos empíricos también se pueden utilizar para lograr mejoras sustanciales en la eficiencia algorítmica . [4]
La científica informática estadounidense Catherine McGeoch identifica dos ramas principales de la algorítmica empírica: la primera (conocida como análisis empírico ) se ocupa del análisis y la caracterización del comportamiento de los algoritmos , y la segunda (conocida como diseño de algoritmos o ingeniería de algoritmos ) se centra en los métodos empíricos para mejorar el rendimiento de los algoritmos . [5] La primera a menudo se basa en técnicas y herramientas de la estadística , mientras que la segunda se basa en enfoques de la estadística , el aprendizaje automático y la optimización . Las herramientas de análisis dinámico , típicamente los perfiladores de rendimiento , se utilizan comúnmente cuando se aplican métodos empíricos para la selección y el refinamiento de algoritmos de varios tipos para su uso en varios contextos. [6] [7] [8]
Las investigaciones sobre algoritmos empíricos se publican en varias revistas, entre ellas, ACM Journal on Experimental Algorithmics (JEA) y Journal of Artificial Intelligence Research (JAIR). Además de Catherine McGeoch, entre los investigadores más conocidos en algoritmos empíricos se incluyen Bernard Moret , Giuseppe F. Italiano , Holger H. Hoos , David S. Johnson y Roberto Battiti . [9]
En ausencia de algoritmos empíricos, el análisis de la complejidad de un algoritmo puede implicar varios métodos teóricos aplicables a varias situaciones en las que se puede utilizar el algoritmo. [10] Las consideraciones sobre la memoria y la memoria caché suelen ser factores importantes a tener en cuenta en la elección teórica de un algoritmo complejo, o el enfoque para su optimización, para un propósito determinado. [11] [12] La elaboración de perfiles de rendimiento es una técnica de análisis de programas dinámicos que se utiliza normalmente para encontrar y analizar cuellos de botella en el código de una aplicación completa [13] [14] [15] o para analizar una aplicación completa para identificar código de bajo rendimiento. [16] Un generador de perfiles puede revelar el código más relevante para los problemas de rendimiento de una aplicación. [17]
Un generador de perfiles puede ayudar a determinar cuándo elegir un algoritmo sobre otro en una situación particular. [18] Cuando se crea un perfil de un algoritmo individual, como en el análisis de complejidad, las consideraciones sobre la memoria y la caché suelen ser más importantes que los recuentos de instrucciones o los ciclos de reloj; sin embargo, los hallazgos del generador de perfiles se pueden considerar a la luz de cómo el algoritmo accede a los datos en lugar de la cantidad de instrucciones que utiliza. [19]
La elaboración de perfiles puede proporcionar una visión intuitiva del comportamiento de un algoritmo [20] al revelar los hallazgos de rendimiento como una representación visual. [21] La elaboración de perfiles de rendimiento se ha aplicado, por ejemplo, durante el desarrollo de algoritmos para hacer coincidir comodines . Los primeros algoritmos para hacer coincidir comodines, como el algoritmo wildmat de Rich Salz , [22] generalmente se basaban en la recursión , una técnica criticada por motivos de rendimiento. [23] El algoritmo de comodines de coincidencia de Krauss se desarrolló en base a un intento de formular una alternativa no recursiva utilizando casos de prueba [24] seguido de optimizaciones sugeridas a través de la elaboración de perfiles de rendimiento, [25] lo que resultó en una nueva estrategia algorítmica concebida a la luz de la elaboración de perfiles junto con otras consideraciones. [26] Los perfiladores que recopilan datos a nivel de bloques básicos [27] o que dependen de la asistencia de hardware [28] brindan resultados que pueden ser lo suficientemente precisos para ayudar a los desarrolladores de software a optimizar algoritmos para una computadora o situación en particular. [29] La elaboración de perfiles de rendimiento puede ayudar a los desarrolladores a comprender las características de los algoritmos complejos aplicados en situaciones complejas, como los algoritmos coevolutivos aplicados a problemas arbitrarios basados en pruebas, y puede ayudar a generar mejoras en el diseño. [30]