Teorema No Free Lunch

Supongamos que tenemos dos algoritmos de optimización, A y B, y dos clases de problemas, P y Q. Asumamos además que el algoritmo A tiene un mejor rendimiento que el algoritmo B en los problemas de la clase P, mientras que el algoritmo B tiene un mejor rendimiento que el algoritmo A en los problemas de la clase Q. Entonces, según el teorema NFL, debe existir alguna distribución de problemas sobre P y Q tal que el algoritmo A y el algoritmo B tengan un rendimiento igual en promedio.

En otras palabras, cualquier mejora en el rendimiento del algoritmo A sobre el algoritmo B en los problemas de clase P se compensa exactamente con una disminución en el rendimiento en los problemas de clase Q, y viceversa.

Podemos expresar esta idea utilizando el concepto de valor esperado. Sea f una función de optimización que asigna un espacio de entrada X a un conjunto de posibles valores de salida Y. Sea F el conjunto de todas las posibles funciones f, y sea D una distribución de probabilidad sobre el espacio de entrada X. Entonces, el valor esperado de una función f con respecto a la distribución D se define como:

${\displaystyle E[f]=\int _{x}f(x)D(x)dx}$

donde la integral se toma sobre todo el espacio de entrada X. En otras palabras, el valor esperado de una función f es el valor promedio que f toma sobre todas las posibles entradas, ponderado por su probabilidad de ocurrencia.

Las implicaciones del teorema NFL son significativas. Sugieren que el desempeño de los algoritmos de optimización está limitado inherentemente por la estructura de los problemas que se resuelven. Esto significa que, en la práctica, diferentes algoritmos de optimización pueden ser más adecuados para diferentes tipos de problemas. También significa que la búsqueda de un algoritmo óptimo universal es inútil.

Los teoremas NFL se pueden expresar matemáticamente. Sean A y B dos algoritmos de optimización, y sean P y Q dos clases de problemas. Sea ${\displaystyle f_{A}(P)}$ la mejor solución encontrada por el algoritmo A en los problemas de la clase P, y ${\displaystyle f_{B}(Q)}$ la mejor solución encontrada por el algoritmo B en los problemas de la clase Q. Entonces, los teoremas NFL establecen que:

${\displaystyle E[f_{A}(P)]=E[f_{B}(Q)]}$

donde ${\displaystyle E[f_{A}(P)]}$ es el valor esperado de la mejor solución encontrada por el algoritmo A sobre los problemas de la clase P, y ${\displaystyle E[f_{B}(Q)]}$ es el valor esperado de la mejor solución encontrada por el algoritmo B sobre los problemas de la clase Q.

Esto significa que, independientemente de lo bien que se desempeñe un algoritmo A en los problemas de la clase P, siempre existe alguna distribución de problemas sobre P y Q tal que el algoritmo B tenga un desempeño igualmente bueno en promedio.

^{[1][1][2][3][4]}

1. 1 2 Wolpert, D.H.; Macready, W.G. (1997-04). «No free lunch theorems for optimization». IEEE Transactions on Evolutionary Computation 1 (1): 67-82. ISSN 1089-778X. doi:10.1109/4235.585893. Consultado el 3 de mayo de 2023. 
2. ↑ Wolpert, David H. (1996-10). «The Lack of A Priori Distinctions Between Learning Algorithms». Neural Computation 8 (7): 1341-1390. ISSN 0899-7667. doi:10.1162/neco.1996.8.7.1341. Consultado el 3 de mayo de 2023. 
3. ↑ Pulido, J.A.G. (1997). «An application of genetic algorithms to the ROBDD optimization». Second International Conference on Genetic Algorithms in Engineering Systems (IEE). doi:10.1049/cp:19971195. Consultado el 3 de mayo de 2023. 
4. ↑ Bandyopadhyay, Sanghamitra; Pal, Sankar K. Genetic Algorithms in Clustering. Springer Berlin Heidelberg. pp. 181-212. ISBN 978-3-540-49606-9. Consultado el 3 de mayo de 2023.