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

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

難點(diǎn)在于：一旦問題規(guī)模擴(kuò)大，傳統(tǒng)算法幾乎無法計(jì)算出最優(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)解，因此分?jǐn)?shù)可以不斷提升。

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

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

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

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

（2）推理階段生成不同多樣解法進(jìn)行性能增強(qiáng)。

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

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

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

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

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

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

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

（每組輸入的CPU時(shí)間限制為2秒）

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

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

智能體與1,000名人類選手同場競技，進(jìn)行實(shí)時(shí)比拼。

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

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

這一成果標(biāo)志著AI在解決現(xiàn)實(shí)世界中的優(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)注？

因?yàn)锳HC是AtCoder舉辦的知名編程比賽之一：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ALE-Agent

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

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

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

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

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

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

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

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

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

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

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

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

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

具體見附錄B。

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

結(jié)果如下：

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

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

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

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

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

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

分析與洞察

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

未來工作

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

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

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

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

未來改進(jìn)方向包括：

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

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