一種改進(jìn)的鳥群優(yōu)化算法

史旭棟，高岳林

(1.寧夏大學(xué) 數(shù)學(xué)統(tǒng)計(jì)學(xué)院， 銀川 750021; 2.北方民族大學(xué) 信息與系統(tǒng)科學(xué)研究所， 銀川 750021)

現(xiàn)實(shí)世界的優(yōu)化問題包括連續(xù)、離散、線性、非線性、非光滑或非凸等不同類別的優(yōu)化問題。連續(xù)可微的問題可以用傳統(tǒng)的方法解決，如共軛梯度法；若遇到非常復(fù)雜的問題，如非凸或是不可微，則通過傳統(tǒng)的方法可能無法有效地解決，盡管仍有方法可以解決那些復(fù)雜的問題，但在可容忍的計(jì)算量上有可能得不到最佳的結(jié)果。例如，在一個(gè)可容忍的時(shí)間內(nèi)，傳統(tǒng)的方法不能解決NP問題。

元啟發(fā)式方法作為一種替代傳統(tǒng)的方法，在可容忍的時(shí)間內(nèi)，其優(yōu)勢(shì)是對(duì)于非凸又不可微的問題能找到可接受的解決方案。近年來，自然元啟發(fā)式算法引起了研究者們極大的關(guān)注。

人類學(xué)習(xí)和設(shè)計(jì)新的元啟發(fā)式算法的靈感來自于自然進(jìn)化和生物系統(tǒng)的抽象。隨著研究的深入，遺傳算法(genetic algorithm,GA)[1]、差分進(jìn)化算法(differential evolution,DE)[2]、文化算法(cultural algorithm,CA)[3]、模擬退火算法(simulated annealing algorithm,SAA)[4]等多種方法被提出。粒子群算法(particle swarm optimization,PSO)[5]、蟻群算法(ant colony optimization,ACO)[6]、人工魚群算法(artificial fish swarm algorithm,AFSA)[7]、人工蜂群算法(artificial bee colony,ABC)[8]、 螢火蟲群算法(glowworm swarm optimization,GSO)[9]、 布谷鳥群算法(cuckoo search,CS)[10]、蝙蝠群算法(bat algorithm,BA)[11]、 磷蝦群算法(krill herd,KH)[12]、雞群優(yōu)化算法(chicken swarm optimization,CSO)[13]和鳥群優(yōu)化算法(bird swarm algorithm,BSA)[14]等算法的靈感來自于社會(huì)動(dòng)物的群體智能。靈感來自于植物的算法有雜草算法(invasive weed optimization,IWO)[15]、花授粉算法(flower pollination algorithm,FPA)[16]。而聲搜索算法(harmony search,HS)[17]、 收費(fèi)系統(tǒng)搜索算法(charged system search,CSS)[18]、頭腦風(fēng)暴算法(brain storm optimization,BSO)[19]等算法的提出則受物理原理和自然現(xiàn)象的啟發(fā)。目前許多算法的開發(fā)是用來處理優(yōu)化應(yīng)用問題，尚不存在通用的算法。尋找更有效的算法的研究仍在繼續(xù)。

1 基本的BSA算法

自然界中許多鳥類是群居的，例如雀。它們可能成群結(jié)隊(duì)地居住、覓食、飛行。這些類似分離、隊(duì)列、內(nèi)聚等的行為被看作是自然發(fā)生且形成簡(jiǎn)單規(guī)則的行為。通過最簡(jiǎn)單的社會(huì)互動(dòng)，群體行為可以發(fā)展成復(fù)雜的運(yùn)動(dòng)和相互作用。

鳥群的社會(huì)行為可以通過一些理想化的規(guī)則簡(jiǎn)化如下：

規(guī)則1 每只鳥可在警覺行為和覓食行為之間切換。無論是覓食還是保持警覺都被模擬為一個(gè)隨機(jī)變量。

規(guī)則2 在覓食過程中，每只鳥都可以迅速地記錄和更新其以往的最佳經(jīng)驗(yàn)和最好的食物塊。這方面的經(jīng)驗(yàn)被用來尋找食物。社會(huì)信息在群體中是被共享的。

規(guī)則3 當(dāng)保持警覺時(shí)，每只鳥都會(huì)嘗試向鳥群的中心移動(dòng)，這些行為可能會(huì)受到干擾從而引起群之間的競(jìng)爭(zhēng)。警惕感更高的鳥比警惕感較低的鳥更可能靠近群體中心。

規(guī)則4 鳥群會(huì)定期飛到另一個(gè)棲息地。當(dāng)飛到另一個(gè)棲息地時(shí)，它們的選擇常常會(huì)于生產(chǎn)與乞討切換，能力最高的鳥是生產(chǎn)者而能力最低的鳥是乞討者。其他的鳥將在生產(chǎn)者與乞討者之間隨機(jī)選擇成為其中之一。

規(guī)則5 生產(chǎn)者會(huì)隨機(jī)尋找食物，而乞討者會(huì)隨機(jī)跟隨生產(chǎn)者去尋找食物。

將這些規(guī)則公式化，通過精確的數(shù)學(xué)模型開發(fā)出新的元啟發(fā)式算法。BSA的基本流程如圖1所示。

1.1 覓食行為

每只鳥根據(jù)自己的經(jīng)驗(yàn)和群體的經(jīng)驗(yàn)尋找食物，規(guī)則2被公式化如下：

(1)

為簡(jiǎn)單起見，規(guī)則1被公式化為一個(gè)隨機(jī)變量。如果一個(gè)范圍(0,1)且服從均勻分布的隨機(jī)數(shù)小于p,p∈(0,1),則鳥以這個(gè)恒定值覓食；否則，將繼續(xù)保持警惕。

圖1 BSA基本流程

1.2 警惕行為

規(guī)則3給出，鳥將嘗試移動(dòng)到鳥群中心，這就無法避免它們之間的相互競(jìng)爭(zhēng)。每只鳥不會(huì)直接移動(dòng)到鳥群中心，它們的運(yùn)動(dòng)行為可以表示如下：

(2)

(3)

(4)

其中：k(k≠i)是一個(gè)范圍為1～N的隨機(jī)正整數(shù)；a1、a2是 [0,2]范圍的正常數(shù)；pFiti表示第i只鳥的最好適應(yīng)度值；sumFit表示群體最好的適應(yīng)度值和；ε用來避免0分錯(cuò)誤，是計(jì)算機(jī)中最小的常數(shù)；meanj表示第j個(gè)元素在鳥群中的平均位置。

當(dāng)一只鳥向鳥群中心移動(dòng)時(shí)，它將無法避免與其他鳥之間的相互競(jìng)爭(zhēng)。為了簡(jiǎn)單起見，鳥群的平均適應(yīng)度值被認(rèn)為受每只鳥移動(dòng)向鳥群的中心時(shí)的間接影響。鑒于每只鳥都想移到鳥群中心的事實(shí)，A1的結(jié)果不應(yīng)超過1。A2在這里用來模擬鳥移向群中心時(shí)受到的特定干擾，如果第k只鳥的最好適應(yīng)度值優(yōu)于第i只鳥的適應(yīng)度值，則A2>a2，這意味著第i只鳥遭受的干擾比第k只鳥要大。即使它們的移動(dòng)是隨機(jī)性的、不可預(yù)測(cè)的，第k只鳥移向群中心的可能仍要比第i只鳥要大。在本文中，除非有特殊說明，越小的適應(yīng)度值代表越好的適應(yīng)度值。

1.3 飛行行為

鳥群為了躲避被捕食威脅會(huì)飛往另一個(gè)位置。當(dāng)?shù)竭_(dá)一個(gè)新的位置時(shí)，它們會(huì)重新尋找食物，一些鳥充當(dāng)生產(chǎn)者角色去搜索食物塊，而另一些鳥試圖享用被生產(chǎn)者發(fā)現(xiàn)的食物補(bǔ)丁。根據(jù)規(guī)則4，生產(chǎn)者和乞討者將會(huì)被群分離，生產(chǎn)者和乞討者的行為被公式化如下：

(5)

(6)

其中：rand是服從均值為0、標(biāo)準(zhǔn)差為1的高斯分布的隨機(jī)數(shù)，k∈[1,2,…,N]且k≠i；FL∈[0,2]表示乞討者會(huì)跟生產(chǎn)者尋找食物。

為簡(jiǎn)單起見，假設(shè)每一只鳥會(huì)以FQ的單位間隔飛到另一個(gè)地方，F(xiàn)Q是一個(gè)正整數(shù)。

2 一種改進(jìn)的鳥群優(yōu)化算法

2.1 模糊推理

本文利用文獻(xiàn)[20-21]中的經(jīng)典模糊推理，其形式如下：

(7)

2.2 慣性粒子

(8)

其中：

(9)

2.3 模糊推理機(jī)制

在文獻(xiàn)[20]中，利用3個(gè)參數(shù)nfi、αi和wi對(duì)算法進(jìn)行自適應(yīng)改變，其中nfi由以下公式得出：

(10)

利用表1～2對(duì)參數(shù)進(jìn)行調(diào)整。

得出Δαi和Δwi的類型后，再通過隸屬度函數(shù)得到對(duì)應(yīng)的模糊推理規(guī)則，見圖2、3。

表1 參數(shù)αi調(diào)整的模糊規(guī)則

表2 參數(shù)wi調(diào)整的模糊規(guī)則

圖2 Δαi的模糊推理規(guī)則

圖3 Δwi的模糊推理規(guī)則

2.4 鳥群更新公式的改進(jìn)

群覓食相對(duì)于憑感覺覓食可能會(huì)得到更多的信息，具有更好的生存優(yōu)勢(shì)和良好的覓食效率。如果一只鳥找到一些食物塊，其他的鳥可以共同享用。

(11)

(12)

(13)

在文獻(xiàn)[20]中，利用3個(gè)參數(shù)nfi、αi和wi對(duì)算法進(jìn)行自適應(yīng)改變，其中nfi由以下公式得出：

(14)

鳥類在覓食和保持警覺之間會(huì)隨機(jī)選擇，當(dāng)他們發(fā)現(xiàn)捕食者時(shí)會(huì)發(fā)出警報(bào)叫聲，一組的所有鳥會(huì)一起起飛。因此很容易總結(jié)出，群飛的鳥比單飛的鳥更有利于檢測(cè)到潛在的危險(xiǎn)。在許多鳥類中，以增加群體的規(guī)模來降低個(gè)體警惕已非常普遍。換言之，隨著組大小的增加，單只鳥可以花更多的時(shí)間去尋找食物，而受攻擊的影響不會(huì)增加。

飛行中乞討者的更新公式改變?nèi)缦拢?/p>

(15)

式(15)中：FL是自適應(yīng)的影響因子，當(dāng)?shù)螖?shù)增多時(shí)FL線性遞減。

(16)

式(16)中：FLmax和FLmin分別表示影響因子的最大值和最小值；tmax為最大迭代次數(shù)；ti為當(dāng)前迭代次數(shù)。

從以上可以看出：FL隨迭代次數(shù)的增加而減小，在算法前期生產(chǎn)者對(duì)乞討者的影響大，有利于增強(qiáng)乞討者的全局搜索能力；在算法后期，由于算法逐漸收斂，生產(chǎn)者對(duì)乞討者的影響減小，有利于增強(qiáng)乞討者的局部搜索能力。

2.5 混沌Gauss映射

為了使算法在迭代后期仍然具有較好的多樣性，本文采用混沌擾動(dòng)，設(shè)計(jì)算法1如下：

步驟1 隨機(jī)生成一個(gè)初始點(diǎn)x0，設(shè)最大混沌迭代次數(shù)為m，令m=1；

步驟2 令粒子數(shù)n=1；

步驟3 令維數(shù)d=1；

步驟4 根據(jù)Tent映射[22]混沌方程計(jì)算混沌序列xd，即

(17)

步驟5 對(duì)第n個(gè)支配解的第d維進(jìn)行混沌局部搜索

xid=xid+α·β·xd

(18)

步驟6 對(duì)超出邊界的粒子進(jìn)行處理；

步驟7d=d+1,如果d≤D,則轉(zhuǎn)步驟4；

步驟8n=n+1,如果n≤N,則轉(zhuǎn)步驟3；

步驟9 判斷新生成的解是否為最優(yōu)解；

步驟10m=m+1，如果m≤M，則轉(zhuǎn)步驟2；否則，結(jié)束搜索。

3 驗(yàn)證和比較

為了研究BSA的有效性、實(shí)用性和穩(wěn)定性，對(duì)表2中的6個(gè)測(cè)試函數(shù)進(jìn)行優(yōu)化。BSA的公式揭示了IBSA與著名的元啟發(fā)式算法BSA、CSO、TLBO之間的自然關(guān)系，同時(shí)將它們進(jìn)行對(duì)比。將案例研究統(tǒng)計(jì)結(jié)果用來分析BSA鳥群算法的優(yōu)越性。本文以問題的最小化為例，改進(jìn)的鳥群算法的基本步驟如下：

步驟1 初始化：設(shè)定種群中有N只鳥，在D維數(shù)空間中飛行，最大迭代次數(shù)為M。

步驟2 根據(jù)初始化條件隨機(jī)產(chǎn)生第一代粒子，求得第一代的每個(gè)粒子的最優(yōu)解(最強(qiáng)的鳥)和最差解(最弱的鳥)，則BSA的種群為：

步驟3 判斷：如果rand(0,1)

步驟4 保持飛行，求出全局最優(yōu)解和全局最差解坐標(biāo)，全局最優(yōu)解作為生產(chǎn)者以式(5)進(jìn)行覓食，全局最差解作為乞討者以式(15)跟隨生產(chǎn)者享用被生產(chǎn)者找到的食物補(bǔ)??；其他鳥將在生產(chǎn)者與乞討者之間隨機(jī)切換。

步驟5 利用算法1進(jìn)行混沌擾動(dòng)。

步驟6 評(píng)價(jià)產(chǎn)生新解的適應(yīng)度值，更新最優(yōu)解，偽代碼如下：

fori=1:N

if fitness(x(i,:))

y(i,:)=x(i,:);

end

end

fori=1:N

if fitness(y(i,:))

pg=y(i,:);

end

end

步驟7 終止準(zhǔn)則：如果達(dá)到終止條件，則輸出最優(yōu)解；否則返回步驟2。

測(cè)試函數(shù)見表3。所有算法迭代1 000次，獨(dú)立運(yùn)行100次。實(shí)驗(yàn)中使用同一臺(tái)計(jì)算機(jī)(3.2 GHz四核處理器，2國(guó)標(biāo)內(nèi)存，視窗7操作系統(tǒng)，Visual Studio 2010)。表4給出了各算法的相關(guān)參數(shù)值。

根據(jù)表5給出的結(jié)果發(fā)現(xiàn)：IBSA明顯優(yōu)于BSA和CSO，對(duì)于測(cè)試函數(shù)f1、f2、f3、f4、f6，PSO可能限于局部最優(yōu)解；對(duì)于f4和f5，BSA陷入局部解，在求解時(shí)BSA有可能過早收斂；在精度和穩(wěn)定性方面，IBSA可以產(chǎn)生比CSO和BSA更準(zhǔn)確和穩(wěn)定的結(jié)果，在f1、f2、f3、f4測(cè)試函數(shù)中，IBSA具有較好的精度，但是對(duì)于f5、f6，TLBO算法與IBSA精度相當(dāng)。

上述4種算法的精度和收斂性比較見圖4～6。在求解f2、f3、f4、f5、f6時(shí)相對(duì)于CSO、TLBO、BSA，IBSA顯著提高了收斂速度，減少了計(jì)算量，且未影響到結(jié)果的準(zhǔn)確性。與TLBO相比，BSA在解決除f5、f6以外的其他問題時(shí)也提高了收斂速度，但在解決f5、f6的問題時(shí)收斂速度略差于TLBO。

根據(jù)表5和圖4～6給出的結(jié)果進(jìn)行比較，發(fā)現(xiàn)IBSA在優(yōu)化精度、效率、穩(wěn)定性和收斂性等性能上優(yōu)于CSO、BSA。

表3 測(cè)試函數(shù)

表4 試驗(yàn)參數(shù)

表5 數(shù)值試驗(yàn)

注：以上數(shù)據(jù)是在維數(shù)100時(shí)由算法運(yùn)行30次得出的平均值。

圖4 四種算法對(duì) f1、 f2的收斂曲線

圖5 四種算法對(duì) f3、 f4的收斂曲線

圖6 四種算法對(duì) f5、 f6的收斂曲線

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

模擬自然界的特征來解決優(yōu)化問題是熱門的研究，受鳥群?jiǎn)l(fā)而設(shè)計(jì)的鳥群算法是一種新的解決優(yōu)化應(yīng)用問題的方法。鳥群主要有3種行為，分別是覓食行為、警惕行為和飛行行為，通過這些行為鳥群能夠在與其他個(gè)體進(jìn)行社會(huì)交往時(shí)獲得生存優(yōu)勢(shì)。

本文將模糊推理和慣性粒子引入鳥群算法，并改進(jìn)了乞討者的更新公式，使得算法的全局搜索能力和局部搜索能力增強(qiáng)。與CSO、TLBO、BSA進(jìn)行性能比較，6個(gè)基準(zhǔn)函數(shù)的試驗(yàn)比較結(jié)果表明IBSA比CSO、TLBO、BSA更加高效、穩(wěn)定和準(zhǔn)確。

參考文獻(xiàn)：

[1] KUO H C,LIN C H.A directed Genetic Algorithm for global optimization[J].Applied Mathematics and Computation,2013,14:7348-7364.

[2] DAS S,SUGANTHAN P N.Differential evolution:A survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation,2011,15:4-31.

[3] JIN X D.Solving constrained optimization problems using cultural algorithm and regional schemata[D].Detroit,MI:Wayne State University,2001.

[4] SMITH J E.Coevolving Memetic Algorithms:A review and progress report[J].IEEE Transaction on System,2007,1:6-17.

[5] JORDEHI A R,JASNI J.Parameter selection in particle swarm optimisation:A survey[J].Journal of Experimental & Theoretical Artificial Intelligence,2013,4:527-542.

[6] DORIGO M,STUTZLE T.Ant colony optimization[M].Cambridge,MA:MIT Press,2004.

[7] GAO X Z,WU Y,ZENGER K,et al.A knowledge-based artificial fish-swarm algorithm[C]//Proceedings of the 13th IEEE international conference on computational science and engineering.Hong Kong:IEEE Computer Society,2010:327-332.

[8] KARABOGA D,BASTURK B A.Powerful and efficient algorithm for numerical function optimization:Artificial bee colony (ABC) algorithm[J].Journal of Global Optimization,2007,3:459- 471.

[9] KRISHNANAND K N,GHOSE D.Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions[J].Swarm Intelligence,2009,3:87-124.

[10] YANG X S,DEB S.Cuckoo search:Recent advances and applications[J].Neural Computing & Applications,2014,24:169-174.

[11] YANG X S.A new metaheuristic bat-inspired algorithm[J].Computer Knowledge & Technology,2010:284,65-74.

[12] GANDOMI A H,ALAVI A H.Krill herd:A new bio-inspired optimization algorithm[J].Communications in Nonlinear Science Numerical Simulation,2012,17:4831- 4845.

[13] MENG X B,LIU Y,GAO X Z,et al.A new bio-inspired algorithm:chicken swarm optimization[C]//Proceedings of the 5th International Conference on Swarm Intelligence.Hefei:Springer International Publishing,2014:86-94．

[14] MENG X B,GAO X Z.A new bio-inspired optimisation algorithm:bird swarm optimization[J].Journal of Experomental & Theoretical Artificial Intelligence,2016(28):673-687.

[15] MEHRABIAN A R,LUCAS C.A novel numerical optimization algorithm inspired from weed colonization[J].Ecological Informatics,2006,1:355-366.

[16] YANG X S,KARAMANOGLU M,HE X S.Flower pollination algorithm:A novel approach for multiobjective optimization[J].Engineering Optimization,2014,46:1222-1237.

[17] MANJARRES D,LANDA-TORRES I.A survey on applications of the harmony search algorithm[J].Engineering Applications of Artificial Intelligence,2013,26:1818-1831.

[18] KAVEH A,TALATAHARI S.A novel heuristic optimization method:Charged system search[J].Acta Mechanica,2010,213:267-289.

[19] SHI Y H.Brain storm optimization algorithm[C]//Proceedings of 2th International Conference on Swarm Intelligence.Chongqing:IEEE Computational Intelligence Society,2011:303-309.

[20] WANG W J,LIN H R.Fuzzy control design for the trajectory tracking on uncertain nonlinear systems[J].IEEE Trans.Fuzzy Syst,1999,7:53-62.

[21] TENG Y W,WANG W J.Constructing a user-friendly Ga-based fuzzy system directly from numerical data[J].IEEE Trans Syst.Man Cybern Part B:Cybern,2004,34:2061-2070.

[22] LIU Bo,WANG Ling,JIN Yihui,et al.Improved particle swarm optimization combined with chaos[J].Chaos,Solitons Fractals,2005,25(5):1261-1271.