帶雜交算子的自適應(yīng)混合花粉授粉算法?

汪 海 趙齊輝 劉 升

1 引言

2012年，著名學者Yang提出了植物花授粉算法［1］（Flower Pollination Algorithm），與其前些年提出來的螢火蟲算法（FA）、布谷鳥算法（CS）、蝙蝠算法（BA）同樣是受到自然現(xiàn)象啟發(fā)而得出靈感。

FPA算法由于通用性強、魯棒性好、編程簡易，具有較好的穩(wěn)定性，已成功應(yīng)用于許多實際中的工程優(yōu)化問題比如：RGB圖像壓縮［2］，九宮格數(shù)獨問題求解［3］，求解制造單元設(shè)計問題［4］。FPA算法如此優(yōu)秀的應(yīng)用性能現(xiàn)已成為人工智能一個新的熱點。但是FPA也存在易陷入局部最優(yōu)、理論基礎(chǔ)薄弱、收斂性證明缺乏等問題。

針對花授粉算法易陷入局部最優(yōu)的特點，國內(nèi)外學者做了很多改進，方法包括：參入局部優(yōu)化算子和其他算法混合。2015年，Rodrigues［5］提出了一種基于二進制編碼的花授粉算法，并應(yīng)用于特征選擇。2014年，El-henawy I，和Ismail M［6］將混沌算法引入到花授粉算法中，并用于整數(shù)規(guī)劃問題的求解。2014年，Abdel-Raouf O［7］將粒子群算法與花授粉相結(jié)合，并用于求解約束優(yōu)化問題。Sakib N［8］等于2014年，將遺傳算法引入到花授粉算法之中，運用遺傳算法中優(yōu)勝劣汰的思想進行算法改進。2016年，肖輝輝［9］等將差分進化的機制參入花朵授粉算法之中，并選擇典型的標準測試函數(shù)進行對比，取得較好的優(yōu)化效果。

花朵授粉算法結(jié)構(gòu)簡單，參數(shù)較少，相對已有算法的局部優(yōu)化和混合其他算法，本文從遺傳變異的角度將隨機花粉個體與最優(yōu)個體雜交產(chǎn)生較優(yōu)的子代；并設(shè)計自適應(yīng)權(quán)重使算法具有更合理的開采能力。綜上，本文針對花授粉算法的兩個關(guān)鍵過程（異花授粉和同花授粉）分別進行改進，對于異花授粉設(shè)計一種自適應(yīng)權(quán)重使得權(quán)重因子根據(jù)迭代次數(shù)進行自適應(yīng)調(diào)整；對于同花授粉，引入雜交算子進行花粉個體與最優(yōu)個體進行雜交使得種群多樣性增加，有效地降低陷入尋優(yōu)的盲目性，最后測試經(jīng)典函數(shù)表明，改進的MFPA在函數(shù)優(yōu)化方面效果優(yōu)于FPA和DEFPA。

2 基本花授粉算法

螢火蟲算法（FA）靈感來自于螢火蟲發(fā)光吸引異性、布谷鳥算法（CS）來源于布谷鳥的巢寄卵生行為、蝙蝠算法（BA）受啟發(fā)于蝙蝠的回聲定位行為，而花授粉算法（FPA）［1］同樣是受到自然界植物花授粉這一行為啟發(fā)而得出靈感，自然界大約有90%的植物進行生物傳粉（Biotic pollination），而存在10%進行非生物傳粉（Abiotic pollination），非生物傳粉需要通過一些介質(zhì)進行傳播，包括：蜜蜂、蝙蝠、鳥類，而這些動物的傳播授粉行為服從萊維分布。

基于植物花授粉的一些特征，在提出該算法之前應(yīng)當遵循以下理想化規(guī)則［1］：

1）進行異花授粉是通過蜜蜂或者鳥類來進行的，而這些異花授粉的“媒介”是進行萊維飛行來傳播花粉的，異花授粉我們看出一個全局授粉的過程；

2）自花授粉的過程我們把它看成一個局部授粉的過程；

3）花恒常性可以認為是授粉行為涉及到兩朵花的繁殖概率與相似度成比例；

4）全局授粉和局部授粉由轉(zhuǎn)換概率 p∈[0 ,1]控制，受物理位置鄰近性的影響以及其他自然因素（風、雨雪等），局部授粉和全局授粉中 p代表著重要的意義。

在FPA算法中，有兩個關(guān)鍵的步驟：全局授粉（異花授粉）和局部授粉（自花授粉）。

在全局授粉的過程中，花粉是由“媒介”（例如昆蟲）進行飛行而傳播，鑒于此，我們把g*定義為當前種群中最優(yōu)花粉所處的位置，則其位置更新公式如下：

其中：xti+1代表著花粉i在t+1循環(huán)時的位置，L代表著授粉的強弱程度，但其本質(zhì)是一個服從萊維分布的步長因子，服從以下式（2）分布：

其中，Γ(λ)是標準伽馬函數(shù)，并且這一分布較為合理當 s(s＞0)為一個較大值的情況，一般地，取λ=3/2。

當花粉進行自花授粉的過程時，其位置xti更新的公式如下：

和是不同于花粉i的兩個花粉的位置，ε∈U[0,1]。

基于以上分析，我們可以將FPA算法步驟描述如下：

1）初始化：給定種群值，自花授粉和異花授粉的轉(zhuǎn)換概率，以及最大迭代次數(shù)和ε的值，隨機給定一個最優(yōu)值位置；

2）基于概率 p選擇自花授粉和異花授粉：rand＜p則進行異花授粉，按照式（1）進行更新新的解；rand＞p則進行自花授粉，按照式（3）進行解的更新：f(xnew)＜f(g*=xnew)；

3）最優(yōu)值評估：將得出的新解與隨機產(chǎn)生的最優(yōu)花粉進行比較，若 f(xnew)＜f(g*)，則令g*=xnew；f(xnew)＞f(g*)，返回2）；

4）判斷是否達到最大迭代次數(shù)；

5）輸出最優(yōu)花粉個體和g*。

3 帶雜交算子的自適應(yīng)花授粉

花授粉算法融入了蝙蝠算法和布谷鳥算法的優(yōu)點，其在全局授粉的過程引入了萊維飛行，這點跟布谷鳥算法的步長移動服從萊維分布具有相似性；花授粉算法利用轉(zhuǎn)換概率 p來與一個隨機數(shù)進行比較，然后進行全局授粉和局部授粉過程的切換，蝙蝠算法也將脈沖的響度和發(fā)射速率與隨機數(shù)進行比較，然后進行解的更新。

但是啟發(fā)于生物現(xiàn)象的算法并不是完全符合自然規(guī)律，存在多條假設(shè)使得算法會存在一定的缺陷，比如：Yang是根據(jù)經(jīng)驗來決定切換概率 p=0.8；考慮到了算法設(shè)計的復(fù)雜性，假設(shè)一朵植物只開一朵花，一朵花的配子代表著一個可行解。這些缺陷使得算法容易陷入局部最優(yōu)、早熟。

針對花授粉算法的不足，本文在算法的兩個過程分別進行改進。在全局授粉的過程之中引入了隨機偏好游動的權(quán)重，使得算法的尋優(yōu)過程更為合理；在局部授粉的過程引入遺傳算法的雜交思想，將花粉個體進行雜交，這樣種群的多樣性便可以得到增加。

3.1 動態(tài)隨機偏好游動

花授粉算法全局授粉過程中的萊維飛行可以使得算法有效地往最優(yōu)值接近，一定程度上可以跳出局部最優(yōu)。為避免算法陷入局部最優(yōu)，本文引入一種動態(tài)權(quán)重進行隨機擾動，公式如下：

其中a代表的是調(diào)節(jié)因子，其取值依賴實驗結(jié)果好壞而定，wmax和wmin代表的是最大權(quán)重和最小權(quán)重，顯然wmin≤w≤wmax。

在粒子群算法的研究中，我們可以知道，權(quán)重是影響算法性能的一個較為關(guān)鍵的因素。過大的權(quán)重容易跳過最優(yōu)解，局部開采能力不足；過小的權(quán)重迭代緩慢，尋優(yōu)空間較小，全局尋優(yōu)能力不強。本文提出的是一種遞減機制的權(quán)重，t→0，w=wmax；反之 t→max t，w=wmin，因此可以很好地協(xié)調(diào)算法搜索的前期需要較大的尋優(yōu)空間；后期可以向最優(yōu)值收斂，加快收斂速度。

3.2 遺傳算法的雜交思想

花授粉算法的局部授粉的過程位置更新過程只是隨機地借鑒了兩個花粉的位置差的信息，這樣執(zhí)行局部授粉搜索最優(yōu)解的過程具有盲目性和不定向性，對此隨機選擇一個花粉與上一代的最優(yōu)個體進行雜交，這樣使得其他花粉能夠獲得最優(yōu)花粉的信息，并且種群的多樣性得到增加。定義如下：

式中r是一個服從0～1之間的均勻分布的隨機數(shù)，是一個隨機產(chǎn)生的花粉個體，經(jīng)過雜交的操作，位置更新會更加合理，局部搜索的過程方向性更強。

3.3 算法的實施步驟

我們將MFPA的算法流程描述如下：

Step 1：定義目標函數(shù) f(x)；x=(x1,x2,…xd)T；

Step 2：花粉種群初始化，隨機產(chǎn)生初始最優(yōu)解；

Step 3：定義轉(zhuǎn)換概率 p；

Step 4：設(shè)定迭代終止的條件（一個固定的迭代次數(shù)或者需要達到的目標精度）；

Step 5：如果 rand＜p，權(quán)重按照式（4）進行異花授粉；

Step 6：如果rand＞p，進行自花授粉，并將種群進行雜交；

Step 7：評價產(chǎn)生的新解，如果優(yōu)于產(chǎn)生的隨機解，則替代掉；否則轉(zhuǎn)到Step 4～Step 6；

Step 8：更新找到的最優(yōu)解。

4 測試與仿真

由于花授粉算法只涉及一個參數(shù)，即轉(zhuǎn)換概率p，Yang在文獻［1］中闡明了 p在選取0.8時實驗效果較好，F(xiàn)PA算法參數(shù)選取轉(zhuǎn)換概率 p=0.8；DEFPA［9］算法參數(shù)選取轉(zhuǎn)換概率 p=0.8，CR=0.1，F(xiàn)=0.5；本文算法選取 p=0.8，a=1，wmax=0.96，wmin=0.36，與基本花授粉算法以及基于差分進化策略的花授粉算法［9］進行對比，種群為20，迭代2000次，選取相一致的測試函數(shù)，只進行固定迭代次數(shù)的尋優(yōu)的精度對比。

4.1 測試函數(shù)

1）min，該函數(shù)全局最小值是0。

2）min f2(x)=xi≤10，該函數(shù)全局最小值是0。

3）+e，-32.768≤xi≤32.768，該函數(shù)全局最小值是0。

4） min f4(x)=-600≤xi≤600，該函數(shù)全局最小值是0。

5） min f5(x)=xi≤100，該函數(shù)全局最小值是-1。

6）min-5≤xi≤5，該函數(shù)全局最小值是0。

4.2 結(jié)果分析

f1是單峰函數(shù)，全局的最優(yōu)值并不是十分難以求得，基本FPA算法與最優(yōu)值相差結(jié)果較大，而DEFPA的數(shù)量級僅僅停留在10-18，但是MFPA都可以搜索到其最優(yōu)值，并且尋優(yōu)標準差達到了0；f2是一個震蕩較為強烈的函數(shù)，全局最小值不易尋得，MFPA在30次迭代實驗中都可以搜尋到最優(yōu)值并且從圖2可以看出來收斂較為迅速；f3是一個指數(shù)疊加并且加上余弦函數(shù)適當放大的連續(xù)型函數(shù)，其特點是：曲面起伏不平，很多算法由于在“爬山”搜索的過程中不免落入了局部最小的陷進，但是MFPA要比DEFPA高8個數(shù)量級，且尋優(yōu)結(jié)果較為穩(wěn)定，但也陷入局部最優(yōu)，這是MFPA需要優(yōu)化的地方；f4函數(shù)的特點是趨于一個單峰函數(shù)，MFPA亦可以搜索到最優(yōu)值0，并且收斂較為迅速；對于二維函數(shù) f5的測試，該函數(shù)的最優(yōu)值被許多局部極小值所包圍，F(xiàn)PA和DEFPA的表現(xiàn)差不多，但是MFPA在30次實驗過程中均可以收斂到-1；30維的 f6函數(shù)，DEFPA可以將精度大提高到了10-3，與0依然存在一定的誤差，而MFPA依然找到了算法的最小值。

表1 三種算法測試結(jié)果

圖1 f1收斂曲線

圖2 f2收斂曲線

圖3 f3收斂曲線

圖4 f4收斂曲線

圖5 f5收斂曲線

圖6 f6收斂曲線

綜上所述，除了Ackley函數(shù)的求解僅僅是停留在了10-16這一數(shù)量級，陷入了局部收斂，其余函數(shù)的優(yōu)化均直接搜索到了其最優(yōu)值，證明了MFPA的優(yōu)越性以及有效性，因此說明MFPA在函數(shù)優(yōu)化方面存在一定的優(yōu)勢。

5 結(jié)語

本文介紹了一種帶雜交算子的自適應(yīng)花授粉算法，針對花授粉算法中異花授粉和同花授粉進行局部改進。在異花授粉的過程中，對權(quán)重進行自適應(yīng)的設(shè)計，使其初期和后期都有良好的尋優(yōu)表現(xiàn)；在自花授粉過程中，引入雜交算子進行最優(yōu)個體雜交，以增強種群的多樣性，避免陷入局部最優(yōu)。選取了6個函數(shù)進行測試，證明其結(jié)果較優(yōu)，尤其是針對高維多峰函數(shù)的優(yōu)化存在一定的優(yōu)勢。

但是花授粉算法也存在一些不足，比如：收斂性的證明、理論基礎(chǔ)薄弱。下一步的工作應(yīng)該是完善其理論以及證明其收斂性，還包括進一步運用到求解現(xiàn)實中的優(yōu)化問題。

［1］Yang X S.Flower pollination algorithm for global optimization［M］//Unconventional computation and natural computation.Springer Berlin Heidelberg，2012：240-249.

［2］Kaur G，Singh D，Kaur M.Robust and Efficient‘RGB’based Fractal Image Compression：Flower Pollination based Optimization［J］.Proc.of International Journal of Computer Applications，2013，78（10）：11-15.

［3］Abdel-Raouf O，El-Henawy I，Abdel-Baset M.A Novel Hybrid Flower Pollination Algorithm with Chaotic Harmony Search for Solving Sudoku Puzzles［J］.International Journal of Modern Education and Computer Science（IJMECS），2014，6（3）：38.

［4］Soto R.et al.Resolving the Manufacturing Cell Design Problem Using the Flower Pollination Algorithm［C］//In：Sombattheera C.，Stolzenburg F.，Lin F.，Nayak A.（eds）Multi-disciplinary Trends in Artificial Intelligence.MIWAI 2016.Lecture Notes in Computer Science，vol 10053.Springer，Cham，2016.

［5］Rodrigues D，Yang X S，de Souza A N，et al.Binary Flower Pollination Algorithm and Its Application to Feature Selection［M］//Recent Advances in Swarm Intelligence and Evolutionary Computation.Springer International Publishing，2015：85-100.

［6］El-henawy I，Ismail M.An improved chaotic flower pollination algorithm for solving large integer programming problems［J］.International Journal of Digital Content Technology and its Applications，2014，8（3）：72.

［7］Abdel-Raouf O，Abdel-Baset M.A new hybrid flower pollination algorithm for solving constrained global optimization problems［J］.International Journal of Applied Operational Research-An Open Access Journal，2014，4（2）：1-13.

［8］Kanagaraj G，Ponnambalam SG，Jawahar N，et al.An effective hybrid cuckoo search and genetic algorithm for constrained engineering design optimization［J］.Engineering Optimization，2014，46（10）：1331-1351.

［9］肖輝輝，萬常選，段艷明.一種改進的新型元啟發(fā)式花朵授粉算法［J］.計算機應(yīng)用研究，2016，33（1）：126-131.

XIAO Huixui，WAN Changxuan，DUAN Yanming.A New Improved Primitive Heuristic Flower Pollination Algorithm［J］.Computer Application Research，2016，33（1）：126-131.

［10］傅文淵，凌朝東.布朗運動模擬退火算法［J］.計算機學報，2014，37（6）：1301-1308.

FU Wenyuan，LING Chaodong.Brownian Motion Based Simulated Annealing Algorithm［J］.Chinese Journal of Computers，2014，37（6）：1301-1308.

［11］Zhang Y，Zhang Y.Particle Swarm Optimization Assisted by Gaussian Processes for Multimodal Function Optimization［C］//International Conference on Computer Engineering and Information Systems，2016.

［12］Kaipa K N，Ghose D.Multimodal Function Optimization［M］.Glowworm Swarm Optimization.Springer International Publishing，2017.

［13］Jamil M，Zepernick H J，Yang X S.Multimodal Function Optimization Using an Improved Bat Algorithm in Noise-Free and Noisy Environments［M］.Nature-Inspired Computing and Optimization.Springer International Publishing，2017.

［14］Yang X S，Karamanoglu M，He X.Flower pollination algorithm：A novel approach for multiobjective optimization［J］.Engineering Optimization，2014，46（9）：194-195.

［15］Alma’Shumah F，Permana D，Sidarto K A.Solving inverse problem for Markov chain model of customer lifetime value using flower pollination algorithm［J］.Journal of Molecular Structure，2015，1692（1）：7-11.