于潤龍 趙洪科 汪 中 葉雨揚 張培寧 劉 淇 陳恩紅

1(大數(shù)據(jù)分析與應用安徽省重點實驗室(中國科學技術大學) 合肥 230027)2(天津大學管理與經(jīng)濟學部 天津 300072)

在現(xiàn)實世界中存在許多復雜的優(yōu)化問題，例如，最小化汽車流體設計的空氣阻力[1]、最小化天線陣列中的峰值傍瓣電平(peak side-lobe levels, PSLLs)[2]以及最優(yōu)經(jīng)濟調度問題中電力設備的折損[3]等.這些復雜優(yōu)化問題都涉及實值參數(shù)空間的許多局部極值解.通常，研究人員設計專門的模擬軟件來擬合復雜的優(yōu)化場景，也就是說顯式的優(yōu)化函數(shù)和梯度信息是很難被獲取的.這類優(yōu)化問題被統(tǒng)稱為多模態(tài)(非凸)實值優(yōu)化問題或黑盒優(yōu)化問題[4]，圖1展示了3個經(jīng)典的實值優(yōu)化函數(shù)在二維情況下的可視化樣例.由于在大多數(shù)場景下，缺少對優(yōu)化函數(shù)的有效信息，因此需要采取一般的啟發(fā)式假設來指導搜索解空間，所有的這些算法被歸納為元啟發(fā)式搜索[5].大量研究表明[6-8]：元啟發(fā)式搜索在求解復雜實值優(yōu)化問題時，展現(xiàn)了比一般遍歷方法和其他近似方法更好的優(yōu)化性能.其中具有代表性的元啟發(fā)式搜索包括：爬山算法[9](hill climbing, HC)、模擬退火算法[10](simulated annealing, SA)、禁忌搜索[11](tabu search, TS)、遺傳算法[12](genetic algorithms, GA)、粒子群算法[13](particle swarm optimizer, PSO)、演化策略[14](evolution strategies, ES)、差分演化[15](differential evolution, DE)等.

Fig. 1 Visualization of benchmark complex real- parameter optimization functions圖1 可視化復雜實值優(yōu)化函數(shù)

元啟發(fā)式搜索是基于一個或多個隨機搜索進程以及個體或種群的迭代實現(xiàn)的，種群中的每個個體代表了實值優(yōu)化問題的一個可行候選解.為了衡量這些解的優(yōu)劣，需要通過計算實值優(yōu)化問題的函數(shù)值來評估這些候選解，稱得到的函數(shù)值為個體或解的適應度.適應度的大小通常被用于指導元啟發(fā)式搜索的搜索方向[16].對于復雜實值優(yōu)化問題，一方面，由于解空間的維度高、規(guī)模大，存在大量的局部極值點，任何包含有限數(shù)量搜索進程的元啟發(fā)式搜索都不能保證發(fā)現(xiàn)全局最優(yōu)解；另一方面，由于解空間的連續(xù)性和缺乏優(yōu)化函數(shù)的梯度信息，采用任何隨機搜索算子的搜索進程都只能在有限的搜索步驟盡可能接近局部極值點，而不能到達極值點.因此，一個元啟發(fā)式搜索方法是注重解空間的探索，即探尋更多的局部極值點以發(fā)現(xiàn)全局更優(yōu)的解，還是注重解的利用，即驅使適應度更優(yōu)的解逼近周圍的某個局部極值點，是設計元啟發(fā)式搜索最為關鍵的問題之一，相關問題也被稱作探索與利用問題，或多樣化與集約化問題[17].許多元啟發(fā)式搜索提出了平衡探索與利用的方法或假設，研究表明這些元啟發(fā)式假設直接影響了搜索算法的性能[18].特別地，負相關搜索[19](negatively correlated search, NCS)是一種基于種群的元啟發(fā)式搜索算法，假設不同的搜索進程應當探索解空間不同的區(qū)域，通過在并行爬山算法中引入負相關的搜索趨勢，目前展現(xiàn)了復雜實值優(yōu)化問題的最佳優(yōu)化性能.

在本文中，我們以概率分布建模每一個搜索進程的搜索行為，并且根據(jù)其概率分布的大小，將搜索進程的搜索行為進一步劃分為全局搜索行為和局部搜索行為.然后提出一種新的元啟發(fā)式搜索算法，即非對稱負相關搜索(negatively correlated search with asymmetry, NSA)，它假設具有全局搜索行為的搜索進程應當遠離具有局部搜索行為的搜索進程，而具有局部搜索行為的搜索進程不受到具有全局搜索行為的搜索進程的影響.針對元啟發(fā)式搜索的探索與利用問題，我們通過研究一對搜索進程之間負相關搜索趨勢的非對稱性，從而提供了一種平衡探索與利用的新的思路.本文首先總結了實值優(yōu)化問題中元啟發(fā)式搜索的探索與利用問題和相關假設，然后介紹了經(jīng)典的并行爬山算法以及負相關搜索的核心思想，接著描述了非對稱負相關搜索以及其元啟發(fā)式假設.相比負相關搜索，可以發(fā)現(xiàn)非對稱負相關搜索的效率更高且性能更優(yōu).在20個多模態(tài)實值優(yōu)化問題上的對比實驗驗證了我們的想法.最后，討論了關于非對稱負相關搜索在并行計算方面的潛力并給出了擴充實驗結果.

1 相關工作

求解復雜實值優(yōu)化問題的元啟發(fā)式搜索一般分為2類方法：基于種群的搜索算法(采用一組候選解)和基于個體的搜索算法(采用單個候選解).基于個體的搜索算法首先產(chǎn)生單個隨機初始候選解，在每一輪迭代過程中，當前的候選解以一定的概率被其鄰域內另一個解所取代；而基于種群的搜索算法利用了多個候選解，在每一輪迭代過程中，整個種群或者部分候選解被新產(chǎn)生的個體取代.由于這2類元啟發(fā)式搜索導致了不同的探索與利用的平衡策略，我們分別討論其分支的相關工作.

1.1 基于個體的搜索算法

本節(jié)介紹3種經(jīng)典的基于個體的搜索算法，分別是爬山算法(hill climbing, HC)、模擬退火算法(simulated annealing, SA)和禁忌搜索(tabu search, TS).這3種基于個體的元啟發(fā)式搜索可以通過獨立地并行工作轉化成為基于種群的搜索算法，但是大多數(shù)情況下使用它們基于個體的搜索形式[9-11].

1) 爬山算法

爬山算法是最基本的元啟發(fā)式搜索之一，通常被形式化為單個搜索進程，也就是說，從單個隨機初始候選解開始，在迭代的過程中被鄰域內適應度更優(yōu)的候選解取代.爬山算法有許多實現(xiàn)方式，其中采用高斯變異算子的實現(xiàn)方式是處理實值優(yōu)化問題最流行的方法之一[20].為了平衡探索與利用，高斯變異算子的搜索步長由1/5成功準則進行調整.1/5成功準則的核心思想是[21]：如果搜索進程經(jīng)常在過去的迭代過程中找到適應度更優(yōu)的候選解，則應當增大搜索步長；如果搜索進程未能在過去的迭代中找到適應度更優(yōu)的候選解，則搜索步長應當減小.

2) 模擬退火算法

與爬山算法相比較，模擬退火算法采用概率方法更好地探索全局最優(yōu)解.受冶金退火工藝的啟發(fā)，模擬退火算法采用加熱和冷卻的控制策略調整搜索進程遠離局部極值點的能力.在模擬退火算法中，緩慢地實施冷卻的概念被解釋為：隨著解空間的探索而接受適應度較差的候選解的概率被緩慢地降低.這意味著在迭代過程中，模擬退火算法的平衡策略從探索轉向利用.

3) 禁忌搜索

禁忌搜索通過放寬爬山算法的取代條件和引入禁忌列表來加強對解空間的探索能力.首先，在每一輪的迭代過程中，如果當前候選解的鄰域內沒有發(fā)現(xiàn)適應度更優(yōu)的解，則可以接受適應度更差的解.然后，引入禁令以阻止搜索進程訪問之前發(fā)現(xiàn)的解.特別地，如果在短期內訪問過某個候選解，或者候選解違反了預先制定的禁忌規(guī)則，將該候選解標記上禁令并存放在禁忌列表中，以便搜索進程不會反復搜索這個候選解，這有助于算法對解空間的探索能力.

1.2 基于種群的搜索算法

研究表明[6-8]，基于種群的搜索算法不僅在理論方面取得了成功，而且在應用方面被認為是經(jīng)驗上更好的元啟發(fā)式搜索.盡管有許多工作討論了基于種群的探索與利用的平衡策略，但是可以從整體上把它們分為3類[19,22-23]：

1) 小生境技術(niching techniques)

諸如適應度共享和擁擠方法的小生境技術旨在選擇解空間中彼此距離較遠的一組候選解，然后利用這些解產(chǎn)生新的候選解(一般通過雜交算子).適應度共享方法試圖與鄰域的個體共享適應度，并通過犧牲部分候選解的適應度來維持種群的多樣化.而擁擠方法依賴于后代與其近代父母之間的競爭機制，允許調整選擇壓力以偏向選擇相隔距離很遠的個體，從而增進種群的多樣化.

2) 自適應搜索步長(adaptive search step-size)

顯然，可以采用具有小搜索步長的搜索進程來發(fā)現(xiàn)更接近當前候選解的新的解，這有助于利用適應度更優(yōu)的候選解.另一方面，可以采用具有大搜索步長的搜索進程來發(fā)現(xiàn)更遠離當前候選解的新的解，這有助于解空間的探索.許多元啟發(fā)式假設基于解空間的屬性提出了自適應搜索步長的策略.但是，這種方法會引入另一個算法設計問題，也就是說，應該使用何種搜索進程及在迭代期間何時切換具有不同搜索步長的進程以實現(xiàn)探索與利用之間的良好折中.

3) 負相關(negative correlation)

基于并行爬山算法的負相關提出元啟發(fā)式假設，即不同的搜索進程應該在解空間中搜索不同的區(qū)域.通過將各搜索進程的搜索行為建模為概率分布，負相關搜索鼓勵保留那些具有較小相關概率的搜索進程.由于搜索進程之間搜索趨勢的負相關性，負相關搜索顯著提高了探索能力，我們將在接下來的章節(jié)詳細介紹這一策略.

2 并行爬山算法與負相關

在本節(jié)中，首先介紹面向實值優(yōu)化的并行爬山算法(parallel hill climbing, PHC)框架，然后在此基礎上進一步討論負相關搜索.并行爬山算法被形式化為多個爬山算法獨立且并行地運行，每個爬山算法從初始的隨機候選解開始，在迭代期間被適應度更優(yōu)的鄰居候選解取代.我們可以將爬山算法視為單個搜索進程，其在大部分情況下是依賴高斯變異算子實現(xiàn)的，通過1/5成功準則調整高斯變異算子的參數(shù).

2.1 高斯變異算子

(1)

xi d表示xi的第d維分量，N(0,σi)表示一個均值為0且標準差為σi的高斯隨機分布.高斯隨機分布的標準差σi對于不同的搜索進程以及其在解空間不同的維度可以給出不同的值，為了保持簡單的形式，在本文默認初始化所有搜索進程相同的高斯變異算子的參數(shù).對于并行爬山算法，采取下啟發(fā)式規(guī)則來選擇丟棄一個解:

(2)

2.2 搜索步長與15成功準則

通過高斯變異算子的數(shù)學形式，可以了解到一個候選解產(chǎn)生新的解的范圍(新的個體與其父親在解空間的歐氏距離)依賴于高斯隨機分布的標準差σi值.因此在并行爬山算法中，對于單個搜索進程來說，高斯隨機分布的標準差σi值可以被看作調整搜索步長的重要指標.15成功準則被經(jīng)常用于協(xié)助基于高斯變異算子的搜索進程，特別地，調整搜索步長以謀求探索與利用之間的平衡.一般的15成功準則可以表示為[21]

(3)

其中，0

2.3 搜索行為與負相關

負相關搜索首先將搜索進程的搜索行為視為概率分布，因為新的解是在每次迭代時由變異算子作用于候選解產(chǎn)生的，并且下一次迭代中搜索進程的搜索趨勢相當于一個新的解被采樣的概率分布.因此，如果一個搜索進程的搜索行為與其他搜索進程的搜索行為負相關，則很可能在不被其他搜索進程的搜索行為覆蓋的區(qū)域產(chǎn)生新的候選解.這需要測量2個概率分布之間的差異或相關性，巴氏距離(Bhattacharyya distance)被引入并測量2個搜索進程的搜索行為之間的相關性[24].對于2個連續(xù)或離散概率分布的巴氏距離可以分別表示為

(4)

(5)

其中，pi和pj表示2個分布的概率密度函數(shù).如果無法獲知顯式的概率密度函數(shù)，可以通過隨機產(chǎn)生候選解的方式來近似概率，并通過巴氏距離的離散形式估計相關性的值.

(6)

其中，概率分布pi表示了第i個搜索進程的搜索行為.Corr(pi)的值越大，與其相關聯(lián)的候選解越傾向于被保留.

3 非對稱負相關搜索算法

在本節(jié)中，首先討論負相關搜索的局限性.針對負相關搜索的缺陷，提出將非對稱的思想引入負相關，根據(jù)搜索行為的概率分布的大小，將搜索行為進一步劃分為全局搜索行為和局部搜索行為，并給出非對稱負相關搜索作為算法實例.

3.1 負相關的局限性

Fig. 2 Illustration of search behaviors in a two-dimensional search space圖2 二維解空間(標注等高線)的搜索示例

除負相關搜索之外，幾乎所有的元啟發(fā)式假設都將多樣性概念定義為各個候選解之間的多樣性，而負相關搜索提出并定義了搜索行為的多樣性，這直接與搜索進程產(chǎn)生新解的概率分布相關.負相關的思想有效改進了并行爬山算法的搜索性能.然而，本研究認為不同的搜索進程覆蓋不同的搜索區(qū)域(具有負相關的搜索行為)過于嚴格.舉例來說，如果多個搜索進程共同覆蓋的解空間的區(qū)域存在局部極值點，那么這些搜索進程互相遠離的結果將導致其中的局部極值點不被任何一個搜索進程發(fā)現(xiàn).在局部極值點密集的區(qū)域，這種情況尤為明顯.當搜索進程共同覆蓋的解空間的區(qū)域較小且集中多個局部極值點時，負相關不僅不能夠更好地探索解空間，而且還會導致搜索進程擁擠，這大大降低了搜索效率.

考慮圖2所描述的情形，R1和R2表示2個搜索進程在二維解空間采納負相關的搜索行為，在圖例中其搜索趨勢以箭頭符號示意.對于R1和R2，我們以候選解的向量值為圓心，高斯變異算子的標準差為半徑，可視化2個搜索進程在二維解空間的搜索范圍，即搜索進程覆蓋的解空間的區(qū)域.可以發(fā)現(xiàn)，R1和R2的搜索范圍覆蓋了部分相同的區(qū)域，且共同覆蓋的區(qū)域存在局部極值點A.由于負相關鼓勵搜索進程探索解空間不同的區(qū)域以維持解的多樣性，因此R1和R2傾向于在遠離彼此的方向上產(chǎn)生新的解，從而遠離局部極值點A.對于這種情形，2個搜索進程無法利用當前候選解發(fā)現(xiàn)鄰域內適應度更優(yōu)的新的解，可以認為負相關限制了搜索進程對解的利用，破壞了探索與利用的平衡.

3.2 非對稱負相關搜索

為了平衡探索與利用的關系，我們首先根據(jù)一對搜索進程其搜索范圍的相對大小，將種群中的搜索進程的搜索行為劃分為全局搜索行為(搜索范圍較大)和局部搜索行為(搜索范圍較小).一方面，具有全局搜索行為的搜索進程搜索范圍大、搜索方向相對不清晰、其覆蓋的區(qū)域可能存在多個局部極值點或者沒有局部極值點；另一方面，具有局部搜索行為的搜索進程搜索范圍小、搜索方向相對清晰其覆蓋的區(qū)域通常只有一個或少個局部極值點.我們區(qū)別對待具有全局搜索行為的搜索進程與具有局部搜索行為的搜索進程對彼此相關性的影響，并提出非對稱負相關的元啟發(fā)式假設：如果一對搜索進程中存在具有全局搜索行為的搜索進程，那么這個搜索進程應鼓勵與另一個搜索進程負相關的搜索行為.也就是說，具有全局搜索行為的搜索進程應當遠離具有局部搜索行為的搜索進程，而具有局部搜索行為的搜索進程不受到具有全局搜索行為的搜索進程的影響.通過引入非對稱到負相關，我們提供了一種平衡探索與利用的新的思路，并且可以大量節(jié)省由負相關操作產(chǎn)生的計算成本，從而節(jié)約算法的運行時間.

下面介紹一種采納非對稱負相關的元啟發(fā)式假設的實例，即非對稱負相關搜索算法.非對稱負相關搜索繼承了并行爬山算法的基本形式，種群中的個體依賴高斯變異算子產(chǎn)生新的解.特別地，高斯變異算子的標準差成為刻畫個體搜索行為的重要指標.對于第i個搜索進程，當前高斯變異算子的標準差為σi，對于第j個搜索進程，當前高斯變異算子的標準差為σj，如果存在σi>σjW，定義第i個搜索進程相對于第j個搜索進程是具有全局搜索行為的搜索進程，第j個搜索進程相對于第i個搜索進程是具有局部搜索行為的搜索進程，反之亦然，如果不存在σi>σjW或者σj>σiW，定義第i個搜索進程與第j個搜索進程互為具有局部搜索行為的搜索進程，這里W被定義為非對稱參數(shù).對于當前一對搜索進程，具有局部搜索行為的搜索進程不受到相關性的影響.如果一個搜索進程相對于其他所有搜索進程均為具有局部搜索行為的搜索進程，那么它的候選解的更新策略只與解的適應度有關，這與并行爬山算法的候選解的更新策略是一致的.

如果一個搜索進程相對于某個搜索進程具有全局搜索行為，那么就需要計算它與這個搜索進程的相關性.由此，在非對稱負相關搜索中，相關性為

(7)

對于采用高斯變異算子的2個個體xi和xj，其產(chǎn)生子代的概率分布的巴氏距離[25]:

(8)

其中，Σ=(Σi+Σj)2，Σi=σi2I，I是單位矩陣.進一步平衡種群中個體的適應度與相關性之間的關系，因為個體的適應度f(xi)和相關性Corr(pi)通常不在一個量級，并且個體的適應度f(xi)可能取負值，而相關性Corr(pi)是非負的.對于最小化問題，我們采取的策略是f(xi)減去目前為止搜索算法得到的最小值，作非負化處理.然后，對于第i個搜索進程，做歸一化處理，使得和Corr(pi)+都等于1.歸一化處理之后，可以不再考慮f(xi)和Corr(pi)的大小，因為現(xiàn)在它們等于和一個較小的表示有較優(yōu)的適應度，一個較大的表示產(chǎn)生的子代會與那些具有局部搜索行為的個體產(chǎn)生的子代處于較遠的距離.因此，那些更小且更大的解將會傾向于被保留.我們采用啟發(fā)式規(guī)則來選擇丟棄一個解:

(9)

(10)

其中，t是當前迭代的輪數(shù)，Tmax是非對稱負相關搜索迭代的總輪數(shù).

由此，我們可以得到非對稱負相關搜索的算法流程：首先產(chǎn)生N個隨機候選解作為初始種群，記錄下初始種群的最優(yōu)解，進入迭代過程.每一輪迭代，一個隨輪數(shù)變化的λ值被產(chǎn)生，N個新的解由高斯變異算子作用在父代上產(chǎn)生，考察新產(chǎn)生的解的適應度并更新最優(yōu)解，然后根據(jù)其搜索行為選擇式(2)或者式(9)決定新的解是否替換父代成為種群中的個體.每經(jīng)過epoch輪迭代，根據(jù)15成功準則更新高斯變異算子的標準差.終止條件被滿足時，迭代結束，返回最優(yōu)解，算法終止.

4 實驗評估

在本節(jié)，為了評估非對稱負相關搜索(negatively correlated search with asymmetry, NSA)的潛力，我們在實驗部分與許多成熟的基于種群的搜索算法進行比較，包括遺傳算法(genetic algorithms, GA)、粒子群算法(particle swarm optimizer, PSO)、演化策略(evolution strategies, ES)、差分演化(differen-tial evolution, DE)和散點搜索[26](scatter search, SS).對于這些算法中的每一種，選擇最新的版本用于比較，即GL-25[12]，CLPSO[13]，CMA-ES[14]，SaDE[15]和SS[26].此外，還選取了2個流行的基于個體的搜索算法，即模擬退火算法[10](simulated annealing, SA)和禁忌搜索[11](tabu search, TS)，因為它們在實踐中取得了優(yōu)異的性能.為了驗證非對稱負相關的元啟發(fā)式假設，選取并行爬山算法(parallel hill climbing, PHC)和負相關搜索[19](negatively corre-lated search, NCS)做參照.我們根據(jù)文獻中的建議設定上述算法的參數(shù)，給出了實驗結果及分析.最后，討論了關于非對稱負相關搜索在并行計算方面的潛力并給出了擴充實驗結果.

4.1 搜索算法的參數(shù)設置

為了使比較公平，對所有的搜索算法設定相同的產(chǎn)生初始解的策略，并用實值向量的形式表示候選解.SA[10]和TS[11]采取相同的高斯變異算子，其中標準差被初始化為優(yōu)化函數(shù)自變量范圍的1/10，式(3)中的參數(shù)r和epoch分別設定為0.99和10.具體地，對于SA中的冷卻過程，溫度初始化為1，然后每100輪迭代以85%的速率降低；對于TS，將最近生成的5個候選解保存在禁忌列表中.遵循標準程序，設定SS[26]的參考集的大小為10，并且參考集中的每一對候選解在迭代中被重新組合以產(chǎn)生新的解，特別地，使用1點雜交算子作為父代的重組方法，使用高斯變異算子產(chǎn)生并改進新的解.在本實驗中，我們比較了標準的CMA-ES[14].GL-25[12]是一種混合實值編碼的遺傳算法，它首先在25%的計算預期內執(zhí)行全局搜索行為，然后執(zhí)行局部搜索行為，其中與全局搜索行為相關的初始種群大小為400，之后適應度最高的100個個體被保留并執(zhí)行局部搜索行為.在CLPSO[13]中，通過利用所有粒子的歷史最佳信息來更新粒子的速度.在SaDE[15]中，嘗試矢量生成方案和相關控制參數(shù)都是通過逐次學習以前產(chǎn)生的適應度更優(yōu)的候選解及其經(jīng)驗而自適應.CLPSO和SaDE的種群規(guī)模分別為40和50.除了相關性的計算過程之外，PHC和NCS[19]復制NSA的所有組件.也就是說，在PHC中，適應度是被認為是丟棄一個候選解的唯一標準.對于NSA，設定非對稱參數(shù)W=10，我們還需要預先設定NSA的種群大小，在這里將其設定為10，即與SS相同.

4.2 實驗方案

多模態(tài)(非凸)實值優(yōu)化問題是最典型的復雜實值優(yōu)化問題，也正是這類問題激發(fā)了大多數(shù)基于種群的搜索算法的設計.在實驗評估中使用CEC2005實值優(yōu)化競賽[27]的基準測試函數(shù)(編號F6～F20)中20個多模態(tài)實值優(yōu)化問題.每個基準測試函數(shù)的維度設置為30維.每個搜索算法在生成300 000個候選解時終止，并輸出到目前獲得的適應度最優(yōu)的解.最優(yōu)解的質量用函數(shù)誤差測量，即所獲取的最優(yōu)解的目標函數(shù)值與問題的最佳候選解的目標函數(shù)值(這些基準測試函數(shù)已知)之間的差值.也就是說，更優(yōu)的解對應于更小的函數(shù)誤差，零函數(shù)誤差表示找到了最佳的候選解.由于所有的搜索算法都采用隨機搜索算子，我們對每種算法重復實驗25次，記錄相應的函數(shù)誤差值，并將10種算法實現(xiàn)的平均函數(shù)誤差與標準偏差一起列出.

4.3 實驗結果與分析

表1給出了10種搜索算法在20個基準測試函數(shù)上的平均函數(shù)誤差，表2給出了非對稱負相關搜索與負相關搜索在基準測試函數(shù)上運行時間的比較.我們使用雙側Wilcoxon秩和統(tǒng)計檢驗[28]來檢查非對稱負相關搜索與對比搜索算法之間的差異(就函數(shù)誤差而言)是否具有統(tǒng)計顯著性，Wilcoxon秩和統(tǒng)計檢驗以0.05顯著水平設計.通過Wilcoxon秩和統(tǒng)計檢驗，如表1最后一行所示，在成對的比較中，非對稱負相關搜索在統(tǒng)計上顯著優(yōu)于其他算法，特別地，非對稱負相關搜索在20個基準測試函數(shù)上均不顯著劣于負相關搜索，并在17個基準測試函數(shù)上顯著優(yōu)于負相關搜索，驗證了非對稱負相關假設的合理性.并且，在運行時間的比較中，非對稱負相關搜索因為緩解了負相關搜索冗余的相關性計算，在許多基準測試函數(shù)與負相關搜索相比大大節(jié)約了運行時間.此外，我們基于成對的雙側Wilcoxon秩和統(tǒng)計檢驗計算了搜索算法執(zhí)行第K佳結果的次數(shù)，即Top-K(K=1,2,…,10)，如圖3所示.如果算法的整體性能是最優(yōu)的，那么對應的折線會高于其他算法的折線，并且在最小的K值達到20(基準測試函數(shù)的總數(shù)).可以觀察到非對稱負相關搜索在K=6時首先到達了20，同時非對稱負相關搜索永遠不會低于其他折線，因此我們驗證了非對稱負相關搜索取得最佳的整體性能.

Table 1 The Averaged Results of Search Algorithms on Benchmark Functions表1 搜索算法在基礎測試函數(shù)上的平均函數(shù)誤差

Note: The averaged results are listed in the form of “mean ± standard deviation”. The last row provides the results of the Wilcoxon test, where “W-D-L” indicates NSA is superior to, not significantly different from or inferior to the corresponding compared algorithms.

Table 2 The Running Time of NSA and NCS表2 非對稱負相關搜索與負相關搜索的運行時間 s

Fig. 3 The Top-K,K=1,2,…,10,curves of the algorithms圖3 搜索算法的Top-K(K=1,2,…,10)折線圖

Fig. 4 The search trajectories of three algorithms with population size N=4 on the 2D version of F18圖4 在二維基準測試函數(shù)F18上3種算法的搜索軌跡

為了進一步驗證非對稱負相關的元啟發(fā)式假設，在二維可視化的基準測試函數(shù)上設計實驗測試非對稱負相關搜索，并比照了并行爬山算法和負相關搜索.我們設定種群的大小為4，在搜索過程中記錄每個個體的搜索趨勢.在基準測試函數(shù)F18上的結果如圖4所示.可以觀察到并行爬山算法探索解空間的能力很差，解的多樣性在迭代的過程中不能夠被很好地保持；負相關搜索擁有優(yōu)異的探索解空間的能力，有效地保持了解的多樣性，但是限制了對優(yōu)質解的利用，不能夠很好地做到集約化；非對稱負相關搜索在探索解空間的同時，有效地利用了高質量的解.綜上所述，可以認為非對稱負相關的元啟發(fā)式假設在探索與利用之間做到了最優(yōu)的平衡.

4.4 非對稱負相關搜索的并行化

因為元啟發(fā)式搜索是遞歸算法的特性，對于元啟發(fā)式搜索細粒度的并行化方法(基于個體間的并行)，如果不面向個體的適應度計算做單獨的并行設計，元啟發(fā)式搜索并行化的最大效率不會超過種群大小，所以對大種群更友好的元啟發(fā)式搜索并行化潛力更大，通常是更被青睞的算法.特別地，基于種群的搜索算法通常因為個體間頻繁的信息交流與現(xiàn)實中昂貴的通信代價，導致并行化效率較低，無法謀求以種群規(guī)模交換迭代輪數(shù)的目的[29]，因此消除個體之間不必要的通信可以很好地釋放算法的并行潛力.這里設計實驗研究了非對稱負相關搜索在并行化方面的性能，并與負相關搜索進行比較.具體地，采用細粒度的“主-從模型”作為并行框架[30]，如圖5所示，主機負責控制搜索流程，每個計算單元享有一個獨立的搜索進程，搜索進程之間的通信由主機轉接.實驗硬件環(huán)境為英特爾至強多核服務器集群，軟件環(huán)境為Matlab分布式計算系統(tǒng).設定搜索算法的種群大小從10增大到100，相應地計算單元由10個擴充到100個，并且保持搜索算法在生成300 000個候選解時終止，也就是說迭代輪數(shù)從30 000輪減少到3 000輪，記錄下平均函數(shù)誤差與算法運行時間的變化.

Fig. 5 Fine-gained Master-Slaves parallel framework圖5 細粒度的“主-從模型”并行框架

在30維基準測試函數(shù)F7上的結果如圖6和圖7所示.通過觀察圖6可以得到，對于最小化基準測試函數(shù)，我們保持搜索算法生成候選解的個數(shù)，在犧牲迭代輪數(shù)的同時擴大種群的規(guī)模，搜索算法的性能受到不同程度上的影響.其中，非對稱負相關搜索對于種群規(guī)模較大的情況適應較好，負相關搜索在種群規(guī)模極大的情況搜索性能急劇下降，兩者的相對差值呈多項函數(shù)趨勢.這是由于負相關搜索在種群規(guī)模極大的情況容易出現(xiàn)因負相關產(chǎn)生的擁擠現(xiàn)象，也就是說個體集中在局部極值點附近且流通性較差.非對稱負相關的元啟發(fā)式假設只關注全局搜索行為，促進了個體的流通，有效緩解了擁擠現(xiàn)象，對基于大種群的大規(guī)模并行環(huán)境更友好.通過觀察圖7可以得到，在生成候選解的個數(shù)不變的情況下，非對稱負相關搜索可以通過細粒度的并行化方法有效節(jié)約運行時間，并且種群規(guī)模越大，運行時間越短，這得益于隨著種群規(guī)模擴大時算法迭代輪數(shù)減少.同時，并行化負相關搜索的運行時間隨著種群規(guī)模的擴大反而急劇提升，這是由于種群規(guī)模擴大導致整體相關性的計算代價呈冪律提升，從而展現(xiàn)了負收益的并行化結果.非對稱負相關的元啟發(fā)式假設避免了部分冗余的相關性計算，在大規(guī)模并行環(huán)境展現(xiàn)了更加優(yōu)異的潛力.

Fig. 6 The function errors of parallelized NSA and NCS圖6 并行化NCS,NSA的平均函數(shù)誤差及相對差(Diff)

Fig. 7 The running time of parallelized NSA and NCS圖7 并行化NSA以及并行化NCS的運行時間

5 總 結

本文首先介紹了求解復雜實值優(yōu)化問題的一般性方法和關于探索與利用的背景研究，然后圍繞平衡探索與利用的策略分析了流行的元啟發(fā)式假設，特別是負相關.我們發(fā)現(xiàn)負相關搜索鼓勵搜索行為的多樣性從而改進了并行爬山算法的探索能力，但是其假設過于嚴格，并且導致搜索進程的擁擠和相關性計算的冗余.我們提出了非對稱負相關的元啟發(fā)式假設，將種群中搜索進程的搜索行為劃分為全局搜索行為和局部搜索行為，鼓勵具有全局搜索行為的搜索進程盡可能遠離具有局部搜索行為的搜索進程.在此基礎上，我們給出了非對稱負相關搜索的算法流程，并在20個多模態(tài)實值優(yōu)化問題上與成熟的搜索算法對比，實驗結果表明非對稱負相關搜索取得了最佳的整體性能，同時在運行效率和并行化潛力方面顯著優(yōu)于負相關搜索.

元啟發(fā)式搜索是通過全局探索和局部利用的不同機制引導并迭代生成解的一類過程，探索與利用之間的平衡是提高元啟發(fā)式搜索優(yōu)化性能的關鍵因素，不同的平衡策略是區(qū)分許多元啟發(fā)式搜索的重要標識.本文繼承了負相關對于搜索行為多樣性的概念，與此同時關注解的利用，面向復雜實值優(yōu)化問題，提供了一種平衡探索與利用的新思路.未來的研究包括：1)關于非對稱負相關搜索的理論研究，比如發(fā)現(xiàn)最優(yōu)解的時間復雜度分析；2)將非對稱負相關搜索擴展到其他優(yōu)化問題，比如，多目標實值優(yōu)化問題，組合優(yōu)化問題，多任務優(yōu)化問題等；3)利用非對稱負相關搜索解決具體的復雜應用問題.