基于族群機制的花朵授粉算法

肖輝輝，段艷明

（1.河池學院計算機與信息工程學院，廣西宜州546300；2.江西財經(jīng)大學信息管理學院，南昌330013）

基于族群機制的花朵授粉算法

肖輝輝1，2，段艷明1

（1.河池學院計算機與信息工程學院，廣西宜州546300；2.江西財經(jīng)大學信息管理學院，南昌330013）

針對花朵授粉算法易陷入局部極值、收斂速度慢等不足，提出一種具有族群機制的花朵授粉算法。該算法把種群分成多個族群，各族群的最優(yōu)個體再組成新的種群，進而促進種群間的信息交流，有效地協(xié)調(diào)種群進化過程中的全局搜索和局部搜索能力，避免個體的早熟收斂，提高算法的全局尋優(yōu)能力及收斂速度。通過8個CEC2005 benchmark測試函數(shù)進行測試比較，仿真結(jié)果表明，改進算法的尋優(yōu)性能明顯優(yōu)于基本的花朵授粉算法、粒子群算法和蝙蝠算法，其收斂精度、收斂速度、魯棒性均較對比算法有較大提高。

花朵授粉算法，尋優(yōu)性能，收斂速度，族群機制，適應度值

0 引言

受自然界中顯花植物花朵授粉過程的啟發(fā)，英國劍橋大學學者Yang于2012年提出一種新型元啟發(fā)式群智能優(yōu)化算法——花朵授粉算法（Flower Pollination Algorithm，F(xiàn)PA）［1］。FPA算法實現(xiàn)簡單，易于各種語言編碼，需要調(diào)節(jié)的參數(shù)較少，其中轉(zhuǎn)換概率參數(shù)p能較好地平衡局部尋優(yōu)和全局尋優(yōu)，同時，該算法中所采用的萊維飛行機制提高了算法的尋優(yōu)效果。FPA算法正用于不少領(lǐng)域:Yang于2013年用其來解決多目標優(yōu)化問題［2］，并取得了較好的結(jié)果；El-henawy I等人于2014年用其解決大整數(shù)規(guī)劃問題［3］；Marwa Sharawi等人于2014年用其優(yōu)化無線傳感器網(wǎng)絡生命周期問題［4］；R.Prathiba等人于2014年用其優(yōu)化電力調(diào)度問題［5］。但因其提出時間短，目前國內(nèi)外對該算法的研究還處于初級階段，算法理論尚未成熟，研究成果也較少，因此，對FPA的研究迫切而有價值。

然而，F(xiàn)PA算法與粒子群等群智能算法類似，也存在易陷入局部最優(yōu)且進化后期收斂速度慢等不足，尤其對于多局部極值、高維的較復雜優(yōu)化問題。針對FPA算法的不足，國內(nèi)外不少學者對其進行改進:Wang等人［6］考慮到維數(shù)對算法的收斂速度和收斂精度的影響，提出對個體進行逐維改進和引入局部領(lǐng)域搜索策略思想來對算法進行改進；K. Lenin等人［7］利用混沌策略改進和聲算法增強其種群的多樣性，再把和聲算法的最優(yōu)解作為花朵授粉算法的初始解。上述這些改進在一定程度上避免了局部極值，提高了算法的尋優(yōu)能力，仍未使算法完全避免陷入局部極值，其收斂精度、穩(wěn)定性、收斂速度等方面仍有待改進。

針對FPA算法的局限性，本文提出一種具有族群機制的花朵授粉算法（Ethnic Group Flower Pollination Algorithm，EGFPA）。在EGFPA算法中，引入了族群機制，把種群分成多個族群（子種群），對每個族群分兩層進行尋優(yōu)，第1層中按FPA算法求解得到各族群的最優(yōu)個體，各族群的最優(yōu)個體組成第2層的種群，再對其進行FPA尋優(yōu)，最后得到優(yōu)化問題的全局最優(yōu)值。族群機制使種群間進行信息交流，增強種群的多樣性，從而使算法很大程度上避免陷入局部最優(yōu)，提高收斂速度。通過8個CEC2005 benchmark測試函數(shù)的仿真實驗結(jié)果，驗證了改進算法的有效性和優(yōu)越性，EGFPA算法能夠在一定程度上有效地避免早熟收斂，提高收斂速度，其尋優(yōu)精度、尋優(yōu)速度、魯棒性均明顯優(yōu)于基本的花朵授粉算法。

1 基于族群機制的花朵授粉算法（EGFPA）

標準花朵授粉算法分成全局授粉和局部授粉兩部分，兩者之間的轉(zhuǎn)換由轉(zhuǎn)換概率P∈［0，1］控制。FPA算法中，需假設每顆顯花植物僅僅只開一朵花，且每朵花僅僅產(chǎn)生一個花粉配子，一朵花或一個配子對應于優(yōu)化問題中的一個解，模擬自然界中顯花植物花朵傳粉的過程，文獻［1］描述了標準的花朵授粉算法的實現(xiàn)步驟。

1.1 族群機制

傳統(tǒng)的進化群體是隨機而無序的，群體間缺乏信息共享，而族群機制是一種針對群體結(jié)構(gòu)的調(diào)控機制，通過對族群進化過程的控制，實現(xiàn)對群體結(jié)構(gòu)演變過程的調(diào)控［8］。把種群分成族群能從群體中篩選出典型個體，從中發(fā)現(xiàn)有用的信息，并利用這些先進信息來調(diào)整群體的結(jié)構(gòu)，促進群體間的信息交流、提高算法的收斂速度。因此，族群機制利用族群間的信息交流能提高群體的全局搜索能力，族群內(nèi)部的繁殖過程則能提高算法的局部搜索能力。因此，族群機制能有效地平衡算法的全局搜索和局部搜索，避免個體的早熟收斂，進而提高算法的尋優(yōu)能力。族群機制有以下特點［9］:

（1）根據(jù)群體進化狀態(tài)的描述角度來確定族群的分類規(guī)則。不同的分類規(guī)則生成不同的族群結(jié)構(gòu)，如群智能算法中的適應度值、個體的編碼方式等都可以是描述群體的角度。

（2）族群描述了種群個體與種群族群間的映射關(guān)系。這種映射關(guān)系僅僅是邏輯從屬關(guān)系，并不是實質(zhì)上地將個體從群體中孤立出來，個體依然是算法的進化主體，只是分散在族群中。

（3）族群依附于群體，其結(jié)構(gòu)隨群體的分類規(guī)則而改變。

鑒于以上分析，族群機制的偽代碼可表示為:

①隨機初始n=m×r個種群，其中m為族群數(shù)，r為每個族群的種群個體數(shù)；最多迭代次數(shù)N_iter；

②for i=1 to N_iter

③for j=1 to m

④對族群按某種算法進行尋優(yōu)，得到該族群的最優(yōu)個體；

⑤end

⑥對所有族群的最優(yōu)個體組成新的種群，按某種算法進行尋優(yōu)，得到全局最優(yōu)個體；

⑦end

1.2 EGFPA算法的實現(xiàn)步驟

EGFPA算法分為兩層，第1層為族群內(nèi)部尋優(yōu)，各族群不進行信息交流，獨立按FPA算法尋優(yōu)求解該族群最優(yōu)個體；所有族群的最優(yōu)個體構(gòu)成第2層，在這層中各族群的最優(yōu)個體使得各族群之間進行信息交流，在第2層中求解到全局最優(yōu)個體。假設種群數(shù)為n，族群（子種群）數(shù)為m，則每個族群有r=n/m個種群個體（花朵），在族群內(nèi)部，花朵按FPA算法進行進化，每個族群i（i=1，2，…，m）中最優(yōu)花朵（局部最優(yōu)值）為bestpi，整個種群的最優(yōu)個體（全局最優(yōu)值）為

EGFPA算法的具體實施步驟如下:

Step 1初始化EGFPA算法的參數(shù):種群數(shù)n，族群數(shù)m，轉(zhuǎn)換概率p，最多迭代數(shù)N_iter，維數(shù)d；

Step 2隨機初始化m個族群，每個族群有r=n/m個種群個體；

Step 3m個族群第1層迭代尋優(yōu):各個族群獨立尋優(yōu)，計算每個族群內(nèi)個體的適應度值，并求解出每個族群的最優(yōu)解和最優(yōu)值；

Step 4若轉(zhuǎn)換概率p＞rand，按式（1）對每個族群的解進行更新，并進行越界處理；

Step 6求解Step 4或者Step 5的各族群內(nèi)部最優(yōu)的花朵個體，組成第2個層次中的花朵種群，并記錄其最優(yōu)值和最優(yōu)解；

Step 7對Step 6中得到各族群最優(yōu)個體（m個花朵），若轉(zhuǎn)換概率p＞rand，按式（1）對解進行更新，并進行越界處理；

Step 8若轉(zhuǎn)換概率p＜rand，按式（3）對解進行更新，并進行越界處理；

Step 9計算Step 7或Step 8的適應度值，并更新全局最優(yōu)值和全局最優(yōu)解；

Step 10計算Step 9的適應度值，并更新全局最優(yōu)值及全局最優(yōu)解；

Step 11判斷結(jié)束條件，若滿足，退出程序并輸出最優(yōu)值及最優(yōu)解，否則，轉(zhuǎn)Step 3。

2 實驗仿真與分析

為了驗證本文算法的正確性和有效性，通過對8個包括單峰、多峰、低維、高維的測試函數(shù)進行仿真來驗證算法的改進效果，并與FPA、PSO及BA算法進行比較。測試函數(shù)選用CEC2005 benchmark測試函數(shù)中的一部分，測試函數(shù)如下［9-11］:

①Sphere函數(shù)

該函數(shù)是一個單峰函數(shù)，函數(shù)在x*=（0，0，…，0）處取得全局min（f1（x））=0。

②Rastrigrin函數(shù)

該函數(shù)是一個多峰函數(shù)，函數(shù)在x*=（0，0，…，0）處取得全局min（f2（x））=0。

③Ackley函數(shù)

該函數(shù)是一個多峰函數(shù)，在x*=（0，0，…，0）處取得全局最小值fmin（x）=0。

④Griewank函數(shù)

該函數(shù)是一個多峰函數(shù)，在x*=（0，0，…，0）處取得全局最小值fmin（x）=0。

⑤Rosenbrock函數(shù)

該函數(shù)是一個單峰函數(shù)，在x*=（0，0，…，0）處取得全局最小值fmin（x）=0。

⑥Schaffer F6函數(shù)

該函數(shù)的是一個二維多峰函數(shù)，在x*=（0，0，…，0）處取得全局最小值fmin（x）=-1。

該函數(shù)是一個多峰函數(shù)，在x*=（0，0，…，0）處取得全局min（f7（x））=0。

該函數(shù)是一個多峰函數(shù)，在x*=（0，0，…，0）處取得全局min（f8（x））=0。

本文實驗的各種參數(shù)設置為:EGFPA算法參數(shù):轉(zhuǎn)換概率p=0.8，beta=1.5，種群個數(shù)n=120，族群個數(shù)m=15（2.1和2.2小節(jié)）；FPA算法參數(shù):轉(zhuǎn)換概率p=0.8，beta=1.5，種群個數(shù)n=15；PSO算法參數(shù): c1=c2=2，w=0.9，vmax（最大速度）=0.5；BA算法參數(shù): A=0.25，r=0.5，alf=0.95，gama=0.05。

為了驗證本文算法的尋優(yōu)性能、有效性和正確性，仿真實驗方法為:①固定迭代次數(shù)，測試4種算法的尋優(yōu)性能和收斂速度；②與參考文獻算法對比，測試本文算法的魯棒性和尋優(yōu)精度；③分析族群個數(shù)對EGFPA算法的影響。

2.1 固定迭代次數(shù)的性能分析

為了防止算法的偶然性帶來的誤差，對每個測試函數(shù)獨立運行20次，計算其最優(yōu)值、優(yōu)化均值、最差值和標準方差，結(jié)果如表1所示，其中，尋優(yōu)成功率=（找到最優(yōu)解的次數(shù)）/總迭代次數(shù)。在實驗中，假定:|實際求解的最優(yōu)值－理論最優(yōu)值|＜0.001，則認為尋優(yōu)成功。對于每個測試函數(shù)，其優(yōu)化均值反映了在固定迭代次數(shù)下所達到的解的精度，標準方差反映了算法的魯棒性和穩(wěn)定性。

從表1中可以看出，本文提出的EGFPA算法的尋優(yōu)性能很大程度上優(yōu)于基本FPA算法及BA、PSO算法。對于f1、f3、f4、f7和f85個函數(shù)，EGFPA算法的最優(yōu)值、優(yōu)化均值、最差值和標準方差均較FPA算法好，最多相差19個數(shù)量級，且尋優(yōu)成功率都為100%，而除了函數(shù)f4中的PSO外，其他3種算法的尋優(yōu)成功率都為0；對于函數(shù)f2、f5和f6，EGFPA算法的最優(yōu)值、優(yōu)化均值、最差值和標準方差均較FPA算法好，最多相差11個數(shù)量級，且尋優(yōu)成功率也都較FPA、BA及PSO算法要高。這表明無論從尋優(yōu)精度、穩(wěn)定性還是尋優(yōu)成功率上看，EGFPA算法都取得較大幅度的提高，同時也說明EGFPA算法在搜索過程中在一定程度上更能有效地避免陷入局部極小，更好地進行全局優(yōu)化。

表14 種算法在固定迭代次數(shù)下的尋優(yōu)性能比較

為了更直觀地反映出改進算法的尋優(yōu)效果，圖1是4種算法對8個測試函數(shù)收斂曲線圖（為了方便收斂曲線的顯示和觀察，對部分函數(shù)的目標函數(shù)值取以10為底的對數(shù)），形象展示了EGFPA算法和FPA、BA、PSO算法的對比適應度值的迭代下降過程和全局最優(yōu)解的收斂速度。從圖1中可以看出，對于8個測試函數(shù)，EGFPA算法較FPA、BA、PSO算法具有更高的尋優(yōu)精度和更快的收斂速度。這表明，本文提出的EGFPA算法具有更好的尋優(yōu)能力，其收斂速度、優(yōu)化精度明顯優(yōu)于FPA、BA和PSO算法。

圖14 種算法在函數(shù)f1～f8上的收斂曲線

2.2 與參考文獻算法性能比較

為了進一步驗證本算法較好的穩(wěn)定性和較高的尋優(yōu)精度，證明本文改進算法的優(yōu)勢，限于篇幅，只選用函數(shù)f1～f5與參考文獻中的CLIWO［10］、CPSO［10］、HMDE［11］、LDWPSO［11］、ABCMSS［12］、C0-KH［13］算法對比，為了文中前后數(shù)據(jù)的一致性，本節(jié)中的EGFPA數(shù)據(jù)來自2.1節(jié)，其結(jié)果如下頁表2所示。由表2可知，EGFPA算法的優(yōu)化性能（優(yōu)化均值、標準方差）較參考文獻中的其他群智能優(yōu)化算法有較大的提高。對于函數(shù)f2，EGFPA的優(yōu)化均值、標準方差較參考文獻［15］中的CO-KH算法要差點，但好于其他參考文獻算法；對于函數(shù)f1、f3和f4，本文算法的優(yōu)化均值、標準方差均遠遠優(yōu)于參考文獻算法，其中優(yōu)化均值最多相差12個數(shù)量級，標準方差最多相差11個數(shù)量級；對于函數(shù)f5，本文算法的優(yōu)化均值、標準方差略好于參考文獻算法。仿真結(jié)果表明，本文改進算法具有更強的魯棒性和更高的收斂精度，也說明本文算法是有效的和可行的。

2.3 族群個數(shù)對EGFPA算法的影響

族群間的信息傳遞可以提高種群間的協(xié)調(diào)能力，提高算法的收斂速度和收斂精度，族群個數(shù)在一定程度上影響著算法的性能，本節(jié)通過設置不同的族群數(shù)來驗證其對EGFPA算法的影響程度，其他參數(shù)設置同2.1節(jié)，鑒于篇幅問題，僅選用函數(shù)f1、f3和f4進行測試，結(jié)果如下頁表3所示。從表3可以看出，族群個數(shù)很大程度上影響著算法的性能，當族群個數(shù)為5和8時，EGFPA算法的性能提高速度較慢，對函數(shù)f1、f3和f4，最優(yōu)值和優(yōu)化均值均僅提高1個數(shù)量級；但當其族群個數(shù)增加到10和12時，EGFPA算法的性能提高速度較快，對于單峰函數(shù)f1，最優(yōu)值提高了3個數(shù)量級，對于多峰函數(shù)f4的最優(yōu)值也提高了2個數(shù)量級。因此，隨著族群個數(shù)的增加，EGFPA算法的性能也逐步提高。當然，過多的族群個數(shù)也影響著算法的運行時間，經(jīng)過反復測試，當族群個數(shù)為15時，算法的性能和運行時間之間的性能比最好。

3 結(jié)論

花朵授粉算法是一種新型的元啟發(fā)式群智能算法，但FPA算法與現(xiàn)有的群智能算法一樣，存在早熟收斂、收斂精度低、收斂速度慢等不足。為此，本文把族群機制作用于花朵授粉算法，增強種群的有效性和多樣性，進而避免早熟收斂，提高其收斂速度和收斂精度。通過8個CEC2005 benchmark測試函數(shù)的測試，仿真結(jié)果表明，改進算法是可行和有效的，其收斂速度和尋優(yōu)精度得到較大幅度地提高。由于花朵授粉算法的理論和應用研究還處于初始階段，還有許多問題有待進一步研究，如算法的收斂性分析，參數(shù)設置的理論依據(jù)，以及與其他智能優(yōu)化算法的有機融合等。

表2 EGFPA算法與參考文獻算法的優(yōu)化均值和標準方差比較

表3 族群個數(shù)對算法的影響

［1］YANG X S.Flower pollination algorithm for global optimization［C］//In:Unconventional Computation and Natural Computation.Berlin:Springer，2012:240-249.

［2］YANG X S，KARAMANOGLU M，HE X.Multi-objective flower algorithm for optimization［J］.International Conference on Computations Science，2013（18）:861-868.

［3］EL-HENAWY I，ISMAIL M.An improved chaotic flower pollination algorithm for solving large integer programming problems［J］.International Journal of Digital Content Technology&its Applications，2014，8（3）:65-71.

［4］MARWA S E.EMARY I A S，HESHAM El-M.Flower pollination optimization algorithm for wireless sensor network lifetime global optimization［J］.International Journal of Soft Computing and Engineering（IJSCE），2014，4（3）:54-59.

［5］PRATHIBA R，BALASINGH M M，SAKTHIVEL S.Flower pollination algorithm applied for different economic load dispatch problems［J］.International Journal of Engineering and Technology（IJET），2014，6（2）:1009-1016.

［6］WANG R，ZHOU Y Q.Flower pollination algorithm with dimension by dimension improvement［J］.Hindawi，2014:1-9.

［7］LENIN K，REDDY B R，KALAVATHI M S.Shrinkage of active power loss by hybridization of flower pollination algorithm with chaotic harmony search algorithm［J］.Control Theory and Informatics，2014，4（8）:31-38.

［8］陳皓，崔杜武，崔穎，等.族群進化算法［J］.計算機學報，2010，21（5）:978-990.

［9］王迎菊.混合型人工螢火蟲群優(yōu)化算法及應用研究［D］.南寧:廣西民族大學，2012.

［10］劉挺，王聯(lián)國.基于云模型的入侵雜草優(yōu)化算法［J］.計算機工程，2014，40（12）:156-160.

［11］喬俊飛，傅嗣鵬，韓紅桂.基于混合變異策略的改進差分進化算法及函數(shù)優(yōu)化［J］.控制工程，2013，20（5）: 943-947.

［12］王志剛.一種改進搜索策略的人工蜂群算法［J］.計算機仿真，2014，31（10）:291-295.

［13］王磊，張漢鵬.基于混沌搜索與精英交叉算子的磷蝦覓食算法［J］.計算機工程，2015，41（3）:156-161.

Improved Flower Pollination Algorithm Based on Ethnic Group Mechanism

XIAO Hui-hui1，2，DUAN Yan-ming1
（1.School of Computer and Information Engineering，Hechi University，Yizhou 546300，China；2.School of Information and Technology，Jiangxi University of Finance and Economics，Nanchang 330013，China）

In order to overcome the problems of easily relapsing into local extremum and low speed of convergence，a improved flower pollination algorithm based on ethnic group mechanism is presented in the paper.The algorithm divided the population into multiple ethnic groups，and the optimal individual of those ethnic groups formed a new population，so as to promote the information communication between the populations，effectively coordinate the global search and local search in the process of population evolution.It can effectively avoid local optimum，and enhance the capacity of global optimization，improve the convergence speed.The comparison and analysis results of the 8 CEC2005 benchmark functions，the simulation results show that the proposed algorithm has the advantages of better global searching ability，faster convergence and more precise convergence than those of the basic flower pollination algorithm，particle swarm algorithm and bat algorithm.

flower pollination algorithm，optimization ability，convergence speed，ethnic group mechanism，fitness

TP391

A

1002-0640（2017）04-0023-06

2016-02-25

2016-03-16

國家自然科學基金（61173146）；廣西自然科學基金（2013GXNSFBA019022）；校級青年科研基金（XJ2015QN003）；江西省研究生創(chuàng)新基金（YC2015-B054）；河池學院計算機網(wǎng)絡與軟件新技術(shù)重點實驗室基金資助項目（院科研（2013）3號）

肖輝輝（1977-），男，江西永新人，副教授，博士生。研究方向：智能計算、情感計算。