MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design

想象你正在试图解决一个巨大的、混乱的拼图，比如为数百个停靠点规划一条庞大的送货卡车路线，或者在行李箱里尽可能装入最有价值的物品。这些被称为“组合优化问题”（combinatorial optimization problems），它们之所以极其困难，是因为可能的排列组合方式数量巨大，以至于即使是最快的超级计算机也无法一一检查。几十年来，人类一直试图编写特殊的“经验法则”（称为启发式算法）来快速解决这些拼图。但问题在于：适用于网格状街道布局城市的规则，在面对拥有蜿蜒圆形道路的城市时可能会彻底失效。这就是“没有免费午餐”（No Free Lunch）的现实：不存在一种能适用于所有情况的单一神奇规则。

最近，科学家开始使用“大语言模型”（LLMs）——即那种可以写故事和回答问题的同类人工智能——来自动发明这些规则。然而，大多数 AI 实验都像是只用一本单一的小教科书来训练学生。AI 会变得非常擅长解决那本特定书里的问题，但如果你给它一个略微不同的拼图，它就会感到困惑。这就像是教一位厨师做出一份完美的煎蛋卷，但只使用来自某一特定农场的鸡蛋；如果给了他们来自另一家农场的鸡蛋，煎蛋卷可能会散架。旧的训练方式还依赖于非常简单的反馈，比如老师只说“做得好”或“做得不好”，而不解释为什么或者错误发生在哪里。

MOSAIC 登场了，这是佐治亚理工学院的研究人员开发的一个新框架。不要把 MOSAIC 看作是一个试图背诵教科书的单一学生，而要把它看作是一个巨大的、活生生的图书馆，其中针对不同类型的拼图训练着不同的“专家级”规则。MOSIC 不仅仅是要求 AI “制定更好的规则”，它还设置了一场高风险的“猫鼠游戏”。它让 AI 当前的规则与一组“对抗性”的拼图制造者进行对决。这些拼图制造者同样是 AI，它们的唯一任务就是设计出专门用来击败当前规则的最难、最令人困惑的拼图。当一条规则失败时，系统并不仅仅说“你输了”。它使用一个智能决策树来弄清楚究竟是哪种类型的拼图击垮了该规则，然后将那个拼图以及学到的教训存储在巨型网格的一个特定“单元格”中。随着时间的推移，这个网格会填满一个多样化的专家集合：一个规则用于处理网格状城市，另一个用于处理集群化社区，还有一个用于处理漫长且蜿蜒的路线。系统随后利用这些存储的教训来进化出更优秀的规则，从而创造出一支专家团队，其中的每一位都是其特定领地的专家。

研究人员在三个经典问题上测试了这个想法：旅行商问题（寻找最短路径）、背包问题（装入最高价值物品）以及带容量限制的车辆路径问题（在有限的卡车空间内运送货物）。他们发现，MOSAIC 的表现始终优于其他最先进的 AI 方法。虽然其他方法在拼图发生轻微变化时会陷入挣扎，但 MOSAIC 的“专家团队”却能轻松应对这些变化，通常能找到更接近完美答案的解法。例如，在旅行商问题上，MOSAIC 最好的规则团队比次优方法准确率高出多达 22%。

或许更令人兴奋的是，MOSAIC 创建的“对抗性”拼图比传统方法制造的拼图更加多样化且更具挑战性。该系统所覆盖的“特征空间”（即不同类型的拼图结构）比以往的方法多出了 33%，这意味着它学会了如何处理更广泛的现实世界场景。这项研究表明，通过将问题视为一种协同进化式的战斗——即拼图变得越来越难以暴露弱点，而规则变得越来越聪明以修复弱点——我们可以构建出不仅仅是记忆几个案例，而是真正理解问题全貌的人工智能。这是一种从“训练一个掌握单一领域知识的全才天才”向“建立一个由了解广泛知识且精通各自特定领域的专家组成的多元化社区”的转变。