基于遺傳算法的混合花粉算法

吳文斌++劉志鋒++魏振華

摘要：花粉算法具有所用參數(shù)少，易調(diào)節(jié)，搜索路徑優(yōu)等特點(diǎn)，已運(yùn)用于很多工程優(yōu)化問(wèn)題。但是存在易過(guò)早收斂、收斂速度慢和易陷入局部最優(yōu)等不足，為了解決這些不足，對(duì)花粉算法做一些改進(jìn)。在算法初期引入混沌序列做初始化，并在較優(yōu)位置引入遺傳算法的改進(jìn)交叉和變異策略，提出一種基于遺傳算法的混合花粉算法（Hybrid flower pollen algorithm Based on Genetic Algorithm）。對(duì)HGFPA 算法與FPA算法通過(guò)優(yōu)化問(wèn)題中4個(gè)典型復(fù)雜測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)對(duì)比，結(jié)果表明HGFPA 算法的收斂速度與精度均優(yōu)于 FPA 算法。

關(guān)鍵詞：混沌理論；遺傳算法；混合花粉算法

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）30-0173-03

Hybrid Flower Pollen Algorithm Based on Genetic Algorithm

WU Wen-bin， LIU Zhi-feng， WEI Zhen-hua

（Information Engineering Institute， East China University Of Technology， Nanchang 330013， China）

Abstract： The pollen algorithm has many characteristics，such as less parameters、easy adjustment and excellent search path，and has been applied to many engineering optimization problems. In order to solve these problems ， the pollen algorithm to do some improvements. In the early stage of the algorithm to introduce chaotic sequence to do initialization，and the pollen gametes are used to initialize the pollen gametes. Then the improved crossover and mutation strategy of genetic algorithm is introduced in the optimal position. The HGFPA algorithm and the FPA algorithm are compared by four typical complex test functions in the optimization problem，the results show that the convergence speed and accuracy of the HGFPA algorithm are better than those of the FPA algorithm.

Key words： chaos theory； genetic algorithm； hybrid flower pollen algorithm

受啟發(fā)于自然界的花授粉行為，楊新社[1]在2012年提出了一種新型的啟發(fā)式算法—花粉算法。該算法能夠有效地解決很多單目標(biāo)或多目標(biāo)問(wèn)題，并很好地運(yùn)用于了某些工程設(shè)計(jì)等領(lǐng)域。

花粉算法一經(jīng)提出就引起了很多學(xué)者的興趣，很多人把它稍加改進(jìn)并運(yùn)用于解決實(shí)際問(wèn)題。王正，何毅等[2]提出了一種基于監(jiān)測(cè)鄰域的改進(jìn)花授粉算法（IFPA），在算法迭代中引入監(jiān)測(cè)鄰域概念，對(duì)鄰域中的粒子，根據(jù)適應(yīng)度指數(shù)定標(biāo)確定不同粒子的選中概率，對(duì)部分粒子選擇性變異，增加了粒子的多樣性，加強(qiáng)了算法的效率。經(jīng)過(guò)實(shí)驗(yàn)仿真，IFPA算法比其他智能算法在做PID控制器參數(shù)整定方面有更好的優(yōu)勢(shì)，尋優(yōu)能力優(yōu)于其他算法。

本文針對(duì)基本FPA在解決復(fù)雜優(yōu)化工程實(shí)踐問(wèn)題時(shí)存在著收斂速度慢、容易陷入局部最優(yōu)值的不足，而提出了一種改進(jìn)的花粉算法（HGFPA）。在HGFPA的演化過(guò)程中，首先利用混沌理論作種群初始化，其次，在較優(yōu)位置引入遺傳算法的改進(jìn)交叉和變異策略，加快收斂速度，增強(qiáng)算法逃離局部最優(yōu)的能力。通過(guò)對(duì)一些演化計(jì)算領(lǐng)域內(nèi)廣泛使用的幾個(gè)基準(zhǔn)測(cè)試函數(shù)作仿真實(shí)驗(yàn)，驗(yàn)證了HGFPA的有效性。

1 基本花粉算法

花粉算法[3]具有參數(shù)少、實(shí)現(xiàn)簡(jiǎn)單、易調(diào)節(jié)等優(yōu)點(diǎn)，能很好地平衡全局搜索與局部搜索之間的問(wèn)題，全局尋優(yōu)能力強(qiáng)，遵循四條準(zhǔn)則：

1） 式（1）是全局授粉過(guò)程，生物異花授粉是帶花粉的傳粉者的全局授粉過(guò)程，其中L服從式（2）；

2） 式（3）是局部授粉過(guò)程，非生物自花授粉是傳粉者的局部授粉過(guò)程；

3） 花恒常被認(rèn)為是正比于兩朵花相似性的繁殖概率；

4） 局部授粉與全局部授粉由轉(zhuǎn)換概率p∈[0，1]控制。

[xt+1i=xti+γL（λ）（G*-xti）] （1）

其中：[xti]是花粉i在第t次迭代的位置，G*是目前發(fā)現(xiàn)的最優(yōu)解，γ是控制步長(zhǎng)的比例因子，L（λ）對(duì)應(yīng)花授粉的強(qiáng)度。由于昆蟲(chóng)可能以各種步長(zhǎng)移動(dòng)一大段距離，Levy飛行可有效地模擬這種特性，也就是說(shuō)， L（λ）>0。并且

[L→λΓ（λ）sin（πλ/2）π1s1+λ] （2）

其中：Γ（λ）是標(biāo)準(zhǔn)的伽馬函數(shù)，它的分布對(duì)較大步長(zhǎng)[s>0]是有效的。

[xt+1i=xti+ε（xtj-xtk）] （3）

其中：[ε]為在[[0，1]]內(nèi)均勻分布的變量，這里[xtj]和[xtk]是來(lái)自相同物種但不同花的花粉。endprint

2 混沌序列初始化

花粉算法采用隨機(jī)初始化的方式，這種方式容易導(dǎo)致花粉種群分布的不均勻?；煦绗F(xiàn)象具有非周期、自相似有序性的特點(diǎn)，它隨機(jī)性、規(guī)律性、遍歷性強(qiáng)。利于豐富種群的多樣性，使算法容易跳出局部最優(yōu)，非常適合與智能算法相結(jié)合使用[4]。其中混沌序列由式（4）的立方映射[5]產(chǎn)生，利于混沌序列初始化花粉配子位置。

[y（n+1）=4y（n）3-3y（n）；-1≤y（n）≤1；n=1，2...] （4）

3 基于遺傳算法的混合花粉算法（HGFPA）

標(biāo)準(zhǔn)花粉算法通過(guò)搜索個(gè)體極值和群體極值完成全局極值尋優(yōu)，雖然方法簡(jiǎn)單，且能夠收斂，但是隨著迭代次數(shù)的增加，在種群收斂集中的同時(shí)，各花粉配子也越來(lái)越相似，易陷入局部最優(yōu)而無(wú)法跳出，混合花粉算法改變傳統(tǒng)花粉算法中的利用跟蹤極值來(lái)更新花粉配子位置的方法，引入遺傳算法中的交叉和變異操作，通過(guò)花粉配子與個(gè)體極值以及群體極值的交叉和花粉配子自身變異的方式產(chǎn)生新個(gè)體，對(duì)產(chǎn)生的新個(gè)體采用保留優(yōu)秀個(gè)體策略，只有在新花粉配子適應(yīng)度好于舊花粉配子才更新花粉配子。通過(guò)這種方式來(lái)搜索最優(yōu)解。

圖1 混合花粉算法流程

4 改進(jìn)的花粉算法流程

Step 1：混沌序列初始化花粉個(gè)體。

Step 2定義最大迭代次數(shù)Tmax ，λ，轉(zhuǎn)移概率[p∈[0，1]]。

Step 3 對(duì)于種群中所有的n個(gè)花粉配子進(jìn)行授粉：產(chǎn)生一個(gè)隨機(jī)數(shù)rand，若rand < p，則以式（1）進(jìn)行全局授粉；否則，以式（1-3）進(jìn)行局部授粉。評(píng)價(jià)新解，若新解更好，則更新種群，找到當(dāng)前的最優(yōu)解G*。

Step 4花粉配子同個(gè)體極值和群體極值的交叉。個(gè)體和個(gè)體最優(yōu)花粉配子作交叉獲得新花粉配子，比較目標(biāo)函數(shù)值，更新花粉配子，找出當(dāng)前的最優(yōu)解G*；把個(gè)體和群體最優(yōu)花粉配子作交叉獲得新花粉配子，比較目標(biāo)函數(shù)值，更新花粉配子種群，找出當(dāng)前的最優(yōu)解G*。

Step 5若算法滿足停止準(zhǔn)則，停止迭代；否則轉(zhuǎn)入Step 3。

Step 6 算法終止，輸出全局最優(yōu)值G*。

5 仿真實(shí)驗(yàn)與結(jié)果分析

5.1 參數(shù)設(shè)置與測(cè)試函數(shù)

本文比較FPA與HGFPA在4個(gè)Benchmark函數(shù)上的優(yōu)化性能，4個(gè)Benchmark函數(shù)都是來(lái)自全局優(yōu)化測(cè)試函數(shù)庫(kù)[6]，如表1所示。各參數(shù)設(shè)置為p=0.8，[λ] =1.5。實(shí)驗(yàn)硬件環(huán)境為Intel?Core? with HD Graphics 4400 2.80 GHz ，4.00GB，操作系統(tǒng)Window 7，利用Matlab編程實(shí)現(xiàn)。

5.2 仿真實(shí)驗(yàn)與分析

5.2.1 實(shí)驗(yàn)1 HGFPA與FPA進(jìn)化曲線對(duì)比

設(shè)置維數(shù)d=10、30，4個(gè)Benchmark函數(shù)的迭代次數(shù)Tmax分別為5000，20000。對(duì)4個(gè)Benchmark測(cè)試函數(shù)做仿真實(shí)驗(yàn)。在迭代次數(shù)為5000次時(shí)，測(cè)試函數(shù)Ackley（10維）的進(jìn)化曲線如圖1所示，測(cè)試函數(shù)Rastrigin（10維）的進(jìn)化曲線如圖2所示；測(cè)試函數(shù)Rosenbrock（10維）進(jìn)化曲線如圖3所示；測(cè)試函數(shù)Levy（10維）的進(jìn)化曲線如圖4所示。

首先，Ackley與Rastrigin測(cè)試函數(shù)屬于多峰函數(shù)，擁有多個(gè)局部極值點(diǎn)，導(dǎo)致算法很容易地陷入局部最優(yōu)，可以用來(lái)測(cè)試算法探索能力強(qiáng)弱。

在圖2和圖3中， HGFPA與FPA兩種算法收斂精度不同，HGFPA能夠快速收斂且進(jìn)度更高，HGFPA收斂到最優(yōu)值的速度明顯的優(yōu)于FPA。經(jīng)過(guò)實(shí)驗(yàn)發(fā)現(xiàn)（圖6、圖7），隨著函數(shù)維數(shù)d的增加，算法收斂到最優(yōu)點(diǎn)所需要迭代的次數(shù)也會(huì)隨之增加，對(duì)于30維的Ackley函數(shù)，F(xiàn)PA的收斂效果與精度較差，在最大迭代次數(shù)之內(nèi)不一定能收斂到最優(yōu)點(diǎn)，從收斂速度和進(jìn)度來(lái)講，對(duì)于Ackley與Rastrigin函數(shù)，HGFPA算法的優(yōu)化性能明顯優(yōu)于PFA。

其次，Rosenbrock與levy函數(shù)屬于高維單峰函數(shù)，只擁有全局最優(yōu)值，可以用來(lái)測(cè)試算法搜索能力的強(qiáng)弱。從圖4和圖5可以看出，對(duì)于Rosenbrock以及l(fā)evy函數(shù)來(lái)說(shuō)，盡管HGFPA與FPA兩種算法收斂精度相同，但是HGFPA能夠快速收斂。實(shí)驗(yàn)發(fā)現(xiàn)，與前面函數(shù)相似，HGFPA算法對(duì)于10維還是30維，算法都能夠快速的收斂到最優(yōu)點(diǎn)，但隨著函數(shù)維數(shù)的增加，HGFPA算法收斂到最優(yōu)點(diǎn)所需的迭代次數(shù)會(huì)隨之增加，而FPA算法的收斂效果會(huì)變差，在設(shè)定的最大迭代次數(shù)下很難收斂到最優(yōu)點(diǎn)。因此對(duì)于Rosenbrock與levy函數(shù)，HGFPA算法收斂精度與收斂速度均優(yōu)于FPA算法。

綜上可以得出，對(duì)于Ackley、Rastrigin、Rosenbrock、Levy這4個(gè)測(cè)試函數(shù)，從收斂精度與收斂速度來(lái)講，HGFPA均優(yōu)于FPA。

5.2.2 實(shí)驗(yàn)2 HGFPA與FPA算法函數(shù)優(yōu)化結(jié)果對(duì)比

我們繼續(xù)對(duì)HGFPA算法的優(yōu)化能力做進(jìn)一步的研究，在相同的實(shí)驗(yàn)參數(shù)下，對(duì)算法函數(shù)優(yōu)化結(jié)果做對(duì)比，d=30，Tmax=10000，兩種算法獨(dú)立運(yùn)行30次， 取這30次的平均值形成以下表格：

從表2可以看出，在測(cè)試函數(shù)30維時(shí)，對(duì)于全局平均最優(yōu)值，HGFPA對(duì)于函數(shù)Ackley、Rastrigin、Rosenbrock和Levy的全局平均最優(yōu)值明顯優(yōu)于FPA，HGFPA全局平均最優(yōu)值與全局最優(yōu)值很接近，因此，HGFPA算法的搜索能力明顯優(yōu)于FPA的搜索能力；對(duì)于方差，HGFPA對(duì)于4個(gè)測(cè)試函數(shù)的全局最優(yōu)值的方差均小于FPA算法，說(shuō)明在HGFPA算法的穩(wěn)定性方面明顯優(yōu)于FPA算法，再次驗(yàn)證了HGFPA的優(yōu)勢(shì)。

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

本文在基本花粉算法上，針對(duì)搜索策略進(jìn)行了改進(jìn)。花粉算法的初始化過(guò)程中利用混沌理論對(duì)花粉配子的位置進(jìn)行了初始化，使花粉配子分布更加均勻；在花粉配子最優(yōu)位置添加了交叉操作和變異操作，增強(qiáng)算法逃離局部最優(yōu)的能力，從而提高算法的收斂速度和算法的優(yōu)化性能。實(shí)驗(yàn)結(jié)果表明基于改進(jìn)搜索策略的混合花粉算法（HGFPA）比花粉算法（FPA）收斂到最優(yōu)解所需的迭代次數(shù)少，收斂精度更高，大大提高了算法運(yùn)行速度和全局平均最優(yōu)值。由于花粉算法是新近提出的算法，可以與其他智能算法相結(jié)合，值得進(jìn)行進(jìn)一步的深入研究。

參考文獻(xiàn)：

[1] Yang X S. Flower pollination algorithm for global optimization[M]. Unconventional Computation and Natural Computation， Lecture Notes in Computer Science， 2012， 7445： 240-249.

[2] 王正， 何毅. 基于改進(jìn)花授粉算法的PID參數(shù)整定[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2017， 38（1）：209-214.

[3] PAVLYUKEVICHI. Levy flights， norrlocal search and simulated annealing[J].Computational Physics， 2007， 6（8）：1830-1844.

[4] 劉召軍， 高興寶. 融合自適應(yīng)混沌差分進(jìn)化的粒子群優(yōu)化算法[J]. 紡織高?；A(chǔ)科學(xué)學(xué)報(bào)， 2015， 28（1）：116-123.

[5] 馮艷紅， 劉建芹， 賀毅朝. 基于混沌理論的動(dòng)態(tài)種群螢火蟲(chóng)算法[J]. 計(jì)算機(jī)應(yīng)用， 2013， 33（3）：796-799.

[6] JAMIL Momin， YANG Xinshe. A literature survey of benchmark functions for global optimization problems[J]. International Journal of Mathematical Modelling and Numerical Optimization， 2013， 4（2）：1-47.endprint