物流路徑選擇、人員排班、工廠調(diào)度、電網(wǎng)平衡、旅行路線……

這些貼近現(xiàn)實的優(yōu)化任務(wù)，看似日常，實則難度極高。

難點在于：一旦問題規(guī)模擴大，傳統(tǒng)算法幾乎無法計算出最優(yōu)解。

通常只能依賴啟發(fā)式或近似算法來接近答案。

這正是NP難(Non-deterministic Polynomial-time hard）題的典型特征。

面對如此復(fù)雜的問題，AI能否勝任？編程智能體表現(xiàn)如何？

為探索這一問題，Sakana AI與AtCoder展開合作，共同構(gòu)建了ALE-Bench（ALgorithm Engineering Benchmark）。

聯(lián)合創(chuàng)始人Llion Jones是Transformer八子之一

不同于傳統(tǒng)的編程基準(zhǔn)測試，ALE-Bench聚焦于需要長推理和創(chuàng)造性思維的高難度的NP難題。

由于NP-困難性質(zhì)，這類問題本身沒有明確的最優(yōu)解，因此分數(shù)可以不斷提升。

研究人員認為，它有潛力成為新一代推理與編程能力的重要評估標(biāo)準(zhǔn)。

為了應(yīng)對這類問題，這次研究特別設(shè)計了端到端的智能體ALE-Agent。

它以Gemini 2.5 Pro為基礎(chǔ)，采用兩大核心策略：

（1）通過Prompt提供常用算法與技術(shù)的領(lǐng)域知識；

（2）推理階段生成不同多樣解法進行性能增強。

在現(xiàn)實環(huán)境中，ALE-Agent已經(jīng)展現(xiàn)出強大能力。

圖1：ALE-Bench概覽。（左）ALE-Bench整合歷屆AtCoder啟發(fā)式競賽題目，如路徑規(guī)劃、任務(wù)調(diào)度等無已知最優(yōu)解的復(fù)雜優(yōu)化問題，并依據(jù)評分對提交程序進行排名。（右）ALE-Bench支持從基礎(chǔ)大語言模型（LLM）到具備結(jié)構(gòu)化引導(dǎo)能力的智能體（scaffolded agent）進行全面評估：智能體接收任務(wù)后提交代碼，可選擇性調(diào)用測試運行與可視化工具，像人類選手一樣迭代優(yōu)化解決方案

以下圖2為例，任務(wù)描述如下：

編寫一個程序，輸入為二維網(wǎng)格上的大量取送請求（pickup-delivery pairs），任務(wù)是從中選擇指定數(shù)量的請求，并規(guī)劃一條從倉庫出發(fā)、最終回到倉庫的路徑。 

路徑必須滿足如下約束：對于每一個被選擇的請求，必須先訪問其取件點，再訪問其對應(yīng)的送達點。

程序的目標(biāo)是使這條路徑的總長度盡可能短。 

評分以路徑總長度為依據(jù)，路線越短，得分越高。

（每組輸入的CPU時間限制為2秒）

圖2：來自ALE-Bench的示例問題（ahc006）

5月，編程競賽平臺AtCoder舉辦了一場啟發(fā)式競賽（AtCoder Heuristic Competition，AHC）,吸引了全球頂尖開發(fā)者參與.

智能體與1,000名人類選手同場競技，進行實時比拼。

最終，ALE-Agent表現(xiàn)出色，排名第21，躋身前2%。

AtCoder啟發(fā)式競賽第47屆（AHC047）的排行榜中，名為「fishylene」的第21名選手，實為Sakana AI提交的智能體ALE-Agent。

這一成果標(biāo)志著AI在解決現(xiàn)實世界中的優(yōu)化問題方面取得了突破。

論文鏈接：https://arxiv.org/abs/2506.09050

數(shù)據(jù)集：https://huggingface.co/datasets/SakanaAI/ALE-Bench

代碼：https://github.com/SakanaAI/ALE-Bench

NP難題

編程智能體新基準(zhǔn)

ALE-Bench基于AtCoder啟發(fā)式競賽（AHC）構(gòu)建而成。

為什么AHC值得關(guān)注？

因為AHC是AtCoder舉辦的知名編程比賽之一：

• 目前規(guī)模最大的得分型算法競賽之一：該賽事每年約舉行10～18場，截至2025年5月1日，已累計舉辦了49場正式比賽。
• 參賽者多: 每場比賽平均吸引約1,000名參賽者，過去兩年共有超過6,000名用戶參與過比賽。
• 題目貼近實際：目類型多種多樣，涵蓋路徑規(guī)劃、任務(wù)調(diào)度、多智能體控制等多個領(lǐng)域。
• 支持長期賽和可視化工具等特色。

每次比賽開始時，主辦方都會發(fā)布一道全新設(shè)計的題目。

圖2所示即為一道典型路徑規(guī)劃題目。這些任務(wù)大多對計算資源要求較高，每個測試用例的運行時間限制通常為2到10秒。

AHC提供兩種比賽形式：短期賽（持續(xù)約4小時）和長期賽（為期1～2周）。

兩者在題目設(shè)計和挑戰(zhàn)難度上存在顯著差異。

短期賽的問題有時可以通過模擬退火（simulated annealing）、束搜索（beam search）等標(biāo)準(zhǔn)算法來求解；

而長期賽更看重深度分析與反復(fù)試驗，解法往往靠「磨」出來。

圖3展示了比賽過程中選手得分逐步提升的過程。

圖3：AHC中的長期賽中，得分上升

在為期兩周的AHC014競賽中，圖3展示了每個時間點上特定排名的得分顯示出持續(xù)的進步。

圖3中線條顏色，標(biāo)記了不同的顏色層級，例如，性能perf=2800（第6名）和性能perf=1200（第379名）。

但無論是哪種形式，想要獲得高分都要針對問題本身，進行推理與反復(fù)調(diào)優(yōu)。

隨著比賽推進，選手可以不斷提交優(yōu)化后的解法，從而逐步提升得分。

圖4：評級和平均表現(xiàn)分布。截至2025年5月1日，至少參與過5次的用戶的累積評級和平均表現(xiàn)分布（背景顏色表示不同的評級層級）

編程新基準(zhǔn)：沒有最佳答案

為了構(gòu)建ALE-Bench，在HuggingFace上，研究團隊發(fā)布了包含40道AHC題目的數(shù)據(jù)集，這些題目均來自截至2025年4月底前舉辦的正式比賽。

數(shù)據(jù)集：https://huggingface.co/datasets/SakanaAI/ALE-Bench/tree/main

這個數(shù)據(jù)集被稱為完整版（full version），還額外提供了一個精簡版（lite version），其中精選了10道具有代表性的題目，方便快速評估和測試。

每道題目的數(shù)據(jù)包包含四大部分：

1. Problem：題目的完整描述，采用Markdown格式，并附帶所有相關(guān)圖示；
2. Scorer：用Rust編寫的評分程序，用于評估選手提交代碼在給定測試用例上的表現(xiàn)；
3. Visualizer：基于網(wǎng)頁的可視化工具和Rust程序，用于動態(tài)展示代碼的執(zhí)行過程，圖2中的圖像即為其示例；
4. Leaderboard：用于計算和展示模型或選手得分排名的參考數(shù)據(jù)。

ALE-Agent

算法工程設(shè)計智能體

在算法工程中，智能體還有多大的發(fā)展?jié)摿Γ?/span>

為了初步探討ALE-Bench所打開的研究空間，這次探索了算法工程領(lǐng)域的特定用途智能體。

該領(lǐng)域具有一些獨特特性。

對許多問題類型而言，已有成熟的高層策略，而選擇正確的整體方案至關(guān)重要。

然而，即使整體思路正確，具體的實現(xiàn)細節(jié)、超參數(shù)設(shè)置和微調(diào)優(yōu)化仍可能顯著影響最終結(jié)果。

基于這一點，在ALE-Agent原型中，研究團隊提出并實現(xiàn)了兩種技術(shù)：

方法一：結(jié)合領(lǐng)域知識的提示策略。

將算法工程中常見技術(shù)的專家知識直接嵌入提示詞中，例如模擬退火（simulatedannealing）和束搜索（beam search）。提示內(nèi)容涵蓋搜索空間和評估函數(shù)的設(shè)計、鄰域生成方式，以及常用的加速技巧。

方法二：注重多樣性的解空間搜索。

研究者采用基于最優(yōu)優(yōu)先搜索（best-first search）的方法，利用大語言模型（LLM）生成并優(yōu)化解的候選項。

為避免過早丟棄有潛力的解路徑，在算法中加入類似束搜索的擴展策略，使每個節(jié)點能一次性生成多個子節(jié)點。

這種寬度擴展有助于保留高潛力假設(shè)，并在實際操作中，通過并行生成候選方案有效減少API延遲，尤其在使用大型推理模型時優(yōu)勢明顯。

具體見附錄B。

研究團隊讓ALE-Agent參加了兩次實時競賽（AHC046和AHC047），與超過1000名人類參賽者遵守相同規(guī)則競爭。

結(jié)果如下：

• AHC046：排名第154（前16%）。
• AHC047：排名第21（前2%），表現(xiàn)尤為出色。

ALE-Bench上的評估結(jié)果

研究團隊在ALE-Bench上對更廣泛的組合優(yōu)化問題進行了評估。

除了ALE-Agent，還測試了其他最先進的AI模型，這些模型在4小時內(nèi)通過自我優(yōu)化持續(xù)改進解決方案（見上圖）。

使用標(biāo)準(zhǔn)優(yōu)化方法的AI模型，表現(xiàn)大致相當(dāng)于人類參賽者的前50%，而ALE-Agent的表現(xiàn)達到了前6.8%，顯示出顯著的性能提升。

完整實驗設(shè)置和結(jié)果請參閱論文。

分析與洞察

在識別復(fù)雜優(yōu)化問題的算法改進方面，ALE-Agent訓(xùn)練得很有競爭力。

更進一步，研究者還觀察了它在算法改進中的表現(xiàn)。

觀察迭代優(yōu)化過程時，研究人員發(fā)現(xiàn)它經(jīng)常應(yīng)用領(lǐng)域知識來提升得分。

例如，它會加速搜索算法和微調(diào)超參數(shù)，就像該領(lǐng)域的頂尖人類專家一樣。

在AHC047實時競賽中，ALE-Agent取得了前2%的成績。

以下是一些迭代創(chuàng)新的例子：加速分數(shù)計算和改進鄰域搜索。

ALE-Agent使用泊松分布近似來加速分數(shù)計算，這是提升AHC047得分的關(guān)鍵策略（代碼見此處，第254-276行）。

ALE-Agent為模擬退火算法設(shè)計了更高效的鄰域搜索策略，通過引入更多樣化的移動方式，擴展了解決方案空間的探索，最終將其排名從第82提升至第21（初始代碼見此處，第304-342行；最終代碼見此處，第492-771行）。

ALE-Agent為何能在AHC047中名列前茅？

其中關(guān)鍵原因是人類與AI解決問題方式的差異。

在4小時的比賽中，人類最多可能優(yōu)化代碼十幾次，而當(dāng)前AI能進行大約100次修訂。

此外，ALE-Agent能生成數(shù)百甚至數(shù)千個潛在解決方案。

這種高速、并行的生成能力，讓AI在短時限比賽中展現(xiàn)出獨特優(yōu)勢。

圖5：迭代優(yōu)化過程中公開分數(shù)與代碼文件大小的變化趨勢。該圖表展示了四小時周期內(nèi)，生成代碼文件大小與對應(yīng)公開評估分數(shù)的同步演變過程。圖中右側(cè)的點位表示更晚的時間節(jié)點

研究者還發(fā)現(xiàn)，當(dāng)前AI非常擅長使用模擬退火，這是AHC中常用的算法（例如，ALE-Agent在AHC039的最佳解決方案，如果參加實際比賽將排名第5）。

未來工作

盡管取得了成功，ALE-Agent仍有一些局限性：

• 調(diào)試困難：ALE-Agent有時無法修復(fù)代碼中的錯誤。
• 時間超限：它無法正確分析自身代碼的復(fù)雜度，導(dǎo)致多次超出時間限制。
• 優(yōu)化誤區(qū)：它有時執(zhí)著于改進對得分貢獻不大的代碼部分。

雖然ALE-Agent在4小時比賽和適合模擬退火的問題上表現(xiàn)良好，但在為期兩周的比賽或需要不同類型算法的問題上表現(xiàn)不佳。

它在基于實驗分析設(shè)計算法（需要通過觀察程序行為進行試錯）時也顯得吃力。

未來改進方向包括：

1. 更可靠的優(yōu)化：通過融入人類專家使用的更多技術(shù)和工具，以及增強反饋機制以支持詳細的執(zhí)行結(jié)果分析。
2. 智能體技術(shù)升級：例如結(jié)合自我改進的方法，使智能體能夠不斷提升自身能力。

最終目標(biāo)是打造一個算法工程能力媲美甚至超越頂尖人類算法工程師的AI。