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

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

關鍵詞：混沌理論；遺傳算法；混合花粉算法

中圖分類號：TP18 文獻標識碼：A 文章編號：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ā)式算法—花粉算法。該算法能夠有效地解決很多單目標或多目標問題，并很好地運用于了某些工程設計等領域。

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

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

1 基本花粉算法

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

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

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

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

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

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

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

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

其中：Γ（λ）是標準的伽馬函數(shù)，它的分布對較大步長[s>0]是有效的。

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

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

2 混沌序列初始化

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

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

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

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

圖1 混合花粉算法流程

4 改進的花粉算法流程

Step 1：混沌序列初始化花粉個體。

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

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

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

Step 5若算法滿足停止準則，停止迭代；否則轉入Step 3。

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

5 仿真實驗與結果分析

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

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

5.2 仿真實驗與分析

5.2.1 實驗1 HGFPA與FPA進化曲線對比

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

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

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

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

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

5.2.2 實驗2 HGFPA與FPA算法函數(shù)優(yōu)化結果對比

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

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

6 結束語

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

參考文獻：

[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] 王正， 何毅. 基于改進花授粉算法的PID參數(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ōu)化算法[J]. 紡織高?；A科學學報， 2015， 28（1）：116-123.

[5] 馮艷紅， 劉建芹， 賀毅朝. 基于混沌理論的動態(tài)種群螢火蟲算法[J]. 計算機應用， 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