A New Approach to Characterising Optimisation Problems Using Programmatic Representation and Complexity Measures

想象一下，你正在试图教一个机器人解迷宫。有时迷宫是一个简单的直通走廊；有时它是一个充满死胡同和陷阱的曲折、转弯的迷宫。在计算机科学领域，这被称为优化（optimisation）：寻找问题的最佳解决方案。但棘手之处在于：并非所有的迷宫都是一样的。有些迷宫很容易让机器人解决，而有些则会让即使是最聪明的算法也迷失方向。

为了帮助机器人选择正确的策略，科学家们尝试在机器人开始运行之前对这些迷宫进行“特征化”或描述。他们寻找线索，比如地面有多颠簸，或者有多少个死胡同。通常，为了找到这些线索，机器人必须走几步，观察四周并测量地形。这就像是派一名侦察兵进入黑暗的洞穴进行测绘。但如果机器人只需看一眼迷宫的“蓝图”，就能猜出解决它有多难，那会怎样呢？这就是这篇论文所提出的核心问题。它指出，一个问题在计算机代码中的编写方式，可能隐藏着解决它难度的秘密，就像食谱的复杂程度可以暗示烹饪难度一样。

---

代码即水晶球

在这篇论文中，马库斯·加拉格尔（Marcus Gallagher）和凯瑟琳·马兰（Katherine Malan）提出了一种看待这些难题的新颖且略带“魔力”的方法。他们建议，我们不需要派侦察兵去测量景观，而是直接阅读用于创建该问题的“食谱”。

把一个优化问题想象成一个电子游戏关卡。为了构建这个关卡，程序员编写了代码。有些关卡很简单：“向前移动，跳过坑洞，收集金币。”这类代码很短，使用的指令也很基础。其他关卡则非常混乱：“如果天空是蓝色的，将你的速度乘以星星的数量，然后减去生命值的平方根，但前提是你必须戴着帽子。”这类代码很长、很乱，并且使用了大量的各种指令。

作者的核心观点是：代码越混乱、越复杂，算法解决该问题的难度就越大。

他们借鉴了软件工程领域的两个工具来衡量这种“混乱度”：

1. Halstead 体积（Halstead Volume）： 想象你在统计一段文字中的每一个单词和符号。如果你有一篇用简单词汇写成的短篇故事，计数就很低。如果你有一部拥有复杂词汇和长句的小说，计数就会很高。这个指标通过计算代码中的“运算符”（如数学符号）和“操作数”（如数字和变量）来进行统计。
2. 香农熵（Shannon Entropy）： 这有点像是在测量“惊喜度”。如果一段文字反复使用同样的五个词，它是可预测的（低熵）。如果它使用了大量独特的词汇并以随机顺序排列，它就是不可预测的（高熵）。

实验：从简单的圆圈到混沌的山峰

为了测试他们的理论，作者使用了科学家们广泛使用的 24 个著名测试问题集（称为 BBOB 系列）。这些问题涵盖了从“球形函数”（Sphere function，一个完美的、光滑的圆顶，容易滚下）到“Lunacek bi-Rastrigin 函数”（一个布满了成千上万个微小峰谷的崎岖、多岩石的地形）的各种类型。

他们写下了每个问题的计算机代码，并在其上运行了“混乱度”计算器。结果正如他们所预期的：

• 简单的、光滑的球形函数具有最低的复杂度得分。
• 崎岖、困难的 Lunacek 函数具有最高的复杂度得分。
• 事实上，Lunacek 函数在代码结构上的复杂度大约是球形函数的 9.3 倍。

他们甚至在另一种类型的题目上进行了测试：训练神经网络（一种 AI 大脑）。他们发现，使用“Tanh”激活函数的网络代码比使用“ReLU”的网络代码稍显复杂，这符合 Tanh 版本是一个稍微更难的谜题这一观点。

魔力的连接：代码复杂度预测性能

真正的“魔力”发生在他们将这些代码得分与不同算法的实际表现进行对比时。他们观察了五个不同的“机器人”算法尝试解决这 24 个问题的过程。

他们发现了一个清晰的模式：代码越复杂，机器人的表现就越差。

这是一种负相关关系。当代码简单（低 Halstead 体积）时，机器人能快速轻松地解决问题。当代码复杂（高 Halstead 体积）时，机器人会遇到困难、耗时更长或陷入困境。例如，在 5 维问题中，代码复杂度与表现不佳之间的联系非常紧密。

然而，作者也谨慎地指出，这并不是一个完美的“水晶球”。在一些“离群值”问题中，代码非常复杂，但机器人的表现并没有像代码所暗示的那样糟糕。这表明，虽然代码复杂度是一个很好的提示，但它并不是唯一的决定因素。

为什么这很重要

这种方法的精妙之处在于它极其迅速，且不需要额外的额外工作。传统理解问题的方法通常涉及运行算法数千次，以观察其景观分布。这就像是派一名侦察兵走遍整个迷宫，只为了画出一张地图。

相比之下，作者的方法就像是直接查看迷宫的蓝图。你可以在一瞬间计算出代码的复杂度，而无需运行该问题一次。它不在乎问题的大小或有多少个维度；它只关注指令的结构。

作者认为，这种新的“代码复杂度”度量标准可以成为设计算法的科学家工具箱中的一个有力补充。它并不取代观察问题的旧方法，而是增加了一种全新的、超快速的方法，让你在开始解决问题之前，就能预判问题的难度。这是一个令人期待的进步，有助于计算机通过仅仅“阅读说明书”来选择最合适的工具。