一種改進的鳥群優化算法

史旭棟，高岳林

(1.寧夏大學 數學統計學院， 銀川 750021; 2.北方民族大學 信息與系統科學研究所， 銀川 750021)

現實世界的優化問題包括連續、離散、線性、非線性、非光滑或非凸等不同類別的優化問題。連續可微的問題可以用傳統的方法解決，如共軛梯度法；若遇到非常復雜的問題，如非凸或是不可微，則通過傳統的方法可能無法有效地解決，盡管仍有方法可以解決那些復雜的問題，但在可容忍的計算量上有可能得不到最佳的結果。例如，在一個可容忍的時間內，傳統的方法不能解決NP問題。

元啟發式方法作為一種替代傳統的方法，在可容忍的時間內，其優勢是對于非凸又不可微的問題能找到可接受的解決方案。近年來，自然元啟發式算法引起了研究者們極大的關注。

人類學習和設計新的元啟發式算法的靈感來自于自然進化和生物系統的抽象。隨著研究的深入，遺傳算法(genetic algorithm,GA)[1]、差分進化算法(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]、雞群優化算法(chicken swarm optimization,CSO)[13]和鳥群優化算法(bird swarm algorithm,BSA)[14]等算法的靈感來自于社會動物的群體智能。靈感來自于植物的算法有雜草算法(invasive weed optimization,IWO)[15]、花授粉算法(flower pollination algorithm,FPA)[16]。而聲搜索算法(harmony search,HS)[17]、 收費系統搜索算法(charged system search,CSS)[18]、頭腦風暴算法(brain storm optimization,BSO)[19]等算法的提出則受物理原理和自然現象的啟發。目前許多算法的開發是用來處理優化應用問題，尚不存在通用的算法。尋找更有效的算法的研究仍在繼續。

1 基本的BSA算法

自然界中許多鳥類是群居的，例如雀。它們可能成群結隊地居住、覓食、飛行。這些類似分離、隊列、內聚等的行為被看作是自然發生且形成簡單規則的行為。通過最簡單的社會互動，群體行為可以發展成復雜的運動和相互作用。

鳥群的社會行為可以通過一些理想化的規則簡化如下：

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

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

規則3 當保持警覺時，每只鳥都會嘗試向鳥群的中心移動，這些行為可能會受到干擾從而引起群之間的競爭。警惕感更高的鳥比警惕感較低的鳥更可能靠近群體中心。

規則4 鳥群會定期飛到另一個棲息地。當飛到另一個棲息地時，它們的選擇常常會于生產與乞討切換，能力最高的鳥是生產者而能力最低的鳥是乞討者。其他的鳥將在生產者與乞討者之間隨機選擇成為其中之一。

規則5 生產者會隨機尋找食物，而乞討者會隨機跟隨生產者去尋找食物。

將這些規則公式化，通過精確的數學模型開發出新的元啟發式算法。BSA的基本流程如圖1所示。

1.1 覓食行為

每只鳥根據自己的經驗和群體的經驗尋找食物，規則2被公式化如下：

(1)

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

圖1 BSA基本流程

1.2 警惕行為

規則3給出，鳥將嘗試移動到鳥群中心，這就無法避免它們之間的相互競爭。每只鳥不會直接移動到鳥群中心，它們的運動行為可以表示如下：

(2)

(3)

(4)

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

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

1.3 飛行行為

鳥群為了躲避被捕食威脅會飛往另一個位置。當到達一個新的位置時，它們會重新尋找食物，一些鳥充當生產者角色去搜索食物塊，而另一些鳥試圖享用被生產者發現的食物補丁。根據規則4，生產者和乞討者將會被群分離，生產者和乞討者的行為被公式化如下：

(5)

(6)

其中：rand是服從均值為0、標準差為1的高斯分布的隨機數，k∈[1,2,…,N]且k≠i；FL∈[0,2]表示乞討者會跟生產者尋找食物。

為簡單起見，假設每一只鳥會以FQ的單位間隔飛到另一個地方，FQ是一個正整數。

2 一種改進的鳥群優化算法

2.1 模糊推理

本文利用文獻[20-21]中的經典模糊推理，其形式如下：

(7)

2.2 慣性粒子

(8)

其中：

(9)

2.3 模糊推理機制

在文獻[20]中，利用3個參數nfi、αi和wi對算法進行自適應改變，其中nfi由以下公式得出：

(10)

利用表1～2對參數進行調整。

得出Δαi和Δwi的類型后，再通過隸屬度函數得到對應的模糊推理規則，見圖2、3。

表1 參數αi調整的模糊規則

表2 參數wi調整的模糊規則

圖2 Δαi的模糊推理規則

圖3 Δwi的模糊推理規則

2.4 鳥群更新公式的改進

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

(11)

(12)

(13)

在文獻[20]中，利用3個參數nfi、αi和wi對算法進行自適應改變，其中nfi由以下公式得出：

(14)

鳥類在覓食和保持警覺之間會隨機選擇，當他們發現捕食者時會發出警報叫聲，一組的所有鳥會一起起飛。因此很容易總結出，群飛的鳥比單飛的鳥更有利于檢測到潛在的危險。在許多鳥類中，以增加群體的規模來降低個體警惕已非常普遍。換言之，隨著組大小的增加，單只鳥可以花更多的時間去尋找食物，而受攻擊的影響不會增加。

飛行中乞討者的更新公式改變如下：

(15)

式(15)中：FL是自適應的影響因子，當迭代次數增多時FL線性遞減。

(16)

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

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

2.5 混沌Gauss映射

為了使算法在迭代后期仍然具有較好的多樣性，本文采用混沌擾動，設計算法1如下：

步驟1 隨機生成一個初始點x0，設最大混沌迭代次數為m，令m=1；

步驟2 令粒子數n=1；

步驟3 令維數d=1；

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

(17)

步驟5 對第n個支配解的第d維進行混沌局部搜索

xid=xid+α·β·xd

(18)

步驟6 對超出邊界的粒子進行處理；

步驟7d=d+1,如果d≤D,則轉步驟4；

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

步驟9 判斷新生成的解是否為最優解；

步驟10m=m+1，如果m≤M，則轉步驟2；否則，結束搜索。

3 驗證和比較

為了研究BSA的有效性、實用性和穩定性，對表2中的6個測試函數進行優化。BSA的公式揭示了IBSA與著名的元啟發式算法BSA、CSO、TLBO之間的自然關系，同時將它們進行對比。將案例研究統計結果用來分析BSA鳥群算法的優越性。本文以問題的最小化為例，改進的鳥群算法的基本步驟如下：

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

步驟2 根據初始化條件隨機產生第一代粒子，求得第一代的每個粒子的最優解(最強的鳥)和最差解(最弱的鳥)，則BSA的種群為：

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

步驟4 保持飛行，求出全局最優解和全局最差解坐標，全局最優解作為生產者以式(5)進行覓食，全局最差解作為乞討者以式(15)跟隨生產者享用被生產者找到的食物補丁；其他鳥將在生產者與乞討者之間隨機切換。

步驟5 利用算法1進行混沌擾動。

步驟6 評價產生新解的適應度值，更新最優解，偽代碼如下：

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 終止準則：如果達到終止條件，則輸出最優解；否則返回步驟2。

測試函數見表3。所有算法迭代1 000次，獨立運行100次。實驗中使用同一臺計算機(3.2 GHz四核處理器，2國標內存，視窗7操作系統，Visual Studio 2010)。表4給出了各算法的相關參數值。

根據表5給出的結果發現：IBSA明顯優于BSA和CSO，對于測試函數f1、f2、f3、f4、f6，PSO可能限于局部最優解；對于f4和f5，BSA陷入局部解，在求解時BSA有可能過早收斂；在精度和穩定性方面，IBSA可以產生比CSO和BSA更準確和穩定的結果，在f1、f2、f3、f4測試函數中，IBSA具有較好的精度，但是對于f5、f6，TLBO算法與IBSA精度相當。

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

根據表5和圖4～6給出的結果進行比較，發現IBSA在優化精度、效率、穩定性和收斂性等性能上優于CSO、BSA。

表3 測試函數

表4 試驗參數

表5 數值試驗

注：以上數據是在維數100時由算法運行30次得出的平均值。

圖4 四種算法對 f1、 f2的收斂曲線

圖5 四種算法對 f3、 f4的收斂曲線

圖6 四種算法對 f5、 f6的收斂曲線

4 結束語

模擬自然界的特征來解決優化問題是熱門的研究，受鳥群啟發而設計的鳥群算法是一種新的解決優化應用問題的方法。鳥群主要有3種行為，分別是覓食行為、警惕行為和飛行行為，通過這些行為鳥群能夠在與其他個體進行社會交往時獲得生存優勢。

本文將模糊推理和慣性粒子引入鳥群算法，并改進了乞討者的更新公式，使得算法的全局搜索能力和局部搜索能力增強。與CSO、TLBO、BSA進行性能比較，6個基準函數的試驗比較結果表明IBSA比CSO、TLBO、BSA更加高效、穩定和準確。

參考文獻：

[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.