基于改進花粉算法的極限學習機分類模型

邵良杉，李臣浩

遼寧工程技術大學 軟件學院，遼寧 葫蘆島125105

1 引言

極限學習機（Extreme Learning Machine，ELM）[1～2]是南洋理工大學黃廣斌副教授在2004 年根據Moore-Penrose pseudoinverse廣義逆矩陣提出的一種單隱層前饋神經網絡（SLFNs）學習算法，相比于其他需要初始化大量參數的神經網絡，ELM 只需預設網絡中間層節點個數，并且不需要通過迭代來優化權值和閾值[3]，具有計算速度快，泛化性能好的特點[4]。MELM（Multi-output Extreme Learning Machine）[5]在繼承ELM優勢的同時，增加了網絡輸出數目，使其能夠更好地適用于多分類問題。

但ELM和MELM的初始輸入權值和閾值隨機選取的問題在一定程度上限制了模型的分類精度，導致分類結果產生一定的隨機性和波動性[6]。近年來，有部分學者對極限學習機的初始輸入權值和閾值進行優化，2006年Huang等人[7]首次采用人工蜂群算法優化MELM的初始輸入權值和閾值，并得到了較好效果；2018年，賈偉等人[8]采用粒子群優化算法對ELM 的初始輸入權值和輸入層閾值進行優化，得到了最優的ELM模型；但是粒子群和人工蜂群算法都存在參數過多，執行過程復雜且易陷入局部最優解的問題。

花粉算法（Flower Pollination Algorithm，FPA）[9]作為一種新型元啟發式優化算法具有參數少、易實現的特點，相比粒子群和遺傳算法有著更好的尋優能力[9]，2013年，賀興時等人[10]將花粉算法應用到多目標優化問題上并取得了較好的效果。鑒于此，本文采用花粉算法優化極限學習機分類模型初始輸入權值和閾值，但是和其他種群優化算法一樣，花粉算法同樣存在易陷入局部最優、收斂速度過慢的問題。肖輝輝等人[11]采用Levy飛行和配子間萬有引力的方法實現配子位置的更新；段艷明等人[12]通過引入量子系統的態疊加特性，用波函數描述種群個體的位置，提高算法的全局尋優能力；Jiang 等人[13]通過入侵雜草的繁殖、空間擴散和競爭策略，動態生成種群，增加種群的多樣性和有效性。以上改進雖然一定程度上提高了花粉算法的尋有能力，但仍然存在易陷入局部最優，尋優速度較慢的問題。為進一步提高FPA 的尋優能力和尋優效率，本文提出改進的花粉算法（self-Adaptive and Tent Chaos based Flower Pollination Algorithm，ACFPA），利用基于反向學習的Tent 映射優化花粉算法配子的初始位置，并在FPA算法的全局搜索上引入Tent混沌搜索策略，在局部搜索策略和切換概率p 中分別引入自適應算子，以此提高FPA算法的搜索效率。然后使用改進的花粉算法優化MELM的輸入權值和閾值，并結合代價敏感（Cost-Sensitive，CS）[14]的思想，引入基于CS 的適應度函數，使花粉算法能夠更加精確地刻畫模型的分類性能，從而進一步提高ACFPAMELM模型的分類精度和收斂速度。

2 基本理論

2.1 MELM分類模型

極限學習機（ELM）是一種單隱層神經網絡，根據輸出數目的不同，可分為單輸出極限學習機（ELM）和多輸出極限學習機（MELM）。鑒于MELM模型在多分類問題上有著更好的適用性，因此本文采用MELM 解決多分類問題。

對于一個有k 個輸入變量{(xi,ti)}ki=1l 個隱含層節點，z 個輸出變量的極限學習機的輸出可以表示為：

式中，j 為迭代次數，g()為激活函數，βi、wi、bi分別為第i 個隱含層節點的輸出權值矩陣、輸入權值矩陣和偏置。

將上式轉換成矩陣Hβ=T 后的具體形式為：

對于基于梯度的神經網絡算法（如BP），需要在迭代過程中優化所有參數，但在ELM算法中，如果激活函數無限可微，只需要隨機給出輸入權值和偏置，算法同時根據公式自動生成輸出矩陣β1，此過程只執行一次，在保證精度的同時，降低了時間和空間的復雜度。輸出矩陣β1可以表示為：

式中，H+是矩陣H 的Moore-Penrose廣義逆矩陣。

2.2 Tent混沌策略

混沌變量能夠運用其特有的非線性規律在目標空間中遍歷所有可行解，擁有隨機性、非線性、規律性和對初始值敏感性的特點[15]。當前解決混沌問題常用的映射方程有蟲口模型方程和切比雪夫方程等[16-17]。由文獻[18]可知，蟲口模型方程在解空間兩端取得的概率較高，在解空間中心區域取得的概率較低且分布均勻，而切比雪夫方程雖然在（0，1）區間上分布均勻，但迭代速度較慢。單梁等人[19]指出，Tent 映射在（0，1）區間上分布均勻并且速度較快，此外，反向學習策略能夠增加解向量的多樣性[20]，因此，基于對上述分析，為使FPA在整個可行域內快速、均勻地搜索MELM 模型輸入權值和閾值，本文采用基于反向學習的Tent混沌映射和Tent搜索優化FPA算法。

2.2.1 基于反向學習的Tent混沌映射

由于Tent 混沌映射在點0.2、0.4、0.6、0.8 上產生混沌吸引子，出現小周期現象，為避免迭代落入小周期循環，當xi={0，0.25，0.5，0.75}時采用xi=zj+1=zj+e（e為0～1 的隨機變量）公式改變迭代初值，增加了混沌的內隨機性，從而增加了混沌強度，同時通過反向學習公式增加了Tent混沌的遍歷性，有助于提高解的質量和求解效率[20]。

Tent映射公式為：

Tent映射的移位變換公式為：

反向解求解公式為：

基于反向學習的混沌序列生成：

步驟1 隨機產生（0，1）的初值x0，z1=x0。

步驟2 根據式（7）生成一個x 序列。

步驟3 若xi={0，0.25，0.5，0.75}，或xi=xi-s,s={0，1，2，3，4}則帶入xi=zj+1=zj+e（e 為0～1 的隨機變量）；否則執行步驟（2）。

步驟4 若滿足迭代次數，則停止迭代返回x 序列；否則轉向步驟2。

步驟5 根據式（8）生成x 序列的反向解，并計算全部解向量的適應度值，返回前N 個最優的解向量。

2.2.2 Tent混沌搜索

本文采用混沌搜索對花粉算法的全局搜索進行優化，其中混沌搜索的步驟如下：

步驟1 利用公式（4）將xi投影到（0，1）區間

步驟3 利用式（10）將zi(k)載波到解空間

步驟4 計算當前解的是適應度，并與歷史最優適應度進行比較，保留最優解。

步驟5 若達到最大迭代次數，則返回最優解，否則執行步驟2。

3 基于Tent混沌和自適應的花粉算法

3.1 花粉算法及改進可行性

花粉算法于2012 年由學者楊新社首次提出，在解決多目標和單目標優化方面效果理想。相比于粒子群等種群優化算法，FPA利用概率p(0 ＜p ＜1)按一定比例進行異花授粉和自花授粉，體現了Levy飛行策略，在一定程度上解決了輸出結果容易陷入局部最優解的問題。因此，相比于其他優化算法，利用花粉算法優化MELM模型能在保證分類精度的同時，大大加快模型的收斂速度。

設花粉配子個數為N ，目標函數維度為d，配子的當前位置為Xi=[xi1,xi2,…,xid](i=1,2,…,N)配子局部搜索（自花授粉）公式為：

式中，L 為服從Levy 分布的隨機變量，g*為全局最優解。其中L 近似表示為：

式中，s ?s0?0，gam(γ)為gamma函數，γ 取1.5。

通過分析FPA的授粉策略不難發現，配子在全局搜索中以全局最優解為目標，在追趕全局最優粒子的過程中，隨著粒子逐步接近全局最優解，大部分粒子仍表現出明顯的“趨同性”，使算法陷入局部最優，出現早熟。在局部搜索過程中，配子不參考全局最優解，僅將花粉群內兩個任意個體的差分作為追趕目標，表現出明顯的隨機性、盲目性和不確定性，從而降低了全局最優解的更新速度。同時，切換概率p 在整個尋優過程中保持恒定，導致全局搜索在算法初期比例過小且后期比例過大，從而降低了算法的搜索效率。此外，由于FPA初始花粉配子位置隨機選取，從而導致配子很難相對均勻的分布在解空間上，因此降低了FPA 搜索的效率。上述缺陷在一定程度上限制了FPA 的尋優精度和收斂速度。

混沌變量能夠運用其特有的非線性規律在目標空間中遍歷所有可行解。同時反向學習策略能夠增加花粉配子的多樣性，采用基于反向學習混沌映射對FPA算法的配子進行初始化，能使配子較為均勻的分布在解空間上并保持其配子的多樣性，提高初始配子的分布質量。在FPA算法的全局搜索中，混沌搜索能夠幫助FPA算法在整個解空間內搜索，避免全局搜索陷入局部最優。在局部搜索方面，通過定義α 算子，將搜索范圍和算法迭代次數相聯系，可使局部搜索范圍隨著迭代次數的增加而縮小，使算法更具針對性，同時，將切換概率p和算法迭代次數相聯系，使算法在不同階段能夠動態的調整局部搜索和全局搜索的比例。進而提高FPA 算法的尋優精度和收斂速度。

3.2 花粉算法改進

3.2.1 改進的配子初始化

在FPA的配子初始化階段，文本利用基于反向學習的Tent 混沌映射對配子群進行初始化。首先隨機產生初始向量，并根據式（1）和式（2）生成混沌解序列。然后根據式（3）生成對應的反向解。最后計算全部解序列的適應度值，并將前N 個最優的解序列作為N 個花粉配子的初始位置。

3.2.2 改進的切換概率p

為使算法能夠在不同階段動態調整全局搜索和局部搜索的比例，本文將切換概率p 轉化成迭代次數t 的函數，使局部搜索的比例隨迭代次數的增加而指數增長，在算法初期，大規模使用全局搜索使算法在較為大的范圍內尋優，幫助局部搜索確定最優所在區域；后期算法逐步接近全局最優解，因此逐漸增加局部搜索的比例，使算法在更為細化的區域內尋優，使算法更加具有針對性。同時定義系數ε（ε ∈[ ]0,1），ε 的大小決定了局部搜索比例的增長速度和上限，防止搜索后期全局搜索消失。相比于原始的搜索策略，改進后的搜索策略更好的平衡了全局搜索和局部搜索的關系，在整個算法運行過程中，兩種不同方式的尋優策略相互促進，增加算法的尋優速度和精度。改進的切換概率p 為：

其中，t 為算法當前迭代次數，tmax為算法最大迭代次數。

3.2.3 改進的全局搜索策略

在FPA的全局搜索策略上，為避免大量配子過分聚集，增強FPA 算法跳出局部最優的能力，本文在原有全局搜索的基礎上，通過變異策略將混沌搜索引入FPA的全局搜索策略，當前引入變異的方法有全局引入，概率引入和到達指定條件引入等。全局引入混沌策略是在每次迭代中將所有配子的有向搜索策略替換成無向混沌搜索，這雖然能使全局搜索在整個運行期間以較大范圍尋優，但所有配子無目標的盲目更新會導致配子位置彼此重疊，并且對所有配子采用混沌搜索會消耗較長時間，這必然會降低FPA 全局搜索尋優效率和尋優精度，從而喪失FPA 原有全局搜索的優勢。而小概率引入是在每次迭代中選取一小部分配子進行混沌搜索，使其在極大保留原有全局搜索優勢的基礎上增加了跳出局部最優的能力，相比于全局引入具有更高的效率和精度，能夠更快、更準地確定最優解所在的局部區域，保障了算法后期大規模局部搜索（根據改進的切換概率p 可知算法后期局部搜索比例逐漸增大）精度和效率。因此，本文通過小概率變異形式在全局搜索策略中引入混沌搜索，改進的全局搜索流程圖為。

3.2.4 改進的局部搜索策略

在FPA 的局部搜索策略上，文獻[21]在原有局部搜索公式的基礎上參考了全局最優解，但局部搜索范圍不能夠動態調整。本文在此基礎上，引入自適應算子，使局部搜索的范圍隨迭代次數的增加而減小，增加局部搜索效率。改進的局部搜索策略為：

4 CS-ACFPA-MELM模型構建

鑒于FPA 算法相比于粒子群和遺傳算法擁有更好的尋有能力，并且ACFPA 算法改善了FPA 易陷入局部最優解和收斂速度過慢的問題，因此，本文采用ACFPA算法優化MELM 的輸入權值和閾值，并在ACFPA 算法的適應度函數引入代價敏感的思想。

4.1 基于CS的適應度函數

傳統的MELM多分類算法采用0-1適用度函數，將模型輸出的連續值轉換成二進制離散值，雖然能在一定程度上評價模型的分類性能，但此過程會損失大量信息。針對上述問題并結合MELM 輸出結構，本文提出一種基于代價敏感的適應度函數，在原有0-1 適應度函數的基礎上，進一步參考每個輸出節點的數值大小，提高ACFPA 算法對MELM 分類性能的評價能力，進而提高ACFPA-MELM的收斂速度。

MELM處理多分類問題時，將輸出節點中最大值所對應的節點序號作為模型的預測結果，因此優化MELM的目標就是要盡可能的增大正確類別節點對應的輸出值。傳統的0-1適應度函數僅將所有樣本中被正確分類的比例作為評價標準。為增強適應度函數對MELM模型的評價能力，本文根據每個樣本下正確節點對應輸出值占總輸出值的比例計算樣本被分到正確類別的概率，并使適應度函數和此概率成正相關。因此對于相同的分類結果，改進的適應度函能根據每個樣本被正確分類的概率給予每個分類結果不同的分類代價，這將大大加快PSO、FPA 等優化算法對神經網絡參數的優化速度，并且在一定程度上降低分類模型的誤差。改進的適應度函數為：

式中，N 表示樣本個數，k 表示樣本類別數，p 表示迭代次數。outright表示每個樣本分類結果中正確類別所對應輸出的輸出值，outj表示模型第j 個輸出的輸出值，rightj表示j 節點對應的真實值。

4.2 CS-ACFPA-MELM算法流程

步驟1 初始化FPA 相關參數，并隨機生成一個d維的花粉配子，然后利用基于反向學習的混沌映射對花粉配子進行初始化。

步驟2 計算切換概率p，對于每一個配子而言，產生一個隨機數e ∈(0,1)。如果e ＞p，則利用式（15）對該配子進行局部搜索；否則根據圖1 進行全局搜索，更新配子位置信息。

圖1 改進的FPA全局搜索流程圖

步驟3 若Xid＞Upper_Boundd（d 維上邊界），則Xid=Upper_Boundd；若Xid＜Low_Boundd（d 維下邊界），則Xid=Low_Boundd。

步驟4 將當前配子位置的適應度函數值和此配子的歷史最優位置的適應度函數值進行比較，若優于歷史最優值，則將歷史最優值更新為當前位置；否則直接進行下一步。

步驟5 將當前配子位置的適應度函數值和全局最優位置的適應度函數值進行比較，若優于全局最優值，則將全局最優值的位置更新為當前配子位置；否則直接進行下一步。

步驟6 對所有配子執行以上步驟。

步驟7 迭代以上步驟指定次數，輸出全局最優位置。

5 仿真實驗與結果分析

為驗證ACFPA-MELM 模型在分類性能和運行效率上的優勢，本文分別設計3組實驗：（1）確定切換概率p 中參數ε 的最優值；（2）縱向對比MELM、FPA-MELM、CAFPA-MELM、CS-ACFPA-ELM模型在分類精度、迭代次數和運行時間上的差距；（3）橫向對比CS-ACFPAELM、LS-SVM、CART模型在分類精度和結果一致性上的差距。

借鑒文獻[22]的實驗方案和數據集使用，采用10組UCI公共數據集進行實驗，其中diabetes、credit-g、kr-vs-kp樣本數量規模較大，10 個數據集的樣本個數和特征個數如表1 所示。實驗中操作系統為Windows7，CPU 為Intel Core i5-3230 主頻2.60 GHz，內存為8 GB，編程語言為Python3.6。采用5×10重交叉驗證和分層抽樣的方法將數據集劃分成5份，每次選取1份作為測試集，其余作為訓練集，循環10次，計算10次精度均值作為模型最終精度結果。算法的運行時間為算法達到最優精度所消耗的時間。

表1 所選用數據集的樣本數和特征數

5.1 算法參數確定

5.1.1 參數ε 確定

采用窮舉法，對比切換概率p 中參數ε 的不同取值時，CS-ACFPA-MELM模型的分類精度和運行時間。選取區間0.1～0.9，步長為0.1的9個值作為參數ε 的測試值帶入到CS-ACFPA-MELM分類模型中，對每個樣本分別進行9 次獨立實驗，每次實驗迭代200 次。CS-ACFPAMELM在10個樣本上精度隨ε 值的變化如圖2所示，運行時間隨ε 值的變化如圖3所示。

圖2 ε取值不同時CS-ACFPA-MELM模型的分類精度對比

圖3 在前3個數據集上ε 取值和運行時間的對比

由圖2可知，10個分類樣本中，在ε=0.8時，ACFPAMELM 分類模型均達到最高精度。由圖3 可知，在ε=0.8 時，模型在前3個樣本上達到最高精度所用的時間最短。因此結合上述數據可知，對于不同樣本數量和不同特征數量的數據集，在ε=0.8 時均能達到模型的時間最優和精度最優，故在實驗時將改進切換概率p 中的參數ε 定為0.8。

5.1.2 變異閾值確定

采用同5.1.1 小節相同的測試方法，選取0.1 到0.9的9個測試值代入CS-ACFPA-MELM模型中進行實驗，在10 個數據集上的模型變異閾值與分類精度、模型運行時間的關系，如表2所示。

由表2 可知，當變異閾值取0.2 時，CS-ACFPAMELM 模型在10 個分類數據集均達到了最高分類精度，以此可知，對于不同規模樣本數量、不同特征維度的分類數據集，變異閾值為0.2時CS-ACFPA-MELM模型達到最優，具有普遍適用性，因此在實驗中將變異閾值定義為0.2。

5.2 CS-ACFPA-MELM模型縱向對比實驗

對于FPA 算法，根據前文分析，將FPA 局部搜索中的參數β 定為0.1；根據5.1 節中的實驗，將切換概率中的參數ε 定0.8，將全局搜索中的變異閾值定為0.2；根據文獻[10]中的建議，將FPA 的γ 的值設定為0.1；將花粉配子個數定為20；為和MELM模型形成對照，在MELM模型外嵌套迭代機制，重復實驗輸出歷史最優結果。

如圖4是MELM、FPA-MELM、ACFPA-MELM、CSACFPA-MELM分類模型在10個數據集上的收斂曲線；如表3是MELM、FPA-MELM、ACFPA-ELM、CS-ACFPAMELM分類模型在10個數據集上的卡帕系數和運行時間。結合圖表可知，嵌套迭代機制的MELM 模型由于自身的隨機性，分類精度提升緩慢，并且都存在很高的迭代次數和運行時間。利用FPA算法優化MELM的初始輸入權值和閾值，使MELM的迭代增加了方向性，大大加快了MELM 模型的分類精度、卡帕系數以及收斂速度。ACFPA算法在FPA算法的基礎上進一步優化了FPA 的尋優策略，從而將FPA-MELM 模型的的分類精度和運行效率分別提高了1.3%和9.9%；此外，基于代價敏感的適應度函數更加細致地刻畫了MELM模型的質量，從而將ACFPA-MELM模型的分類精度和效率提升了0.8%和8.7%；從卡帕系數的對比可知，FPA-MELM、ACFPA-ELM、CS-ACFPA-MELM 模型，分別將MELM模型的分類一致性逐步提高了1.63%、1.97%和2.30%，達到了模型預測值和真實值的高度一致性。以上數據驗證了基于CS 適應度函數和ACFPA 算法對MELM 模型優化的有效性。

5.3 CS-ACFPA-MELM模型橫向多尺度對比

為證明CS-ACFPA-MELM 分類模型的優勢，實驗對比LS-SVM、CART、CS-ACFPA-MELM 分類模型在10 個測試數據集上的分類精度和卡帕系數。如表4 是LS-SVM、CART、CS-ACFPA-MELM分類模型在10個數據集上卡帕系數和分類精度的對比。不同于LS-SVM模型和CART 模型從全局角度出發逐漸逼近全局最優解，CS-ACFPA-MELM模型能夠從全局和局部兩個角度入手逼近全局最優解，使算法具有跳出局部最優的能力，進而提高分類精度和收斂速度。

由表4 可知，CS-ACFPA-MELM 模型在diabetes、Ionosphere、breast-w、credit-a、credit-g、heart-s、kr-vs-kp這7數據集上的準確率和卡帕系數明顯高于LS-SVM和CART兩種經典分類模型。結合表1可知，上述7個數據集的樣本數均值為2 244，而kr-vs-kp、credit-g、diabetes這3個數據集的樣本數均值為286，遠遠低于前者，這表明CS-ACFPA-MELM分類模型在規模較大的樣本上分類性能明顯優于LS-SVM和CART；在sonar和liver-disorders數據集上，CS-ACFPA-MELM模型的分類精度和卡帕系數相比于比LS-SVM、CART模型優勢較小，這表明隨著樣本數量的增加，CS-ACFPA-MELM模型訓練效果更全面，CS-ACFPA-MELM模型的優勢更加明顯。上述結論驗證了CS-ACFPA-MELM模型在大規模樣本上的優勢以及小樣本上的適用性。

6 結束語

為提高MELM 模型的分類性能，本文采用花粉算法優化MELM 的輸入權值和閾值，并通過分析FPA 算法的不足，在配子初始化和全局搜索中引入Tent混沌策略，在局部搜索和切換概率p 中引入自適應算子，并且將代價敏感的思想引入適應度函數之中。對比實驗表明，改進的花粉算法對MELM 模型分類精度和的收斂速度均有較大提升。

表2 變異閾值取不同值時CS-ACFPA-MELM模型在10個數據集上的分類精度

圖4 MELM、FPA-MELM、ACFPA-ELM、CS-ACFPA-MELM在不同數據集下的收斂曲線

表3 4種模型在不同數據集的卡帕系數和運行時間對比

表4 LS-SVM，CART，CS-ACFPA-ELM在不同數據集的卡帕系數和分類精度對比

在今后的工作中，將會增加測試數據集的種類和數量，進而對CS-ACFPA-MELM 模型的適用樣本類型進行更深入的研究。