楊杰，蒲亦非

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

許多現(xiàn)實(shí)世界的應(yīng)用涉及目標(biāo)優(yōu)化，如成本、能源消耗的最小化，性能、效率和可持續(xù)性的最大化。在許多情況下，優(yōu)化問題存在于高度非線性多模態(tài)目標(biāo)場(chǎng)景，受制于一套復(fù)雜的非線性約束，這些問題很難解決。即使現(xiàn)代計(jì)算機(jī)性能不斷增強(qiáng)，使用簡單暴力破解仍不現(xiàn)實(shí)。因此，高效的算法對(duì)這類應(yīng)用至關(guān)重要。雖然優(yōu)化算法種類很多，如基于梯度的算法、內(nèi)點(diǎn)法、信賴域法等，但大多數(shù)都是基于梯度的局部搜索算法[1]，這意味著最終解可能依賴于起始點(diǎn)。此外，導(dǎo)數(shù)計(jì)算代價(jià)非常昂貴，一些問題如非連續(xù)目標(biāo)在某些區(qū)域可能不具有導(dǎo)數(shù)。近期趨勢(shì)是使用自然啟發(fā)優(yōu)化，可以分成四個(gè)大類：進(jìn)化算法、生物啟發(fā)算法、基于物理/化學(xué)的算法和群智能算法。

在過去的幾十年里，出現(xiàn)了各種各樣的群智能算法，包括蟻群算法、粒子群算法、蝙蝠算法、螢火蟲算法、布谷鳥搜索等[2]。這些自然啟發(fā)算法往往是全局優(yōu)化器，使用多個(gè)相互作用的代理來生成搜索空間中的搜索行為。這類全局優(yōu)化器通常簡單、靈活，高效，在許多應(yīng)用和案例研究中得到了證明[2]。在過去的三十年中，自然啟發(fā)優(yōu)化已經(jīng)取得了顯著的進(jìn)展，并出現(xiàn)了各種各樣的應(yīng)用。

盡管自然啟發(fā)優(yōu)化的有效性和流行度很高，但仍然存在許多問題。第一，還沒有找到開發(fā)與探索之間的平衡。第二，還沒有統(tǒng)一的數(shù)學(xué)框架來對(duì)這些算法進(jìn)行分析，深入了解它們的穩(wěn)定性、收斂性、收斂速度和魯棒性。第三，自然啟發(fā)算法中參數(shù)的取值會(huì)影響算法的性能，但什么是最佳參數(shù)取值或設(shè)置方案以及如何調(diào)優(yōu)這些參數(shù)以獲得最佳性能尚不明確。第四，這些算法的對(duì)比研究主要基于數(shù)值實(shí)驗(yàn)，很難證明這種比較是否公平。分析自然啟發(fā)算法面臨的問題和未來的研究方向，很有必要。

1 問題

1.1 多未必佳

自然啟發(fā)優(yōu)化首要問題是決定是改進(jìn)當(dāng)前社區(qū)發(fā)現(xiàn)的方法，或是尋找新的啟發(fā)來源。最近，圍繞基于隱喻的方法的爭(zhēng)議尚未就社區(qū)在該領(lǐng)域應(yīng)采用的策略達(dá)成任何共識(shí)，也沒有阻止越來越多的基于所謂的創(chuàng)新自然啟發(fā)的優(yōu)化技術(shù)的出現(xiàn)。令人遺憾的是，這類文獻(xiàn)爆發(fā)的部分原因是對(duì)該領(lǐng)域的實(shí)際需求缺乏看法。然而，就如何從理論上（新穎性、特性）和經(jīng)驗(yàn)上（比較方法、基準(zhǔn)問題）評(píng)估新算法這一問題不能達(dá)成共識(shí)，那么就絕對(duì)不可能分清良莠。建議重新開始該領(lǐng)域的工作，著重整個(gè)自然啟發(fā)優(yōu)化的基礎(chǔ)范例，這有助于解決社區(qū)中有爭(zhēng)議的問題。

1.2 統(tǒng)一數(shù)學(xué)框架、符號(hào)和描述

不同的經(jīng)驗(yàn)觀察和數(shù)值模擬已經(jīng)闡明，自然啟發(fā)優(yōu)化在實(shí)踐中表現(xiàn)出色，但我們很少理解為什么它們?cè)诮o定的條件下對(duì)給定類型的問題有效。盡管在理論分析方面取得了一些進(jìn)展，但迫切需要使用更系統(tǒng)的方法（理想情況下，一個(gè)大類別使用一個(gè)統(tǒng)一的框架）來分析自然啟發(fā)算法，以便從數(shù)學(xué)上深入了解它們的工作機(jī)制，評(píng)估其性能，幫助解決為給定的問題集選擇合適的算法的難題。最近提出的理論研究似乎對(duì)分析和理解群智能算法很有希望，例如使用網(wǎng)絡(luò)科學(xué)來表征群智能算法[3]。

圍繞新舊自然啟發(fā)算法之間的類比已經(jīng)進(jìn)行了很多討論，如和聲搜索和進(jìn)化策略；粒子群優(yōu)化與螢火蟲算法；蟻群優(yōu)化和智能水滴。通過統(tǒng)一描述算法的語義可以避免分歧，新算法的提出也可以利用這種統(tǒng)一描述方式。大量新自然啟發(fā)算法被提出證明了采用標(biāo)準(zhǔn)符號(hào)的重要性，標(biāo)準(zhǔn)符號(hào)關(guān)注新算法操作符的領(lǐng)域無關(guān)性描述以及啟發(fā)式和元啟發(fā)式的設(shè)計(jì)模式。

這種標(biāo)準(zhǔn)化無隱喻的詞匯將防止社區(qū)混淆當(dāng)今廣泛使用的模糊數(shù)學(xué)公式和新算法的真實(shí)機(jī)制。例如，通過無隱喻描述，一個(gè)候選解可以被明確地標(biāo)識(shí)，而不是用雞蛋、水滴或蜂巢來指代。文獻(xiàn)[4]將不同蜂群算法的隱喻解碼為標(biāo)準(zhǔn)化優(yōu)化術(shù)語，強(qiáng)調(diào)了符號(hào)唯一性的重要性。除了評(píng)估算法之間的異同之外，該標(biāo)準(zhǔn)化過程還可以帶來其他好處，例如提高模塊化和啟發(fā)式組件的可重用性，更好地檢測(cè)非必要算法復(fù)雜性的可能來源以及使結(jié)果更直接、更可靠、可復(fù)現(xiàn)。描述標(biāo)準(zhǔn)化的透明宣言在多年前就已發(fā)布[5]，但至今仍未在此方向上產(chǎn)生任何重大進(jìn)展。

1.3 參數(shù)調(diào)優(yōu)

對(duì)于擬牛頓法等傳統(tǒng)算法，單個(gè)參數(shù)的調(diào)優(yōu)具有嚴(yán)格的數(shù)學(xué)基礎(chǔ)[1]。而對(duì)于自然啟發(fā)算法，調(diào)優(yōu)主要是根據(jù)經(jīng)驗(yàn)或通過參數(shù)研究[6]。一個(gè)具有m 個(gè)參數(shù)pm=(p1,p2,…,pm)的算法可以用以下形式表示：

其中，ε1,ε2,…,εs是s 個(gè)不同的隨機(jī)數(shù)，可以來自不同的概率分布。這些隨機(jī)數(shù)一般都是迭代選取的。因此，算法調(diào)優(yōu)主要是跟這m 個(gè)參數(shù)有關(guān)，可以把公式（1）簡化成以下形式：

原則上，我們應(yīng)該使用調(diào)優(yōu)好的算法（或沒有任何參數(shù)的算法）來調(diào)優(yōu)新算法。但如果我們使用算法B對(duì)算法A 進(jìn)行調(diào)優(yōu)，算法B 最初是如何調(diào)優(yōu)的？因此，關(guān)鍵問題是如何正確地調(diào)優(yōu)未知算法。

如果參數(shù)數(shù)量很多，暴力調(diào)優(yōu)可能非常耗時(shí)。此外，調(diào)優(yōu)好的算法對(duì)一種類型的問題有效，不能保證其對(duì)另一種類型的問題也有效。算法的參數(shù)設(shè)置可能同時(shí)依賴于算法和問題，而且沒有理由不在迭代過程中改變參數(shù)。事實(shí)上，一些研究表明，參數(shù)的變化可能是有利的。例如，自適應(yīng)差分進(jìn)化算法似乎比其基本版本性能更高[7]。調(diào)優(yōu)算法的一種方法是將參數(shù)調(diào)優(yōu)視為一個(gè)雙邊過程，從而形成一個(gè)自調(diào)優(yōu)框架[8]，使算法可以調(diào)優(yōu)自身。但這仍然是一個(gè)非常耗時(shí)的方法。

如何優(yōu)化指定算法的參數(shù)，使其在給定問題集上達(dá)到最佳性能?或者說，如何改變或控制這些參數(shù)，以最大限度地提高算法的性能?自然啟發(fā)算法的參數(shù)調(diào)優(yōu)問題，尚需研究。

1.4 合適的基準(zhǔn)測(cè)試

對(duì)于任何一種新自然啟發(fā)算法，使用基準(zhǔn)函數(shù)來對(duì)比測(cè)試新算法與其他算法的性能非常重要。這樣的基準(zhǔn)測(cè)試可以讓研究人員更好地了解算法的收斂性、穩(wěn)定性、優(yōu)點(diǎn)和缺點(diǎn)。然而，關(guān)鍵問題是應(yīng)該使用什么基準(zhǔn)。

在目前的文獻(xiàn)中，基準(zhǔn)測(cè)試實(shí)踐似乎使用了一組具有不同屬性的測(cè)試函數(shù)（如振型、可分性和最優(yōu)局域性）。但是這種基準(zhǔn)在實(shí)踐中并沒有太大的用處。這些測(cè)試函數(shù)通常在常規(guī)域上是無約束的或帶有簡單約束的，而實(shí)際應(yīng)用中的問題可能有許多復(fù)雜的非線性約束，并且域可以由許多孤立的區(qū)域或島嶼構(gòu)成。因此，在測(cè)試函數(shù)表現(xiàn)良好的算法不一定在實(shí)際應(yīng)用中表現(xiàn)良好。

為了正確地驗(yàn)證算法，測(cè)試和驗(yàn)證應(yīng)該包括具有不規(guī)則域、受到各種約束的測(cè)試函數(shù)。例如下面這個(gè)看起來很簡單的二維函數(shù)f(x,y)：

定義域?yàn)椋?/p>

其中i,j都是整數(shù)，N=100 ，a=10 。該函數(shù)有4(N+1)2個(gè)局部峰，但在四個(gè)角有4 個(gè)最高峰。其定義域由4(N+1)2=40401個(gè)獨(dú)立區(qū)域構(gòu)成。

根據(jù)無免費(fèi)午餐定理[9]，沒有一個(gè)通用的工具可以用來解決所有或至少絕大多數(shù)的優(yōu)化問題。算法A 解決某些問題的能力優(yōu)于另一個(gè)算法B，那么還有一些其他問題B 會(huì)優(yōu)于A。在實(shí)際解決問題時(shí)，我們總是關(guān)注一組特定的問題，而不是所有的問題。因此，使用有限的算法集和有限的函數(shù)集進(jìn)行基準(zhǔn)測(cè)試成為一個(gè)零和博弈問題[10]。此外，最近的研究似乎表明，免費(fèi)午餐可能存在，特別是對(duì)于持續(xù)優(yōu)化[11]、多目標(biāo)優(yōu)化[12]或協(xié)同進(jìn)化[13]。因此，什么類型的基準(zhǔn)測(cè)試是有用的?免費(fèi)午餐存在嗎?在什么條件下存在?這些問題仍需研究。

1.5 合適公平的性能指標(biāo)

比較算法性能時(shí)，應(yīng)采用合適、公平的指標(biāo)。在目前的文獻(xiàn)中，比較研究主要關(guān)注準(zhǔn)確性、計(jì)算量、穩(wěn)定性和成功率。

驗(yàn)證準(zhǔn)確性比較好的做法是，對(duì)于給定的問題，將算法獲取的最優(yōu)解與已知最優(yōu)解或其他已被驗(yàn)證表現(xiàn)優(yōu)秀的算法的最優(yōu)解進(jìn)行對(duì)比。顯然，這取決于算法的停止條件，即使是無效的算法，運(yùn)行時(shí)間足夠長也可以獲得足夠好的結(jié)果。因此，為了公平起見，所有算法應(yīng)使用相同的計(jì)算量。

驗(yàn)證計(jì)算量，目前大多采用固定精度，將函數(shù)調(diào)用或求值的數(shù)量作為計(jì)算成本的度量進(jìn)行比較。函數(shù)求值的次數(shù)越少被認(rèn)為越好。

自然啟發(fā)算法的結(jié)果不是完全可重復(fù)的，需要多次運(yùn)行才能獲得有意義的統(tǒng)計(jì)數(shù)據(jù)。因此，一些研究人員使用在最終迭代中獲得的最佳目標(biāo)值，以及它們的平均值、標(biāo)準(zhǔn)差和其他統(tǒng)計(jì)數(shù)據(jù)。這可能會(huì)提供有關(guān)算法的更完整描述。雖然標(biāo)準(zhǔn)差越小可能表明算法更穩(wěn)定，但也可能與所考慮的問題有關(guān)，此外，算法中使用的初始化總體和概率分布的方式也有可能影響標(biāo)準(zhǔn)差結(jié)果，盡管尚不清楚初始化如何確切地影響最終結(jié)果。

還有一個(gè)用于比較的指標(biāo)是成功率。多次運(yùn)行（Nr）算法，可能存在Ns次找到最優(yōu)解的情況，則成功率是顯然，這取決于“成功”的定義。對(duì)于函數(shù)f(x)，已知其最優(yōu)解x*和最小化目標(biāo)fmin(x*)，成功可以由解達(dá)到滿意的誤差界|x-x*|≤δ或|f(x)-fmin|≤δ來定義。但是，搜索域相對(duì)平坦與否，會(huì)使得標(biāo)準(zhǔn)非常不同。

大部分文獻(xiàn)使用一種或多種性能指標(biāo)，但尚不清楚上述性能指標(biāo)是否真的公平。我們?nèi)孕杷伎?，要公平比較所有算法，最合適的性能度量是什么？是否有可能設(shè)計(jì)一個(gè)統(tǒng)一的框架來公平而嚴(yán)格地比較所有算法？

2 挑戰(zhàn)

2.1 效能到效率

全球?qū)δ茉葱实年P(guān)注與日俱增，最近創(chuàng)造了所謂的綠色計(jì)算概念[14]。在這個(gè)規(guī)則下的算法以環(huán)境可持續(xù)性作為設(shè)計(jì)目標(biāo)，在它們執(zhí)行線程的步驟中施加了嚴(yán)格的約束。采用此類設(shè)計(jì)會(huì)在資源分配、內(nèi)存索引或運(yùn)行時(shí)間等方面產(chǎn)生重要的修改。最重要的是，算法的實(shí)現(xiàn)方式對(duì)其實(shí)際效率也有很大影響，這就要求從算法設(shè)計(jì)的一開始就采用綠色計(jì)算。支持綠色計(jì)算的良好做法應(yīng)該是使社區(qū)始終對(duì)新的算法執(zhí)行復(fù)雜度分析。在任何情況下，對(duì)自然啟發(fā)算法效率的研究都應(yīng)該避免報(bào)告與算法本身的實(shí)現(xiàn)和部署密切相關(guān)的度量，例如計(jì)時(shí)日志或凈內(nèi)存消耗，這些度量會(huì)因非算法事項(xiàng)產(chǎn)生巨大偏差。未來還應(yīng)推導(dǎo)出算法組件的特征與其預(yù)期碳足跡之間的對(duì)應(yīng)關(guān)系。

2.2 以人為中心的應(yīng)用中的自然啟發(fā)算法

以人為中心的應(yīng)用程序，如視頻游戲或虛擬現(xiàn)實(shí)/增強(qiáng)現(xiàn)實(shí)（VR/AR），目前處于各種場(chǎng)景的前沿，而自然啟發(fā)計(jì)算可以為之提供前所未有的機(jī)器智能水平[15]。這類應(yīng)用以用戶和機(jī)器之間持續(xù)交互為特征，要求底層算法具有用于動(dòng)態(tài)適應(yīng)、增量學(xué)習(xí)和有限復(fù)雜性的卓越能力。盡管存在這些計(jì)算限制，自然啟發(fā)計(jì)算可能給這些應(yīng)用領(lǐng)域帶來的無數(shù)機(jī)會(huì)：從改進(jìn)自我定位到優(yōu)化人群仿真或虛擬對(duì)象的操作。例如，VR/AR 中的延遲會(huì)受到運(yùn)動(dòng)到光子閾值（～20ms）的嚴(yán)重限制，這對(duì)任何自然啟發(fā)優(yōu)化算法都提出了具有挑戰(zhàn)性的設(shè)計(jì)約束，畢竟這些算法的設(shè)計(jì)目的是為了改善用戶體驗(yàn)或優(yōu)化來自流服務(wù)器的媒體內(nèi)容的呈現(xiàn)過程。

要勇于在一個(gè)巨大的領(lǐng)域中探索未來，釋放出新的有趣的范式，如針對(duì)多個(gè)不斷變化的問題語句的持續(xù)優(yōu)化（與持續(xù)/終身機(jī)器學(xué)習(xí)[16]明確相關(guān)），以及自我影響模型（根據(jù)預(yù)測(cè)采取的行動(dòng)可能會(huì)影響隨后的預(yù)測(cè)結(jié)果）。

2.3 自然啟發(fā)優(yōu)化和新興的計(jì)算范例

除上述研究途徑外，整個(gè)社區(qū)都應(yīng)該密切關(guān)注即將到來的新計(jì)算范式，從大數(shù)據(jù)架構(gòu)下的Map/Reduce模型到短暫計(jì)算、億級(jí)計(jì)算和量子計(jì)算。大約十年前，我們沒有預(yù)料到計(jì)算技術(shù)的發(fā)展速度會(huì)像我們后來目睹的那樣快，開發(fā)出了能夠提取、存儲(chǔ)和處理海量數(shù)據(jù)的數(shù)據(jù)密集型技術(shù)。如今，自然啟發(fā)算法的Map/Reduce 實(shí)現(xiàn)可用于在大數(shù)據(jù)平臺(tái)上部署[17]。在處理能力方面，類似的趨勢(shì)可以在當(dāng)今的短暫計(jì)算[18]和億級(jí)計(jì)算[19]中看到，它們?yōu)閿U(kuò)展復(fù)雜的仿生算法提供了有效手段。然而，量子計(jì)算仍然處于初級(jí)階段，它已經(jīng)將其適用性擴(kuò)展到機(jī)器學(xué)習(xí)領(lǐng)域，并預(yù)計(jì)可在許多其他領(lǐng)域的處理吞吐量方面將獲得驚人的收益，包括機(jī)器學(xué)習(xí)和大規(guī)模優(yōu)化[20-21]。

我們不知道未來還會(huì)遇到哪些計(jì)算范例，它們將如何影響自然啟發(fā)優(yōu)化方法的設(shè)計(jì)和部署。然而，我們必須沿著這一領(lǐng)域有價(jià)值的方向開展研究工作，為它們的最終到來做好準(zhǔn)備。除非我們都認(rèn)識(shí)到這種聯(lián)合力量的迫切需要，并就自然啟發(fā)優(yōu)化的真正優(yōu)先事項(xiàng)達(dá)成一致，否則我們將在這一領(lǐng)域毫無進(jìn)展的漸進(jìn)式研究道路上徘徊不定，盲目前進(jìn)。

3 結(jié)論與展望

本文分析自然啟發(fā)優(yōu)化目前面臨的問題及今后的研究方向，以利于這些問題得到充分探索。在自然啟發(fā)領(lǐng)域，未揭示的范例肯定會(huì)繼續(xù)促進(jìn)自然啟發(fā)優(yōu)化的新進(jìn)展，以不可預(yù)見的性能水平和計(jì)算效率為特色。現(xiàn)今，研究界有機(jī)會(huì)拋開誤導(dǎo)性的研究道路，以一種和諧、有原則和科學(xué)的方式，共同面對(duì)這一領(lǐng)域勢(shì)不可擋的未來。