国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

改進布谷鳥算法的數(shù)據(jù)庫查詢優(yōu)化

2017-08-30 10:17席潔
微型電腦應用 2017年8期
關鍵詞:布谷鳥鳥巢蝙蝠

席潔

(陜西國防工業(yè)職業(yè)技術學院,戶縣 710300)

改進布谷鳥算法的數(shù)據(jù)庫查詢優(yōu)化

席潔

(陜西國防工業(yè)職業(yè)技術學院,戶縣 710300)

針對布谷鳥算法局部搜索能力弱、尋優(yōu)精度低等缺陷,提出了一種改進布谷鳥算法的數(shù)據(jù)庫查詢優(yōu)化算法(BACS)。按照布谷鳥優(yōu)化算法對鳥巢位置進行更新,然后利用蝙蝠算法的動態(tài)轉換策略對鳥巢位置進一步更新,避免算法陷入局部最優(yōu),將BACS應用于數(shù)據(jù)庫查詢優(yōu)化問題求解,并通過仿真實驗對BACS的性能進行測試。結果表明,BACS加快了數(shù)據(jù)庫查詢優(yōu)化求解的收斂速度,獲得了質量更高的查詢優(yōu)化方案。

數(shù)據(jù)庫; 查詢優(yōu)化; 布谷鳥搜索算法; 蝙蝠算法

0 引言

隨著數(shù)據(jù)庫規(guī)模日益增大,數(shù)據(jù)查詢頻率增加,如何找到滿足用戶查詢要求方案,提高數(shù)據(jù)庫查詢效率,成為當前研究的熱點問題[1]。

針對數(shù)據(jù)庫查詢優(yōu)化問題,國內外學者投入了大量時間和精力進行了研究[2]。由于數(shù)據(jù)庫查詢優(yōu)化問題是一個多約束的組合優(yōu)化問題,是一個NP難題,一些學者將啟發(fā)式算法引入到數(shù)據(jù)庫查詢中[3]。帥訓波等提出了一種遺傳算法的查詢優(yōu)化方法[4]。Zhou等人提出了進化算法的數(shù)據(jù)庫查詢策略[5]。Chen利用模擬退火和遺傳算法的組合式查詢優(yōu)化方法,但是該算法仍然容易產(chǎn)生早熟現(xiàn)象,難以得到最優(yōu)解[6]。郭聰莉提出基于蟻群算法的數(shù)據(jù)庫查詢優(yōu)化方法,但查詢效果欠優(yōu)[7]。布谷鳥搜索算法(CS)具有原理簡單、參數(shù)少、易實現(xiàn)等優(yōu)點,為數(shù)據(jù)庫查詢優(yōu)化提供了一種新的研究算法[8]。但基本CS算法存在著后期收斂速度慢、收斂精度不高、易陷入局部極小等不足[9]。蝙蝠算法(BA)是一種新興的啟發(fā)式群智能算法,可以實現(xiàn)動態(tài)控制局部搜索和全局搜索間的相互轉換過程,避免算法陷入局部最優(yōu),具有更好的收斂性[10]。

為了提高數(shù)據(jù)庫查詢的優(yōu)化效率,提出改進布谷鳥算法的數(shù)據(jù)庫查詢優(yōu)化算法(BACS)。首先按照基本布谷鳥優(yōu)化算法對鳥巢的位置進行更新,然后利用蝙蝠算法中的動態(tài)轉換策略對鳥巢位置進一步更新,從而在一定程度上避免算法陷入局部最優(yōu),最后通過仿真實驗對BACS的性能進行測試。結果表明,BACS加快了數(shù)據(jù)庫查詢優(yōu)化求解的收斂速度,獲得了質量更高的查詢優(yōu)化方案。

1 BACS算法

1.1 BA算法

BA算法是模擬自然界中蝙蝠利用一種聲吶來探測獵物、避免障礙物的隨機搜索算法,其將種群數(shù)量為NP的蝙蝠個體映射為D維問題空間中的可行解,將優(yōu)化過程和搜索模擬成種群蝙蝠個體移動過程和搜尋獵物,利用求解問題的適應度函數(shù)值來衡量蝙蝠所處位置的優(yōu)劣,將個體的優(yōu)勝劣汰過程模擬為優(yōu)化和搜索過程中用好的可行解替代較差可行解的迭代過程。為了模擬蝙蝠探測獵物、避免障礙物,需假設三個近似或理想化的規(guī)則:

(1) 所有蝙蝠利用回聲定位的方法感知距離,并且它們采用一種巧妙的方式來區(qū)別獵物和背景障礙物之間的不同。

(2) 蝙蝠在位置xi以速度vi隨機飛行,以固定的頻率fmin、可變的波長λ和音量A0來搜索獵物。蝙蝠根據(jù)自身與目標的鄰近程度來自動調整發(fā)射的脈沖波長(或頻率)和調整脈沖發(fā)射率r∈[0,1]。

(3) 雖然音量的變化方式有多種,但在蝙蝠算法中,假定音量A是從一個最大值A0(整數(shù))變化到固定最小值Amin[11]。

1.2 BA算法工作步驟

對于目標函數(shù)為minf(X),目標變量為X=(x1,x2,…,xd)T的優(yōu)化問題,BA算法的實施過程描述如下:

Step1:種群初始化,即蝙蝠以隨機方式在D維空間中擴散分布一組初始解。具體包括:初始種群個體數(shù)(蝙蝠數(shù)目)NP,最大脈沖音量A0,最大脈沖率R0,搜索脈沖頻率范圍[fmin,fmax],音量的衰減系數(shù)α,搜索頻率的增強系數(shù)γ,搜索精度ε或最大迭代次數(shù)iter_max。

Step2:隨機初始化蝙蝠的位置xi,并根據(jù)適應度值的優(yōu)劣尋找當前最優(yōu)解x*。

Step3:蝙蝠的搜索脈沖頻率、速度和位置更新。種群在進化過程中,每一代個體的搜索脈沖頻率、速度和位置按如下公式進行變化,即式(1)至(3)

(1)

(2)

(3)

Step4:生成均勻分布隨機數(shù)rand,如果rand>ri,則對當前最優(yōu)解進行隨機擾動,產(chǎn)生一個新的解,并對新的解進行越界處理。

Step5:生成均勻分布隨機數(shù)rand,如果rand

(4)

(5)

Step6:對所有蝙蝠的適應度值進行排序,找出當前的最優(yōu)解和最優(yōu)值。

Step7:重復Step2~Step6步驟,直至滿足設定的最優(yōu)解條件或者達到最大迭代次數(shù)。

Step8:輸出全局最優(yōu)值和最優(yōu)解。

1.3 CS算法

在基本CS算法中,在目標函數(shù)定義的可行解空間內對N個鳥巢位置隨機初始化,在進化過程中,首先適應度值最優(yōu)的鳥巢位置被保留到下一代,再利用Levy Flight機制對鳥巢的位置進行更新,得到新的鳥巢位置,最后用外來蛋的發(fā)現(xiàn)概率pa與服從均勻分布的隨機數(shù)R∈[0,1]進行比較,如R>pa,隨機改變鳥巢的位置,從而得到一組新的鳥巢位置,并確定當前最優(yōu)的鳥巢位置及最優(yōu)解。

在CS算法中,布谷鳥在每一次迭代中尋找鳥巢的路徑和位置按式(6)進行更新。

(6)

為實現(xiàn)CS算法,學者提出的模擬Lévy(λ)飛行跳躍路徑的公式,見式(7)。

(7)

式中,s為Lévy飛行跳躍路徑;μ、ν為正態(tài)分布隨機數(shù),服從正態(tài)分布即為式(8)。

(8)

式中,σμ,σν值分別為式(9)。

(9)

2.4 BACS算法思想

針對基本CS算法的不足,將蝙蝠算法融入到基本CS算法中,使各自的優(yōu)點融合在一起,提出了一種蝙蝠算法和布谷鳥優(yōu)化算法的混合優(yōu)化算法(BACS)。具體步驟為:

(1) 用一個均勻分布隨機數(shù)與脈沖的發(fā)射速率對比,如條件成立,則對當前最優(yōu)的鳥巢位置進行隨機擾動,得到新的鳥巢位置,并對其進行越界處理及評估其對應的適應度值。

(2) 利用響度與均勻分布隨機數(shù)比較,如果條件得到滿足,用新的鳥巢位置更新基本布谷鳥算法中得到的鳥巢位置,并同時更新響度和脈沖的發(fā)射速率。

(3) 最后評估鳥巢的適應度值,找出當前最優(yōu)的鳥巢位置和最優(yōu)值,并進入下一次迭代,繼續(xù)利用基本的布谷鳥算法進行搜索和位置更新。

2 BACS的數(shù)據(jù)庫查詢優(yōu)化問題求解

2.1 數(shù)據(jù)庫查詢優(yōu)化的數(shù)學模型

對于含有n個關系表的數(shù)據(jù)查詢優(yōu)化問題,就是左深樹和右深樹共有n!個數(shù)據(jù)庫查詢方案,從中找到一條查詢代價最小的查詢方案。本文選擇“左深樹”作為搜索策略空間。對于一個連接J=RjoinS,其計算代價cost(J)如式(10)。

(10)

其中,V(c,R)的計算如式(11)。

(11)

2.2 BACS的數(shù)據(jù)庫查詢求解步驟

(1) 對左深樹組成的解空間中的連接操作進行編碼,后續(xù)遍歷連接樹得到編碼序列L。

(2) 參數(shù)初始化:初始化BACS算法的各個參數(shù),如最大迭代次數(shù)等。

(3) 根據(jù)式(13)目標函數(shù)計算鳥巢的適應度值,并確定當前最優(yōu)的鳥巢位置及最優(yōu)值。

(4) 保留上代最優(yōu)的鳥巢位置,利用Levy Flight機制的式(6)~(9)對鳥巢的位置進行更新,得到新的鳥巢位置,并對鳥巢的位置進行越界處理。

(5) 利用目標函數(shù)計算步驟(4)獲得的新鳥巢位置適應度值,并與上代鳥巢位置適應度值對比,若好,則替換上一代的適應度值,并更新其對應的鳥巢位置,然后確定當前的最優(yōu)鳥巢位置和最優(yōu)值。

(6) 用外來蛋的發(fā)現(xiàn)概率pa與服從均勻分布的隨機數(shù)R∈[0,1]進行比較,如R>pa,隨機改變鳥巢的位置,從而得到一組新的鳥巢位置。

(7) 把獲得新的鳥巢位置作為蝙蝠算法的初始點并利用式(1)~(5)繼續(xù)對鳥巢的位置進行更新,得到一組新的鳥巢位置。

(8) 評估Step6獲得的鳥巢位置的適應度值,經(jīng)比較后,確定當前最優(yōu)的鳥巢位置及最優(yōu)值;

(9) 一次迭代完成,進入下一次迭代,判斷是否滿足終止條件,最優(yōu)粒子對應的數(shù)據(jù)庫查詢計劃。如果不滿足則轉到步驟(4),繼續(xù)循環(huán)迭代。

3 仿真實驗

3.1 仿真環(huán)境

為了測試BACS算法的性能,在CPU為Intel CoreTM 2 Quad 2.5 GHz,RAM為4.0 GB,操作系統(tǒng)為Windows XP的平臺下,采用VC++編程數(shù)據(jù)庫查詢優(yōu)化算法實現(xiàn)仿真實驗。數(shù)據(jù)庫來自一個大型人事系統(tǒng)的數(shù)據(jù),共有1萬條記錄,每條記錄包括多個子字段。同時為了使本文算法具有可對比性,選擇的對比算法為:基本布谷鳥算法(CS)算法、文獻[13]改進的布谷鳥優(yōu)化(MCS)算法。

3.2 結果與分析

最優(yōu)查詢方案的收斂情況和質量,如圖1和圖2所示。對圖1與圖2結果進行分析,可以得到如下結論:

圖1 各種數(shù)據(jù)庫查詢優(yōu)化算法的迭代次數(shù)

圖2 各種數(shù)據(jù)庫查詢優(yōu)化算法的執(zhí)行時間對比

(1) 對于10個關系的數(shù)據(jù)查詢問題,當?shù)?90代時,CS算法才找到最優(yōu)數(shù)據(jù)庫查詢方案,對應的執(zhí)行時間為280.22 s;

(2) 在相同條件,當?shù)?77代時,MCS算法找到最優(yōu)數(shù)據(jù)庫查詢方案,其執(zhí)行時間為210.25 s,相對于CS算法,性能更優(yōu)。

(3) 對于相同問題,BACS算法迭代230次后得到比CS算法和MCS算法更優(yōu)的數(shù)據(jù)庫查詢方案,其執(zhí)行時間為175.29 s。

(4) 相對CS算法,MCS算法提高了求解速度,獲得更優(yōu)的查詢解,同時BACS算法性能得到進一步提高,克服了對比算法存在的不足,是一種速度快、效率的數(shù)據(jù)庫查詢優(yōu)化方法。

4 總結

數(shù)據(jù)庫查詢優(yōu)化是一個NP問題,針對CS算法查詢代價高,效率低的問題,為此提出基于BACS算法的數(shù)據(jù)庫查詢優(yōu)化方法。結果表明,相對于比算法,BACS算法可以獲得更優(yōu)的數(shù)據(jù)查詢效果。

[1] 張敏,馮登國,徐震. 多級多版本數(shù)據(jù)庫管理系統(tǒng)全局串行化[J]. 軟件學報,2007,18(2):346-347.

[2] 張麗平,李松,郝忠孝. 球面上的最近鄰查詢方法研究[J]. 計算機工程與應用, 2011, 47(5): 126-129.

[3] Zhang Jun, Huang De-Shuang, Lok Tat-Ming, et al. A novel adaptive sequential niche technique for multimodal function optimization [J]. Neurocomputing, 2006, 69(16): 2396-2401.

[4] 帥訓波,馬書南,周相廣,等. 基于遺傳算法的分布式數(shù)據(jù)庫查詢優(yōu)化研究[J]. 小型微型計算機系統(tǒng),2009,30(8):1600-1604.

[5] Zhou Zehai. Using heuristics and genetic algorithms for large scale database query optimization [J]. Journal of Information and Computing Science, 2007, 2(4):261-280.

[6] Chen Po-Han, Shahandashti S M. Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints [J]. Automation in Construction, 2009, 18(4):434-443.

[7] 郭聰莉,朱莉,李向. 基于蟻群算法的多連接查詢優(yōu)化方法[J]. 計算機工程,2009,35(10):173-176.

[8] Wei Ling yun, Zhao Mei. A niche hybrid genetic algorithm for global optimization of continuous multimodal functions [J]. Applied Mathematics and Computation, 2005, 160(3):649-661.

[9] 林桂亞. 基于粒子群算法的數(shù)據(jù)庫查詢優(yōu)化[J]. 計算機應用研究,2012,29(3):974-975.

[10] Yang X S. A new metaheuristic bat-inspired algorithm[J]. Springer,2010,28(10):65-74.

[11] Amir Hossein Gandomi, Xin-She Yang, Amir Hossein Alavi. Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems [J]. Springer, 2013, 30(2):17-35.

[12] 石偉. 混沌粒子群算法在數(shù)據(jù)庫查詢優(yōu)化中的應用[J]. 科技通報,2012,28(4):116-118.

[13] 王凡,賀興時,王燕.基于高斯擾動的布谷鳥搜索算法[J]. 西安工程大學學報,2011,25(4): 566-569.

Database Query Optimization Based on Improved Cuckoo Search Algorithm

Xi Jie

(Shanxi Institute of Technology, Huxian 710300, China)

In order to solve the problems of Cuckoo algorithm including low optimizing accuracy, weakly local search ability, a novel query optimization method for database is proposed based on imrpoved Cuckoo search algorithm (BACS). Firstly, nest location is updated according to the basic Cuckoo search algorithm, and then Cuckoo nest location is further replaced according to the dynamic conversion strategy in the Bat algorithm to avoid falling into a local optimum, finally it is applied to solve the query optimization problem of database. The performance of BACS is tested by simulation experiments. The results show that, BACS accelerates the convergence speed of database query optimization, and can obtain higher quality query optimization scheme.

Database; Optimization query; Cuckoo algorithm; Bat algorithm

席 潔(1983-),講師,碩士,研究方向:計算機網(wǎng)絡技術。

1007-757X(2017)08-0043-03

TP311

A

2017.06.05)

猜你喜歡
布谷鳥鳥巢蝙蝠
布谷鳥讀信
布谷鳥讀信
鳥巢
重回鳥巢
鳥巢大作戰(zhàn)
蝙蝠
布谷鳥叫醒的清晨
蝙蝠女
蝙蝠為什么倒掛著睡覺?
打聯(lián)賽 去鳥巢 看中網(wǎng)