本文第一作者柳斐（https://feiliu36.github.io/ ）是香港城市大學(xué)計算機科學(xué)系博士生，師從張青富教授。研究領(lǐng)域為計算智能，自動算法設(shè)計，組合優(yōu)化等。姚一鳴，郭平，楊致遠(yuǎn)，趙哲和林熙來自香港城市大學(xué)張青富教授團隊。陸智超為香港城市大學(xué)計算機科學(xué)系助理教授。王振坤為南方科技大學(xué)系統(tǒng)設(shè)計與智能制造學(xué)院助理教授。童夏良和袁明軒來自華為諾亞方舟實驗室。

• 論文標(biāo)題：A Systematic Survey on Large Language Models for Algorithm Design
• 論文地址：https://arxiv.org/abs/2410.14716

算法設(shè)計（AD）對于各個領(lǐng)域的問題求解至關(guān)重要。大語言模型（LLMs）的出現(xiàn)顯著增強了算法設(shè)計的自動化和創(chuàng)新，提供了新的視角和有效的解決方案。在過去的三年里，LLMs 被整合到 AD（LLM4AD）中取得了顯著進展，在優(yōu)化、機器學(xué)習(xí)、數(shù)學(xué)推理和科學(xué)發(fā)現(xiàn)等各個領(lǐng)域獲得廣泛研究和應(yīng)用。鑒于這一領(lǐng)域的快速發(fā)展和廣泛應(yīng)用，進行系統(tǒng)性的回顧和總結(jié)既及時又必要。本文對 LLM4AD 的研究進行了系統(tǒng)性回顧。首先，我們概述和總結(jié)了現(xiàn)有研究。然后，我們沿著四個維度，包括 LLMs 的作用、搜索技術(shù)、提示策略和應(yīng)用，提出了一個系統(tǒng)性分類和現(xiàn)有研究的回顧，討論了使用 LLMs 的潛力和成就。最后，我們探討當(dāng)前的挑戰(zhàn)，并提出了幾個未解問題和未來研究的方向。

1. 引言

算法在解決各個領(lǐng)域的問題中發(fā)揮著至關(guān)重要的作用，包括工業(yè)、經(jīng)濟、醫(yī)療和工程等領(lǐng)域。傳統(tǒng)的手工設(shè)計算法的方法繁瑣且耗時，需要廣泛的專業(yè)知識和大量的努力。因此，人們越來越關(guān)注在算法設(shè)計中采用機器學(xué)習(xí)和計算智能技術(shù)以自動化和增強算法開發(fā)過程。

近年來，大型語言模型（LLMs）已經(jīng)成為生成人工智能領(lǐng)域的重大突破。LLMs 以其龐大的模型規(guī)模、巨大的訓(xùn)練數(shù)據(jù)和在語言理解、數(shù)學(xué)推理、代碼生成等各個研究領(lǐng)域中有著出色的表現(xiàn)。在過去的三年里，大型語言模型用于算法設(shè)計（LLM4AD）已經(jīng)成為一個新興的研究領(lǐng)域，有望增強甚至重塑算法的構(gòu)思、優(yōu)化和實施方式。LLMs 的強大功能和適應(yīng)性展示了其在改進和轉(zhuǎn)變算法設(shè)計過程中的潛力，包括啟發(fā)式生成、代碼優(yōu)化，甚至創(chuàng)造針對特定問題的新算法。這種方法不僅減少了設(shè)計階段所需的人力，還提高了算法設(shè)計過程的創(chuàng)新性和效率。

盡管 LLM4AD 領(lǐng)域正在受到廣泛研究和應(yīng)用，但在這一新興領(lǐng)域仍然缺乏系統(tǒng)性綜述。本文旨在通過提供一個最新的多維度的系統(tǒng)綜述來填補這一空白，全面展示 LLMs 在算法設(shè)計中的應(yīng)用現(xiàn)狀、主要挑戰(zhàn)和未來研究方向。本文有助于深入探討 LLMs 在增強算法設(shè)計方面的潛力，并為這一令人興奮的領(lǐng)域的未來創(chuàng)新打下堅實基礎(chǔ)。我們希望這將成為對該領(lǐng)域感興趣的研究人員的有益資源，并為經(jīng)驗豐富的研究者提供一個系統(tǒng)性的綜述。本文的貢獻如下：

• LLM4AD 的系統(tǒng)綜述：我們首次對過去三年中發(fā)表的 180 多篇高度相關(guān)的研究論文進行了系統(tǒng)綜述，探討了使用 LLMs 進行算法設(shè)計的發(fā)展。
• LLM4AD 的多維度分類：我們引入了一個多維度分類法，將 LLM4AD 的作品和功能分為四個不同的維度：1）LLMs 在算法設(shè)計中使用的四種范式，概述了這些模型如何為算法設(shè)計做出貢獻或增強算法設(shè)計；2）搜索方法，探討了 LLMs 用于導(dǎo)航和優(yōu)化算法設(shè)計中搜索空間的各種方法；3）提示詞設(shè)計，研究了如何使用不同的提示策略；以及 4）應(yīng)用領(lǐng)域，確定 LLMs 正在應(yīng)用于解決的不同領(lǐng)域。
• LLM4AD 的挑戰(zhàn)和未來方向：我們不僅僅是對現(xiàn)有文獻進行總結(jié)，而是對當(dāng)前關(guān)于算法設(shè)計中大型語言模型（LLMs）研究的局限性進行了批判性分析。此外，我們提出了潛在的未來研究方向，包括開發(fā)領(lǐng)域特定的 LLMs、探索多模態(tài) LLMs、促進人與 LLM 的互動、使用 LLMs 進行算法評估和理解 LLM 行為、推進全自動算法設(shè)計，以及為系統(tǒng)評估 LLM 在算法設(shè)計中的表現(xiàn)進行基準(zhǔn)測試。這一討論旨在激發(fā)新的方法并促進該領(lǐng)域的進一步發(fā)展。

2. 大模型用于算法設(shè)計概覽

本文旨在對新興領(lǐng)域 “大語言模型用于算法設(shè)計”（LLM4AD）中現(xiàn)有研究工作進行系統(tǒng)的梳理和分類。我們并不打算涵蓋所有關(guān)于大型語言模型（LLMs）和算法的文獻。我們的調(diào)查范圍如下所述：1）“大語言模型” 一詞指的是規(guī)模足夠大的語言模型。這些模型通常采用 Transformer 架構(gòu)，并以自回歸方式運行。使用較小模型進行算法設(shè)計的研究，如傳統(tǒng)的基于模型和機器學(xué)習(xí)輔助的算法，不在考慮范圍內(nèi)。雖然精確定義 “大型” 模型具有挑戰(zhàn)性，但大多數(shù)前沿的大型語言模型包含超過十億個參數(shù)。使用其他大型模型缺乏語言處理能力的研究，如純視覺模型，不在考慮范圍內(nèi)。然而，包括語言處理的多模態(tài)大型語言模型則在我們的調(diào)查范圍之內(nèi)。2）“算法” 一詞指的是一組設(shè)計用來解決問題的數(shù)學(xué)指令或規(guī)則，特別是當(dāng)由計算機執(zhí)行時。這個廣泛的定義包括傳統(tǒng)的數(shù)學(xué)算法、大多數(shù)啟發(fā)式方法，以及可以被解釋為算法的某些策略。

我們介紹了論文收集和掃描的詳細(xì)流程，包括四個階段：

• 第一階段 數(shù)據(jù)提取和收集：我們通過谷歌學(xué)術(shù)、科學(xué)網(wǎng)和 Scopus 收集相關(guān)論文。我們的搜索邏輯是標(biāo)題必須包含以下兩組詞語中至少一組的任意組合：“LLM”、“LLMs”、“大型語言模型”、“算法”、“啟發(fā)式”、“搜索”、“優(yōu)化”、“優(yōu)化器”、“設(shè)計”、“方法”（例如，LLM 和優(yōu)化，LLMs 和算法）。在移除重復(fù)的論文后，截至 2024 年 7 月 1 日，我們共收集到 850 篇論文。
• 第二階段 摘要篩選：我們檢查每篇論文的標(biāo)題和摘要，以有效排除不相關(guān)的論文。排除的標(biāo)準(zhǔn)包括這些論文不是英文的，不是用于算法設(shè)計的，沒有使用大型語言模型的。掃描后，剩余 260 篇論文。
• 第三階段 全文篩選：我們徹底審查每篇論文，排除缺乏相關(guān)內(nèi)容的論文。掃描后，剩余 160 篇論文。
• 第四階段補充：根據(jù)對該領(lǐng)域的了解，我們手動添加了一些相關(guān)的工作，以避免遺漏任何重要的貢獻。在整合了額外的論文后，我們最終得到了 180 多篇論文。我們將首先介紹 LLM4AD 論文列表的概覽，然后提出一個分類法來系統(tǒng)地回顧進展。除了組織好的論文列表之外，我們還納入了 2024 年 7 月 1 日之后發(fā)布的一些重要出版物。

圖中展示了隨時間變化的論文發(fā)表數(shù)量趨勢，時間線以月份表示。圖表顯示，與 LLM4AD 相關(guān)的研究活動顯著增加，特別是注意到大多數(shù)研究是在近一年進行的。這表明 LLM4AD 是一個新興領(lǐng)域，隨著來自不同領(lǐng)域的學(xué)者意識到其巨大潛力，我們預(yù)計在不久的將來研究產(chǎn)出將顯著增加。

圖中還顯示了在 LLM4AD 出版物中領(lǐng)先的機構(gòu)及其所在國家。美國領(lǐng)先，緊隨其后的是中國，這兩個國家單獨占據(jù)了 50％的出版物。接下來的八個國家，包括新加坡、加拿大和日本，共同貢獻了總出版物的三分之一。發(fā)表最多論文的研究機構(gòu)包括清華大學(xué)、南洋理工大學(xué)和多倫多大學(xué)等知名大學(xué)，以及華為、微軟和谷歌等大型公司。這種分布強調(diào)了研究主題的廣泛興趣和它們在現(xiàn)實世界中的實際應(yīng)用的重大相關(guān)性。

我們從所有審查過的論文的標(biāo)題和摘要中生成了詞云，每個詞至少出現(xiàn)五次。它展示了前 80 個關(guān)鍵詞，這些詞被組織成四個顏色編碼的簇，分別是 “語言”、“GPT”、“搜索和優(yōu)化” 以及 “科學(xué)發(fā)現(xiàn)”。還突出顯示了幾個關(guān)鍵詞，如 “進化”、“策略”、“優(yōu)化器” 和 “代理”。

3. 大模型用于算法設(shè)計的四種范式

LLM4AD 論文按照大模型的結(jié)合方法可以分為四個范式：1）大模型作為優(yōu)化算子（LLMaO）、2）大模型用于結(jié)果預(yù)測（LLMaP）、3）大模型用以特征提取（LLMaE）、4）大模型用來算法設(shè)計（LLMaD）。

• LLMaO 把 LLMs 用作算法框架內(nèi)的黑盒優(yōu)化器。將 LLMs 整合到優(yōu)化任務(wù)中，充分利用它們理解和生成復(fù)雜模式和解決方案的能力，以及在提示工程中的良好靈活性。然而，由于它們的黑盒性質(zhì)，它們通常缺乏可解釋性，并在面對大規(guī)模問題時面臨挑戰(zhàn)。
• LLMaP 使用 LLMs 作為代理模型，預(yù)測結(jié)果或響應(yīng)，功能上大體可以分為分類或回歸兩類。與其他基于模型的預(yù)測器（如高斯過程和傳統(tǒng)神經(jīng)網(wǎng)絡(luò)）相比，1) LLMs 能夠基于其在龐大數(shù)據(jù)集上接受的訓(xùn)練，處理和生成類人響應(yīng)。這種能力使它們能夠理解和解釋數(shù)據(jù)中的復(fù)雜模式，適用于傳統(tǒng)建模技術(shù)可能因數(shù)據(jù)的復(fù)雜性和復(fù)雜表示而難以應(yīng)對的任務(wù)。2) 預(yù)訓(xùn)練的 LLMs 可以顯著減少與訓(xùn)練高保真模型相比所需的計算負(fù)載和時間。
• LLMaE 利用 LLMs 挖掘和提取目標(biāo)問題和（或）算法中的嵌入特征或特定知識，然后在解決新問題中利用這些特征。這一過程利用了 LLMs 的獨特和強大的能力，如文本和代碼理解，使它們能夠識別數(shù)據(jù)中可能通過傳統(tǒng)特征提取方法無法處理或理解的模式和關(guān)系。
• LLMaD 直接創(chuàng)建算法或特定組件。這種范式充分利用了 LLMs 的語言處理、代碼生成和推理能力。LLMs 通過生成啟發(fā)式算法、編寫代碼片段或設(shè)計函數(shù)，進一步推動了算法設(shè)計自動化，顯著加速算法設(shè)計過程，減少人力勞動，并可能為算法開發(fā)帶來創(chuàng)造性和更好的設(shè)計。這是單靠傳統(tǒng)算法設(shè)計方法難以實現(xiàn)的。

4. 大模型用于算法設(shè)計中的搜索方法

目前的經(jīng)驗表明，單獨采用大模型來進行算法設(shè)計往往難以應(yīng)對特定的復(fù)雜算法設(shè)計任務(wù)。通過搜索方法的框架下調(diào)用大模型能夠顯著提升算法設(shè)計效率和效果。我們綜述了目前在 LLM4AD 中采用的搜索方法，并將其大致分為四類：1）基于采樣的方法，2）單點迭代的搜索方法，3）基于種群的搜索方法和 4）基于不確定性的搜索方法。詳細(xì)的介紹和討論可以在原文中查看。

5. 大模型用于算法設(shè)計中的提示詞設(shè)計

圖中展示了文獻中使用的領(lǐng)域或預(yù)訓(xùn)練語言模型（LLMs）的百分比。其中，超過 80％的研究選擇使用未經(jīng)特定微調(diào)的預(yù)訓(xùn)練模型，大約 10％的研究在領(lǐng)域數(shù)據(jù)集上對預(yù)訓(xùn)練模型進行了微調(diào)，其中只有 4.4％的模型是在特定問題上從頭開始訓(xùn)練的。圖中還展示了最常使用的 LLMs。在 LLM4AD 的論文中，GPT-4 和 GPT-3.5 是使用最多的 LLMs，總共占了大約 50％。Llama-2 是最常用的開源 LLM。一旦我們擁有了預(yù)訓(xùn)練的 LLMs，提示工程對于有效整合 LLMs 到算法設(shè)計中非常重要。我們討論了 LLM4AD 論文中使用的主要提示工程方法的應(yīng)用情況，包括零樣本、少樣本、思維鏈、一致性和反思。

6. 大模型用于算法設(shè)計的應(yīng)用領(lǐng)域

我們整理了四個主要的應(yīng)用領(lǐng)域：1）優(yōu)化，2）機器學(xué)習(xí)，3）科學(xué)發(fā)現(xiàn)，4）工業(yè)。其主要工作按照應(yīng)用類別、方法、大模型結(jié)合范式、提示詞策略和具體應(yīng)用問題進行了分類羅列。具體介紹可以在全文中查看。

7. 未來發(fā)展方向

1. 算法設(shè)計大模型 與使用通用的預(yù)訓(xùn)練 LLMs 不同，研究如何專門訓(xùn)練 LLM 以自動設(shè)計算法是值得的。在開發(fā)領(lǐng)域特定 LLM 時可以探索以下幾個方面：1）訓(xùn)練領(lǐng)域 LLM 成本高且資源消耗大。借助領(lǐng)域數(shù)據(jù)和知識可以減小特定應(yīng)用的算法 LLM 的規(guī)模。2）算法設(shè)計生成和收集領(lǐng)域數(shù)據(jù)存在挑戰(zhàn)。與通用代碼生成或語言處理任務(wù)不同，沒有專門用于算法設(shè)計的大型且格式化的數(shù)據(jù)。3）與其學(xué)習(xí)一個文本和代碼生成模型，如何學(xué)習(xí)算法開發(fā)思想和算法推理能力仍是一個未探索的問題。
2. 多模態(tài) LLM 現(xiàn)有的 LLM4AD 工作主要集中在利用 LLM 的文本理解和生成能力，無論是在語言、代碼還是統(tǒng)計方面。與傳統(tǒng)的基于模型的優(yōu)化相比，LLM 的一個優(yōu)勢是它們能像人類一樣處理多模態(tài)信息，這一點很少被研究。已經(jīng)有一些嘗試展示了在算法設(shè)計中融入多模態(tài)信息的優(yōu)勢，預(yù)計將開發(fā)更多利用多模態(tài) LLM 的方法和應(yīng)用。
3. 人類 - 大模型交互 需要進一步研究 LLM 與人類專家在算法設(shè)計中的互動。例如，在 LLMaD 工作中，LLM 可以被視為智能代理，使人類專家可以介入并接管生成、修改和評估算法等任務(wù)。研究如何促進 LLM 與人類專家之間高效且富有成效的合作將是有價值的。可以為此目的使用群體智能中的思想和技術(shù)。
4. 基于 LLM 的算法評估 LLM 在算法評估中可能是有幫助的。已經(jīng)進行了一些嘗試來自動評估算法和評估算法設(shè)計。例如，已有工作利用基礎(chǔ)模型自動生成定義下一個可學(xué)習(xí)任務(wù)的代碼，通過生成環(huán)境和獎勵函數(shù)，能夠為算法評估創(chuàng)建各種模擬學(xué)習(xí)任務(wù)。我們期待更多關(guān)于基于 LLM 的算法評估的研究。
5. 理解 LLM 的行為 在大多數(shù)研究中，LLM 作為一個黑盒模型運作。解釋 LLM 的行為不僅能豐富我們對 LLM 行為的理解，還有助于那些直接請求 LLM 困難或成本高昂的情況。已經(jīng)有一些嘗試來近似和理解 LLM 在解決方案生成中的上下文學(xué)習(xí)行為。例如，已有人設(shè)計了一個白盒線性算子來近似 LLM 在多目標(biāo)進化優(yōu)化中的結(jié)果。盡管有這些初步嘗試，如何解釋 LLM 的行為在許多算法設(shè)計案例中仍是一個開放的問題，包括啟發(fā)式生成和想法探索。
6. 全自動算法設(shè)計 全自動算法設(shè)計面臨兩個主要挑戰(zhàn)：1) 生成新的算法思想；2) 創(chuàng)建復(fù)雜、冗長的代碼。雖然一些研究已經(jīng)探討了新思想的生成，但完整的算法設(shè)計（而不僅是啟發(fā)式組件），包括啟發(fā)式組件和詳細(xì)的代碼實現(xiàn)，仍然是一個挑戰(zhàn)。現(xiàn)有應(yīng)用通常專注于自動化預(yù)定義算法框架內(nèi)的組件，而不是從頭開始創(chuàng)建新算法。未來的研究需要解決這些復(fù)雜性，以推進全自動算法設(shè)計領(lǐng)域的發(fā)展。
7. LLM4AD 的標(biāo)準(zhǔn)測試集和平臺 標(biāo)準(zhǔn)測試集能促進進行公平、標(biāo)準(zhǔn)化和便捷的比較。雖然我們很高興見證了多樣化的研究工作和應(yīng)用的出現(xiàn)，但仍然缺乏對基于 LLM 的算法設(shè)計的系統(tǒng)和科學(xué)的標(biāo)準(zhǔn)評估手段。未來，預(yù)計會有更多的基準(zhǔn)測試出現(xiàn)，它們將在推進 LLM4AD 方面發(fā)揮關(guān)鍵作用。

8. 總結(jié)

本文提供了一份最新的關(guān)于大語言模型在算法設(shè)計中應(yīng)用（LLM4AD）的系統(tǒng)性綜述。通過系統(tǒng)回顧這一新興研究領(lǐng)域的主要貢獻文獻，本文不僅突出了 LLM 在算法設(shè)計中的當(dāng)前狀態(tài)和發(fā)展，還引入了一個全新的多維分類體系，分類了 LLM 的結(jié)合范式、搜索方法、提示詞方法和應(yīng)用場景。這一分類體系為學(xué)術(shù)界和工業(yè)界的研究人員提供了一個框架，幫助他們理解和使用 LLM 進行算法設(shè)計。我們還討論了該領(lǐng)域當(dāng)前面臨的限制和挑戰(zhàn)并提出和探討未來研究方向來激發(fā)和指引后續(xù)研究。

展望未來， LLM 與算法設(shè)計的交叉具有革命性地改變算法設(shè)計和應(yīng)用方式的巨大潛力。LLM 在算法設(shè)計過程中的應(yīng)用有助于極大的提高自動化程度并可能促進產(chǎn)生更高效、更有效和更具創(chuàng)造性的算法，以更好解決各個領(lǐng)域的復(fù)雜問題。我們希望本文能夠有助于理解這一潛力，并促進 LLM4AD 這一有前景的研究領(lǐng)域的發(fā)展。