混合變異花授粉算法

李焰華 趙齊輝 肖子雅

Abstract： Flower pollination algorithm is a new type of meta-heuristic optimization algorithm proposed by scholar Yang. It has the defects of being easy to fall into local optimum and low precision. In order to improve its optimization performance， a Hybrid Mutation Flower Pollination Algorithm（HMFPA） is proposed. The pollination algorithm designs chaotic random perturbation and exchange operator for the global pollination and local pollination processes respectively， which effectively balances the local search and global development of the algorithm， and the effectiveness of the algorithm are verified by using multiple standard test functions. The experimental results show that the various optimization indicators of the improved algorithm proposed in this paper are superior to the basic flower pollination algorithm and flower pollination algorithm based on differential evolution strategy.

引言

近些年來，受自然界中生物現象啟發而產生的算法有很多，這些生物包括：布谷鳥、魚、狼、蜜蜂等，這些算法人們稱之為群智能算法。群智能算法受歡迎的程度取決于其做現實中優化問題的能力，函數優化便是檢驗算法的一種有效的工具。

生物啟發式算法很多，像蟻群算法[1]、粒子群算法[2]、螢火蟲算法[3]，這些算法受啟發于自然現象和動物行為。這些算法魯棒性好，并且是不需要求導數的優化方法，能夠有效地解決一些優化問題。但也存在著收斂效率慢、運行時間長、容易陷入局部最優等問題。

花授粉（Flower Pollination Algorithm）[4]作為一種新興元啟發式算法，靈感也是來自于自然界的植物花授粉這一現象。FPA算法由于通用性強、魯棒性好、編程簡易，具有較好的穩定性，已成功應用于許多工程優化問題。Hari Mohan Dubey等人提出了一種改進的FPA算法[5]，并成功應用于短期水火電調度問題。Atul Mishra等人將花授粉應用到離散型問題領域[6]，用于裝配序列規劃問題求解。Ricardo Soto1成功地將花授粉算法應用于求解制造單元設計問題。FPA算法如此優秀的應用性能已成為人工智能一個新的熱點。但是FPA也存在易陷入局部最優、理論基礎薄弱、收斂性證明缺乏等問題。

鑒于花授粉算法存在的不足，相關學者也做出了許多改進，主要有混合其他算法和嵌入局部優化算子。Shifali Kalra等提出了一種混合螢火蟲算法的花授粉算法[8]，并用于多模態函數優化，但求解的高維函數精度不是特別高；Meera Ramadas等提出了一種基于差分進化策略的花授粉算法[9]，并應用于數據聚類。本文分別針對花授粉算法的全局授粉和局部授粉，用混沌擾動和交流算子進行優化，較好地平衡了局部搜索和全局搜索的關系，并測試常用的標準函數，證明其函數優化性能優于FPA和DEFPA。

1基本花授粉算法

自然界的植物進行授粉大致可以分為有性授粉和無性授粉，有性授粉的過程需要借助載體（昆蟲、蝴蝶、鳥類等）進行傳播，而這些動物的飛行過程大致服從萊維分布；而無性授粉常常發生在那些雌雄一體的植物上，這些雌雄植物不需要載體進行花粉的傳播，其依靠風或者雨雪進行傳播。

1.1異花授粉過程

在全局授粉過程中，花粉是由‘媒介（例如昆蟲）進行飛行而傳播，鑒于此，可以把g*定義為當前種群中最優花粉所處的位置，則其位置xti更新公式如下： xt+1i=xti+Lxti-g*（1）其中：xt+1i代表花粉i在t+1循環時的位置；L代表授粉的強弱程度，其本質是一個服從萊維分布的步長因子，其遵循以下公式分布：L～λΓλsinπλ2π1s1+λ，（s≥s00）（2）其中，Γλ是標準伽馬函數，并且分布較為合理。當s（s>0）為較大值時，一般情況下，取λ=3/2。

1.2自花授粉過程

當花粉進行自花授粉時，其位置xti更新公式如下：xt+1i=xti+εxtj-xtk（3）xtj和xtk是不同于花粉i的2個花粉的位置，ε∈U[0，1]。

1.3FPA的描述

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

（1）初始化：給定種群值、自花授粉和異花授粉的轉換概率、以及最大迭代次數和ε的值，隨機給定一個最優值位置。

（2）基于概率p選擇自花授粉和異花授粉：randp則進行自花授粉，按照公式（3）進行解的更新；f（xnew）

（3）最優值評估：將得出的新解與隨機產生的最優花粉進行比較，若f（xnew）f（g*），返回（2）。

（4）判斷是否達到最大迭代次數。

（5）輸出最優花粉個體和g*。

2混合變異花授粉算法

由于花授粉算法是通過轉換概率p來進行自花授粉和異花授粉的切換過程，因此異花授粉的過程是與最優解存在一定的關系。也就是說個體與最優解之間存在著信息交流，但是自花授粉之間是不存在信息交流與共享的。基于此，首先將異花授粉的過程中引入混沌算法進行隨機擾動，擴大種群多樣性；自花授粉的過程引入交流算子，以增強種群之間的信息交流，有效地避免了算法陷入局部最優。

2.1異花授粉隨機擾動策略

混沌算法是一種常用的全局優化算法，引入logistic映射對全局授粉的花粉個體進行隨機擾動，用來增強種群的多樣性，算法如公式（4）所示：xt+1i=μ*xti*1-xti（4）μ=4為完全混沌狀態。一般來說，混沌算法作為優化設計的常用機制，具有遍歷性和隨機性的特點。混沌算法的引入有效地避免了算法陷入局部最優。

2.2自花授粉的交流算子

針對自花授粉采用交流算子增強種群之間的信息交流，使得花粉粒子不斷地靠近最優個體g*。這樣做有利于增加局部授粉中種群的信息共享程度，以避免算法陷入局部最優，提高全局搜索最優值的能力，定義如下：xt+1i=k*xti+（1-k）*g*（5）其中，k=rand（0，1）。

2.3HMFPA算法描述

HMFPA算法流程描述如下：

Step 1：定義目標函數f（x），x=（x1，x2，…，xd）TStep 2： 花粉種群初始化，隨機產生初始最優解。

Step 3：定義轉換概率p。

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

Step 5：如果rand

Step 6：如果rand>p，進行自花授粉，并將種群引入交流算子。

Step 7：評價產生的新解，如果優于產生的隨機解，則替代掉；否則轉到Step 4-Step 6。

Step 8：更新找到的最優解。

3測試與仿真

本文選取p=0.8，max t=2 000，n=20，并與差分進化策略的花授粉算法[10]進行比較，獨立運行30次。

3.1測試函數

各測試函數的形式及取值情況如下所述。

（1）minf1x=∑ni=1x2i， 當-5.12≤xi≤5.12，該函數全局最小值是0。

（2）minf2x=∑ni=1x2i-10cos2πxi+10，當-10≤xi≤10，該函數全局最小值是0。

（3）minf3x=-20exp-0.21n∑ni=1x2i-exp1n∑ni=1（cos 2πxi）+20+e，當-32.768≤xi≤32.768，該函數全局最小值是0。

（4） minf4x=14 000∑ni=1x2i-∏ni=1cosxii+1，當-600≤xi≤600，該函數全局最小值是0。

（5）minf5x=∑n-1i=1[100（xi+1-x2i）2+（xi-1）2]，-2.048≤xi≤2.048，該函數全局最小值是0。

（6）minf6x=sin2x21+x22-0.51+0.001（x21+x22）2，-100≤xi≤100，該函數全局最小值是-1。

（7）minf7x=0.01+∑5i=11i+（xi-1）2-1，-10≤xi≤10，該函數全局最小值是0.436。

（8）minf8x=x21+x22-cos18x1-cos18x2，-100≤xi≤100，該函數全局最小值是-2。

（9）minf9x=∑ni=1xi+∏ni=1xi，-10≤xi≤10，該函數全局最小值是0。

（10）minf10x=∑ni=1x2i+12∑ni=1ixi2+12∑ni=1ixi4，-5≤xi≤5，該函數全局最小值是0。

各函數測試結果的對比見表1。

3.2結果分析

表1給出了3種算法的測試結果。

函數f6x、 f7（x）、 f8x均屬于低維函數。這類函數局部震蕩較為強烈，有很多的局部最優值將全局最優值包圍起來，因此很難穿過局部最小值找到全局最小值，因此常用來測試算法的全局最優值開采能力。HMFPA在這3個函數的尋優中均迅速找到了最優值，并且收斂迅速。DEFPA僅僅是在求解f8x時不存在誤差，其在f6x、 f7x不能每次都尋找到最優值。

函數f1x、 f9x此類函數屬于高維單峰函數。全局最優值較為容易求得，常用來測試算法的收斂速度。f1x的優化HMFPA比DEFPA高了近200個數量級，優化性能的提升非常顯著；f9x的優化基本穩定在10-107，遠遠高于DEFPA的10～30。

函數f2x、 f3x、 f4x、 f10x此類函數為高維多峰函數。屬于典型的多模態非線性函數。該函數均存在較多的局部最小點，尋找其全局最小值較為困難。f2x的優化HMFPA和DEFPA均值直接搜索到了其最小值。f3x的優化HMFPA求解要優于EDFPA，其結果大致是10～16。EDFPA并沒有直接搜索到f4x的最小值，但是HMFPA在30次測試中結果均為0。f10x的適應度值達到了10～210，尋優的結果較為理想，也優于DEFPA的尋優結果。

f5x即Rosenbrock函數的求解結果不令人滿意。該函數是復雜單峰函數，HMFPA難以找到搜索的方向，這是一個需要改進的地方。

綜上所述，HMFPA在處理各種復雜函數之間存在一定的優勢，不易陷入局部最優。

4結束語

花授粉算法是一種較新穎的群智能算法，已成功運用在大量實際工程問題之中，并且優化函數具有收斂迅速、效率高、能夠較快的捕捉極值等優點，但也存在易陷入局部收斂等問題。本文針對花授粉算法的2個關鍵步驟分別進行優化，兼顧了全局尋優和局部尋優，使得算法無論在處理簡單函數還是高維多峰函數都存在一定的優勢。仿真結果表明算法的尋優性得到提升、穩定性得到提高，并且優于差分進化策略的花授粉算法，表明本文提出的算法在函數優化方面存在一定的優勢。后續工作可以將花授粉算法應用到求解組合優化問題中，例如：旅行商問題、項目調度問題等。

參考文獻

[1] DORIGO M， BIRATTARI M， STUTZLE T. Ant colony optimization[J]. IEEE Computational Intelligence Magazine，2016，1（4）： 28-39.

[2] KENNEDY J. Particle swarm optimization[C]// Encyclopedia of Machine Learning. Berlin： Springer， 2010：760-766.

[3] YANG Xinshe. Firefly algorithms for multimodal optimization[C]// Stochastic algorithms： Foundations and applications. Berlin/ Heidelberg：Springer，2009：169-178.

[4] YANG Xinshe， KARAMANOGLU M， HE X S. Flower pollination algorithm： A novel approach for multiobjective optimization[J]. arXiv preprint arXiv：1408.5332，2014.

[5] DUBEY H M， PANIGRAHI B K， PANDIT M. Improved flower pollination algorithm for short term hydrothermal scheduling[C]// Swarm， Evolutionary， and Memetic Computing（SEMCCO 2014）. Switzerland： Springer， 2015：721-737.

[6] MISHRA A， DEB S. Assembly sequence optimization using a flower pollination algorithm-based approach[EB/OL].[2016-09-14]. Https：//DOI.ORG/10.1007/S10845-016-1261-7.

[7] KALRA S， ARORA S . Firefly algorithm yybridized with flower pollination algorithm for multimodal functions[C]//Proceedings of the International Congress on Information and Communication Technology. Singapore：Springer，2016：207-219.

[8] RAMADAS M， ABRAHAM A， KUMAR S. Using data clustering on ssFPA/DE- a search strategy flower pollination algorithm with differential evolution[C]//Proceedings of the 16th International Conference on Hybrid Intelligent Systems （HIS 2016）. Cham：Springer，2017：539-550.

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