耿艷香，張立毅，孫云山，費?騰，蔣師賢，馬嘉駿

?

基于RNA遺傳操作的改進蝙蝠算法

耿艷香1, 2，張立毅1, 2，孫云山2，費?騰2，蔣師賢2，馬嘉駿2

(1. 天津大學電氣自動化與信息工程學院，天津 300072；2. 天津商業(yè)大學信息工程學院，天津 300134)

蝙蝠算法作為一種新型的元啟發(fā)式算法，具有優(yōu)越的尋優(yōu)能力和廣泛的應用空間，同時也存在著收斂速度和精度的制約問題及個體之間欠缺交互等問題，針對這些不足，引入了RNA遺傳算法增強個體之間的交流，通過信息的交叉和變異等變化措施，加快了算法的搜索能力，提高了搜索精度. 通過測試函數(shù)驗證了改進后的算法具有較好的收斂精度、可靠性和穩(wěn)定性，大大提升了蝙蝠算法的尋優(yōu)能力.

蝙蝠算法；RNA遺傳；交叉；變異

智能仿生算法做為新興的智能優(yōu)化算法，是解決函數(shù)優(yōu)化[1]、路徑搜索[2]、數(shù)據(jù)分析[3]等問題的有效手段．近年來學者們提出了多種新型智能仿生算法，典型代表有魚群算法[4]、粒子群算法[5]、蟻群算法[6]、蜂群算法[7]，并在多個領域得到較好的應用．

2010年，劍橋大學的Yang教授[8]根據(jù)蝙蝠自身的回聲定位能力，提出一種新型的智能仿生算法——蝙蝠算法．蝙蝠在飛行過程中發(fā)出不同頻率的超聲波，經(jīng)過物體反射后，根據(jù)反饋信息調(diào)整飛行策略．盛孟龍等[9]通過對蝙蝠算法的全局收斂性分析驗證，得出該算法無法確保全局收斂的結論，因此對蝙蝠算法提出有效的改進是有必要的．李雅梅等[10]運用Powell機制改進蝙蝠算法，將傳統(tǒng)的Powell算法作為一種局部搜索算子，嵌入到蝙蝠算法中，提高蝙蝠算法的局部搜索能力．屈遲文等[11]將入侵雜草算法的生長繁殖、空間擴散和競爭機制引入蝙蝠算法，增加了蝙蝠算法的局部搜索能力．尚俊娜等[12]提出的具有自學習能力和個體變異的蝙蝠算法，彌補了算法高維弱勢的缺陷．RNA遺傳算法[13]是受到生物RNA分子編碼和變異方式的啟發(fā)，模擬生物分子進化的智能仿生算法．其特有的單鏈分子結構，大大降低了計算的成本，通過交叉、變異、頸環(huán)等分子間的變換，個體間的交流增大，擾動性加強，有利于全局尋優(yōu)能力的增強[14]．受到這一啟發(fā)，本文針對蝙蝠算法收斂精度低、易于陷入局部最優(yōu)的缺點，提出利用RNA算法增加蝙蝠個體之間的聯(lián)系，動態(tài)改變種群規(guī)模，加大擾動力度，使搜索更為全面，達到快速的收斂能力．

1?基于RNA遺傳操作的改進蝙蝠算法

在覓食過程中，蝙蝠依靠精準的回聲定位能力，能夠快速地找到并捕獲獵物，基于這種原理模擬出具有生物學機理的蝙蝠算法[15]．

1.1?蝙蝠算法的概述

文獻[8]中，Yang教授歸納的數(shù)學模型為

?(1)

?(2)

?(3)

局部搜索過程中，位置的更新公式為

?(4)

?(5)

?(6)

1.2?RNA遺傳操作與蝙蝠算法的結合

隨著現(xiàn)代生物技術的發(fā)展，提出了使用生物分子作為計算載體的求解實際問題的方法，經(jīng)過研究發(fā)現(xiàn)具備相同遺傳特性的單鏈RNA結構更有利于信息的計算[16]．本文通過RNA算法與蝙蝠算法相結合的方式，利用RNA算法極強的變異性和擾動性，拓展蝙蝠算法的搜索空間，加快了算法前期的收斂速度，提高了收斂精度．

RNA分子是由4種堿基構成的：腺嘌呤(A)、尿嘧啶(U)、鳥嘌呤(G)和胞嘧啶(C)．4種堿基配對互補的原則為：腺嘌呤和尿嘧啶配對，鳥嘌呤和胞嘧啶配對．本文用到的RNA計算方法[17]如下．

圖1?交叉操作

圖2?變異操作

圖3?頸環(huán)操作

對需要變異的蝙蝠個體的位置信息進行編碼，將編碼后的位置信息按照RNA算法的交叉、變異、頸環(huán)操作進行變換，得到新的位置信息編碼，再反變換回位置信息傳遞給子代．

2?基于RNA遺傳操作的改進蝙蝠算法

步驟2 啟動蝙蝠進行隨機搜索，每個蝙蝠進行一次尋優(yōu)計算，記錄下各個蝙蝠的尋優(yōu)結果，找出當前最優(yōu)解．

步驟3 將每只蝙蝠的尋優(yōu)結果按照從小到大排序，取前1/4的蝙蝠個體進行保留．

步驟4 開始迭代計算．將上一步保留的蝙蝠個體進行自身變異，檢測變異后的蝙蝠是否超界，超界蝙蝠用臨界值替代，將變異后的蝙蝠與上一代保留的蝙蝠合并恢復至原種群數(shù)量的1/2．

步驟5 將現(xiàn)有種群進行RNA交叉、變異、頸環(huán)操作，檢測變異后蝙蝠是否越界，超界蝙蝠用臨界值替代，將變異后的蝙蝠與上一步的蝙蝠合并恢復至原種群數(shù)量，形成新一代蝙蝠種群．

步驟6 啟動新種群進行最優(yōu)化搜索，每個蝙蝠進行一次尋優(yōu)計算，記錄下各個蝙蝠的尋優(yōu)結果，更新當前最優(yōu)解．

步驟7 判斷是/否完成迭代次數(shù)，“是”則執(zhí)行步驟8，“否”則跳轉至步驟3繼續(xù)執(zhí)行，迭代次數(shù)加1．

步驟8 結束算法，輸出最優(yōu)結果．

3?算法測試

為了證明基于RNA改進的蝙蝠算法性能，選取6個標準測試函數(shù)進行Matlab仿真．測試函數(shù)如表1所示．

表1?測試函數(shù)

Tab.1?Test function

表1中6種測試函數(shù)驗證RNA優(yōu)化蝙蝠算法的性能，通過搜索精度、算法可靠性和穩(wěn)定性來直觀的分析算法優(yōu)化的性能．

算法的搜索精度通過合理的迭代次數(shù)后，算法尋找到的最優(yōu)解、最差解和平均解來表征．算法的可靠性可以通過算法的成功率很好的表征，算法的成功率則是指在設定好的閾值下，算法達到標準的次數(shù)與總運行次數(shù)的比值．算法的收斂速度則是通過算法的平均收斂代數(shù)來表征的．算法的穩(wěn)定性是通過標準差和相對誤差來表征的．相對誤差最佳性能比是指算法找到的最優(yōu)解和理論最優(yōu)解的差的絕對值與理論最優(yōu)解的比值．

3.1?使用Sphere函數(shù)測試

表2?Sphere測試函數(shù)的運行結果統(tǒng)計

表3?各算法的穩(wěn)定性和可靠性統(tǒng)計

由表2和表3以及圖4可以分析出RNA蝙蝠算法與文獻[17]算法在各方面均優(yōu)于普通蝙蝠算法，雖然文獻[17]算法的搜索精度略高于RNA蝙蝠算法，但RNA算法的穩(wěn)定性高于文獻[17]算法．

圖4 各算法對Sphere測試函數(shù)的收斂曲線比較

3.2?使用Schaffer函數(shù)測試

表4?Schaffer測試函數(shù)的運行結果統(tǒng)計

Tab.4?Statistical results of the Schaffer test function

表5?各算法的穩(wěn)定性和可靠性統(tǒng)計

Tab.5 Stability and reliability statistics of the Schaffer test function

由表4、表5和圖5可以分析出，RNA蝙蝠算法與文獻[17]算法二者在尋優(yōu)精度以及算法可靠性上基本相同．但RNA蝙蝠算法的穩(wěn)定性(標準方差)優(yōu)于文獻[17]算法，除此以外RNA蝙蝠算法的成功率也高于文獻[17]算法和基本蝙蝠算法．

圖5?各算法對Schaffer測試函數(shù)的收斂曲線比較

3.3?使用Rastrgrin函數(shù)測試

表6?Rastrgrin測試函數(shù)的運行結果統(tǒng)計

Tab.6?Statistical results of the Rastrgrin test function

表7?各算法的穩(wěn)定性和可靠性統(tǒng)計

Tab.7 Stability and reliability statistics of the Rastrgrin test function

由表6、表7和圖6可以分析出，RNA蝙蝠算法與文獻[17]算法二者在穩(wěn)定性方面相同，但RNA蝙蝠算法在搜索精度以及成功率上要好于文獻[17]中的算法．除此以外RNA蝙蝠算法的收斂速度以及收斂精度都要高于普通蝙蝠算法．

圖6?各算法對Rastrgrin測試函數(shù)的收斂曲線比較

3.4?使用Ackley函數(shù)測試

表8?Ackley測試函數(shù)的運行結果統(tǒng)計

Tab.8?Statistical results of the Ackley test function

表9?各算法的穩(wěn)定性和可靠性統(tǒng)計

Tab.9 Stability and reliability statistics of the Ackley test function

由表8、表9和圖7可以分析出，RNA蝙蝠算法在各項數(shù)據(jù)上均高于基本蝙蝠算法與文獻[18]算法．在收斂精度方面，RNA蝙蝠算法遠超基本蝙蝠算法和文獻[18]算法，穩(wěn)定性也強于基本蝙蝠算法與文獻[18]算法．

圖7?各算法對測試函數(shù)Ackley的收斂曲線比較

3.5?使用Griewank函數(shù)測試

表10?Griewank測試函數(shù)的運行結果統(tǒng)計

Tab.10?Statistical results of the Griewank test function

表11?各算法的穩(wěn)定性和可靠性統(tǒng)計

由表10、表11和圖8可以分析出，RNA蝙蝠算法與文獻[18]算法二者在成功率上相同且均高于基本蝙蝠算法，但在算法穩(wěn)定性方面還是RNA蝙蝠算法更強一些，此外雖然基本蝙蝠算法的收斂速度略高于RNA蝙蝠算法，但收斂精度遠低于RNA蝙蝠?算法．

圖8?各算法對Griewank測試函數(shù)的收斂曲線比較

3.6?使用Rosebrock函數(shù)測試

表12?Rosebrock測試函數(shù)的運行結果統(tǒng)計

Tab.12?Statistical results of the Rosenbrock test function

表13?各算法的穩(wěn)定性和可靠性統(tǒng)計

Tab.13 Stability and reliability statistics of the Rosen-brock test function

由表12、13和圖9可以分析出文獻[18]算法在算法的可靠性上略好于RNA蝙蝠算法，但RNA算法的搜索精度要高于文獻[18]算法．在算法穩(wěn)定性方面二者相似，文獻[18]算法穩(wěn)定性略高．

圖9?各算法對Rosebrock測試函數(shù)的收斂曲線比較

4?結?語

蝙蝠算法是一種新型智能仿生算法．該算法由Yang教授提出，是一種搜索全局最優(yōu)解的有效算法，該算法在準確性和有效性等方面優(yōu)于其他算法．但算法也存在著一些局限性，在受到局部極限約束后將無法擺脫，因而很難跳出局部最優(yōu)解，本文提出的RNA蝙蝠算法針對這一問題對蝙蝠算法進行改進，運用RNA遺傳算法的各種變異策略增加蝙蝠算法的擾動性，加大蝙蝠之間的交流，經(jīng)過實驗證明，算法可以快速找到最優(yōu)解，避免在局部最優(yōu)解附近進行大量計算浪費工作效率．

［1］ Hamidzadeh J. Weighted support vector data description based on chaotic bat algorithm[J]. Impact Factor，2017，60(3)：550-553.

［2］ Chaib L，Choucha A. Optimal design and tuning of novel fractional order PID power system stabilizer using a new metaheuristic bat algorithm[J]. Ain Shams Engineering Journal，2015，8(2)：113-120.

［3］ Chakri A，Khelif R. New directional bat algorithm for continuous optimization problems[J]. Expert Systems with Applications，2017，69：159-175.

［4］ Ahmadianfar I，IAdibA. Optimizing multireservoir operation：Hybrid of bat algorithm and differential evolution[J]. Journal of Water Resoures Planning and Management，2016，142(2)：25-27.

［5］ Chen Meiwen，Zhong Yiwen，Wang Lijin，et al. Bat algorithm with one-dimension learning[J]. Journal of Chinese Computer Systems，2015，36(11)：2614-2616.

［6］ 吳華鋒，陳信強，毛奇凰，等. 基于自然選擇策略的蟻群算法求解TSP問題[J]. 通信學報，2013，34(4)：166-170.

Wu Huafeng，Chen Xinqiang，Mao Qihuang，et al. Natural selection of ant colony algorithm for solving TSP problems[J]. Journal of Communication Strategy，2013，34(4)：166-170(in Chinese).

［7］ 秦全德，程?適，李?麗，等. 人工蜂群算法研究綜述[J]. 智能系統(tǒng)學報，2014，9(2)：127-135.

Qin Quande，Cheng Shi，Li Li，et al. An overview of artificial bee colony algorithms[J]. Journal of Intelligent Systems，2014，9(2)：127-135(in Chinese).

［8］ Yang X S. A new meta heuristic bat-inspired algorithm[J]. Nature Inspired Cooperative Strategies for Optimization，2010：65-74.

［9］ 盛孟龍，賀興時，丁文靜. 蝙蝠算法的全局收斂性分析[J]. 紡織高?；A科學學報，2013， 26(4)：543-547.

Sheng Menglong，He Xingshi，Ding Wenjing. Analysis of bat algorithm’s global convergence[J]. Basic Sciences Journal of Textile Universities，2013，26(4)：543-547(in Chinese).

［10］ 李雅梅，曹益華. 基于Powell機制的改進蝙蝠算法[J]. 微電子學與計算機，2015，32(3)：73-80.

Li Yamei，Cao Yihua. An improved bat algorithm based on powell mechanism[J]. Microelectronics & Com-puter，2015，32(3)：73-76(in Chinese).

［11］ 屈遲文，傅彥銘，侯勇順. 融合入侵雜草算子的蝙蝠算法[J]. 計算機應用與軟件，2015，32(4)：243-246.

Qu Chiwen，F(xiàn)u Yanming，Hou Yongshun. Bat algorithm fused with invasive weed operator[J]. Computer Applications and Software，2015，32(4)：243-246(in Chinese).

［12］ 尚俊娜，劉春菊，岳克強，等. 具有自學習能力的變異蝙蝠優(yōu)化算法及性能仿真[J]. 系統(tǒng)仿真學報，2017，29(2)：301-308.

Shang Junna，Liu Chunju，Yue Keqiang，et al. Variation bat algorithm with self-learning capability and its property analysis[J]. Journal of System Simulation，2017，29(2)：301-308(in Chinese).

［13］ Tao Jili，Wang Ning. DNA computing based RNA genetic algorithm with applications in parameter estimation of chemical engineering processes[J]. Computers and Chemical Engineering，2017，31(12)：1602-1618.

［14］ Wang Kangtai，Wang Ning. A novel RNA genetic algorithm for parameter estimation of dynamic systems[J]. Chemical Engineering Research and Design，2010，88(11)：1485-1493.

［15］ 肖輝輝，段艷明. 基于DE算法改進的蝙蝠算法的研究及應用[J]. 計算機仿真學報，2014， 3(1)：272-301.

Xiao Huihui，Duan Yanming. Research and application of improved bat algorithm based on DE algorithm[J]. Journal of Computer Simulation，2014，31(1)：272-301(in Chinese).

［16］ 羅?亮，吳文峻，張?飛. 面向云計算數(shù)據(jù)中心的能耗建模方法[J]. 軟件學報，2014，25(7)：1371-1387.

Luo Liang，Wu Wenjun，Zhang Fei. Modeling method of energy consumption for cloud computing data center[J]. Software Journal，2014，25(7)：1371-1387(in Chinese).

［17］ 肖輝輝. 基于單純形法的蝙蝠算法[J]. 河池學院學報，2016，36(2)：60-66.

Xiao Huihui. Bats algorithm based on simplex method [J]. Journal of Hechi University，2016，36(2)：60-66(in Chinese).

［18］ 岳偉娜，馬吉明，蘇日建，等. 基于反向學習機制的蝙蝠算法[J]. 湖北民族學院學報：自然科學版，2016，34(3)：251-255.

Yue Weina，Ma Jiming ，Su Rijian，et al. Reverse learning mechanism based on bat algorithm[J]. Journal of Hubei Institute for Nationalities：Natural Science Edition，2016，34(3)：251-255(in Chinese).

(責任編輯：王曉燕)

Improved Bat Algorithm Based on RNA Genetic Algorithm

Geng Yanxiang1, 2，Zhang Liyi1, 2，Sun Yunshan2，F(xiàn)ei Teng2，Jiang Shixian2，Ma Jiajun2

1. School of Electrical and Information Engineering，Tianjin University，Tianjin 300072，China；2. School of Information Engineering，Tianjin University of Commerce，Tianjin 300134，China)

As a new metaheuristic algorithm，the bat algorithm has excellent search capability and can be applied to a variety of scenarios. However，the bat algorithm has problems with regard to its convergence rate and precision and the lack of interaction between individuals. In response to these deficiencies，the RNA genetic algorithm was introduced to enhance the interaction between individuals. Through the change of information，such as crossover and mutation，the search speed and precision of the algorithm can be improved. The test functions proved that the improved algorithm has good robustness，reliability and stability，which considerably improve the search capability of the bat algorithm.

bat algorithm；RNA inheritance；crossover；variation

10.11784/tdxbz201801027

TP399

A

0493-2137(2019)03-0315-06

2018-01-03；

2018-05-31.

耿艷香（1983—??），女，博士研究生，實驗師，gengyanxiang@163.com.

張立毅，zhangliyi@tucu.edu.cn.

國家自然科學基金資助項目(61401307)；國家軟科學研究計劃資助項目(2014GXS4D089)；天津市應用基礎與前沿技術研究計劃資助重點項目(14JCZDJC32600)；天津市高等學?？萍及l(fā)展基金計劃資助項目(20110709)；天津市應用基礎與前沿技術研究計劃資助項目(15JCYBJC17100)；中國物流學會資助項目(2014CSLKT3-16)；天津企業(yè)科技特派員計劃項目(18JCTPJC66900).

the National Natural Science Foundation of China(No.61401307)，the National Soft Science Research Plan of China (No.2014GXS4D089)，the Tianjin Key Research Program of Application Foundation and Advanced Technology (No.14JCZDJC32600)，the University Technology Development Fund of Tianjin(No.20110709)，the Tianjin Key Research Program of Application Foundation and Advanced Technology(No.15JCYBJC17100)，the Key Program of the Chinese Society of Logistics(No.2014CSLKT3-16)，the Tianjin Enterprise Science and Technology Correspondent Project (No.18JCTPJC 66900).