前言

本文属于搬运内容！向原作者：Leon Fedden 致敬！博主将内容归类也是属于总结学习的过程，希望将来本社区也能出现很多优质原创内容成为知识传播的地方！

本文共有四个章节，本章节为第一章。

后续内容：

• 以仿生学的方式优化神经网络
• 微调 —— 发散性昆虫优化
• 随机发散搜索（入门）

没有免费的午餐定理（NFLT）简介

NFLT 的名字来源于一句谚语：“天下没有免费的午餐”（There ain’t no such thing as a free lunch）。在文章开始之前，有必要探讨这句话的含义。这句谚语源于19世纪中期，当时一些酒吧和沙龙会通过提供免费食物吸引顾客，但前提是顾客必须购买饮品。而工薪阶层如果能保持清醒并节省这笔钱，往往会更划算。

没有免费的午餐的基本原理

在深入 NFLT 的核心内容之前，我们需要回顾一些基础知识。如果您像我一样对数学感到头疼，可以跳到文章后面的高级概述部分。

首先，我们处理的是优化问题的比较，有时称为“代价函数”或“能量函数”。这些函数将搜索空间中的点映射到可能的“适应度”或“代价”值的空间。需要注意的是，NFLT 同样适用于搜索算法，但本文不涉及具体细节。

接下来是 NFLT 的一些前提条件：

• 优化器所遍历的搜索空间是有限的。

• 可能的代价值空间也是有限的。

对于在计算机上运行的优化算法，这两个条件是自动满足的；即使代价值是浮点数，由于浮点数在计算机中的表示方式，其值域仍然是离散的（下方有注释）。因为搜索空间和代价值空间都是有限的，所以所有可能问题的集合也是有限的。

David H. Wolpert 和 William G. Macready 使用概率理论将他们的结果推广到随机和确定性算法。

注释：

当我们说值域是离散的时，指的是一个函数或变量的取值范围是由离散的点组成的，而不是连续的区间。

• 不连续性：值域中的点彼此之间存在间隔，中间没有包含其他可能的取值，比如 {1，2，3，4}。但中间实际存在小数。

• 有限或可数无限：离散的值域可以是有限个值，例如 {1,2,3,4}，也可以是可数无限个值，例如所有整数 Z

NFLT 的数学表述

假设 dₘ 是一个包含 m 个代价值 y 的集合，这些 y 值由搜索空间与代价值空间之间的映射（即代价函数 f）产生。上述公式描述了算法 a 在迭代 m 次使用代价函数 f 时产生代价值序列的概率。

基于此，Wolpert 和 Macready 提出了他们的第一个定理：

Wolpert 和 Macready 的第一个定理：

该定理表明，对于任意两个算法 a₁ 和 a₂，它们的平均性能是与算法无关的。换句话说，某个算法在一类问题上表现得更好，其在其余问题上的表现就会相应变差。

他们的论文还提出了第二个 NFLT，与第一个定理类似，但针对随时间变化的目标函数。由于篇幅限制以及作者自身考虑，本文省略了这一部分。第二个定理表明，如果一个算法在某些代价函数动态变化时优于另一个算法，那么在其他代价函数动态上，情况必然反转。

深度概述

NFLT 是一组数学证明和通用框架，探讨了通用算法（“黑箱”算法）与其解决问题之间的关系。

NFLT 的核心观点是：没有任何一个算法能够在所有优化问题上始终优于其他算法。

这是由于通用算法可能面对的问题空间过于庞大。如果一个算法特别擅长解决某一类问题（以及与之相关的适应度曲面），那么它在其他问题上的平均表现必然较差。正如 Wolpert 和 Macready 在论文《No Free Lunch Theorems for Optimisation》中所写：

“如果一个算法在某些问题上优于随机搜索，那么它必然在其余问题上劣于随机搜索。”

简单来说，NFLT 告诉我们：不存在优越的通用黑箱优化策略。

此外，还需权衡算法的通用性与专用性。具体来说，一个高效的算法可能只能解决有限的问题空间，而一个通用算法可能样样都行，但却样样不精。

现实世界中的“没有免费的午餐”

在实际应用中，我们需要为工程问题设计实际模型。那么，理解 NFLT 后，我们如何选择合适的解决方法？

对于特定的模式识别问题，我们通常会发现某些算法表现更好，这取决于算法的适应度函数或代价函数是否适配于该问题。NFLT 提醒我们：要找到最优算法，我们需要聚焦于具体问题、假设、先验信息（额外信息）、数据以及代价函数。

Wolpert 和 Macready 在早期论文《No Free Lunch Theorems for Search》中写道：

“最终，真正重要的问题是：如何为给定的代价函数‘f’找到良好的解决方案？正确的答案是，从给定的‘f’出发，确定其某些显著特征，然后构建一个搜索算法‘a’，专门匹配这些特征。“

但我想用深度学习解决一切问题！

别担心，您依然可以用深度学习。

NFLT 的意义在于，它提醒我们通常找不到现成的算法完美匹配数据。我们需要根据数据特性调整算法结构。例如：

• 将神经网络变为循环网络（RNN），以更好地处理时间序列数据；

• 或将多层感知机（MLP）转为卷积神经网络（CNN），以更好地理解输入数据中的空间信息。

神经网络的优势在于其结构可修改性，使我们能够设计针对性强的解决方案，并随着配置优化变得更加专业化。

此外，无论您使用遗传算法、模拟退火或其他方法，都可以通过调整其编码或选择策略进行适配。

总结

NFLT 的核心教训是：随机选择一个算法，而不考虑问题的结构性假设，等同于在大海捞针。我们需要认真分析问题和数据，并据此采取行动，设计与任务高度匹配的解决方案。

感谢阅读！

原文链接