魯曉藝， 劉 升， 韓斐斐， 于建芳

(上海工程技術(shù)大學(xué) 管理學(xué)院， 上海 201620)

引言

近年來(lái)，群智能算法作為一種新興的演化計(jì)算技術(shù)，其良好的尋優(yōu)性能已成為越來(lái)越多研究者關(guān)注的焦點(diǎn)。在管理科學(xué)和自然科學(xué)等領(lǐng)域中發(fā)揮著重要作用，廣泛應(yīng)用于解決工程調(diào)度[1]、組合優(yōu)化[2]、風(fēng)險(xiǎn)預(yù)測(cè)[3]等復(fù)雜問(wèn)題。群智能算法受自然規(guī)律的啟迪，利用仿生原理進(jìn)行設(shè)計(jì)，如人工蜂群(artificial bee colony，ABC)[4]算法模擬蜜蜂群體尋找優(yōu)質(zhì)花蜜源的過(guò)程，把蜜蜂分為引領(lǐng)蜂、跟隨蜂和偵察蜂3種角色；螢火蟲算法(firefly algorithm，F(xiàn)A)[5]模擬自然界螢火蟲在晚上群聚活動(dòng)的自然現(xiàn)象而提出的，在螢火蟲的群聚活動(dòng)中，每只螢火蟲通過(guò)散發(fā)熒光素與同伴進(jìn)行尋覓食物以及求偶等信息交流；人工魚群(artificial fishswarm，AF)[6]算法通過(guò)模仿魚群的覓食、聚群及追尾行為，從而實(shí)現(xiàn)尋優(yōu)。

緞藍(lán)園丁鳥優(yōu)化算法(satin bower bird optimization algorithm，SBO)[7]是由Seyyed Hamid Samareh Moosavi和Vahid Khatibi Bardsiri于2017年模擬自然界成年雄性緞藍(lán)園丁鳥的求偶行為而提出的一種新型群智能算法，并結(jié)合了自適應(yīng)神經(jīng)模糊推理系統(tǒng)(ANFIS)，發(fā)現(xiàn)能夠有效地提高軟件開發(fā)工作評(píng)估的準(zhǔn)確性。該算法融合了動(dòng)態(tài)步長(zhǎng)和變異等操作，具有良好的尋優(yōu)性能。但由于提出時(shí)間較短，目前國(guó)內(nèi)外少有文獻(xiàn)對(duì)其進(jìn)行研究。

由于大多數(shù)的群智能算法，存在著求解精度粗糙、后期迭代速度緩慢等不足，這些新穎群智能算法在求解精度、尋優(yōu)效果等方面仍存在較大的提升空間，國(guó)內(nèi)外眾多的專家學(xué)者針對(duì)這些不足進(jìn)行了有效的改進(jìn)。2015 年，孔飛和吳定會(huì)提出了一種改進(jìn)的雞群算法[8]，算法中對(duì)小雞的位置更新公式中引入慣性權(quán)值和學(xué)習(xí)因子，解決了求解優(yōu)化問(wèn)題時(shí)易于跳過(guò)最優(yōu)解及早熟收斂的問(wèn)題。徐辰華等人于2017年基于Cat混沌與高斯變異改進(jìn)灰狼優(yōu)化算法[9]，該算法采用高斯變異擾動(dòng)和優(yōu)勝劣汰選擇規(guī)則，對(duì)當(dāng)前最優(yōu)解進(jìn)行變異操作以避免算法陷入局部最優(yōu)。

本文鑒于改進(jìn)的基礎(chǔ)上，首先從原理上對(duì)算法的實(shí)現(xiàn)步驟進(jìn)行闡述，并提出了基于自適應(yīng)權(quán)重的緞藍(lán)園丁鳥優(yōu)化算法，通過(guò)自適應(yīng)權(quán)重的方法改進(jìn)SBO算法的局部搜索能力，提高了收斂精度；另外用修改后的高斯變異方法對(duì)緞藍(lán)園丁鳥求偶亭的位置進(jìn)行變異，提高了SBO算法的全局搜索能力，避免了陷入局部最優(yōu)的問(wèn)題。

1 基本緞藍(lán)園丁鳥優(yōu)化算法

緞藍(lán)園丁鳥是一種以水果和昆蟲為食的雀形目鳥，分布在澳大利亞?wèn)|部的熱帶雨林。成熟的雄鳥在其各自的領(lǐng)地上以特殊的木棍結(jié)構(gòu)建造求偶亭，裝飾以鮮花、羽毛、漿果等，并發(fā)出嘹亮的鳴聲來(lái)吸引雌鳥。雄性緞藍(lán)園丁鳥建筑求偶亭的行為源于其天生的本能和對(duì)另類雄鳥的模仿。另外，并不是所有的成年雄鳥都能成功的構(gòu)建和維護(hù)求偶亭，存在求偶亭被破壞的情況[10]。根據(jù)緞藍(lán)園丁鳥的生活原理，SBO算法由以下幾個(gè)步驟組成：

(1)初始化種群。在可行域內(nèi)隨機(jī)生成一個(gè)包含NP個(gè)求偶亭的初始種群，每個(gè)求偶亭的位置定義為D維，當(dāng)前進(jìn)化代數(shù)為t。

(2)計(jì)算每個(gè)求偶亭的吸引力。即該個(gè)體被選中的概率，由等式(1)計(jì)算。fiti代表第i個(gè)求偶亭的適應(yīng)值，可通過(guò)等式(2)計(jì)算；f(xi)是第i個(gè)求偶亭的成本函數(shù)(目標(biāo)函數(shù))，每次迭代需保證成本函數(shù)值不斷減小。

(1)

(2)

(3)位置更新。雄鳥會(huì)根據(jù)自身的歷史經(jīng)驗(yàn)和種群交流對(duì)求偶亭的位置不斷進(jìn)行調(diào)整，其更新公式如等式(3)所示。

(3)

其中，xikt表示第t次迭代第i個(gè)個(gè)體的第k維分量；j是通過(guò)輪盤賭機(jī)制確定的；xelite,k為當(dāng)前整個(gè)種群的最優(yōu)位置。λk是步長(zhǎng)因子，由等式(4)確定。

(4)

其中，α是最大步長(zhǎng)，Pj是目標(biāo)求偶亭被選中的概率，概率值在0到1之間。從等式(4)中明顯看出，步長(zhǎng)與目標(biāo)位置的概率成反比。換句話說(shuō)，當(dāng)目標(biāo)位置的概率為0，步長(zhǎng)最大為ɑ；當(dāng)目標(biāo)位置概率為1時(shí)，步長(zhǎng)最小為ɑ/2。

(4)變異。在許多情況下，強(qiáng)壯的雄鳥會(huì)從較弱的雄鳥那里偷取材料，甚至破壞其求偶亭。因此，在算法的每個(gè)周期結(jié)束時(shí)，有一定的概率發(fā)生隨機(jī)變異。在這個(gè)過(guò)程中，xik服從正態(tài)分布，如等式(5)所示。

(5)

(6)

在等式(6)中，標(biāo)準(zhǔn)差σ的計(jì)算公式如(7)所示。

σ=z*(varmax-varmin)

(7)

其中，varmax和varmin分別是變量xi的上界和下界，z是上下限之間差值的百分比，是可變的。

(5)將舊種群和從變異中獲得的種群進(jìn)行組合。在每個(gè)周期的最后，對(duì)舊種群和從變異中獲得的種群進(jìn)行評(píng)價(jià)。評(píng)估后，這兩個(gè)種群被組合并對(duì)組合種群中的所有個(gè)體的成本函數(shù)值進(jìn)行排序，保留函數(shù)值最小的個(gè)體，其余個(gè)體被刪除。若此時(shí)滿足終止條件，則輸出最佳位置及其對(duì)應(yīng)的最優(yōu)值，否則繼續(xù)進(jìn)行步驟(2)到(4)。SBO算法的偽代碼設(shè)計(jì)如下：

Initialize the first population of bowers randomly

Calculate the cost of bowers

Find the best bower and assume it as elite

While the end criterion is not satisfied

Calculate the probability of bowers using Eqs. (1) and (2)

For every bower

For every element of bower

Select a bower using roulette wheel

Calculate λkusing Eq. (4)

Update the position of bower using Eqs. (3) and (6)

End for

End for

Calculate the cost of all bowers

Update elite if a bower becomes fitter than the elite

End while

Return best bower

2 改進(jìn)的緞藍(lán)園丁鳥優(yōu)化算法

2.1 自適應(yīng)權(quán)重

慣性權(quán)重是粒子群中很重要的一個(gè)參數(shù)，如果慣性權(quán)重較大，算法搜索能力較強(qiáng)，便于進(jìn)行全局搜索；如果慣性權(quán)重較小，則有利于算法在最優(yōu)解周圍精確搜索。本文受文獻(xiàn)[11]的啟發(fā)，運(yùn)用自適應(yīng)權(quán)重策略。當(dāng)所有個(gè)體的適應(yīng)值差異較大時(shí)，將慣性權(quán)重減小，當(dāng)所有個(gè)體的適應(yīng)值趨于一致或趨于局部最優(yōu)時(shí)，將慣性權(quán)重增大。慣性權(quán)重W求解如式(8)所示。

W=Wmax-(Wmax-Wmin)*(t/itmax)＾2

(8)

式中，Wmax、Wmin分別表示W(wǎng)設(shè)置的最大值和最小值，t為當(dāng)前迭代次數(shù)，itmax是最大迭代次數(shù)。運(yùn)用上述方法設(shè)置權(quán)重，在迭代初期，W較大，有利于在全局范圍進(jìn)行搜索；在迭代后期，W較小，便于向最優(yōu)解靠近。

2.2 改進(jìn)原高斯變異形式

高斯分布又叫正態(tài)分布，是數(shù)理統(tǒng)計(jì)中非常重要的概率分布。高斯變異就是在原有的個(gè)體上加一個(gè)服從高斯分布的隨機(jī)擾動(dòng)項(xiàng)來(lái)取代原先的個(gè)體[12]。高斯變異能以較大的概率產(chǎn)生較小的變異值，在小范圍內(nèi)具有良好的搜索能力，不易像柯西變異因其過(guò)大的步長(zhǎng)而跳離最優(yōu)值。在智能優(yōu)化算法中引入變異算子，既可以增強(qiáng)種群的多樣性，又可以避免使算法陷入局部極小?；镜木勊{(lán)園丁鳥優(yōu)化算法采用了公式(6)的高斯變異策略對(duì)個(gè)體進(jìn)行變異，但效果不太理想。經(jīng)過(guò)多次實(shí)驗(yàn)，本文對(duì)原本的高斯變異方法進(jìn)行了修改如公式(9)，不僅能使個(gè)體跳出局部極值點(diǎn)的束縛收斂于全局極值點(diǎn)，同時(shí)也提高了SBO算法的收斂速度和精度。

(9)

其中，N(0,1)為服從均值為0、方差為1的高斯分布。

2.3 混合優(yōu)化的SBO算法

為了能夠較好地避免基本緞藍(lán)園丁鳥算法存在的收斂速度慢，尋優(yōu)精度低等問(wèn)題，本文通過(guò)上述方法將原SBO算法進(jìn)行了改進(jìn)，稱為基于自適應(yīng)權(quán)重的緞藍(lán)園丁鳥優(yōu)化算法(WSBO)。WSBO的基本步驟如下：

(1)初始化最大步長(zhǎng)α、變異概率P、最大迭代次數(shù)Maxit等參數(shù)，隨機(jī)初始化種群；

(2)計(jì)算每個(gè)求偶亭的成本函數(shù)值，確定最佳求偶亭的位置xelite及最優(yōu)值；

(3)采用公式(2)計(jì)算每個(gè)求偶亭的適應(yīng)值，并根據(jù)公式(1)計(jì)算每個(gè)求偶亭被選中的概率；

(4)采用公式(4)計(jì)算步長(zhǎng)；

(5)采用公式(8)更新慣性權(quán)重W；

(6)采用公式(3)更新求偶亭的位置；

(7)如果rand

(8)將舊種群和從變異中獲得的種群進(jìn)行組合，并計(jì)算組合種群中的最優(yōu)解和最優(yōu)值。判斷此時(shí)是否滿足終止條件，若達(dá)到最大迭代次數(shù)，則終止算法，輸出最佳位置及其對(duì)應(yīng)的最優(yōu)值；反之，繼續(xù)迭代轉(zhuǎn)向(3)。

2.4 算法流程圖

改進(jìn)的緞藍(lán)園丁鳥算法從兩個(gè)方面優(yōu)化了雄鳥的求偶行為，一方面通過(guò)自適應(yīng)權(quán)重，使算法有更好的局部勘探能力，另一方面通過(guò)改進(jìn)的高斯變異形式使算法獲得了更好的全局尋優(yōu)能力，使求偶亭獲得更好的全局最優(yōu)解，改進(jìn)后的緞藍(lán)園丁鳥優(yōu)化算法流程如圖1所示。

圖1 改進(jìn)的SBO算法流程圖

3 WSBO性能分析

3.1 函數(shù)測(cè)試及參數(shù)設(shè)置

為了進(jìn)一步驗(yàn)證混合優(yōu)化SBO算法的性能和收斂情況，本文對(duì)8個(gè)基準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)來(lái)檢驗(yàn)算法的改進(jìn)效果，表1中詳細(xì)地列出了各個(gè)測(cè)試函數(shù)的信息。

將本文所提出的基于自適應(yīng)權(quán)重的緞藍(lán)園丁鳥優(yōu)化算法(WSBO)與人工蜂群算法(artificial bee colony algorithm，ABC)和螢火蟲算法(firefly algorithm，F(xiàn)A)以及基本緞藍(lán)園丁鳥算法進(jìn)行對(duì)比實(shí)驗(yàn)。為了盡量保證各算法在實(shí)驗(yàn)中的客觀性，所有算法種群規(guī)模統(tǒng)一設(shè)置為20，迭代次數(shù)為500次，各種算法的其它參數(shù)設(shè)置如下：基本SBO算法和WSBO算法的最大步長(zhǎng)α=0.94，縮放比例因 子z=0.02，變異概率p=0.05；ABC算法的放棄閾值limit=60；FA算法參數(shù)：β0=2，α=0.2，γ=1。

表1 測(cè)試函數(shù)

3.2 實(shí)驗(yàn)結(jié)果分析

為減少實(shí)驗(yàn)中隨機(jī)性的影響，每種算法對(duì)每個(gè)測(cè)試函數(shù)均獨(dú)立運(yùn)行30次，分別記錄其最優(yōu)值、均值和標(biāo)準(zhǔn)差，實(shí)驗(yàn)結(jié)果見表2。對(duì)于每個(gè)測(cè)試函數(shù)，在固定迭代次數(shù)下，均值反映了算法的尋優(yōu)精度，標(biāo)準(zhǔn)方差反映了算法的魯棒性和穩(wěn)定性。

表2列出了4種算法在單峰、多峰函數(shù)上的測(cè)試結(jié)果，根據(jù)數(shù)值結(jié)果可以看出：在進(jìn)行單峰函數(shù)測(cè)試中，相較于SBO、ABC和FA 3種算法，WSBO算法在最優(yōu)值、平均值和標(biāo)準(zhǔn)差上都顯著優(yōu)于這3種算法，說(shuō)明WSBO算法具有較高的搜索精度和較好的穩(wěn)定性。

WSBO算法在處理多峰函數(shù)優(yōu)化中同樣也表現(xiàn)出了優(yōu)越的性能。多峰值函數(shù)存在許多局部極小點(diǎn)，很難優(yōu)化查找到全局最優(yōu)值，但在Rastrigrin函數(shù)f2和Griewank函數(shù)f4的測(cè)試中，WSBO算法都能夠快速找到理論最優(yōu)值，且標(biāo)準(zhǔn)方差均為0；對(duì)于函數(shù)f3和f6，WSBO 算法同樣也獲得了最優(yōu)的精度值，收斂速度和穩(wěn)定度都明顯優(yōu)于其它3種算法。

通過(guò)以上分析表明，在大部分函數(shù)優(yōu)化問(wèn)題中，本文提出的改進(jìn)算法的尋優(yōu)精度以及穩(wěn)定性要優(yōu)于SBO、ABC以及FA 3種算法，并且在多極值、多峰函數(shù)上，WSBO算法仍然尋找到了最優(yōu)的精度值，說(shuō)明WSBO算法具有較好的全局和局部搜索性能，并且在函數(shù)尋優(yōu)過(guò)程中表現(xiàn)出較好的魯棒性，相較于原SBO算法有了很大程度的提高。

表2 4種算法實(shí)驗(yàn)結(jié)果比較

為了能更直觀地顯示W(wǎng)SBO 算法的優(yōu)化效果，圖2給出了4 種算法在8個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)f1～f8上搜索函數(shù)最優(yōu)值過(guò)程中隨迭代次數(shù)增加的收斂曲線。從圖中可以看出，WSBO 算法不管對(duì)于多峰函數(shù)還是單峰函數(shù)，變化近似于直線，說(shuō)明其速度下降快，能夠在較短的時(shí)間內(nèi)找到或者接近理論最優(yōu)值，并不斷向最優(yōu)解靠近，達(dá)到很高的精度。這體現(xiàn)了WSBO算法的尋優(yōu)速度、收斂精度都優(yōu)于其余3種算法。函數(shù)f2和f4的優(yōu)化圖表明，在迭代次數(shù)不到500次時(shí),WSBO 算法已經(jīng)找到理論最優(yōu)值；函數(shù)f1、f3、f5、f6、f7和f8的優(yōu)化圖表明，在迭代過(guò)程中, WSBO算法能夠快速接近理論最優(yōu)值。這充分證明了WSBO 算法的可行性及其尋優(yōu)性能的提升。同時(shí)表明，改進(jìn)的WSBO算法能有效提升全局搜索能力，并在算法后期，有效提升局部開發(fā)能力。

(a) f1函數(shù)收斂曲線對(duì)比

(c) f3函數(shù)收斂曲線對(duì)比

(e) f5函數(shù)收斂曲線對(duì)比

(g) f7函數(shù)收斂曲線對(duì)比

(b) f2函數(shù)收斂曲線對(duì)比

(d) f4函數(shù)收斂曲線對(duì)比

(f) f6函數(shù)收斂曲線對(duì)比

(h) f8函數(shù)收斂曲線對(duì)比

圖24種算法在函數(shù)f1～f8上的收斂曲線

Fig.2Theconvergencecurvesof4algorithmsonfunctionf1～f8

3.3 WSBO時(shí)間復(fù)雜度分析

對(duì)WSBO算法的時(shí)間復(fù)雜度進(jìn)行分析，設(shè)算法的種群規(guī)模為NP；問(wèn)題維度為numbervar，最大迭代次數(shù)為MaxIt,則每個(gè)操作的時(shí)間復(fù)雜度如下：初始化：O(NP*numbervar)；計(jì)算求偶亭個(gè)體被選擇概率：O(NP*numbervar)；自適應(yīng)參數(shù)：O(NP*numbervar)；位置更新：O(NP*numbervar)；適應(yīng)度計(jì)算：O(NP)；整體復(fù)雜度為：O(MaxIt*NP*numbervar)，這與基本SBO的時(shí)間復(fù)雜度相同，沒有增加計(jì)算負(fù)擔(dān)。

4 結(jié)束語(yǔ)

為提高SBO算法的收斂精度，避免算法陷入局部最優(yōu)，本文提出了基于自適應(yīng)權(quán)重的緞藍(lán)園丁鳥優(yōu)化算法—WSBO 算法。該算法通過(guò)使用自適應(yīng)權(quán)重和改變高斯變異形式提升了基本SBO算法的全局搜索能力和局部尋優(yōu)能力，從而在很大程度上提高了算法的收斂精度。本文還進(jìn)行了8個(gè)函數(shù)的仿真測(cè)試，實(shí)驗(yàn)結(jié)果表明，改進(jìn)的SBO 算法是可行有效的，在收斂速度和收斂精度方面都要優(yōu)于原緞藍(lán)園丁鳥算法、人工蜂群算法和螢火蟲算法，其尋優(yōu)性能有了很大的提高。如何將改進(jìn)算法應(yīng)用到更多的領(lǐng)域，是今后的研究工作。