葛錢星，馬 良，劉 勇

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

0 引 言

近年來，元啟發(fā)式算法取得了巨大的發(fā)展，出現(xiàn)了許多有代表性的方法。例如，遺傳算法(genetic algorithm，GA)是基于生物進(jìn)化論中“自然選擇、適者生存”規(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]。這些方法有助于許多復(fù)雜困難優(yōu)化問題的求解[8-15]。但是，隨著所研究的優(yōu)化問題越來越復(fù)雜，具有大規(guī)模、不可微、非線性、不確定性、多目標(biāo)等特征，這些算法也相繼暴露出一些固有的缺陷，如易陷入局部極值和收斂速度慢等。因此，設(shè)計(jì)新型的優(yōu)化算法仍然是值得關(guān)注的研究方向。

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

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

1 隨機(jī)分形

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

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

2 隨機(jī)分形搜索算法

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

圖1 通過受限擴(kuò)散凝聚方法產(chǎn)生的一種簡單分形

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

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

GW2=Gaussian(μP,σ)

(2)

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

(3)

Pj=LB+ε×(UB-LB)

(4)

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

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

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

(5)

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

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

(6)

(7)

(8)

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

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

Step2：計(jì)算種群中每個(gè)個(gè)體Pi的適應(yīng)度函數(shù)值，并找到最佳點(diǎn)BP。

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

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

3 仿真實(shí)驗(yàn)及其結(jié)果

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

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

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

續(xù)表1

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

表2 三種搜索機(jī)制的仿真測試結(jié)果

4 結(jié)束語

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

(1)算法的理論研究：當(dāng)前對隨機(jī)分形搜索算法的研究主要借助于數(shù)值實(shí)驗(yàn)，缺少嚴(yán)格的數(shù)學(xué)論證。因此，后續(xù)研究可以對此進(jìn)行展開。針對收斂性的證明可以嘗試?yán)民R爾可夫鏈等進(jìn)行推導(dǎo)。

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

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