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

張 超, 楊 憶

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

0 引 言

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

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

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

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

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

1 花授粉算法(FPA)

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

(1)

(2)

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

(3)

2 SCFPA改進策略

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

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

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

(4)

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

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

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

(5)

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

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

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

2.2 基于優勝劣汰法則的自花授粉策略

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

(6)

2.3 SCFPA的執行流程

SCFPA的主要執行流程偽代碼如下:

開始

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

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

whilet

ifP

ifPsc

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

else

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

end if

else

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

end if

更新全局最優花粉適應度及位置

end while

2.4 SCFPA的時間復雜度分析

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

SCFPA自花授粉過程的算法結構與FPA一樣,因此,自花授粉過程的時間復雜度為(N×D×T×(1-P))。SCFPA異花授粉階段,由參數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屬于同一數量級。

3 仿真實驗與結果分析

3.1 測試函數和對比算法

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

表1 基準測試函數

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

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

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

3.2 與標準FPA的性能比較

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

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

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

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

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

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

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

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

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

3.4 收斂曲線分析

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

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

3.5 消融實驗

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

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

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

4 SCFPA工程實例應用

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

(7)

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

(8)

本文取k=2。

4.1 懸臂梁設計問題

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

圖3 懸臂梁設計問題

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

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

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

表5 懸臂梁設計問題的最優解對比

4.2 壓力容器設計問題

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

圖4 壓力容器設計

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

其中(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 壓力容器設計問題的統計結果比較

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

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

5 結 語

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