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

王 蕾，丁正生

西安科技大學(xué) 理學(xué)院，西安710054

1 引言

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

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

基本花授粉算法雖然已經(jīng)有多位學(xué)者進(jìn)行了討論和研究，但是在改進(jìn)的算法中仍存在局部搜索過程的授粉范圍較小而導(dǎo)致的種群不夠豐富以及易陷入局部最優(yōu)等問題；全局搜索過程的授粉范圍較大從而花粉個(gè)體傳播作者具有盲目性而導(dǎo)致的尋優(yōu)精度低等問題?；谝陨系幕净ㄊ诜鬯惴ㄈ源嬖诘娜毕?、不足，本文將正弦余弦算法和精英算子引入花授粉算法中，提出融合正弦余弦算法和精英算子的花授粉算法。該算法將正弦余弦算法嵌入到局部搜索過程中；在全局搜索過程中引入精英算子進(jìn)行變異和交叉操作，增強(qiáng)種群多樣性，提高算法的收斂精度。

2 花授粉算法

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

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

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

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

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

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

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

異花授粉過程中，花粉的傳播是由自然界中的例如鳥類等飛行而實(shí)現(xiàn)傳播的。定義g*是當(dāng)前種群中最優(yōu)的花粉位置，若在第t 次循環(huán)時(shí)花粉i 進(jìn)行異花授粉，則對應(yīng)位置更新如下式：

其中，Γ(λ)是標(biāo)準(zhǔn)的gamma 函數(shù)，并且當(dāng)步長s(s ＞0)為較大值時(shí)此分布有效，一般地，取λ=1.5。

自花授粉過程中，若在第t 次循環(huán)時(shí)花粉i進(jìn)行自花授粉，則對應(yīng)位置更新如下式：

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

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

步驟2進(jìn)入主循環(huán)，當(dāng)rand ＞p時(shí)，進(jìn)行異花授粉，根據(jù)公式（1）更新當(dāng)前的花粉位置；當(dāng)rand ＜p 時(shí)，進(jìn)行自花授粉，按照公式（3）更新當(dāng)前花粉位置。

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

步驟4判斷算法是否滿足停止條件，即達(dá)到最大迭代數(shù)N iter，若滿足進(jìn)行步驟5，否則返回步驟2。

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

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

3.1 正弦余弦算法

正弦余弦算法（Sine and Cosine Algorithm，SCA）是格里菲斯大學(xué)教授Mirjalili 于2016 年提出的一種新型的群體智能算法。該算法具有結(jié)構(gòu)簡單，魯棒性好等特點(diǎn)，利用正弦函數(shù)和余弦函數(shù)的性質(zhì)進(jìn)行迭代達(dá)到尋找最優(yōu)解的目的。

標(biāo)準(zhǔn)正弦余弦算法首先初始化解的位置，再依據(jù)該算法的更新公式如下：

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

3.2 改進(jìn)正弦余弦算法

結(jié)合兩種算法的特性，將標(biāo)準(zhǔn)正弦余弦算法的個(gè)體位置更新公式稍作改變。簡化參數(shù)數(shù)量，在保持性能不變的基礎(chǔ)上降低公式的復(fù)雜度。從而在每次迭代中，群體中的花粉個(gè)體位置更新公式如下：

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

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

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

花粉的變異公式如下：

其中，g*是當(dāng)前種群中的最優(yōu)花粉；和是種群中不同于花粉i的任意兩個(gè)花粉的位置。

這里的rand()是一個(gè)服從(0,1)標(biāo)準(zhǔn)均勻分布1×dim的隨機(jī)數(shù)矩陣（其中dim 表示改進(jìn)算法搜索空間維數(shù)）。算法主循環(huán)中的rand 表示一個(gè)區(qū)間在(0,1)內(nèi)服從均勻分布的隨機(jī)數(shù)。

花粉的交叉操作公式：

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

3.4 SCA-EFPA算法描述

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

首先初始化各項(xiàng)參數(shù)，尋找當(dāng)前最優(yōu)花粉及其適應(yīng)度值，然后按照切換概率分別進(jìn)行自花授粉和異花授粉過程。

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

進(jìn)而評價(jià)當(dāng)前花粉，在滿足停止條件下輸出最優(yōu)花粉個(gè)體及其最優(yōu)解。

SCA-EFPA算法流程如圖1。

圖1 SCA-EFPA算法流程圖

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

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

步驟2進(jìn)入主循環(huán)，基于切換概率p：

當(dāng)rand ＞p 時(shí)，進(jìn)行異花授粉。首先，按照公式（1）更新當(dāng)前的花粉位置。其次，選取當(dāng)前最優(yōu)花粉為精英花粉算子，依次按照公式（6）和（7）進(jìn)行變異和交叉操作。

當(dāng)rand ＜p 時(shí)，進(jìn)行自花授粉。直接按照引入的改進(jìn)正弦余弦算法位置更新公式（5）更新當(dāng)前花粉位置。

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

步驟4判斷算法是否滿足停止條件，即達(dá)到最大迭代數(shù)N iter，若滿足進(jìn)行步驟5，否則返回步驟2。

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

4 測試結(jié)果與分析

4.1 參數(shù)設(shè)置與測試函數(shù)

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

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

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

4.2 結(jié)果分析

對于表1 中的10 組測試函數(shù)分別獨(dú)立運(yùn)行20 次并取得最優(yōu)值、平均值、最差值和經(jīng)過計(jì)算的標(biāo)準(zhǔn)差值。此外，在相同的測試函數(shù)下進(jìn)行花授粉算法（FPA）、粒子群算法（PSO）、差分變異算法（DE）和本文提出的SCA-EFPA 算法進(jìn)行尋優(yōu)精度和穩(wěn)定性的對比實(shí)驗(yàn)。如表2 所示的標(biāo)準(zhǔn)測試函數(shù)對比結(jié)果，根據(jù)測試結(jié)果可以得到：

f1～f5均是高維單峰函數(shù)，本文提出的SCA-EFPA算法的尋優(yōu)精度在f1～f4均達(dá)到E-100以上，并且f5找到了其理論最優(yōu)解。尋優(yōu)精度明顯高于對比智能算法的值。測試結(jié)果還可以得到改進(jìn)算法的穩(wěn)定性相比之下也較高，標(biāo)準(zhǔn)差基本上均可以達(dá)到0，f4也達(dá)到了E-200以上。

表1 標(biāo)準(zhǔn)測試函數(shù)

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

f9～f10均是低維函數(shù)，在最優(yōu)值、最差值均表現(xiàn)出較高的精度值，并且都找到了理論最優(yōu)值。在穩(wěn)定性方面標(biāo)準(zhǔn)差都是0，顯示出了極高的穩(wěn)定性。雖然對比的智能算法中基本上也可以找到接近理論值的結(jié)果，但是本文提出的改進(jìn)算法得到了更精確的結(jié)果，并且在穩(wěn)定性方面具有一定的優(yōu)勢，可以表明高精度的取值不是偶然，保障了結(jié)果的穩(wěn)定性和準(zhǔn)確性。

算法的收斂曲線可以直觀地了解算法的收斂性能，是衡量改進(jìn)算法的收斂性能的重要指標(biāo)和表述方式。在圖2～圖5 中給出了基本花授粉算法（FPA 算法）和本文提出的改進(jìn)算法（SCA-EFPA 算法）分別進(jìn)行10 個(gè)測試函數(shù)的運(yùn)行結(jié)果圖。從圖2～圖5 中可以更直觀地得到，對于測試函數(shù)f7本文提出的改進(jìn)算法雖然沒有達(dá)到理論最優(yōu)值但是無限接近最優(yōu)值，并且收斂較快。而對于其他測試函數(shù)本文提出的改進(jìn)算法快速地達(dá)到了理論最優(yōu)值?？朔颂岢龅尼槍净ㄊ诜鬯惴ǖ囊紫萑刖植繕O值和尋優(yōu)精度不高的缺陷問題。直觀地體現(xiàn)了本文提出的改進(jìn)算法具有快速收斂性和好的尋優(yōu)性能。

表2 標(biāo)準(zhǔn)測試函數(shù)結(jié)果

圖2 f1 ～f3標(biāo)準(zhǔn)測試函數(shù)結(jié)果

所以根據(jù)以上分析，相較于比較算法本文提出的SCA-EFPA算法不論是最優(yōu)值還是標(biāo)準(zhǔn)差均得到了較理想的數(shù)值。體現(xiàn)了本文提出的改進(jìn)算法高質(zhì)量的尋優(yōu)精度和穩(wěn)定性，從而在智能算法中具有一定的競爭力強(qiáng)度。

5 結(jié)束語

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

圖3 f4 ～f6標(biāo)準(zhǔn)測試函數(shù)結(jié)果

圖4 f7 ～f9標(biāo)準(zhǔn)測試函數(shù)結(jié)果

圖5 f10標(biāo)準(zhǔn)測試函數(shù)結(jié)果

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