劉 東

LIU Dong

陜西理工學院 物理與電信工程學院，陜西 漢中 723001

School of Physics and Communication Engineering,Shaanxi University of Technology,Hanzhong,Shaanxi 723001,China

1 引言

隨著數(shù)據(jù)庫技術成熟和應用范圍的擴大，出現(xiàn)了許多大規(guī)模數(shù)據(jù)庫，而查詢優(yōu)化是提高數(shù)據(jù)庫性能的關鍵技術之一，因此針對一個查詢問題，如何找到一種最優(yōu)查詢計劃至關重要，成為數(shù)據(jù)庫研究中的重要課題[1-2]。

找到數(shù)據(jù)庫的最優(yōu)查詢計劃就是要構造一棵代價最小的多連接查詢樹，為此針對數(shù)據(jù)庫查詢優(yōu)化問題，國內(nèi)外學者從不同角度做了大量的工作，提出許多查詢優(yōu)化算法[3]。最傳統(tǒng)的查詢優(yōu)化算法采用窮盡搜索算法或其他變形算法，當連接關系數(shù)目較小時，可以取得較好的查詢效果，但現(xiàn)代數(shù)據(jù)庫管理系統(tǒng)的查詢連接數(shù)目通常很大，這類算法毫無用處，沒有什么實際應用價值[4]。隨后有學者提出動態(tài)規(guī)劃算法解決數(shù)據(jù)庫查詢優(yōu)化問題，但查詢效率低，不能滿足現(xiàn)代數(shù)據(jù)庫查詢要求[5]。大量研究表明，數(shù)據(jù)庫查詢優(yōu)化包括了許多約束條件，實質上是一個組合優(yōu)化問題，群智能算法具有搜索速度快的優(yōu)點，因此一些學者將群智能算法應用于數(shù)據(jù)庫查詢優(yōu)化問題的求解中[5]。文獻[6]等提出一種基于遺傳算法的數(shù)據(jù)庫查詢優(yōu)化方法，采用遺傳算法對查詢執(zhí)行計劃代價進行求解，取得了不錯的效果。Kumar等人根據(jù)查詢數(shù)據(jù)關聯(lián)度之間的關系，提出一種基于遺傳算法的數(shù)據(jù)庫查詢優(yōu)化方法[7]。遺傳算法雖然具有尋優(yōu)能力強的優(yōu)點，但是對于不同問題需要設置不同的遺傳算子，存在局部搜索能力差等不足[8]。為此，一些學者基于組合優(yōu)勢，如Zhou對遺傳算法進行改進，但對于不同問題，需要進行相應的改進，通用性差[9]。Po-Han Chen等將模擬退火算法引入遺傳算法的變異過程中，獲得比遺傳算法更優(yōu)的數(shù)據(jù)庫查詢優(yōu)化效果，但是存在尋優(yōu)結果不穩(wěn)定等缺陷[10]。林桂亞等利用蟻群算法對數(shù)據(jù)庫查詢優(yōu)化問題進行求解，取得了不錯的效果[11]。螢火蟲群算法（Firefly Algorithm，F(xiàn)A）是一種模擬螢火蟲發(fā)光行為的群智能優(yōu)化算法，多個螢火蟲被隨機散布于整個搜索空間內(nèi)，所有螢火蟲都具有一個由被優(yōu)化問題所決定的適應度值，對應于該螢火蟲的熒光亮度。然后每個螢火蟲個體都在其視覺范圍內(nèi)追隨熒光亮度更強的螢火蟲飛行，經(jīng)過多次群體運動后，所有個體將聚集在熒光亮度最強的螢火蟲附近，完成最終尋優(yōu)，為解決數(shù)據(jù)庫查詢優(yōu)化問題提供了一種新的研究方法[12]。

針對數(shù)據(jù)庫查詢優(yōu)化效率低的難題，提出一種多子群螢火蟲群算法（MG-FA），并將其應用于數(shù)據(jù)庫查詢優(yōu)化問題求解中。首先將數(shù)據(jù)庫查詢計劃左深樹看作一個螢火蟲，然后通過螢火蟲相互學習機制和信息交流找到數(shù)據(jù)庫查詢最優(yōu)方案，并通過仿真實驗測試其性能。

2 多子群螢火蟲優(yōu)化算法

螢火蟲優(yōu)化算法是一種模擬螢火蟲發(fā)光行為的群智能優(yōu)化算法，其基本思想為：用搜索空間中的點模擬自然界中的螢火蟲個體，將問題目標函數(shù)定義成螢火蟲所處位置的相應解，將尋優(yōu)過程模擬成螢火蟲個體向更亮螢火蟲的移動過程。設共有m個螢火蟲，第i個螢火蟲在 N 維空間中的當前位置為 Xi=(xi1，xi2，…，xiN)，螢火蟲位置優(yōu)劣通過螢火蟲亮度描述，并決定其移動方向，其相對熒光亮度為：

式中，I0為表示第i只螢火蟲最大熒光亮度；λ為光強度吸收參數(shù)；rij為螢火蟲i與 j之間的距離，定義為：

吸引度(β)決定了螢火蟲移動的距離，定義為：

式中，β0為最大吸引度因子。

螢火蟲i被螢火蟲 j吸引后移動的位置更新由式（4）決定：

式中，xi、xj為第i和第 j個螢火蟲所處的空間位置；α為步長因子；rand()是隨機數(shù)[13-14]。

在實際應用中，由于螢火蟲算法實質是一種隨機優(yōu)化算法，因此存在一些不足，如果螢火蟲算法進化后期收斂速度慢，易陷入局部最優(yōu)解等[15]。

2.1 保持種群的多樣性

種群多樣性對螢火蟲的尋優(yōu)性能起著至關重要的作用，為此，首先將螢火蟲群分為n個子群，并為不同子群設置不同α、λ、β0等參數(shù)，各子群根據(jù)自己尋優(yōu)方式進行并行尋優(yōu)，以滿足全局尋優(yōu)要求；然后為每個子群設置公告板，記錄每次迭代后的各子群最優(yōu)值及相應個體位置，并將所有子群的最優(yōu)個體組建為“決策層”，如果某子群最優(yōu)值連續(xù)3次沒有發(fā)生變化，那么就認為該子群發(fā)生早熟，可能陷入局部最優(yōu)，此時從“決策層”找到更優(yōu)螢火蟲個體，并對早熟子群的最優(yōu)個體將利用式（1）～（4）向其他子群的更優(yōu)個體進行學習，從而完成位置轉移，跳出當前局部最優(yōu)區(qū)域。“決策層”構建了各子群之間的信息交流與相互學習的途徑，能夠對早熟子群提供更明確有效的指導；最后若發(fā)現(xiàn)某子群已陷入局部最優(yōu)，但在“決策層”中找到更優(yōu)的其他子群個體時，采用高斯變異因子對該子群進行擾動。高斯分布是一種工程常用的重要概率分布，其概率密度函數(shù)如式（5）所示：

式中，σ為高斯分布的方差，μ為期望。

將子群內(nèi)的螢火蟲按照優(yōu)劣大小排序，利用子群內(nèi)的最優(yōu)螢火蟲將排名最后的螢火蟲群體進行狀態(tài)替換更新，同時對更新螢火蟲群體的狀態(tài)進行高斯變異處理，如式（6）所示。

式中，N(μ，σ)為服從期望為 μ，方差為σ的高斯分布的隨機向量。

2.2 自適應變步長機制

步長因子α取值影響螢火蟲算法的收斂性能影響，為了提高算法收斂速度和全局尋優(yōu)能力，在尋優(yōu)過程中采用自適應變步長機制：初期α值較大，提高全局尋優(yōu)能力；隨著迭代次數(shù)增加，逐步減小α值，加快后期收斂速度，具體調整方式為：

式中，Δα為步長衰減系數(shù)，在（0.95，1）內(nèi)取值。

2.3 域約束

為保證螢火蟲個體始終在有效搜索空間進行搜索，對螢火蟲個體進行域約束處理，具體為：

式中，xmin和xmax分別為搜索空間下限和上限。

采用4個準測試函數(shù)：Sphere、Griewank、Ackley和Rastrigin對FA算法、粒子群優(yōu)化（PSO）算法和MG-FA算法的性能進行測試，4個測試函數(shù)見表1所示。

圖1 不同算法的收斂性能比較

表1 用于測試算法性能的函數(shù)

FA、PSO和MG-FA算法的運行結果如圖1所示。從圖1可知，Sphere函數(shù)只有一個全局最優(yōu)值，較容易求出；Griewank函數(shù)在全局最優(yōu)值附近不是光滑連續(xù)的，增大了搜索難度；Ackle函數(shù)只有一個全局最優(yōu)值，但在全局最優(yōu)值的附近幾乎呈不連續(xù)狀態(tài)，在全局最優(yōu)值附近搜索的難度很大。Rastrigin是一種病態(tài)函數(shù)，全局最優(yōu)與局部最優(yōu)有很深的狹縫，很多搜索算法幾乎無法找到全局最優(yōu)值，由此可知，針對所有函數(shù)，MG-FA算法的進化迭代次數(shù)更少，收斂速度更快，并且具有更高的收斂精度，主要是由于在多子群相互學習機制的驅動下，MG-FA算法更容易跳出進化停滯狀態(tài)，當發(fā)生進化變慢或者停滯時，MG-FA算法能通過子群之間的信息傳遞，牽引進化受阻的螢火蟲重新進入進化狀態(tài)，具備一定的進化復蘇能力，從而能夠更好地滿足局部搜索和全局精度的全面尋優(yōu)要求，具有更好的求解效率。

3 查詢優(yōu)化的MG-FA設計模型

3.1 設計模型

數(shù)據(jù)庫查詢過程會涉及到多個關系表，不同表之間的連接次序導致查詢結果的多樣性。對于n個表，左、右深樹均含有n!個查詢優(yōu)化計劃，查詢優(yōu)化是找到一條最小查詢代價的執(zhí)行計劃[11]。設一個查詢請求可能的查詢計劃集合為S，那么元素 s的相關聯(lián)代價為cost(s)， 若有 n 個關系 R={r1，r2，…，rn}參與連接運算，tm表示中間關系，那么cost(s)為中間關系tm代價的總和，數(shù)據(jù)庫查詢優(yōu)化問題的數(shù)學模型為：

3.2 查詢優(yōu)化的MG-FA設計

3.2.1 編碼

MG-FA算法第一個步驟是對所解問題進行編碼，因此，編碼好壞是MG-FA是否成功的一個關鍵因素。為了保留連接樹的特征，本文采用直接以樹的形式編碼。對于圖2的左深樹，螢火蟲的編碼方式為“653412”。

圖2 左深樹表示

3.2.2 適應度函數(shù)

查詢優(yōu)化的目標是要獲得代價cost(Xi)最小的執(zhí)行計劃，因此螢火蟲個體的適應度函數(shù)必須與cost(Xi)相關，因此適應度值函數(shù)定義如下：

3.2.3 MG-FA數(shù)據(jù)庫查詢優(yōu)化算法的工作流程

MG-FA算法將數(shù)據(jù)庫查詢計劃左深樹看作一個螢火蟲，然后通過螢火蟲之間的協(xié)作找到數(shù)據(jù)庫查詢最優(yōu)計劃，在螢火蟲搜索過程中，引入高斯變異策略，提高算法的全局搜索能力，避免陷入局部最優(yōu)，具體工作步驟如下：

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

（2）初始化參數(shù)。設置螢火蟲數(shù)目m及螢火蟲子群數(shù)n，并為各子群分別設置光強吸收系數(shù)λ、最大吸引度因子 β0及步長因子α。設定收斂條件，并在求解空間內(nèi)隨機生成各螢火蟲的初始位置 xij(i=1，2，…，n，j=1，2，…，m/n)。

（3）根據(jù)式（10）計算各子群螢火蟲的適應度值 f(xi)作為其最大熒光強度，并將各子群中的最佳適應度值記為 fibest，計入子群公告板。

（4）由式（2）計算各子群螢火蟲個體的相對熒光亮度Iij，比較所屬子群鄰域內(nèi)螢火蟲的熒光亮度大小，并確定各螢火蟲的位置進化方向。

（5）由式（3）計算各子群螢火蟲的吸引度 βij，并根據(jù)式（4）更新螢火蟲的空間位置。

（6）查詢各子群公告板，判斷各子群是否出現(xiàn)迭代次數(shù)已達到3次，并且 fibest的連續(xù)變化量小于1e－3的現(xiàn)象，若是，則轉步驟（7），否則，轉步驟（8）。

（7）從其他子群公告板中尋找最優(yōu)個體，若存在優(yōu)于自身子群的最優(yōu)值，則讓自身的最優(yōu)螢火蟲向其他更優(yōu)子群的最優(yōu)個體進行位置轉移；若否，則在自身子群內(nèi)進行高斯變異操作。

（8）根據(jù)式（5）收縮步長，并對所有螢火蟲個體進行域約束操作。

（9）如果滿足終止條件，最優(yōu)螢火蟲位置對應的數(shù)據(jù)庫查詢計劃。

綜合上述可知，基于MG-FA具體流程如圖3所示。

4 仿真實驗

4.1 仿真環(huán)境

為了測試MG-FA算法的性能，在AMD Athlon II X46313.0 GHz，RAM 4 GB，Windows 7操作系統(tǒng)環(huán)境中進行仿真實驗，采用SQL Server 2005作為數(shù)據(jù)庫軟件，采用VC++編程數(shù)據(jù)庫查詢優(yōu)化算法。對比算法為：螢火蟲優(yōu)化算法（FA）、粒子群優(yōu)化（PSO）算法。采用查詢和執(zhí)行代價評估算法性能。

圖3 MG-FA算法的數(shù)據(jù)庫查詢流程

4.2 結果與分析

4.2.1 搜索和查詢消耗代價比

不同數(shù)據(jù)庫查詢優(yōu)化方法的查詢和執(zhí)行最優(yōu)計劃的代價比如圖4、5所示。

圖4 各種算法的搜索代價比

圖5 各種算法的查詢代價比

從圖4和5的結果進行分析可以得到如下結論：

（1）PSO算法代價消耗比曲線變化幅度較大，說明PSO算法在求解數(shù)據(jù)庫查詢問題時，性能不穩(wěn)定且求得最優(yōu)查詢執(zhí)行計劃的準確率不高。

（2）相對于PSO算法，F(xiàn)A的整體搜索代價比曲線并未出現(xiàn)明顯變化，變化相對平衡，對比結果表明，相對于PSO算法，F(xiàn)A算法加快了算法的收斂速度，隨著關系數(shù)的增加，F(xiàn)A算法的整體優(yōu)化效果要優(yōu)于FA算法。

（3）相對于PSO、FA算法，MG-FA算法的性能得到相應提升，主要是由于高斯變異算子增加了種群多樣性，有較地實現(xiàn)了算法全局與局部搜索的平衡，不僅提高了數(shù)據(jù)庫查詢效率，而且大幅度地減少了執(zhí)行代價，能夠更快速地找到最優(yōu)數(shù)據(jù)庫查詢計劃。

4.2.2 迭代次數(shù)和執(zhí)行時間

不同算法的收斂速度和最優(yōu)查詢計劃執(zhí)行時間見表2和3。

表2 各算法的查詢優(yōu)化計劃迭代次數(shù)

表3 各算法的執(zhí)行時間對比 s

對表2和表3進行分析可知：

（1）對于數(shù)據(jù)庫的關系連接數(shù)n=20的查詢優(yōu)化問題，當?shù)?76次時，PSO算法便找到了最優(yōu)數(shù)據(jù)庫查詢計劃，其相應執(zhí)行時間為250.77 s。

（2）相同條件下，當?shù)?70次時，螢火蟲優(yōu)化算法（FA）便找到了最優(yōu)數(shù)據(jù)庫查詢計劃，相應的數(shù)據(jù)查詢的執(zhí)行時間為200.27 s，相對于PSO算法，F(xiàn)A加快了算法的收斂速度，提高了最優(yōu)解的質量。

（3）MG-FA算法迭代240次后得到比FA和PSO算法更優(yōu)的數(shù)據(jù)庫查詢計劃，其執(zhí)行時間為185.05 s。

綜上可知，MG-FA算法的搜索速度更快，較好地防止了早熟收斂，提高了數(shù)據(jù)庫查詢效率。

5 結束語

數(shù)據(jù)庫查詢優(yōu)化是一種要求速度快、效率高的優(yōu)化問題，針對當前數(shù)據(jù)庫查詢優(yōu)化算法存在的效率低，難以獲得最優(yōu)解的缺陷，結合數(shù)據(jù)庫查詢的特點和螢火蟲算法的優(yōu)點，提出一種多子群螢火蟲算法的數(shù)據(jù)庫查詢優(yōu)化方法，首先將螢火蟲群分為不同參數(shù)的多個子群，各子群內(nèi)的螢火蟲跟隨所屬子群的最優(yōu)螢火蟲分別進行尋優(yōu)操作，然后在各子群的最優(yōu)螢火蟲之間構建相互學習機制，實現(xiàn)子群間的信息交流，最后采用數(shù)據(jù)庫查詢優(yōu)化數(shù)據(jù)進行仿真實驗，實驗結果表明，MG-FA是一種性能良好的數(shù)據(jù)庫查詢優(yōu)化方法，能夠獲得比其他算法更佳的查詢結果。

[1]許新華，胡世港，唐勝群，等.數(shù)據(jù)庫查詢優(yōu)化技術的歷史、現(xiàn)狀與未來[J].計算機工程與應用，2009，45（18）：156-161.

[2]于洪濤，錢磊.一種改進的分布式查詢優(yōu)化算法[J].計算機工程與應用，2013，49（8）：151-155.

[3]林鍵，劉仁義，劉南，等.基于查詢優(yōu)化器的分布式空間查詢優(yōu)化方法[J].計算機工程與應用，2012，48（22）：161-165.

[4]邱桃榮，葛寒娟，魏玲玲，等.基于相似度的粗關系數(shù)據(jù)庫的近似查詢[J].計算機工程與應用，2008，44（21）：195-198.

[5]史恒亮，任崇廣，白光一，等.自適應蟻群優(yōu)化的云數(shù)據(jù)庫動態(tài)路徑查詢[J].計算機工程與應用，2010，46（9）：10-12.

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

[7]Kumar T V V，Singh V，Verma A K.Distributed query processing plans generation using genetic algorithm[J].International Journal of Computer Theory and Engineering，2011，3（1）：38-45.

[8]Zhou Z H.Using heuristics and genetic algorithms for large-scale database query optimization[J].Journal of Information and Computing Science，2007，2（4）：261-280.

[9]Chen P H，Seyed 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.

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

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

[12]劉長平，葉春明.一種新穎的仿生群智能優(yōu)化算法：螢火蟲算法[J].計算機應用研究，2011，28（9）：3295-3297.

[13]Horng M H.Vector quantization using the firefly algorithm forimage compression[J].ExpertSystemswith Applications，2012，39（1）：1078-1091.

[14]Senthilnath J，Omkar S N，Mani V.Clustering using firefly algorithm：performance study[J].Swarm and Evolutionary Computation，2011，1（3）：164-171.

[15]Coelho L S，Mariani V C.Firefly algorithm approach based on chaotic Tinkerbell map applied to multivariable PID controller tuning[J].Computers&Mathematics with Applications，2012，64（8）：2371-2382.