融合正弦余弦算法和精英算子的花授粉算法

王 蕾，丁正生

西安科技大學 理學院，西安710054

1 引言

花授粉算法（Flower Pollination Algorithm，FPA）是2012年由英國著名學者Yang首次提出的一種基于種群的人工智能優化算法，主要通過模擬自然界植物花朵的自花授粉和異花授粉行為分別構成該算法的局部搜索過程和全局搜索過程。

花授粉算法具有結構簡單、魯棒性強、搜索能力強、參數少等特點的新興算法，并已成功應用于多個領域，例如Prathiba使用花授粉算法來解決不同的經濟負荷調度問題[1]；Abdel-Baset 等人提出的復雜編碼花授粉算法用于約束工程優化問題[2]；Zhou 等人提出了一種用于求解最優無人水下車輛路徑規劃問題的改進花授粉算法，提出了融合花授粉算法和原子勢函數進行形狀匹配，提出了離散貪婪花授粉算法求解球形旅行商問題[3-5]；Wang等人提出了利用蜜蜂授粉算法進行聚類分析[6]；肖輝輝等人提出的基于單純形法和自適應步長的花授粉算法以及新授粉方式的花授粉算法[7-8]；Nabil 提出的一種改進的全局優化算法[9]等等。

基本花授粉算法雖然已經有多位學者進行了討論和研究，但是在改進的算法中仍存在局部搜索過程的授粉范圍較小而導致的種群不夠豐富以及易陷入局部最優等問題；全局搜索過程的授粉范圍較大從而花粉個體傳播作者具有盲目性而導致的尋優精度低等問題。基于以上的基本花授粉算法仍存在的缺陷、不足，本文將正弦余弦算法和精英算子引入花授粉算法中，提出融合正弦余弦算法和精英算子的花授粉算法。該算法將正弦余弦算法嵌入到局部搜索過程中；在全局搜索過程中引入精英算子進行變異和交叉操作，增強種群多樣性，提高算法的收斂精度。

2 花授粉算法

花授粉算法[10]是一種由天然植物的開花和授粉過程啟發和模擬的算法。在自然界中，植物開花授粉分為非生物自花授粉和生物異花授粉，其中異花授粉需要借助自然界的花粉傳播者，例如蜜蜂、蝴蝶、鳥類等進行授粉過程。

為了簡化植物開花授粉過程，花授粉算法需要滿足以下理想化規則：

（1）非生物自花授粉行為認定為局部搜索授粉過程。

（2）生物異花授粉過程認定為借助自然界介質傳播的全局搜索授粉過程，其中花粉傳播者的飛行服從萊維分布。

（3）花朵恒常性認定為植物花授粉行為涉及到的兩朵花的繁殖概率和相似度成比例。

（4）植物花授粉的異花授粉和自花授粉過程由轉化概率p ∈[ ]0,1 控制的。由于在授粉過程可能會受到地理位置、天氣溫度等因素的影響，所以轉換概率p 具有著重要意義。

在花授粉算法中，主要有兩個步驟：自花授粉（局部搜索）過程和異花授粉（全局搜索）過程。

異花授粉過程中，花粉的傳播是由自然界中的例如鳥類等飛行而實現傳播的。定義g*是當前種群中最優的花粉位置，若在第t 次循環時花粉i 進行異花授粉，則對應位置更新如下式：

其中，Γ(λ)是標準的gamma 函數，并且當步長s(s ＞0)為較大值時此分布有效，一般地，取λ=1.5。

自花授粉過程中，若在第t 次循環時花粉i進行自花授粉，則對應位置更新如下式：

基于以上分析，花授粉算法具體步驟描述如下：

步驟1初始化花粉群體規模N，自花授粉過程和異花授粉過程的切換概率p，服從(0,1)均勻分布的隨機數rand，最大迭代數N iter，尋求當前最優花粉g*并計算其適應度值f(g*)。

步驟2進入主循環，當rand ＞p時，進行異花授粉，根據公式（1）更新當前的花粉位置；當rand ＜p 時，進行自花授粉，按照公式（3）更新當前花粉位置。

步驟3根據適應度值判斷是否更新花粉個體。若)接受新的解并更新位置，并將得出的新解和隨機產生的最優花粉進行比較；若f(xnew)＜f(g*)，則替換最優花粉g*。否則返回步驟2。

步驟4判斷算法是否滿足停止條件，即達到最大迭代數N iter，若滿足進行步驟5，否則返回步驟2。

步驟5輸出最優花粉個體g*和全局最優解f()。

3 融合正弦余弦和精英算子的花授粉算法

3.1 正弦余弦算法

正弦余弦算法（Sine and Cosine Algorithm，SCA）是格里菲斯大學教授Mirjalili 于2016 年提出的一種新型的群體智能算法。該算法具有結構簡單，魯棒性好等特點，利用正弦函數和余弦函數的性質進行迭代達到尋找最優解的目的。

標準正弦余弦算法首先初始化解的位置，再依據該算法的更新公式如下：

正弦余弦算法與基于個體的智能算法相比，本質上的優勢是較強的搜索能力和避免局部最優的能力。并且SCA 算法同時具有“局部開發”和“全局搜索”的特性：當正弦余弦函數的返回值在區間[-1,1]時，開發出期望的搜索空間，又稱為局部開發；當函數返回值在閉區間之外時，將開發搜索不同的區域，可視為全局搜索。而花授粉算法在自花授粉過程中，由于授粉范圍較小有易陷入局部最優的缺陷，將SCA 算法引入FPA 算法的自花授粉環節。一方面，提高了種群中隨機花粉的質量，當正弦余弦函數的返回值不同時，搜索空間區域不同（分別為局部開發和全局搜索）使得FPA 算法局部搜索環節時少量的花粉個體被充分利用。另一方面，正弦余弦算法中幾個重要參數能夠提升尋優性能。

3.2 改進正弦余弦算法

結合兩種算法的特性，將標準正弦余弦算法的個體位置更新公式稍作改變。簡化參數數量，在保持性能不變的基礎上降低公式的復雜度。從而在每次迭代中，群體中的花粉個體位置更新公式如下：

3.3 精英算子的變異和交叉操作

花授粉算法在異花授粉過程中，搜索范圍較大從而尋優能力較低，收斂性不高的問題，從而引入精英花粉算子并進行變異和交叉操作。

首先，將花授粉算法的異花授粉過程選取的當前最優花粉作為精英算子，從而明確方向和減小搜索范圍；然后，為依舊保持種群個體的豐富性，對該精英花粉算子進行變異和交叉操作，不僅增強了算法的收斂性能，同時也能避免算法陷入局部最優的問題。

花粉的變異公式如下：

其中，g*是當前種群中的最優花粉；和是種群中不同于花粉i的任意兩個花粉的位置。

這里的rand()是一個服從(0,1)標準均勻分布1×dim的隨機數矩陣（其中dim 表示改進算法搜索空間維數）。算法主循環中的rand 表示一個區間在(0,1)內服從均勻分布的隨機數。

花粉的交叉操作公式：

其中，xi,j是第i個花粉的第j個決策變量；Cr 是交叉率，一般取Cr=0.15。

3.4 SCA-EFPA算法描述

SCA-EFPA 算法主要從基本花授粉算法的自花授粉（局部搜索）過程和異花授粉（全局搜索）過程入手。

首先初始化各項參數，尋找當前最優花粉及其適應度值，然后按照切換概率分別進行自花授粉和異花授粉過程。

自花授粉時，引用改進后的正弦余弦算法的個體位置更新公式替換基本花授粉算法的位置更新公式進行尋優，克服了易陷入局部最優的缺陷；異花授粉時，先按照基本花授粉全局搜索尋找最優解，再將其視為精英花粉算子并進行交叉和變異操作，提高尋優精度的同時不失種群豐富性。

進而評價當前花粉，在滿足停止條件下輸出最優花粉個體及其最優解。

SCA-EFPA算法流程如圖1。

圖1 SCA-EFPA算法流程圖

基于以上分析，SCA-EFPA算法具體步驟描述如下：

步驟1初始化花粉群體規模N，自花授粉過程和異花授粉過程的切換概率p，服從( )0,1 均勻分布的隨機數rand，最大迭代數N iter，尋求當前最優花粉g*并計算其適應度值f(g*)。

步驟2進入主循環，基于切換概率p：

當rand ＞p 時，進行異花授粉。首先，按照公式（1）更新當前的花粉位置。其次，選取當前最優花粉為精英花粉算子，依次按照公式（6）和（7）進行變異和交叉操作。

當rand ＜p 時，進行自花授粉。直接按照引入的改進正弦余弦算法位置更新公式（5）更新當前花粉位置。

步驟3根據適應度值判斷是否更新花粉個體。若)接受新的解并更新位置，并將得出的新解和隨機產生的最優花粉進行比較；若f(xnew)＜f(g*)，則替換最優花粉g*。否則返回步驟2。

步驟4判斷算法是否滿足停止條件，即達到最大迭代數N iter，若滿足進行步驟5，否則返回步驟2。

步驟5輸出最優花粉個體g*和全局最優解f()。

4 測試結果與分析

4.1 參數設置與測試函數

所有參與測試函數測試的對比智能算法參數設置：種群規模n=20，搜索空間維數D=30，最大迭代數N iter=2 000。

在基本花授粉算法中，轉換概率p是其涉及的唯一參數，本文選取實驗效果最好的p=0.8；本文提出的SCA-EFPA 算法選取轉換概率p=0.8，全局授粉中的精英算子交叉操作選取交叉率Cr=0.15。

如表1所示，選取的10組標準測試函數分為高維單峰 函 數(f1～f5)、高 維 多 峰 函 數(f6～f8)和 低 維 函 數(f9～f10)。并且f5是經典的測試函數，易陷入局部最小值；f6在其定義域內存在大量的局部極小值；低維函數具有強震蕩的特點，從而難以找到全局最小值。

4.2 結果分析

對于表1 中的10 組測試函數分別獨立運行20 次并取得最優值、平均值、最差值和經過計算的標準差值。此外，在相同的測試函數下進行花授粉算法（FPA）、粒子群算法（PSO）、差分變異算法（DE）和本文提出的SCA-EFPA 算法進行尋優精度和穩定性的對比實驗。如表2 所示的標準測試函數對比結果，根據測試結果可以得到：

f1～f5均是高維單峰函數，本文提出的SCA-EFPA算法的尋優精度在f1～f4均達到E-100以上，并且f5找到了其理論最優解。尋優精度明顯高于對比智能算法的值。測試結果還可以得到改進算法的穩定性相比之下也較高，標準差基本上均可以達到0，f4也達到了E-200以上。

表1 標準測試函數

f6～f8均是高維多峰函數，SCA-EFPA 算法相較于對比算法中的基本花授粉算法、粒子群算法和差異演化算法的性能效果較為顯著。f5、f6、f8三個測試函數均找到了理論最優值，具有明顯更的算法競爭優勢。雖然f7沒有達到理論最優值，但是相較于對比算法的結果更優，并且穩定性較高。f6～f8的尋優效果上均高于對比算法。并且搜索性和穩定性都極高，標準差均為0。保證了改進算法在尋優的過程中具有良好的性能。

f9～f10均是低維函數，在最優值、最差值均表現出較高的精度值，并且都找到了理論最優值。在穩定性方面標準差都是0，顯示出了極高的穩定性。雖然對比的智能算法中基本上也可以找到接近理論值的結果，但是本文提出的改進算法得到了更精確的結果，并且在穩定性方面具有一定的優勢，可以表明高精度的取值不是偶然，保障了結果的穩定性和準確性。

算法的收斂曲線可以直觀地了解算法的收斂性能，是衡量改進算法的收斂性能的重要指標和表述方式。在圖2～圖5 中給出了基本花授粉算法（FPA 算法）和本文提出的改進算法（SCA-EFPA 算法）分別進行10 個測試函數的運行結果圖。從圖2～圖5 中可以更直觀地得到，對于測試函數f7本文提出的改進算法雖然沒有達到理論最優值但是無限接近最優值，并且收斂較快。而對于其他測試函數本文提出的改進算法快速地達到了理論最優值。克服了提出的針對基本花授粉算法的易陷入局部極值和尋優精度不高的缺陷問題。直觀地體現了本文提出的改進算法具有快速收斂性和好的尋優性能。

表2 標準測試函數結果

圖2 f1 ～f3標準測試函數結果

所以根據以上分析，相較于比較算法本文提出的SCA-EFPA算法不論是最優值還是標準差均得到了較理想的數值。體現了本文提出的改進算法高質量的尋優精度和穩定性，從而在智能算法中具有一定的競爭力強度。

5 結束語

本文提出的融合正弦余弦和精英算子的花授粉算法（SCA-EFPA）是分別在全局授粉和局部授粉過程引入精英算子和正弦余弦算法的一種改進花授粉算法。由于標準正弦余弦算法將優化問題視為一個黑匣子，可以較為容易地結合不同的算法和問題。所以將標準正弦余弦算法的位置更新公式稍作改變引入基本的花授粉算法的自花授粉過程中；在異花授粉中引入精英算子提高尋優精度。

圖3 f4 ～f6標準測試函數結果

圖4 f7 ～f9標準測試函數結果

圖5 f10標準測試函數結果

在標準測試函數對比結果中可以得到，在尋優精度方面具有明顯優勢，并且具有較好的穩定性，避免了易陷入局部最優的問題。從最優值和標準差的數值上可以具體看到，本文提出的SCA-EFPA 算法的尋優性能和穩定性等方面的優越性。雖然結果分析表明SCA-EFPA算法性能具有較強的優勢和競爭力，但是本文提出的改進花授粉算法仍有不足，如理論證明方面仍有欠缺，以及算法程序運行時間方面還沒有得到較好的改善。鑒于所述問題，未來需要更進一步的研究和證明。