葛錢星，馬 良，劉 勇

(上海理工大學，上海 200093)

0 引 言

近年來，元啟發(fā)式算法取得了巨大的發(fā)展，出現(xiàn)了許多有代表性的方法。例如，遺傳算法(genetic algorithm，GA)是基于生物進化論中“自然選擇、適者生存”規(guī)律而提出的優(yōu)化方法；粒子群優(yōu)化算法(particle swarm optimization，PSO)是基于鳥群覓食行為規(guī)律而提出的群體智能優(yōu)化方法[1]；人工蜂群算法(artificial bee colony，ABC)是基于蜜蜂群覓食行為特性而提出的優(yōu)化方法[2]；蟻群算法(ant colony，AC)是基于蟻群在覓食過程中的行為特性而提出的仿生類算法[3]；引力搜索算法(gravitational search，GSA)是基于萬有引力定律而提出的智能優(yōu)化算法[4-5]；布谷鳥搜索算法(cuckoo search,CS)是基于布谷鳥的寄生育雛的行為特性而提出的元啟發(fā)式算法[6-7]。這些方法有助于許多復雜困難優(yōu)化問題的求解[8-15]。但是，隨著所研究的優(yōu)化問題越來越復雜，具有大規(guī)模、不可微、非線性、不確定性、多目標等特征，這些算法也相繼暴露出一些固有的缺陷，如易陷入局部極值和收斂速度慢等。因此，設計新型的優(yōu)化算法仍然是值得關注的研究方向。

伊朗德黑蘭大學學者Hamid Salimi于2015年提出了隨機分形搜索算法(stochastic fractal search ，SFS)[16]，該算法是基于分形的擴散性質進行優(yōu)化搜索。其基本原理是，引入分形的擴散過程作為其搜索機制，并選擇高斯分布作為擴散過程的隨機游走方式。然后，根據(jù)各個體的適應度函數(shù)值進行選擇，并對各個個體的分量和位置進行更新，最終求得問題的最優(yōu)解。

Hamid Salimi利用隨機分形搜索算法對一系列標準無約束函數(shù)優(yōu)化問題進行數(shù)值實驗，并與回溯搜索優(yōu)化算法、差分進化算法和引力搜索算法等進行比較，實驗結果表明，該算法具有較高的計算精度和較快的收斂速度。此外，還利用隨機分形搜索算法求解了部分工程設計優(yōu)化問題，包括彈簧設計問題、壓力容器設計問題和焊接梁設計問題等，并與遺傳算法、共同進化粒子群優(yōu)化算法、共同進化差分進化算法等進行比較。實驗結果同樣表明，隨機分形搜索算法具有較好的優(yōu)化性能。

1 隨機分形

隨機分形是一種常見的分形，它們的生成具有很大的隨機性，沒有確定的數(shù)學法則，其自相似性不是表現(xiàn)在形態(tài)上，而是表現(xiàn)在結構或復雜度上，這種相似性是近似的，具有統(tǒng)計意義上的自相似性。因此，又稱為統(tǒng)計分形[17]。

隨機分形可以通過隨機規(guī)則來產生，如萊維飛行，高斯游走，滲透集群，自回避行走，分形景觀，布朗運動和布朗樹的軌跡(即通過模擬受限擴散凝聚或受限反應聚集簇產生的樹枝狀分形)[18]。一些隨機分形，例如描述細菌菌落的簇，可以通過稱為“受限擴散凝聚”(diffusion limited aggregation，DLA)的物理模型而生成[19]。為簡單起見，考慮在平面上形成這樣的簇，初始(種子)粒子位于原點。隨后在原點附近產生其他粒子，從而引起擴散。為了模擬擴散過程，采用了隨機游走的數(shù)學算法。擴散產生的粒子粘附在種子粒子上并重復該過程直到形成簇。在形成簇時，與穿透內部的粒子相比，擴散產生的粒子粘附于簇上的概率增加。因此，這種性質會導致所形成的簇呈分支狀結構，如圖1所示。

2 隨機分形搜索算法

受隨機分形擴散性質的啟發(fā)所提出的隨機分形搜索算法，主要包括擴散過程和更新過程。在擴散過程中，每個個體圍繞其當前位置進行擴散，從而增加了找到全局最優(yōu)值的機會，并且可以防止陷入局部最優(yōu)值。另外，在隨機分形搜索中，來自擴散過程的最佳生成個體是唯一被保留的個體，剩下的個體均被丟棄，這樣就有效地避免了因擴散過程導致個體數(shù)量急劇增加；在更新過程中，群體中一個個體的位置的更新是根據(jù)其他個體的位置來進行的。

圖1 通過受限擴散凝聚方法產生的一種簡單分形

為了在擴散過程中產生新的個體，文獻[16]研究了萊維飛行和高斯分布兩種統(tǒng)計方法[20]。對萊維飛行和高斯分布的初步研究顯示，盡管萊維飛行在幾代中收斂速度高于高斯游走，但高斯游走比萊維飛行更有希望找到全局最優(yōu)解。因此，選擇高斯分布作為隨機分形搜索的擴散過程中唯一的隨機游走方式。通常，參與擴散過程的一系列高斯游走如下所示：

GW1=Gaussian(μBP,σ)+(ε×BP-ε'×Pi)(1)

GW2=Gaussian(μP,σ)

(2)

其中，ε和ε'是在區(qū)間[0,1]上服從均勻分布的隨機數(shù)；BP和Pi分別表示群體中的最佳個體和第i個個體的位置。式1中兩個高斯參數(shù)是μBP和σ，其中μBP正好等于|BP|；式2中兩個高斯參數(shù)是μP和σ，其中μP等于|Pi|。高斯參數(shù)中的標準差σ為：

(3)

Pj=LB+ε×(UB-LB)

(4)

其中，LB和UB分別是求解問題的向量的上下邊界；ε是在區(qū)間[0,1]上服從均勻分布的隨機數(shù)。

在初始化所有個體之后，計算每個個體的適應度函數(shù)值以獲得所有個體中的最佳個體(BP)。根據(jù)擴散過程的開發(fā)性質，所有個體都圍繞著當前的位置游走以開發(fā)問題的搜索空間。另一方面，由于探索屬性，考慮了兩個旨在進行更好的空間探索的統(tǒng)計過程作為更新過程。第一次更新過程對每個個體的分量索引執(zhí)行，然后將第二個統(tǒng)計方法應用于所有的個體。

對于第一次更新過程，首先根據(jù)適應度函數(shù)值對所有的個體進行排序，然后給種群中的每個個體i設置性能級別Pai，如下：

(5)

其中，rank(Pi)為個體Pi在種群中的排名；N為種群中個體的數(shù)量。

事實上，式5表明點越好，則其被選中的概率越高。該式用于在還未獲得良好解決方案的情況下增加改變個體的位置的機會；另一方面，在下一代傳遞良好解決方案的機會將會增加。對于群體中的每個個體Pi，判定條件Pai<ε是否滿足,若滿足，則根據(jù)式6更新點Pi的第j個分量；否則，保持不變。

(6)

(7)

(8)

基于以上分析，隨機分形搜索算法的主要步驟可描述如下：

Step1：設置參數(shù)，并初始化種群。

Step2：計算種群中每個個體Pi的適應度函數(shù)值，并找到最佳點BP。

Step3：執(zhí)行擴散過程。對于每一個進行擴散的個體，根據(jù)所選擇的高斯游走方式創(chuàng)建各個新個體的位置，并找到所有個體中的最佳個體，進行函數(shù)返回。

Step6：判定迭代次數(shù)G>最大迭代次數(shù)是否滿足，若滿足，則算法結束，處理并輸出結果；否則，執(zhí)行Step3。

3 仿真實驗及其結果

為驗證算法的可行性和有效性，采用CEC’2010標準測試函數(shù)庫進行仿真實驗，并與回溯搜索優(yōu)化算法(backtracking search optimization，BSA)[21]、協(xié)方差矩陣自適應進化策略(covariance matrix adaptation evolution strategy，CMA-ES)[22]、差分進化算法(differential evolution，DE)[23]、引力搜索算法(gravitational search，GSA)[4-5]、人工蜂群算法(artificial bee colony，ABC)[2,24]、動物遷徙優(yōu)化算法(animal migration optimization，AMO)[25]進行比較。

對于CEC’2010測試函數(shù)，統(tǒng)一設置維度為30。所有算法的種群規(guī)模統(tǒng)一設置為100，并且每種算法獨立運行25次。對于隨機分形搜索算法，最大擴散數(shù)量設置為q=1，其他幾種算法的控制參數(shù)詳見文獻[2,4,21-22,25-26]。仿真結果如表1所示，可參考文獻[27]查看函數(shù)詳細信息。對于每個基準函數(shù)，表1給出了各個算法運行25次的平均解，并根據(jù)平均解從最低到最高對所有的算法進行排名，然后對這二十個函數(shù)的排名進行平均化處理，從而得到各算法的綜合排名。

表1 不同算法求解CEC’2010基準函數(shù)的仿真結果比較

續(xù)表1

由表2中得到的結果表明，隨機分形搜索算法中的每個過程都能顯著影響最終結果的質量，并且隨機分形搜索算法的所有過程共同形成了一個完整的系統(tǒng)來解決優(yōu)化問題。此外，通過大量的實驗表明，對于大多數(shù)的函數(shù)優(yōu)化問題，當MDN (最大擴散數(shù)量)=1時，隨機分形搜索算法通?？梢哉业絾栴}的全局最優(yōu)解。一般來說，根據(jù)所研究的問題調整MDN這一參數(shù)肯定是有益的，但是其重要性是相對而言的；另一方面，增加MDN會面臨要進行時間消耗和收斂速度之間的權衡。

表2 三種搜索機制的仿真測試結果

4 結束語

隨機分形搜索算法是一種在精度和時間消耗方面都很成功的新型元啟發(fā)式算法。該算法基于分形的擴散特性進行優(yōu)化搜索，為優(yōu)化算法的設計提供了新思路。為驗證算法性能，對CEC’2010基準函數(shù)進行了仿真實驗，并與其他算法進行比較，實驗結果表明該算法具有較好的可行性和有效性?；谒惴己玫膬?yōu)化性能，其潛在的研究方向包括但不限于以下幾點：

(1)算法的理論研究：當前對隨機分形搜索算法的研究主要借助于數(shù)值實驗，缺少嚴格的數(shù)學論證。因此，后續(xù)研究可以對此進行展開。針對收斂性的證明可以嘗試利用馬爾可夫鏈等進行推導。

(2)算法的設計研究：與大部分仿生智能優(yōu)化算法不同，隨機分形搜索算法是將分形擴散性質融入智能優(yōu)化算法思想當中的新型算法。要充分吸收分形擴散的研究成果，從而更加有效地設計算法的搜索機制，進一步提高算法的優(yōu)化性能。其次，還可以利用現(xiàn)有的優(yōu)化算法，包括經典優(yōu)化算法和智能優(yōu)化算法，結合隨機分形搜索算法提出改進的混合優(yōu)化算法。此外，還可以考慮引入自適應策略進行參數(shù)控制等。

(3)算法的應用研究：基于算法良好的優(yōu)化性能，其應用前景將十分廣闊。目前，隨機分形搜索算法已經用于求解機械零部件設計等問題，并且取得較好的結果。算法的應用范圍還可以進一步推廣，例如TSP問題、0-1背包問題和二次分配問題等組合優(yōu)化問題以及路徑規(guī)劃、智能電網(wǎng)調度優(yōu)化和應急選址等。