引入正弦余弦算子和新自花授粉的花授粉算法

張 超, 楊 憶

(1.宿州職業(yè)技術學院 計算機信息系, 安徽 宿州 234000;2.淮北師范大學 計算機科學與技術學院, 安徽 淮北 235000)

0 引 言

群智能優(yōu)化算法作為人工智能學科一個重要分支,近年來該領域的研究比較活躍,新型的群智能優(yōu)化算法不斷涌現(xiàn),如鯨魚優(yōu)化算法[1]、斑點鬣狗優(yōu)化算法[2]、樽海鞘算法[3]、哈里斯鷹優(yōu)化算法[4]、人工生態(tài)系統(tǒng)優(yōu)化算法[5]、麻雀搜索算法[6]、政治優(yōu)化算法[7]等。這些算法已幫助人們解決了現(xiàn)實世界的很多實際問題,如圖像特征選擇、芯片設計優(yōu)化等[8]。基于“無免費午餐”定理,任何算法都不能適應于解決所有實際問題;在大數(shù)據(jù)時代,優(yōu)化問題的決策變量與目標函數(shù)越來越多和復雜:這為新算法的提出和對現(xiàn)有算法的改進提供了更多研究空間。

花授粉算法(flower pollination algorithm,FPA)是YANG通過模擬自然界顯花植物授粉過程,仿生設計的元啟發(fā)式算法[9]。FPA只有一個全局搜索和局部開發(fā)轉換的概率參數(shù),結構簡單,在處理低維優(yōu)化問題時有較好的收斂精度,已在數(shù)據(jù)聚類[10]、機器人系統(tǒng)優(yōu)化[11]等領域成功應用,但在處理高維優(yōu)化問題時,亦存在收斂精度較低,易陷入局部極值等元啟發(fā)式算法共有的缺陷。為了提高FPA的尋優(yōu)性能,國內(nèi)外學者使用不同的策略對其進行了改進:肖輝輝等將引力搜索算法融入FPA中,使用萬有引力和FPA自身的Lévy飛行共同引導花粉個體位置更新,提升了FPA的尋優(yōu)能力[12];李煜等使用反向學習策略初始花粉種群,采用逐維隨機擾動策略更新自花授粉階段的花粉個體位置,提高了FPA在求解大規(guī)模優(yōu)化問題時的尋優(yōu)性能[13];張慧穎等采用有利于全局廣泛搜索的自適應移動因子提高FPA的收斂速度,并將其應用到室內(nèi)可見光定位系統(tǒng)中[14];DRAA通過數(shù)值實驗對FPA的性能做了詳細的定量和定性分析[15];NABIL將FPA與克隆選擇算法進行雜交,提高了算法的收斂精度[16];ABDEL-BASET等提出了一種復數(shù)編碼的花授粉算法,將種群更新分為實部和虛部2個部分,以擴大個體基因中包含的信息量,進而增強花粉群體的多樣性[17];NGUYEN等使用并行技術將花粉種群劃分為若干亞種群獨立迭代更新,以增強空間探索的多樣性,使用緊湊技術減少算法在無線傳感器網(wǎng)絡節(jié)點優(yōu)化過程中的存儲變量和運行時間[18];OZSOYDAN等修改了非生物局部授粉的方式,并在算法的全局和局部授粉中采用了步長函數(shù)和隨機因子,生成了基于物種的FPA[19]。

上述算法通過參數(shù)優(yōu)化、與其他元啟法式算法混合、采用不同編碼方式、改進全局或局部授粉方式等策略對FPA進行了改進,并在實際應用中解決一些特定問題,取得了一定優(yōu)化效果。不過,通過研究分析文獻發(fā)現(xiàn):①一些變體在不同程度地提升算法性能的同時,由于改進策略過于復雜,使得算法的計算復雜度大幅提升,導致算法的時間復雜度增加;②一些變體一定程度上提升了算法處理高維優(yōu)化問題的尋優(yōu)能力,但在一些經(jīng)典的低維函數(shù)上的測試實驗顯示,其收斂精度甚至不如基本FPA算法,即改進算法失去了基本FPA處理低維優(yōu)化問題的良好性能。

為了解決上述問題,本文提出一種引入正弦余弦算子和新自花授粉方式的改進算法(sine cosine flower pollination algorithm,SCFPA)。SCFPA做了2方面的改進工作:①使用振幅自適應指數(shù)非線性調(diào)整的正弦余弦算子,逐維擾動花粉個體以保持花粉個體的多樣性;②基于優(yōu)勝劣汰的自然法則思想,算法的自花授粉只在適應度排名在25%～75%之間的骨干花粉個體與前10%的精英個體之間隨機展開,淘汰排名靠后的25%的劣質個體,防止“劣幣驅逐良幣”,以提高算法的尋優(yōu)性能。

在9個基準測試函數(shù)上做仿真實驗,驗證了SCFPA的尋優(yōu)性能和魯棒性;并將其應用到懸臂梁設計、壓力容器設計2個經(jīng)典的機械工程實例上,驗證了算法在解決實際工程問題時的有效性和實用性。

1 花授粉算法(FPA)

FPA是在4個理想規(guī)則[9]假設下,使用式(1)和式(3)分別模擬顯花植物異花授粉和自花授粉過程,驅使花粉種群迭代更新,從而達到尋優(yōu)的目的。FPA通過轉換概率參數(shù)p控制算法進入異花授粉過程和自花授粉過程,即算法進行全局搜索和局部開發(fā)的轉換。

(1)

(2)

式中:λ=1.5;Γ(λ)為標準伽瑪函數(shù)。

(3)

2 SCFPA改進策略

本小節(jié)介紹在異花授粉階段和自花授粉階段本文的改進策略以及SCFPA。

2.1 正弦余弦算子逐維擾動的異花授粉策略

正弦余弦算法[20](sine cosine algorithm,SCA)是MIRJALILI于2016年,根據(jù)正弦余弦函數(shù)的周期性,提出的基于種群的群體智能優(yōu)化算法。本文利用SCA中的正弦余弦算子對異花授粉階段的花粉個體位置向量實施逐維擾動,并繼承基本FPA以Lévy飛行向全局最優(yōu)解方向迭代更新的策略不變。SCFPA通過定義正弦余弦算子轉換概率參數(shù)Psc∈[0,1],將算法異花授粉階段花粉位置的更新按2種方式隨機進行:如果Psc

(4)

式中:A為正弦函數(shù)和余弦函數(shù)的振幅;a∈[0,2π]為服從均勻分布的隨機數(shù);L為Lévy飛行分布;g*為到當前為止最優(yōu)花粉個體的位置;r∈[0,1]為服從均勻分布的隨機數(shù),控制算法以相等概率執(zhí)行正弦算子或余弦算子。

算法迭代初期種群個體需在盡可能大的空間范圍搜索,以勘探最有希望的區(qū)域;而在迭代中后期,種群個體應在最有希望的區(qū)域進行精細化搜索,以期收斂到最佳全局最優(yōu)解。SCFPA中,這一過程通過正弦余弦函數(shù)設計自適應指數(shù)非線性調(diào)整的振幅模擬實現(xiàn),使用式(5)計算。

A=β·exp(-100·(t/T)m)

(5)

式中:β為一個常量;t為當前迭代次數(shù),T為最大迭代次數(shù);m為形狀調(diào)整參數(shù),主要控制指數(shù)遞減函數(shù)的下降速率?？筛鶕?jù)實際優(yōu)化問題設置合適的下降速率,m≥1,一般不超過3,如圖1所示。隨著算法的運行,振幅A可以以不同的下降速率自適應指數(shù)遞減。

圖1 不同下降速率的振幅A

式(4)對花粉個體位置向量實施正弦余弦算子逐維擾動變異,并繼承基本FPA以Lévy飛行向全局最優(yōu)解方向迭代更新的機制。在保持提升原算法尋優(yōu)性能的同時,因正弦余弦算子的逐維擾動操作,有效增加了花粉種群的多樣性,避免了算法因失去多樣性而停滯收斂,進而達到提高算法性能的目的。

2.2 基于優(yōu)勝劣汰法則的自花授粉策略

基本FPA中,自花授粉在任意2個花粉個體之間進行。因其選擇的隨意性,容易造成當前個體朝著不如自己適應度好的劣質花粉個體進化,進而導致算法收斂速度變慢,收斂精度下降,影響算法尋優(yōu)性能。鑒于此,本文借鑒自然界優(yōu)勝劣汰的生存法則思想,SCFPA的自花授粉只在適應度排名在25%～75%之間的骨干花粉個體與前10%的精英花粉個體之間隨機展開,控制當前花粉個體不朝向適應度排名靠后的25%的劣質個體進化。該策略可以充分保持種群進化的優(yōu)越性,充分發(fā)揮精英個體和骨干個體對種群的引領作用;同時,多精英個體的設置,又可避免算法陷入局部極值,提高收斂精度。此種策略與自然界中的真實授粉相符合,例如蝴蝶、蜜蜂等傳粉者總是偏好造訪花形大、顏色鮮艷的花朵,這樣的花朵也優(yōu)先得到授粉,繁育下一代。新的自花授粉策略計算方法為

(6)

2.3 SCFPA的執(zhí)行流程

SCFPA的主要執(zhí)行流程偽代碼如下:

開始

算法參數(shù)設置:設置自花授粉和異花授粉轉換概率參數(shù)P、正弦余弦算子轉換概率參數(shù)Psc、常量β、形狀調(diào)整參數(shù)m

在解空間隨機初始化花粉種群

whilet

ifP

ifPsc

按式(1)更新異花授粉花粉個體位置

else

按式(4)更新異花授粉花粉個體位置

end if

else

按式(6)更新自花授粉花粉個體位置

end if

更新全局最優(yōu)花粉適應度及位置

end while

2.4 SCFPA的時間復雜度分析

假設花粉種群規(guī)模為N,最大迭代次數(shù)為T,問題維度為D,轉換概率參數(shù)為P。FPA重復執(zhí)行的基本語句為異花授粉和自花授粉過程中花粉個體的位置更新語句。因此,根據(jù)時間復雜度運算規(guī)則,FPA異花授粉的時間復雜度為(N×D×T×P),自花授粉的時間復雜度為(N×D×T×(1-P)),二者合并后的FPA時間復雜度為(N×D×T)。

SCFPA自花授粉過程的算法結構與FPA一樣,因此,自花授粉過程的時間復雜度為(N×D×T×(1-P))。SCFPA異花授粉階段,由參數(shù)Psc控制分為2個過程隨機進行,過程1的時間復雜度為(N×D×T×P×Psc),過程2的時間復雜度為(N×D×T×P(1-Psc)),二者合并后的SCFPA異花授粉的時間復雜度為(N×D×T×P),將SCFPA自花授粉和異花授粉的時間復雜度合并計算后(N×D×T)。因此,SCFPA與FPA屬于同一數(shù)量級。

3 仿真實驗與結果分析

3.1 測試函數(shù)和對比算法

在9個基準測試函數(shù)上做仿真實驗,以客觀評價SCFPA的尋優(yōu)性能。9個測試函數(shù)的名稱、變量區(qū)間、目標精度等信息見表1。

表1 基準測試函數(shù)

9個測試函數(shù)的具體表達式可參見文獻[3-5]。其中,f1～f4為高維單峰函數(shù),f5～f7為高維多峰函數(shù),f8和f9為固定維度多峰函數(shù)。

對比算法包括基本FPA[9],花授粉的改進算法MFPA[16]和EOBLFPA[21],其他智能算法及其改進算法WOA[1]、SSA[6]、SCA[20]和灰狼優(yōu)化算法的改進算法I-GWO[8]。通過對以上多元對比算法的選擇,確保了充分客觀地評價SCFPA的性能。

算法參數(shù)設置:SCFPA和FPA的自花授粉和異花授粉的轉換概率參數(shù)設置一樣,都為P=0.4。SCFPA的其他參數(shù)經(jīng)數(shù)值實驗得出:當β=6,在f1～f7高維函數(shù)上m=1,Psc=0.5;在f8～f9固定維度函數(shù)上m=2,Psc=0.1,此時算法的尋優(yōu)效果較好。其他對比算法均使用對應參考文獻推薦的參數(shù)設置。所有算法的種群規(guī)模為30,最大迭代次數(shù)為1 000。

3.2 與標準FPA的性能比較

與FPA進行比較時,在f1～f7高維函數(shù)上做維度分別為30、1 000和5 000的仿真實驗,以側重檢驗SCFPA在解決大規(guī)模優(yōu)化問題(問題的決策變量,即維度大于等于1 000維以上[13])時的尋優(yōu)性能。表2為2種算法分別獨立運行30次的實驗結果,其中“—”表示數(shù)據(jù)無法獲得。下述各表格中,比較結果的較優(yōu)值或最優(yōu)值用黑體編排。

表2 SCFPA與基本FPA比較的實驗結果

從表2可見,在高維單峰和多峰函數(shù)上,SCFPA在f1～f3、f5、f7等5個函數(shù)3種維度實驗中每次都收斂到函數(shù)的理論最優(yōu)值;在f4和f6函數(shù)上,SCFPA的各指標均明顯優(yōu)于FPA。從尋優(yōu)精度與維度增長之間的關系看,隨著維度大幅增長到1 000、5 000時,SCFPA的尋優(yōu)精度基本不受影響,而FPA的尋優(yōu)精度呈指數(shù)級增長,算法陷入了“維數(shù)災難”。特別在f2上,維度增長到1 000維以后,FPA已不能進行尋優(yōu),而SCFPA仍能收斂到函數(shù)的理論最優(yōu)值?？梢?SCFPA較FPA在高維優(yōu)化問題上的尋優(yōu)性能得到大幅提升。

在f8和f92個固定維度多峰函數(shù)上,SCFPA在預設精度下的尋優(yōu)成功率都為100%。從最小值、最大值、平均值和標準差指標可知,SCFPA每次都能收斂到函數(shù)的理論最優(yōu)值,算法的魯棒性較好。FPA雖能夠收斂到函數(shù)的理論最優(yōu)值,但從最大值、標準差和成功率指標看,FPA易陷入局部極值,算法不夠穩(wěn)定。

綜上,SCFPA在高維上的尋優(yōu)性能較FPA大幅提升,結論可拓展到有效求解問題維度達到1 000維以上的大規(guī)模優(yōu)化問題;在低維上進一步增強了FPA的尋優(yōu)性能。因此,本文提出的在異花授粉階段引入正弦余弦算子策略,在自花授粉階段引入基于優(yōu)勝劣汰法則的新授粉方式策略,顯著地提升了FPA的尋優(yōu)性能。

3.3 與FPA改進算法和其他智能算法性能比較

表3是SCFPA與FPA改進算法,及近年出現(xiàn)的其他智能算法和改進算法的對比實驗的結果,其中高維函數(shù)的維度為30。使用平均值和標準差作為算法性能評價指標;使用Wilcoxon秩和檢驗,做p=5%的顯著性水平檢驗,驗證實驗數(shù)據(jù)的真實性,并決策SCFPA與對比算法的性能優(yōu)劣:優(yōu)于、劣于和相當于3種等級使用“+”“-”和“=”符號標記,決策結果在表3中最后一行列出。

從表3中可見:SCFPA在9個函數(shù)上均優(yōu)于SCA、I-GWO和MFPA;SCFPA在8個函數(shù)上優(yōu)于WOA,在f5函數(shù)上性能相當;SCFPA在6個函數(shù)上優(yōu)于SSA,在f5～f7函數(shù)上性能相當;SCFPA在4個函數(shù)上優(yōu)于EOBLFPA,在5個函數(shù)上性能相當,但EOBLFPA在固定維度多峰函數(shù)上易陷入局部極值,收斂精度較低。與多元的對比算法的比較結果表明,SCFPA具有顯著尋優(yōu)性能,在智能優(yōu)化算法中具有競爭性。

表3 SCFPA與其他FPA改進算法和其他智能算法比較的實驗結果

3.4 收斂曲線分析

限于篇幅,圖2僅列出SCFPA和FPA、MFPA、EOBLFPA、I-GWO、WOA、SSA等對比算法在部分函數(shù)上尋優(yōu)的收斂曲線。圖2中,對所有函數(shù)的適應度值(F)做以10為底的對數(shù)處理。

從圖2可見,SCFPA在f1、f2、f3、f5、f7上分別運行到大約170、220、150、40、40代,已經(jīng)收斂到函數(shù)的理論最優(yōu)值,收斂速度較對比算法優(yōu)勢明顯。從SCFPA在f4函數(shù)上的收斂曲線可見,其收斂到的最佳精度優(yōu)于所有對比算法。因此,進一步驗證了本文提出的改進策略,有效地提升了基本FPA的收斂速度。

3.5 消融實驗

均勻隨機選擇SCFPA的正弦算子或余弦算子,對花粉個體進行逐維擾動。將僅使用正弦算子,余弦算子擾動的算法分別記為SINFPA、COSFPA;將SCFPA與上述2種算法進行消融實驗,結果見表4。

表4 正弦余弦算子消融實驗結果

從表4可見:在高維函數(shù)上僅使用單一算子和均勻隨機選擇算子的尋優(yōu)效果相當,但在固定維度多峰函數(shù)上,均勻隨機選擇算子較單一算子的擾動,使得算法性能穩(wěn)定性有所提升。

4 SCFPA工程實例應用

機械工程約束優(yōu)化是優(yōu)化領域的一個重要分支,經(jīng)典的機械工程實例常作為檢驗工程約束優(yōu)化算法性能優(yōu)劣的標準。應用SCFPA求解懸臂梁設計和壓力容器設計2個著名機械工程實例,以檢驗算法的性能和解決現(xiàn)實世界中相似工程約束優(yōu)化問題時的適用性。目前,公認的最有效的處理約束優(yōu)化方法,是通過定義罰函數(shù)將約束優(yōu)化轉化為無約束優(yōu)化求解。使用的罰函數(shù)定義為

(7)

式中:F(x)為罰函數(shù);f(x)為原目標函數(shù);φ?1是懲罰因子,本文取φ=1030;n為約束不等式數(shù)量;gj(x)為不等式約束;

(8)

本文取k=2。

4.1 懸臂梁設計問題

懸臂梁由5個等厚空心砌塊組成,其結構如圖3所示。

圖3 懸臂梁設計問題

梁為剛性支撐,垂直力作用于第5塊的自由端。這個問題需優(yōu)化5個構件的高度或寬度,使懸臂的總質量最小。該問題數(shù)學描述如下:

將SCFPA和FPA對懸臂梁問題求解的最優(yōu)解與相關文獻報道的SCAHGM[22]、SSA[3]、AEO[5]、GOA[23]、SOS[24]和MFA[25]等算法求解的最優(yōu)解進行比較。為了客觀公正地評價SCFPA,并使比較有意義,將SCFPA的種群規(guī)模設為20,最大迭代次數(shù)設為700,即最大適應度函數(shù)評價次數(shù)(maximum fitness evalutions,maxFEs)為14 000,比較結果見表5。

表5中“-”表示對比算法文獻沒有給出實驗數(shù)據(jù)(下文同)。從表5可見,SCFPA明顯優(yōu)于FPA;在算法的最大適應度函數(shù)評價次數(shù)設置整體少于其他對比算法的情況下,除了SSA外,SCFPA求解的最優(yōu)解優(yōu)于所有其他對比算法,與SSA相當。對比結果說明,SCFPA在解決實際工程約束優(yōu)化問題時具有一定優(yōu)勢。

表5 懸臂梁設計問題的最優(yōu)解對比

4.2 壓力容器設計問題

壓力容器結構如圖4所示。

圖4 壓力容器設計

壓力容器共有4個設計參數(shù),即半球形蓋子厚度 (Th)、圓柱形管子內(nèi)徑(R)、圓柱形管子厚度(Ts)和長度(L)。設計目標是4個參數(shù)在滿足一定約束條件下的總成本最少。該問題的數(shù)學描述如下:

其中(x1,x2,x3,x4)=(Ts,Th,R,L)。

約束條件:

g1(x)=-x1+0.019 3x3≤0,

g2(x)=-x2+9.54×10-3x3≤0,

g4(x)=x4-240≤0,

其中,0≤x1,x2≤99,10≤x3,x4≤200。

使用SCFPA求解該問題,程序獨立運行30次。與解決該問題相關文獻報道的AEO[5]、WOA[26]、SHO[2]、PO[7]、WAROA+JADE[26](簡記為WJADE)、NM-PSO[27]、CS-BSA[28]、I-GWO[8]、GSFPA[12]等算法的結果進行了比較,比較結果見表6。

表6 壓力容器設計問題的統(tǒng)計結果比較

為了使比較有意義,突出SCFPA的性能,將SCFPA的種群規(guī)模設為25,最大迭次數(shù)分別設為1 000和2 000,即maxFEs分別為25 000和50 000。從表6可見:在SCFPA的最大適應度函數(shù)評價次數(shù)為25 000,整體上遠小于對比算法的情況下,除了CS-BSA外,SCFPA在4個指標上的值均優(yōu)于所有對比算法,而且SCFPA的最優(yōu)值優(yōu)于CS-BSA;在評價次數(shù)提升到50 000次時,SCFPA在獲得最佳解的同時,其標準差為0,優(yōu)于所有對比算法,表現(xiàn)出了良好的穩(wěn)定性。SCFPA獲得的最佳解為:Ts=0.778 168 641,Th=0.384 649 163,L=200,R=40.319 618 72。

綜上所述,SCFPA在求解2個經(jīng)典機械工程優(yōu)化問題上,在收斂到的最優(yōu)解和穩(wěn)定性方面優(yōu)于文獻報道的對比算法,說明SCFPA適應于求解現(xiàn)實世界的工程約束優(yōu)化問題,具有良好性能。

5 結 語

花授粉算法在解決高維優(yōu)化問題時,存在易陷入局部極值、收斂精度較低的缺陷。為此,本文在異花授粉階段,引入振幅具有自適應指數(shù)非線性調(diào)整的正弦余弦算子,對花粉個體逐維擾動;在自花授粉階段引入基于優(yōu)勝劣汰生存法則的新授粉方式,對花授粉算法進行了改進。在9個包含高維單峰、多峰和固定維度多峰函數(shù)上的實驗結果表明:SCFPA鞏固提高了基本FPA處理低維優(yōu)化問題的能力,大幅提升了處理高維優(yōu)化問題的性能。在維度不小于1 000維,達到5 000維的大規(guī)模優(yōu)化問題上,算法仍具有良好的尋優(yōu)能力。在2個經(jīng)典的機械工程實例上的實驗結果表明:SCFPA在最大適應度函數(shù)評價次數(shù)遠少于對比算法的情況下,收斂的精度和穩(wěn)定性優(yōu)于對比算法,說明SCFPA在處理實際工程問題時具有良好性能。鑒于SCFPA良好的大規(guī)模優(yōu)化問題處理能力,后續(xù)將在解決具體的大規(guī)模應用問題上開展進一步研究。