混合變異花授粉算法

李焰華 趙齊輝 肖子雅

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.

引言

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

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

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

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

1基本花授粉算法

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

1.1異花授粉過(guò)程

在全局授粉過(guò)程中，花粉是由‘媒介（例如昆蟲(chóng)）進(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è)服從萊維分布的步長(zhǎng)因子，其遵循以下公式分布：L～λΓλsinπλ2π1s1+λ，（s≥s00）（2）其中，Γλ是標(biāo)準(zhǔn)伽馬函數(shù)，并且分布較為合理。當(dāng)s（s>0）為較大值時(shí)，一般情況下，取λ=3/2。

1.2自花授粉過(guò)程

當(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)值評(píng)估：將得出的新解與隨機(jī)產(chǎn)生的最優(yōu)花粉進(jìn)行比較，若f（xnew）f（g*），返回（2）。

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

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

2混合變異花授粉算法

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

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

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

2.2自花授粉的交流算子

針對(duì)自花授粉采用交流算子增強(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：評(píng)價(jià)產(chǎn)生的新解，如果優(yōu)于產(chǎn)生的隨機(jī)解，則替代掉；否則轉(zhuǎn)到Step 4-Step 6。

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

3測(cè)試與仿真

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

3.1測(cè)試函數(shù)

各測(cè)試函數(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ù)測(cè)試結(jié)果的對(duì)比見(jiàn)表1。

3.2結(jié)果分析

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

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

函數(shù)f1x、 f9x此類函數(shù)屬于高維單峰函數(shù)。全局最優(yōu)值較為容易求得，常用來(lái)測(cè)試算法的收斂速度。f1x的優(yōu)化HMFPA比DEFPA高了近200個(gè)數(shù)量級(jí)，優(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并沒(méi)有直接搜索到f4x的最小值，但是HMFPA在30次測(cè)試中結(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)勢(shì)，不易陷入局部最優(yōu)。

4結(jié)束語(yǔ)

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

參考文獻(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] 肖輝輝，萬(wàn)常選，段艷明. 一種改進(jìn)的新型元啟發(fā)式花朵授粉算法[J]. 計(jì)算機(jī)應(yīng)用研究，2016，33（1）：126-131.