En teoría de la complejidad computacional y optimización, el teorema de no hay almuerzo gratis es un resultado que establece que, para ciertos tipos de problemas matemáticos, el recurso computacional de encontrar una solución, promediado sobre todos los problemas de la clase, es el mismo para cualquier método de solución. El nombre alude a la premisa conocida como tANSTAAFL, que indica que ningún método ofrece un atajo para solucionar el problema. Esto se da bajo el supuesto de que el espacio de búsqueda es una función de densidad de probabilidad. No se aplica cuando el espacio de búsqueda tiene una estructura subyacente (por ejemplo, una función diferenciable) que puede explotarse de manera más eficiente (por ejemplo, con el método de Newton en optimización) que la búsqueda aleatoria, o incluso tiene soluciones cerradas (como por ejemplo, en el caso de los valores extremos de un polinomio cuadrático) que pueden determinarse sin búsqueda alguna. Para tales supuestos probabilísticos, los resultados de todos los procedimientos que resuelven un tipo particular de problema son estadísticamente idénticos. Una forma original de describir tal circunstancia, introducida por David Wolpert y William G. Macready en relación con los problemas de búsqueda ( y optimización, es decir que no hay almuerzo gratis. Wolpert había deducido previamente teoremas de no hay almuerzo gratis para los procesos de aprendizaje automático (en estadística inferencial).

Antes de la publicación del artículo de Wolpert, Cullen Schaffer demostró de forma independiente una versión restringida de uno de los teoremas de Wolpert y la utilizó para criticar el estado actual de la investigación en aprendizaje automático sobre el problema de la inducción.

En el caso metafórico de no hay almuerzo gratis, cada "restaurante" (procedimiento de resolución de problemas) tiene un "menú" que asocia cada "plato" (problema) con un "precio" (el rendimiento del procedimiento para resolver el problema). Los menús de los restaurantes son idénticos, excepto en un aspecto: los precios se intercambian entre restaurantes. Para un omnívoro con la misma probabilidad de pedir cualquier plato, el coste medio del almuerzo no depende de la elección del restaurante. Sin embargo, un vegetariano que almuerza regularmente con un carnívoro que busca ahorrar podría pagar un coste medio elevado. Para reducir metódicamente el coste medio, es necesario conocer con antelación a) qué se pedirá y b) cuánto costará el pedido en distintos restaurantes. Es decir, la mejora del rendimiento en la resolución de problemas depende del uso de información previa para adecuar los procedimientos a los problemas.

En términos formales, no hay nada gratis cuando la distribución de probabilidad en las instancias del problema es tal que todos los solucionadores tienen resultados distribuidos idénticamente. En el caso de un proceso de búsqueda, una instancia del problema en este contexto es una función de pérdida particular, y un resultado es una sucesión de valores obtenidos en la evaluación de la región factible en el dominio de la función. Para interpretaciones típicas de resultados, la búsqueda es un proceso de optimización. No hay nada gratis en la búsqueda si y solo si la distribución en las funciones objetivo es invariante bajo permutación del espacio de soluciones candidatas. Streeter, M. (2003) "Two Broad Classes of Functions for Which a No Free Lunch Result Does Not Hold," Genetic and Evolutionary Computation – GECCO 2003, pp. 1418–1430.Igel, C., and Toussaint, M. (2004) "A No-Free-Lunch Theorem for Non-Uniform Distributions of Target Functions," Journal of Mathematical Modelling and Algorithms 3, pp. 313–322.English, T. (2004) No More Lunch: Analysis of Sequential Search, Proceedings of the 2004 IEEE Congress on Evolutionary Computation, pp. 227–234. Esta condición no se cumple con precisión en la práctica, pero un teorema de casi nada es gratis sugiere que se cumple aproximadamente.S. Droste, T. Jansen, and I. Wegener. 2002. "Optimization with randomized search heuristics: the (A)NFL theorem, realistic scenarios, and difficult functions," Theoretical Computer Science, vol. 287, no. 1, pp. 131–144.

Resumen Algunos problemas computacionales se resuelven mediante la búsqueda de buenas soluciones en un espacio de región factible. La descripción de cómo seleccionar repetidamente soluciones candidatas para su evaluación se denomina algoritmo de búsqueda. En un problema particular, diferentes algoritmos de búsqueda pueden obtener resultados diferentes, pero en general son indistinguibles. De ello se deduce que si un algoritmo obtiene resultados superiores en algunos problemas, debe pagar con resultados inferiores en otros. En este sentido, no existe almuerzo gratis en la búsqueda. Alternativamente, siguiendo a Schaffer, el rendimiento de la búsqueda es conservado. Generalmente, la búsqueda se interpreta como optimización, lo que lleva a la observación de que no hay nada gratis en la optimización.

El teorema de Wolpert y Macready, todo es gratis, como lo expresaron claramente los propios Wolpert y Macready, establece que "dos algoritmos cualesquiera son equivalentes cuando su rendimiento se promedia en todos los problemas posibles".Wolpert, D.H., and Macready, W.G. (2005) "Coevolutionary free lunches," IEEE Transactions on Evolutionary Computation, 9(6): 721–735 Los resultados de todo es gratis indican que la adecuación de algoritmos a los problemas ofrece un rendimiento promedio mayor que la aplicación de un algoritmo fijo a todos. Igel y Toussaint y English han establecido una condición general bajo la cual todo es gratis. Si bien es físicamente posible, no se cumple con precisión. Droste, Jansen y Wegener han demostrado un teorema que, según su interpretación, indica que "casi todo es gratis" en la práctica.

Para ser más concretos, considérese a un profesional de la optimización que se enfrenta a un problema. Conociendo cómo surgió el problema, el profesional podría aprovechar este conocimiento para seleccionar un algoritmo que funcione bien en la solución del problema. Si el profesional no comprende cómo aprovechar el conocimiento, o simplemente carece de él, se enfrenta a la pregunta de si un algoritmo suele superar a otros en problemas del mundo real. Los autores del teorema de casi nada es gratis afirman que la respuesta es básicamente no, pero admiten algunas reservas sobre si el teorema se aplica a la práctica.

Teoremas Un problema es, más formalmente, una función de pérdida que asocia la región factible con valores de bondad. Un algoritmo de búsqueda toma una función objetivo como entrada y evalúa las soluciones candidatas una por una. La salida del algoritmo es la sucesión de valores de bondad observados.Un algoritmo de búsqueda también genera la secuencia de soluciones candidatas evaluadas, pero ese resultado no se utiliza en este artículo.

Wolpert y Macready estipulan que un algoritmo nunca reevalúa una solución candidata y que su rendimiento se mide en función de las salidas. Para simplificar, no se considera la aleatoriedad en los algoritmos. En estas condiciones, cuando un algoritmo de búsqueda se ejecuta en cada entrada posible, genera cada salida posible exactamente una vez. Dado que el rendimiento se mide en función de las salidas, los algoritmos son indistinguibles en cuanto a la frecuencia con la que alcanzan determinados niveles de rendimiento.

Algunas medidas indican el rendimiento de los algoritmos de búsqueda en optimización de la función objetivo. De hecho, no parece haber ninguna aplicación interesante de los algoritmos de búsqueda en la clase considerada, salvo en problemas de optimización. Una medida común del rendimiento es el índice menor del valor menor en la secuencia de salida. Este es el número de evaluaciones necesarias para minimizar la función objetivo. Para algunos algoritmos, el tiempo necesario para encontrar el mínimo es proporcional al número de evaluaciones.

Los teoremas originales de no hay almuerzo gratis (NFL) asumen que todas las funciones objetivo tienen la misma probabilidad de ser introducidas en los algoritmos de búsqueda. Desde entonces, se ha establecido que existe NFL si y solo si, en términos generales, la reorganización de las funciones objetivo no afecta a sus probabilidades. Aunque esta condición para no hay almuerzo gratis es físicamente posible, se ha argumentado que ciertamente no se cumple con precisión.

La interpretación obvia de no NFL es "almuerzo gratis", pero esto es engañoso. NFL es una cuestión de grado, no una proposición de todo o nada. Si la condición para la NFL se cumple aproximadamente, entonces todos los algoritmos producen aproximadamente los mismos resultados en todas las funciones objetivo. "No NFL" implica únicamente que los algoritmos son inequivalentes en general según alguna medida de rendimiento. Para una medida de rendimiento de interés, los algoritmos pueden permanecer equivalentes, o casi.

Aleatoriedad de Kolmogorov

Casi todos los elementos del conjunto de todas las funciones posibles (en el sentido de función en la teoría de conjuntos) son aleatorios de Kolmogorov y, por lo tanto, los teoremas de la NFL se aplican a un conjunto de funciones que casi en su totalidad no pueden expresarse de forma más compacta que como una tabla de búsqueda que contiene una entrada distinta (y aleatoria) para cada punto en el espacio de búsqueda. Las funciones que pueden expresarse de forma más compacta (por ejemplo, mediante una expresión matemática de tamaño razonable) no son, por definición, aleatorias según la ley de Kolmogorov.

Además, dentro del conjunto de todas las posibles funciones objetivo, los niveles de bondad están igualmente representados entre las soluciones candidatas. Por lo tanto, las buenas soluciones se encuentran dispersas en el espacio de candidatas. En consecuencia, un algoritmo de búsqueda rara vez evaluará más de una pequeña fracción de las candidatas antes de encontrar una muy buena solución.

Casi todas las funciones objetivo son de complejidad de Kolmogórov tan alta que no pueden ser almacenadas en una computadora en particular. Más precisamente, si se modela una computadora física dada como una máquina de registro con una memoria de tamaño dado en el orden de las memorias de las computadoras modernas, entonces la mayoría de las funciones objetivo no pueden ser almacenadas en sus memorias. Hay más información en la función objetivo o algoritmo típico de lo que Seth Lloyd estima que el universo observable es capaz de registrar. Por ejemplo, si cada solución candidata está codificada como una secuencia de 300 ceros y unos (0 y 1) , y los valores de bondad son 0 y 1, entonces la mayoría de las funciones objetivo tienen una complejidad de Kolmogorov de al menos 2300 bits, y esto es mayor que el límite de Lloyd de 1090 ˜ 2299 bits. De ello se desprende que el teorema original de ninguna cosa es gratis no se aplica a lo que se puede almacenar en una computadora física. En su lugar, deben aplicarse los llamados teoremas de ninguna cosa es gratis reforzados. También se ha demostrado que los resultados de la NFL se aplican a funciones incomputables.

Sinopsis formal es el conjunto de todas las funciones objetivo f:X→Y, donde es una región factible finita e es un conjunto parcialmente ordenado finito. El conjunto de todos las permutaciones de X es J. Una variable aleatoria F se distribuye en . Para todo j en J, F o j es una variable aleatoria distribuida en , con P(F o j = f) = P(F = f o j−1) para todo f en .