李焰華 趙齊輝 肖子雅

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.

引言

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

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

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

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

1基本花授粉算法

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

1.1異花授粉過程

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

1.2自花授粉過程

當(dāng)花粉進(jìn)行自花授粉時(shí)，其位置xti更新公式如下：xt+1i=xti+εxtj-xtk（3）xtj和xtk是不同于花粉i的2個(gè)花粉的位置，ε∈U[0，1]。

1.3FPA的描述

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

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

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

（3）最優(yōu)值評估：將得出的新解與隨機(jī)產(chǎn)生的最優(yōu)花粉進(jìn)行比較，若f（xnew）f（g*），返回（2）。

（4）判斷是否達(dá)到最大迭代次數(shù)。

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

2混合變異花授粉算法

由于花授粉算法是通過轉(zhuǎn)換概率p來進(jìn)行自花授粉和異花授粉的切換過程，因此異花授粉的過程是與最優(yōu)解存在一定的關(guān)系。也就是說個(gè)體與最優(yōu)解之間存在著信息交流，但是自花授粉之間是不存在信息交流與共享的?；诖?，首先將異花授粉的過程中引入混沌算法進(jìn)行隨機(jī)擾動，擴(kuò)大種群多樣性；自花授粉的過程引入交流算子，以增強(qiáng)種群之間的信息交流，有效地避免了算法陷入局部最優(yōu)。

2.1異花授粉隨機(jī)擾動策略

混沌算法是一種常用的全局優(yōu)化算法，引入logistic映射對全局授粉的花粉個(gè)體進(jìn)行隨機(jī)擾動，用來增強(qiáng)種群的多樣性，算法如公式（4）所示：xt+1i=μ*xti*1-xti（4）μ=4為完全混沌狀態(tài)。一般來說，混沌算法作為優(yōu)化設(shè)計(jì)的常用機(jī)制，具有遍歷性和隨機(jī)性的特點(diǎn)?；煦缢惴ǖ囊胗行У乇苊饬怂惴ㄏ萑刖植孔顑?yōu)。

2.2自花授粉的交流算子

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

2.3HMFPA算法描述

HMFPA算法流程描述如下：

Step 1：定義目標(biāo)函數(shù)f（x），x=（x1，x2，…，xd）TStep 2： 花粉種群初始化，隨機(jī)產(chǎn)生初始最優(yōu)解。

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

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

Step 5：如果rand

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

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

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

3測試與仿真

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

3.1測試函數(shù)

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

（1）minf1x=∑ni=1x2i， 當(dāng)-5.12≤xi≤5.12，該函數(shù)全局最小值是0。

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

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

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

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

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

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

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

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

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

各函數(shù)測試結(jié)果的對比見表1。

3.2結(jié)果分析

表1給出了3種算法的測試結(jié)果。

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

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

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

f5x即Rosenbrock函數(shù)的求解結(jié)果不令人滿意。該函數(shù)是復(fù)雜單峰函數(shù)，HMFPA難以找到搜索的方向，這是一個(gè)需要改進(jìn)的地方。

綜上所述，HMFPA在處理各種復(fù)雜函數(shù)之間存在一定的優(yōu)勢，不易陷入局部最優(yōu)。

4結(jié)束語

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

參考文獻(xiàn)

[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ìn)的新型元啟發(fā)式花朵授粉算法[J]. 計(jì)算機(jī)應(yīng)用研究，2016，33（1）：126-131.