雙種群協同下帶混沌閃爍機制的螢火蟲算法研究

陳亞峰, 張曉明, 曹國清, 周澤彧, 戴波

(1.北京石油化工學院信息工程學院, 102617, 北京; 2.北京化工大學信息科學與技術學院, 100029, 北京)

螢火蟲算法(FA)作為一種比較新穎的仿生物智能優化算法,在科學研究和工程中逐漸得到廣泛應用,該算法擁有更高的尋優成功率、更強的可擴展性,更加適用于混合多參數的工程優化應用[1-5]。但是,螢火蟲算法在處理復雜模型時會出現早熟、收斂性慢等問題。針對這些問題,一些學者在該算法的基礎上進行了改進。Shadi等引入反收斂算子的概念同時也加強了種群之間的交互,使得算法的局部探索能力顯著提高,尤其體現在單模函數的尋優方面,但是算法對于多峰值函數尋優缺乏有效的應對措施[6]。Wang等針對螢火蟲算法運行過程中過早收斂的問題提出了基于光強差值修正的LFA算法,增強了算法的全局探索能力,降低了過早收斂的風險,表現出良好的適用性,但算法對種群的初始位置和參數的要求更為苛刻[7]。Gandomi等通過對螢火蟲算法中的多個初始變量進行混沌映射,使螢火蟲的種群多樣性和全局探索能力得到了加強,但是卻沒有對產生的原因給出合理解釋,同時算法在尋優精度方面也沒得到較大改善[8]。

本文就如何改善螢火蟲算法快速收斂、過早融合的矛盾和獲取全局搜索、局部探索的平衡展開了研究,提出了一種擁有多種群策略和混沌閃爍機制的新型螢火蟲算法。通過混沌閃爍機制不斷調制種群內吸引度大小,在提升收斂速度的同時避免了過早融合現象的產生;通過全局、局部種群的交互,解決了全局、局部搜索的平衡問題。

1　螢火蟲算法

1.1　基本算法

FA作為一種模仿螢火蟲種群內發光機制和運動行為的智能優化算法,其仿生學原理是將d維解空間中的坐標點看作自然界中的螢火蟲個體,將目標函數的適應度看作是螢火蟲的亮度,將尋優過程看成是螢火蟲之間的吸引過程,每個螢火蟲個體都在自己的搜索范圍內向比自己更亮螢火蟲移動,通過不斷對個體自身位置、亮度進行調整從而到達全局最優[1-2]。在基本螢火蟲算法中,空間的螢火蟲亮度與目標函數之間有近似的正比關系,并且存在亮度隨著距離的增加而弱化的過程,光強可定義為

I(r)=I0e-γr2

(1)

式中:I0為最大熒光亮度;γ為光強吸收因子;r為任意兩個螢火蟲之間的距離。

同時,螢火蟲的吸引度會根據其熒光亮度的變化而逐漸改變,定義吸引度參數為

β=β0e-γr2

(2)

式中:β0為最大吸引度因子。β在r=0時取值達到最大。在運動過程中,任意兩個螢火蟲xi、xj之間歐式距離可表示為

rij=‖xi-xj‖

(3)

螢火蟲在受到比自身更亮個體吸引時,位置的更新可表示為

(4)

式中:n為迭代次數;α為步長因子,取值與初始的探索范圍相關。α(r-0.5)為隨機擾動項,其目的是增強種群多樣性,防止過早收斂,陷入局部最優。

1.2　尋優過程分析

初始螢火蟲算法中,螢火蟲位置更新過程由個體特性之間的位置項、吸引項和種群特性之間的隨機項組成[9]。吸引項主要包含螢火蟲個體的相對位置信息、γ和β0,對于種群的收斂速度、個體的運動狀態起著至關重要的作用。但是,γ、β0通常被定為常數,這樣距離就成為吸引度大小的主導性影響因素,忽略了個體在運動過程中的自主性、智能性。對于一些復雜的多極值函數來說,螢火蟲算法本身就存在收斂速度慢的特點,且在算法運行過程中,種群一旦有融合趨勢,β會逐步收斂到最大,其他螢火蟲個體失去自主性,容易陷入局部最優。

在螢火蟲算法運行過程中,隨著α的增大,全局探索能力逐步增強,但是極有可能產生種群無法收斂的情況,而過小則會出現過早融合或是局部最優的現象。

1.3　FA吸引度分析

在對螢火蟲算法的研究中發現,種群間吸引力的大小對收斂速度有著至關重要的影響。算法運行過程中,隨著迭代次數的增加,種群內個體之間的距離逐漸縮小,β漸進增加到最大,最終維持收斂在β=β0,即

(5)

采用單模函數Sphere、多模函數Ackley進行測試,FA算法收斂曲線與吸引度的關系如圖1所示。由圖1可知:初始階段種群之間的β維持在較低的水平,螢火蟲個體的自主性、動力性較強,有較大的全局探索能力;中期階段,種群間的融合趨勢愈發明顯,每到達一個吸引力在0～1的上升期,收斂曲線急劇下降,種群偏向于更優處移動;收斂后期,吸引力維持在1處,種群急劇融合、漸進穩定,尋優值大致被確定。

在螢火蟲尋優過程中,β較大時,種群會偏向于融合;β較小時,個體保持有較強的自主性和動力性;當β在0～1的上升階段時,收斂曲線急劇下降,種群偏向于更優移動。為了使算法達到一個收斂更快、更優的過程,同時在快速收斂過程中保持種群內個體的部分自主性,減小早熟現象發生的概率,β應滿足如下規則:在最大迭代次數N內,吸引度應該盡可能維持在0～1隨機振蕩的過程。

(a)Sphere測試函數

(b)Ackley測試函數圖1　FA算法收斂曲線與吸引度的關系

2　基于雙種群協同和閃爍機制的螢火蟲算法

2.1　螢火蟲混沌閃爍機制

隨著混沌理論的研究與發展,混沌序列獨特的隨機性和高遍歷性已經逐步應用到圖像、加密、優化等問題中,基于混沌序列隨機性的高效搜索可以取代依賴于概率的隨機搜索。為了達到對吸引度進行混沌調制的效果,依據螢火蟲時亮時熄的閃爍機制,定義光強閃爍因子ξ,通過ξ不斷調制吸引度大小,使得β符合規則要求,即

ξ(n+1)=sin(πξ(n))

(6)

式中:n為迭代步數。初始值ξ0為(0,1)區間的任意實數,經過映射之后的ξ在0～1之間隨機震蕩,其中0代表熄滅,1代表最亮,可充分模擬螢火蟲時亮時熄的動態閃爍過程。

同時,為了使尋優過程中吸引度滿足在0至最大吸引度之間分布的要求,對原算法中吸引力項做出如下改進

β=ξβ0e-|ξ-γ|r2

(7)

分別對加入閃爍機制下的Flicker-FA算法進行單模、多模函數收斂性測試,測試效果如圖2所示。相比于原算法,閃爍因子的調制使得種群之間吸引度出現混沌波動現象,在初期簡短的探索之后快速向全局較優收斂,同時種群還保持有較強的個體探索能力,不斷嘗試向全局最優移動。由圖2可知,螢火蟲種群在達到快速收斂的同時,能夠降低早熟的風險。

(a)Sphere測試函數

(b)Ackley測試函數圖2　Flicker-FA算法收斂曲線與吸引度的關系

2.2　基于隨機項的改進

在螢火蟲算法中,引入隨機項是為了擴展種群的多樣性,其中α對種群的探索能力和尋優精度都有著較為重要的影響。α較大時,種群的全局探索能力較強,但可能造成無法收斂;α較小時,個體之間的移動距離較小,但是局部搜索能力可能更高。對參數做如下改進

(8)

式中:α0為初始步長因子。算法開始時的全局探索能力較強,隨著迭代次數的增加,步長因子會逐漸減小,算法將會轉向更為精細的局部搜索。

2.3　雙種群機制

根據自然界中生物種群之間存在多樣性,不同種群之間存在著自動調節、自動適應、協同進化的特點[10-11],對傳統的螢火蟲算法進行改進。在引入雙種群協同進化策略的同時保持算法中對隨機項的相關改進,形成雙種群協同下帶混沌閃爍機制的螢火蟲算法(DFFA)。

設置全局種群S1采用較大的初始步長因子α1,負責全局搜索;初始局部種群S2擁有更小的初始步長因子α2,使其具備更高的搜索精度,更快的搜索速度,能夠進行小范圍內最優位置的快速搜索。種群S1對種群S2起到指向性作用,在尋優的過程中,S1到達新的全局最優時,將會通過個體之間的信息傳遞,指導S2到達新的位置再進行局部搜索,從而提高搜索效率來平衡全局搜索與局部搜索。DFFA算法在開始時需要確定待優化函數,初始化各種群參數,迭代過程中需要不斷更新其閃爍因子,不斷改進隨機項,同時保持種群內交互和種群間交互,最終到達全局最優點,算法流程如圖3所示。

3　算法的性能分析和比較

通過對初始螢火蟲算法的針對性改進,改進后的DFFA算法能夠有效解決快速收斂于過早融合和全局搜索局部搜索的矛盾。為了驗證算法的普適性,采用經典單模、多模函數Benchmark對本文算法進行測試比較,實驗測試函數如表1所示。

Sphere、Schwefel、Rosenbrock均為單模函數,主要用于測量和驗證算法在計算過程中的收斂性快慢和局部探索能力。Schaffer、Ackley、Rastrigin是擁有多極值的高非線性多模函數,可用來測試算法的全局探索能力和對陷入局部最優的可抗性。為了簡化計算,對Benchmark中所有測試函數全部考慮在2維分布情況下來計算,全部測試函數都在(0,0)處取得全局最優值0。分別對算法進行全部6個測試函數的實驗,每個測試函數進行30組實驗,采用計算平均值的方法來獲取最終全局最優的收斂值,結果如表2所示。

為了更加直觀地觀察DFFA算法在測試實驗中的表現,在標準測試函數的基礎上,分別與PSO、FA、LFA、CFA算法進行相同規模和迭代次數下最佳適應度的比較,相關實驗參數如下[7-8]:PSO算法的種群規模為20,最大迭代次數為200,學習因子c1=c2=2,慣性權重w=1;FA算法的種群規模為20,最大迭代次數為200,γ=1,β0=1,α=0.2;LFA算法的種群規模為20,最大迭代次數為200,γ0=4,η1=0.3,η2=0.1;CFA算法的種群規模為20,最大迭代次數為200,γ=1,β0=1,α=0.2;DFFA算法的種群規模為20,最大迭代次數為200,γ=0.8,β0=0.8,ξ0=0.5,種群S1的α1=0.2,種群S2的α2=0.02。

圖3　算法流程圖

表1　實驗測試函數

表2　不同算法下全局最優值比較

由表2可知,對于單模測試函數來說,PSO、FA、LFA、CFA、DFFA算法都能夠保持良好的局部探索能力。以FA為代表的系列算法,相比于粒子群算法具有更高的尋優精度,并且DFFA算法達到最高;對于多模測試函數,各種算法所表現出的差異較大,LFA和CFA算法的全局探索能力相較于PSO和FA算法有較大的提升,但是并不穩定,只有DFFA算法在保持極強的全局探索能力的同時對陷入局部最優有一定的免疫能力。對于所有測試函數,DFFA算法無論在局部探索能力、全局探索能力都表現出極強的穩定性和優越性,相比于其他算法,收斂精度顯著提高,部分測試函數收斂精度提高了5、6個數量級以上。

圖4　Sphere函數下不同算的法收斂速度曲線

圖5　Schwefel函數下不同算法的收斂速度曲線

圖6　Rosenbrock函數下不同算法的收斂速度曲線

圖7　Schaffer函數下不同算法的收斂速度曲線

圖8　Ackley函數下不同算法的收斂速度曲線

圖9　Rastrigin函數下不同算法的收斂速度曲線

為了比較算法的收斂速度,采用函數評價次數策略(FEs),設置最大函數評價數為20 000。分別作出Benchmark下6個測試函數與各個算法之間的平均收斂速度曲線如圖4～9所示。由圖4～9可知,CFA、LFA算法對于單模測試函數Sphere、Schewfel、Rosenbrock在收斂速度上相較于初始算法都有較大提升,但是對于多模測試函數Schaffer、Ackley、Rastrigin收斂速度不夠穩定,甚至會陷入局部最優。在Schaffer測試函數中,FA、LFA、CFA都陷入了局部最優,出現了早熟收斂的問題,而DFFA算法有效解決了快速收斂和過早融合的矛盾,在所有單模和多模測試函數中都能達到最快收斂,同時避免局部最優的效果。

4　結　論

通過模仿螢火蟲個體不斷發光、熄滅的閃爍機制,在螢火蟲算法中引入閃爍因子ξ進行了相關修正,使種群間的吸引度在快速達到最大后保持了混沌的振蕩狀態,提高了種群間的收斂速度,同時也使種群間個體保持良好的動力性和自主性。在此基礎上,本文算法借助雙種群策略有效平衡了全局搜索和局部搜索,解決了現有的螢火蟲算法全局搜索和局部搜索不能兼顧、快速收斂和過早融合矛盾的問題,具有良好的應用前景。

參考文獻:

[1]YANG X S. Firefly algorithms for multimodal optimization [J]. Mathematics, 2009, 5792: 169-178.

[2]YANG X S. Firefly algorithm Levy flight and global optimization research and development intelligent system [M]. Berlin, Germany: Springer, 2010: 209-218.

[3]劉澤蒙, 張瑞, 張廣明. 基于離散螢火蟲算法的近紅外波長優選方法研究 [J]. 光譜學與光譜分析, 2016, 36(12): 3931-3936.

LIU Zemeng, ZHANG Rui, ZHANG Guangming. Wavelength variable s election method in near infrared spectroscopy based on discrete firefly algorithm [J]. Spectroscopy and Spectral Analysis, 2016, 36(12): 3931-3936.

[4]陳愷, 陳芳, 戴敏. 基于螢火蟲算法的二維熵多閾值快速圖像分割 [J]. 光學精密工程, 2014, 22(2): 517-523.

CHEN Kai, CHEN Fang, DAI Min. Fast image segmentation with multilevel threshold of two-dimensional entropy based on firefly algorithm [J]. Optics and Precision Engineering, 2014, 22(2): 517-523.

[5]武岳, 胡慶杰, 李清朋. 基于改進螢火蟲算法的桿系結構拓撲優化 [J]. 建筑結構學報, 2016, 37(6): 46-52.

WU Yue, HU Qingjie, LI Qingpeng. Topology optimization for truss structures based on improved firefly algorithm [J]. Journal of Building Structures, 2016, 37(6): 46-52.

[6]FARAHANI S M, NASIRI B, MEYBODI M R. A multiswarm based firefly algorithm in dynamic environments [C]∥IEEE Conference on Signal Processing Systems. Piscataway, NJ, USA: IEEE, 2011: 68-72.

[7]WANG B, LI D X, JIANG J P, et al. A modified firefly algorithm based on light intensity difference [J]. Journal of Combinatorial Optimization, 2016, 31(3): 1045-1060.

[8]GANDOMI A H, YANG X S, TALATAHARI S. Firefly algorithm with chaos [J]. Communications in Nonlinear Science and Numerical Simulation, 2013, 18(1): 89-98.

[9]劉暢, 劉利強, 張麗娜. 改進螢火蟲算法及其在全局優化問題中的應用 [J]. 哈爾濱工程大學學報, 2017, 38(4): 569-577.

LIU Chang, LIU Liqiang, ZHANG Lina. A Improved firefly algorithm for global optimization [J]. Journal of Harbin Engineering University, 2017, 38(4): 569-577.

[10] 張勇, 夏長紅, 鞏敦衛, 等. 基于多種群協同微粒群優化的流數據聚類算法 [J]. 控制與決策, 2016, 31(10): 1879-1883.

ZHANG Yong, XIA Changhong, GONG Dunwei, et al. Streaming data clustering using cooperative particle swarm optimization [J]. Control and Decision, 2016, 31(10): 1879-1883.

[11] 郭森, 秦貴和, 張晉東. 多目標車輛路徑問題的粒子群優化算法研究 [J]. 西安交通大學學報, 2016, 50(9): 97-104.

GUO Sen, QIN Guihe, ZHANG Jindong. Study on particle swarm optimization algorithm for multi-objective vehicle routing problem [J]. Journal of Xi’an Jiaotong University, 2016, 50(9): 97-104.

[本刊相關文獻鏈接]

張喆,達新宇,劉慧軍,等.衛星混合載波混沌相位擾碼安全傳輸方案.2017,51(12):42-48.[doi:10.7652/xjtuxb201712 007]

張亮修,王宇,吳光強,等.汽車阻尼可調半主動懸架混雜模型預測控制.2017,51(11):156-164.[doi:10.7652/xjtuxb 201711022]

周亞東,陳凱悅,冷俊園,等.軟件定義網絡流表溢出脆弱性分析及防御方法.2017,51(10):53-58.[doi:10.7652/xjtuxb 201710009]

趙龍海,沙學軍.多輸入多輸出單載波頻分多址系統的魯棒波束賦形算法.2017,51(8):53-58.[doi:10.7652/xjtuxb 201708009]

李石磊,劉崇新,胡曉宇,等.用于保密通信的高安全性混沌振蕩器.2017,51(6):35-40.[doi:10.7652/xjtuxb201706006]

王延緯,劉凡,丁濤,等.含多分區電力系統能量備用實時優化調度的動態積極集求解算法.2017,51(4):45-52.[doi:10。7652/xjtuxb201704007]

程市,黃斌科,師振盛.一種分析微帶線隨機參數敏感性的多項式混沌展開方法.2016,50(12):121-127.[doi:10.7652/xjtuxb201612019]

朱正倉,趙季紅,唐睿,等.移動中繼協助下終端直通中的模式選擇和資源分配方案.2016,50(10):111-117.[doi:10.7652/xjtuxb201610017]

趙博選,高建民,陳琨.求解多目標柔性作業車間調度問題的兩階段混合Pareto蟻群算法.2016,50(7):145-151.[doi:10.7652/xjtuxb201607022]

劉岳鐳,馮祖仁,任曉棟.具有惡化效應的雙代理單機最優調度算法.2016,50(6):9-14.[doi:10.7652/xjtuxb201606002]

陸建濤,成瑋,訾艷陽,等.結合改進粒子群的非線性盲源分離方法研究.2016,50(6):15-22.[doi:10.7652/xjtuxb201606 003]

賀王鵬,訾艷陽,陳彬強.沖擊特征受控極小化通用稀疏表示及其在機械故障診斷中的應用.2016,50(4):94-99.[doi:10.7652/xjtuxb201604015]

劉香浪,張英杰,李云龍,等.面向低碳制造的切削液供給系統優化研究.2016,50(2):91-97.[doi:10.7652/xjtuxb2016 02016]

翟永惠,吳江,王鼎.采用時延估計的外輻射源雷達雜波抑制算法.2015,49(12):47-52.[doi:10.7652/xjtuxb201512008]

滿興博,伍曉紅,孫清.采用非線性Galerkin方法的柔性梁模型降階研究.2015,49(7):113-119.[doi:10.7652/xjtuxb2015 07019]

吳一全,孟天亮,吳詩婳.人工蜂群優化的非下采樣Shearlet域引導濾波圖像增強.2015,49(6):39-45.[doi:10.7652/xjtuxb201506007]

龐霞,劉凌,劉崇新,等.利用異結構同步對鐵磁混沌電路的非線性反饋控制.2015,49(4):18-23.[doi:10.7652/xjtuxb 201504004]