陳志鵬 李環(huán) 魏文紅

(東莞理工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,廣東東莞 523808)

近些年來(lái),啟發(fā)式優(yōu)化算法吸引了眾多研究者的關(guān)注。通過(guò)模擬自然界的現(xiàn)象,生物行為和物理現(xiàn)象,一系列的啟發(fā)式算法不斷被提出。根據(jù)NFL定理,不存在一種算法能夠解決所有問(wèn)題。因此,研究者需要不斷改進(jìn)現(xiàn)有算法或提出更優(yōu)秀的算法來(lái)優(yōu)化不同問(wèn)題。自20世紀(jì)以來(lái),受自然界生物的啟發(fā),研究人員提出了多種優(yōu)化算法,如蝙蝠算法[1]、灰狼算法[2]以及鯨魚(yú)優(yōu)化算法[3]等。這些算法一經(jīng)提出就受到了廣泛的關(guān)注和研究,為不同領(lǐng)域問(wèn)題的求解提供了更多技術(shù)支持。

烏鴉搜索算法(Crow Search Algorithm,CSA)[4]是由Askarzadeh于2016年提出的一種新的優(yōu)化算法,其靈感來(lái)源于烏鴉覓食行為。CSA模擬了烏鴉進(jìn)行覓食和藏匿食物的兩種行為,和其他智能算法比較,CSA具有控制參數(shù)較少、結(jié)構(gòu)簡(jiǎn)單、易于掌握且全局搜索能力強(qiáng)等優(yōu)點(diǎn)。當(dāng)下,烏鴉搜索算法已經(jīng)成功在特征選擇[5]、圖像處理[6]、航空運(yùn)力調(diào)度[7]、無(wú)人機(jī)路徑規(guī)劃[8]等領(lǐng)域取得了應(yīng)用。

與其他的智能優(yōu)化算法相比較,烏鴉搜索算法具有全局搜索能力強(qiáng),搜索過(guò)程中能夠保持較高的種群多樣性優(yōu)點(diǎn)。然而,由于該算法在搜索過(guò)程中缺乏最優(yōu)個(gè)體或精英個(gè)體的引導(dǎo),即使在搜索后期,算法仍然難以收斂,導(dǎo)致種群分散并陷入多個(gè)局部最優(yōu)點(diǎn)。為此,國(guó)內(nèi)外不少研究者提出了各種策略對(duì)烏鴉搜索算法進(jìn)行了相應(yīng)的改進(jìn)。文獻(xiàn)[9]提出了正余弦指引的烏鴉搜索算法,通過(guò)采用嵌入正余弦算子的方式對(duì)烏鴉進(jìn)行位置更新的引導(dǎo),提高了算法的收斂精度。文獻(xiàn)[10]提出了動(dòng)態(tài)自適應(yīng)的感知概率AP和飛行長(zhǎng)度f(wàn)l,以此來(lái)調(diào)控算法在不同時(shí)期的全局搜索和局部尋優(yōu)的能力。文獻(xiàn)[11]在算法中使用交叉算子和變異算子,從而防止CSA在運(yùn)行過(guò)程中陷入局部最優(yōu)。文獻(xiàn)[12]提出向最優(yōu)粒子學(xué)習(xí)的策略,并在不同階段加入擾動(dòng)策略,提升了算法的收斂速度和精度。文獻(xiàn)[13]采用高斯變異進(jìn)行優(yōu)化全局最優(yōu)個(gè)體,并引入Jaya引導(dǎo)策略提升個(gè)體位置更新的精度,從而提升了算法的整體性能。盡管上述文獻(xiàn)提出的改進(jìn)CSA比經(jīng)典CSA在優(yōu)化精度方面有了一定的提升,但在維護(hù)種群多樣性和提升算法的收斂速度和精度等方面,仍需要進(jìn)一步改進(jìn)。針對(duì)該問(wèn)題,本文融入記憶遺忘機(jī)制對(duì)烏鴉搜索算法進(jìn)行了改進(jìn),通過(guò)選取優(yōu)秀記憶對(duì)烏鴉的個(gè)體位置進(jìn)行引導(dǎo),進(jìn)一步提升算法在前期的收斂性,同時(shí)也避免算法在迭代后期種群多樣性低的問(wèn)題,并且在算法中嵌入黃金正弦算子,以減少位置更新的盲目性。以上改進(jìn)加快了算法的收斂速度和收斂精度,并在仿真數(shù)值實(shí)驗(yàn)中驗(yàn)證。

1 烏鴉搜索算法

1.1 基本理論

烏鴉搜索算法模擬的是烏鴉,藏匿食物和竊取其他烏鴉食物的兩種行為。一方面它們會(huì)在覓食之后,將食物藏匿于某個(gè)地點(diǎn);另一方面,烏鴉也會(huì)觀察其他烏鴉的食物儲(chǔ)藏點(diǎn)以便竊取其他烏鴉更好的食物。

在上述情況中,fl表示烏鴉的飛行距離,r1則是一個(gè)服從 [0,1] 均勻分布的隨機(jī)數(shù)。

同時(shí)還存在另一種情況,即烏鴉j意識(shí)到烏鴉i在追蹤自己以竊取食物。為了保護(hù)食物,烏鴉j選擇隨機(jī)飛往搜索空間中的任意一個(gè)位置,以欺騙烏鴉i。綜上兩種情況,烏鴉i的位置更新公式如式(1)。

(1)

其中,r2表示為服從[0,1]均勻分布的一個(gè)隨機(jī)數(shù);AP表示烏鴉j發(fā)現(xiàn)烏鴉i追隨的感知概率。

1.2 烏鴉搜索算法基本流程

CSA算法具體步驟如下:

步驟1:初始化變量種群總數(shù)n,感知概率AP,飛行距離fl和迭代次數(shù)T;

步驟2:初始化每只烏鴉在d維搜索空間的位置和記憶。由于初始時(shí)烏鴉并沒(méi)有先前記憶,所以烏鴉的初始位置即為烏鴉的初始記憶;

步驟3:設(shè)置目標(biāo)函數(shù),并且計(jì)算每只烏鴉所在位置的適應(yīng)度值;

步驟4:根據(jù)式(1)計(jì)算,生成烏鴉在空間中的新位置;

步驟5:檢測(cè)新位置是否超出搜索空間。如果還在空間內(nèi),則將新位置更新,否則停留在原來(lái)的位置。

步驟6:計(jì)算新的位置的適應(yīng)度;

步驟7:對(duì)于當(dāng)前的烏鴉,比較其記憶位置和新位置的適應(yīng)度值,若新位置的適應(yīng)度值更優(yōu),則將該新位置作為該烏鴉的新的記憶位置;

步驟8:不斷重復(fù)步驟4～步驟7,直到達(dá)到最大迭代次數(shù)。

2 改進(jìn)烏鴉搜索算法

為提升經(jīng)典烏鴉搜索算法的搜索精度和收斂速度,本文提出了融合多策略改進(jìn)的自適應(yīng)烏鴉搜索算法(ACSA)。該算法引入記憶遺忘機(jī)制,選取優(yōu)秀記憶對(duì)烏鴉進(jìn)行引導(dǎo)。同時(shí),對(duì)原有的位置更新公式進(jìn)行改進(jìn),并融入黃金正弦算子,克服算法位置更新的盲目性。最后,使用自適應(yīng)感知概率和飛行長(zhǎng)度對(duì)原有算法進(jìn)行改進(jìn),從而對(duì)算法的性能有了較大的提升。下面是對(duì)改進(jìn)算法的詳細(xì)表述。

2.1 引入記憶遺忘機(jī)制

遺忘是自然界中普遍存在的一種生物現(xiàn)象。學(xué)習(xí)和遺忘被認(rèn)為是相互互補(bǔ)的過(guò)程,因此也有部分學(xué)者將遺忘現(xiàn)象運(yùn)用到各種算法中。例如,文獻(xiàn)[14]將多目標(biāo)策略和遺忘機(jī)制相結(jié)合,以此改進(jìn)了粒子群算法的更新公式,充分提升了粒子群算法的性能。文獻(xiàn)[15]利用遺忘機(jī)制和平均信息,改進(jìn)了算法群體的搜索能力。這讓粒子群算法能夠更好地尋找到全局最優(yōu)。通過(guò)引入遺忘機(jī)制,這些算法的性能都得到了一定的提升。因此,本文將遺忘機(jī)制引入烏鴉搜索算法。

烏鴉搜索算法的個(gè)體位置更新是通過(guò)向個(gè)體記憶進(jìn)行學(xué)習(xí)更新,因此記憶的優(yōu)異程度對(duì)于產(chǎn)生解的好壞有著重要的影響。但在算法初期階段,烏鴉的記憶位置分布比較分散,如果進(jìn)行隨機(jī)選擇個(gè)體記憶進(jìn)行位置引導(dǎo),這樣的策略并不利于算法的收斂。為了解決這個(gè)問(wèn)題,本文提出遺忘適應(yīng)度值較差記憶,使用優(yōu)質(zhì)記憶的策略進(jìn)行個(gè)體位置的更新。同時(shí),提出記憶閾值的概念以此用于衡量記憶的優(yōu)劣。其中,記憶閾值Fv(Forgetting value)用于衡量記憶的優(yōu)劣,記憶閾值的表達(dá)如公式(2)所示:

Fv=fit(Mt)min+(fit(Mt)max-fit(Mt)min)×

e-(tmax/t),

(2)

式中:fit(Mt)min為第t代種群記憶中的適應(yīng)度值最優(yōu)個(gè)體的適應(yīng)度值;fit(Mt)max為第t代種群記憶的適應(yīng)度最差個(gè)體的適應(yīng)度值。當(dāng)烏鴉的記憶適應(yīng)度值優(yōu)于記憶閾值時(shí),則被判定為優(yōu)秀記憶,可以有機(jī)會(huì)被選為下一次烏鴉位置更新的引導(dǎo)記憶;否則,被選擇遺忘。從式(2)中可以看出,在算法初期,種群的分布較為發(fā)散,這時(shí)讓Fv趨近于種群記憶的最優(yōu)值,可以選出更為優(yōu)質(zhì)的個(gè)體記憶對(duì)烏鴉進(jìn)行搜索引導(dǎo),這避免了算法初期的盲目搜索。隨著迭代次數(shù)的增加,記憶閾值逐漸增大,這時(shí)可被選擇的引導(dǎo)記憶越來(lái)越多,也避免了種群一直由最優(yōu)個(gè)體引導(dǎo),從而能夠較好地保持種群的多樣性。

2.2 融合黃金正弦引導(dǎo)和改進(jìn)原有搜索方式

鑒于經(jīng)典的CSA的個(gè)體更新方式單一,這不僅不利于算法的全局搜索,同時(shí)也不利于局部的尋優(yōu),就導(dǎo)致CSA產(chǎn)生收斂精度低,收斂速度較慢的問(wèn)題。本文借鑒粒子群算法的速度更新方式,將全局最優(yōu)位置引入CSA,幫助算法能夠有著更快的收斂速度。具體改進(jìn)如式(3)。

(3)

c1=1.5×e-(tmax/t),

(4)

c2=1.5×e-(tmax/t),

(5)

其中,c1和c2為權(quán)重系數(shù),根據(jù)式(4)、式(5)。當(dāng)?shù)螖?shù)t不斷增加時(shí),c1不斷增加,c2不斷減小。目的是讓迭代初期,全局最優(yōu)個(gè)體的引導(dǎo)占據(jù)更大的比重,提高算法的收斂速度。在迭代后期時(shí),隨機(jī)選取的個(gè)體占據(jù)更大比重,以提高算法跳出局部最優(yōu)的可能。

同時(shí)根據(jù)式(1)可知,當(dāng)r2小于AP時(shí),烏鴉的位置更新是搜索空間中隨機(jī)產(chǎn)生一個(gè)位置。雖然有助于提高算法跳出局部最優(yōu)的概率,但也存在極大的盲目性,導(dǎo)致算法的收斂速度和尋優(yōu)精度并不理想。為克服該缺點(diǎn),本文采用引入黃金正弦算子來(lái)解決此問(wèn)題。

黃金正弦算子是根據(jù)黃金正弦算法[16]提出的,是Erkan Tanyildizi在2017年根據(jù)數(shù)學(xué)中的正弦函數(shù)提出的一種新型智能算法,具有收斂速度快、尋優(yōu)能力強(qiáng)的優(yōu)點(diǎn)。當(dāng)r2小于AP時(shí),使用黃金正弦算子對(duì)烏鴉進(jìn)行引導(dǎo),幫助算法獲得更快的尋優(yōu)能力和收斂精度。融合黃金正弦算子和改進(jìn)原有的位置更新方式如式(6)。

(6)

2.3 自適應(yīng)飛行長(zhǎng)度和感知概率

為平衡全局搜索和局部開(kāi)發(fā)的程度,本文使用動(dòng)態(tài)自適應(yīng)參數(shù)。其中,引入動(dòng)態(tài)感知概率AP,隨著迭代次數(shù)的增加,AP逐漸增大。在算法的后期,將更有可能使用黃金正弦算子進(jìn)行局部尋優(yōu),以找到最優(yōu)解。此外,為解決固定飛行長(zhǎng)度帶來(lái)的問(wèn)題,本文采用動(dòng)態(tài)飛行長(zhǎng)度f(wàn)l,即在算法初期,飛行步長(zhǎng)較大,有利于進(jìn)行全局搜索,而在迭代的后期,飛行步長(zhǎng)逐漸縮小,使算法可以更好地進(jìn)行局部尋優(yōu)。通過(guò)非線性動(dòng)態(tài)飛行步長(zhǎng)的控制,將能夠有效地平衡算法的全局搜索和局部搜索能力,提高算法的收斂速率和尋優(yōu)精度。其中,飛行步長(zhǎng)的變化如式(7),感知概率的變化如式(8)。

(7)

AP=ρ×1.5(t/tmax).

(8)

2.4 ACSA的算法基本流程

綜合上述改進(jìn)策略,ACSA的算法基本流程如下。

步驟1:初始化烏鴉種群位置,烏鴉記憶,初始感知概率ρ,初始飛行步長(zhǎng)flinit和最大迭代次數(shù)tmax;

步驟2:計(jì)算每只烏鴉個(gè)體的適應(yīng)度值并找出當(dāng)前最優(yōu)位置;

步驟3:計(jì)算當(dāng)前烏鴉的記憶閾值,并從中找出較為優(yōu)異的記憶位置;

步驟4:判斷產(chǎn)生的隨機(jī)數(shù)是否大于當(dāng)前的感知概率,若是則使用式(3)進(jìn)行烏鴉位置更新。否則,采用式(6)進(jìn)行更新烏鴉位置;

步驟5:判斷烏鴉新位置是否可行,若可行則更新烏鴉的位置和記憶,否則保持原樣;

步驟6:進(jìn)行最大迭代次數(shù)的判斷,若達(dá)到,則輸出最優(yōu)位置和其適應(yīng)度值;否則,重復(fù)步驟2～步驟6,直到滿足終止條件。

3 仿真實(shí)驗(yàn)和結(jié)果分析

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

本文選取鯨魚(yú)優(yōu)化算法(WOA)[3]、經(jīng)典的烏鴉搜索算法(CSA)[4]、正余弦指引的烏鴉搜索算法(SCACSA)[9]和多段擾動(dòng)的共享型烏鴉算法(MISCSA)[12]進(jìn)行對(duì)比實(shí)驗(yàn),所涉及算法的種群規(guī)模均為30,迭代次數(shù)為1 000,其余共有參數(shù)保持一致,各算法的參數(shù)設(shè)定如表1。

表1 算法參數(shù)設(shè)置

3.2 測(cè)試函數(shù)

將ACSA在13個(gè)基準(zhǔn)測(cè)試函數(shù)上進(jìn)行尋優(yōu)測(cè)試,同時(shí)和上述提及的算法進(jìn)行分析比較,其中13個(gè)基準(zhǔn)測(cè)試函數(shù)的相關(guān)基本信息見(jiàn)表2。

表2 基準(zhǔn)測(cè)試函數(shù)信息

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

為驗(yàn)證本文提出的ACSA的性能。使用13個(gè)測(cè)試函數(shù)對(duì)其進(jìn)行實(shí)驗(yàn),同時(shí)為避免偶然性形成的誤差,算法需要在每個(gè)函數(shù)上進(jìn)行30次的尋優(yōu)。表3列出ACSA、鯨魚(yú)優(yōu)化算法(WOA)、CSA、SCACSA、MISCSA在多個(gè)測(cè)試函數(shù)上運(yùn)行30次后產(chǎn)生的實(shí)驗(yàn)結(jié)果。

表3 測(cè)試函數(shù)實(shí)驗(yàn)結(jié)果

從表3和圖1可知,對(duì)于函數(shù)F1(x)、F3(x),ACSA相比其他的5種算法能夠在更少的迭代次數(shù)的情況下找到理論最優(yōu)值,而其他4種算法卻無(wú)法達(dá)到全局最優(yōu)。對(duì)于F2(x)和F4(x),由圖2、圖3以及表3中數(shù)據(jù)可得,雖然ACSA也無(wú)法尋得理論最優(yōu)值,但收斂精度卻遠(yuǎn)遠(yuǎn)高于其他算法,對(duì)于函數(shù)F5(x),ACSA的平均值不如SCACSA和MISCSA,但是從最優(yōu)值的情況來(lái)看,ACSA是優(yōu)于所有算法的。綜上,ACSA對(duì)于高維單峰函數(shù)擁有較好的尋優(yōu)能力。

圖1 F1(x)的收斂曲線

圖2 F2(x)的收斂曲線

圖3 F4(x)的收斂曲線

由表3可知,ACSA在求解高維多峰函數(shù)F6(x)、F7(x)、F8(x)時(shí),能夠表現(xiàn)出較為優(yōu)異的尋優(yōu)精度。雖然別的算法在某些測(cè)試函數(shù)中也可得到最優(yōu)值,但通過(guò)圖4可知,ACSA的收斂速度相對(duì)更為占優(yōu)。對(duì)于F9(x),由表3和圖5所知,只有ACSA在規(guī)定的迭代次數(shù)內(nèi)尋找到了最高精度的解,這也表明了ACSA具有不錯(cuò)的求解高維多峰函數(shù)的能力。對(duì)于F10(x),ACSA的結(jié)果劣于大部分比較算法,但與最優(yōu)值的求解數(shù)據(jù)差距不大,求解精度均在一個(gè)數(shù)量級(jí)內(nèi)。對(duì)F11(x)、F12(x)和F13(x)進(jìn)行比較,ACSA在這3個(gè)函數(shù)中均求得了最優(yōu)值,同時(shí)標(biāo)準(zhǔn)差在這3個(gè)函數(shù)的求解中,僅次于CSA,說(shuō)明ACSA在求解精度較好的同時(shí),也有著還不錯(cuò)的穩(wěn)定性。同時(shí)根據(jù)圖6,ACSA的收斂速度也更優(yōu)于其他算法。

圖4 F7(x)的收斂曲線

圖5 F9(x)的收斂曲線

圖6 F13(x)的收斂曲線

3.4 統(tǒng)計(jì)校驗(yàn)

參考文獻(xiàn)[17]指出,僅僅通過(guò)對(duì)算法獨(dú)立執(zhí)行30次后得到的最優(yōu)值、平均值和標(biāo)準(zhǔn)差進(jìn)行評(píng)價(jià),并不夠嚴(yán)謹(jǐn)。因此,本研究將采用統(tǒng)計(jì)檢驗(yàn)方法對(duì)算法進(jìn)行更為科學(xué)的性能評(píng)估。

為了比較文獻(xiàn)中所提出的6種算法,將使用Wilcoxon秩和檢驗(yàn)和Friedman檢驗(yàn)來(lái)進(jìn)行分析。

3.4.1 Wilcoxon秩和檢驗(yàn)

通過(guò)上一節(jié)中ACSA在每個(gè)測(cè)試函數(shù)中的收斂曲線和表3可以得出。

ACSA相比于其他算法有著更好的收斂速度和收斂精度。同時(shí),為提高實(shí)驗(yàn)的嚴(yán)謹(jǐn)性,避免少數(shù)的偏離數(shù)據(jù)影響算法的性能評(píng)價(jià),本部分將采用Wilcoxon秩和檢驗(yàn)進(jìn)行算法評(píng)估。根據(jù)參考文獻(xiàn)[18]中描述的p值的統(tǒng)計(jì)理論,可以得出結(jié)論:當(dāng)p值小于0.05時(shí),表示兩種對(duì)比算法之間存在顯著差異;當(dāng)p值大于或等于0.05時(shí),表示兩種對(duì)比算法存在一定程度的相似性。從表4可以看出,ACSA在F5(x)函數(shù)中的優(yōu)化結(jié)果和SCACSA以及MISCSA存在一定的相似性,以及在F10(x)中,ACSA和WOA的優(yōu)化結(jié)果存在一定相似性,而在其他函數(shù)的比較中都具有較大的不同,這說(shuō)明了ACSA有著優(yōu)異的性能。

表4 Wilcoxon秩和檢驗(yàn)的p

3.4.2 Friedman檢驗(yàn)

對(duì)ACSA算法和其他5種比較算法在13個(gè)基準(zhǔn)測(cè)試函數(shù)上獲取的平均值,進(jìn)行Friedman檢驗(yàn)。表5列示了這6種算法在13個(gè)測(cè)試函數(shù)上進(jìn)行Friedman檢驗(yàn)的結(jié)果。

表5 Friedman檢驗(yàn)秩均值表

通過(guò)表5可知,ACSA的秩均值是所有算法中最小的,僅為2.03,在比較的算法中位居第一,相比未改進(jìn)過(guò)的CSA的秩均值大幅減小。這表明了本文中對(duì)原有算法的改進(jìn)具有一定的有效性。

4 ACSA求解三桿桁架設(shè)計(jì)問(wèn)題

從上一節(jié)可知,ACSA對(duì)比其他的算法在函數(shù)尋優(yōu)方面有著更好的性能。為進(jìn)一步探究ACSA的優(yōu)化性能。本節(jié)將使用ACSA對(duì)三桿桁架設(shè)計(jì)這一實(shí)際問(wèn)題求解,并且和其他多種算法的求解結(jié)果進(jìn)行對(duì)比。以表明ACSA可運(yùn)用于實(shí)際工程問(wèn)題的求解。三桿桁架設(shè)計(jì)的目標(biāo)是通過(guò)不斷調(diào)整x1和x2,并在一定的約束條件下,使三桿桁架的體積達(dá)到最小。相關(guān)設(shè)計(jì)示意圖如圖7,該問(wèn)題的數(shù)學(xué)模型表示如式(9)。

圖7 三桿桁架示意圖

l=100 cm,p=2 kN/cm2,σ=2 kN/cm2.

(9)

本實(shí)驗(yàn)的求解迭代次數(shù)設(shè)置為500,對(duì)比算法各個(gè)獨(dú)立運(yùn)行30次,其余參數(shù)設(shè)置和相關(guān)參考文獻(xiàn)保持一致,ACSA求解數(shù)據(jù)和其他CSA[4]、MVO[19]、GOA[20]、MFO[21]、MFCSA[22]的對(duì)比結(jié)果如下表6所示,實(shí)驗(yàn)結(jié)果對(duì)比得出ACSA能夠在相比較的其余5種算法中取得最優(yōu)的求解結(jié)果。

表6 不同算法對(duì)于三桿桁架問(wèn)題的測(cè)試結(jié)果

5 結(jié)語(yǔ)

本研究提出了一種融合多策略改進(jìn)的自適應(yīng)烏鴉搜索算法(ACSA),該算法結(jié)合了記憶遺忘機(jī)制和黃金正弦算子來(lái)改進(jìn)烏鴉搜索算法。ACSA通過(guò)使用記憶閾值來(lái)挑選出優(yōu)秀的記憶,并使用這些優(yōu)秀記憶來(lái)引導(dǎo)烏鴉個(gè)體的位置更新,該方法有效地提高了算法前期的收斂速度,同時(shí)能夠防止算法后期種群多樣性的降低。此外,ACSA還嵌入了黃金正弦算子來(lái)避免個(gè)體位置更新的盲目性,從而提高了算法的整體性能。

通過(guò)對(duì)13個(gè)測(cè)試函數(shù)和一個(gè)工程約束設(shè)計(jì)問(wèn)題進(jìn)行實(shí)驗(yàn)可以得出結(jié)論,ACSA在函數(shù)優(yōu)化方面具有更出色的尋優(yōu)性能,并且能夠有效地解決三桿桁架的設(shè)計(jì)問(wèn)題。未來(lái),研究計(jì)劃將重點(diǎn)關(guān)注如何將改進(jìn)后的算法應(yīng)用于實(shí)際應(yīng)用。