基于RNA遺傳操作的改進(jìn)蝙蝠算法

耿艷香，張立毅，孫云山，費(fèi)?騰，蔣師賢，馬嘉駿

?

基于RNA遺傳操作的改進(jìn)蝙蝠算法

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

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

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

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

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

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

1?基于RNA遺傳操作的改進(jìn)蝙蝠算法

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

1.1?蝙蝠算法的概述

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

?(1)

?(2)

?(3)

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

?(4)

?(5)

?(6)

1.2?RNA遺傳操作與蝙蝠算法的結(jié)合

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

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

圖1?交叉操作

圖2?變異操作

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

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

2?基于RNA遺傳操作的改進(jìn)蝙蝠算法

步驟2 啟動(dòng)蝙蝠進(jìn)行隨機(jī)搜索，每個(gè)蝙蝠進(jìn)行一次尋優(yōu)計(jì)算，記錄下各個(gè)蝙蝠的尋優(yōu)結(jié)果，找出當(dāng)前最優(yōu)解．

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

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

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

步驟6 啟動(dòng)新種群進(jìn)行最優(yōu)化搜索，每個(gè)蝙蝠進(jìn)行一次尋優(yōu)計(jì)算，記錄下各個(gè)蝙蝠的尋優(yōu)結(jié)果，更新當(dāng)前最優(yōu)解．

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

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

3?算法測(cè)試

為了證明基于RNA改進(jìn)的蝙蝠算法性能，選取6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行Matlab仿真．測(cè)試函數(shù)如表1所示．

表1?測(cè)試函數(shù)

Tab.1?Test function

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

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

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

表2?Sphere測(cè)試函數(shù)的運(yùn)行結(jié)果統(tǒng)計(jì)

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

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

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

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

表4?Schaffer測(cè)試函數(shù)的運(yùn)行結(jié)果統(tǒng)計(jì)

Tab.4?Statistical results of the Schaffer test function

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

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

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

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

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

表6?Rastrgrin測(cè)試函數(shù)的運(yùn)行結(jié)果統(tǒng)計(jì)

Tab.6?Statistical results of the Rastrgrin test function

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

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

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

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

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

表8?Ackley測(cè)試函數(shù)的運(yùn)行結(jié)果統(tǒng)計(jì)

Tab.8?Statistical results of the Ackley test function

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

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

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

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

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

表10?Griewank測(cè)試函數(shù)的運(yùn)行結(jié)果統(tǒng)計(jì)

Tab.10?Statistical results of the Griewank test function

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

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

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

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

表12?Rosebrock測(cè)試函數(shù)的運(yùn)行結(jié)果統(tǒng)計(jì)

Tab.12?Statistical results of the Rosenbrock test function

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

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

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

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

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

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

［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］ 吳華鋒，陳信強(qiáng)，毛奇凰，等. 基于自然選擇策略的蟻群算法求解TSP問(wèn)題[J]. 通信學(xué)報(bào)，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)學(xué)報(bào)，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］ 盛孟龍，賀興時(shí)，丁文靜. 蝙蝠算法的全局收斂性分析[J]. 紡織高?；A(chǔ)科學(xué)學(xué)報(bào)，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ī)制的改進(jìn)蝙蝠算法[J]. 微電子學(xué)與計(jì)算機(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]. 計(jì)算機(jī)應(yīng)用與軟件，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］ 尚俊娜，劉春菊，岳克強(qiáng)，等. 具有自學(xué)習(xí)能力的變異蝙蝠優(yōu)化算法及性能仿真[J]. 系統(tǒng)仿真學(xué)報(bào)，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ìn)的蝙蝠算法的研究及應(yīng)用[J]. 計(jì)算機(jī)仿真學(xué)報(bào)，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］ 羅?亮，吳文峻，張?飛. 面向云計(jì)算數(shù)據(jù)中心的能耗建模方法[J]. 軟件學(xué)報(bào)，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]. 河池學(xué)院學(xué)報(bào)，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］ 岳偉娜，馬吉明，蘇日建，等. 基于反向?qū)W習(xí)機(jī)制的蝙蝠算法[J]. 湖北民族學(xué)院學(xué)報(bào)：自然科學(xué)版，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).

(責(zé)任編輯：王曉燕)

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—??），女，博士研究生，實(shí)驗(yàn)師，gengyanxiang@163.com.

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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61401307)；國(guó)家軟科學(xué)研究計(jì)劃資助項(xiàng)目(2014GXS4D089)；天津市應(yīng)用基礎(chǔ)與前沿技術(shù)研究計(jì)劃資助重點(diǎn)項(xiàng)目(14JCZDJC32600)；天津市高等學(xué)?？萍及l(fā)展基金計(jì)劃資助項(xiàng)目(20110709)；天津市應(yīng)用基礎(chǔ)與前沿技術(shù)研究計(jì)劃資助項(xiàng)目(15JCYBJC17100)；中國(guó)物流學(xué)會(huì)資助項(xiàng)目(2014CSLKT3-16)；天津企業(yè)科技特派員計(jì)劃項(xiàng)目(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).