基于多蟻群遺傳算法的分布式數據庫查詢優化

周瑩 陳軍華

摘要：

針對單一普通算法在查詢優化方面的不足，提出了一種結合遺傳算法與蟻群算法優點的多蟻群遺傳算法，克服了蟻群算法前期搜索的盲目性，并引入多蟻群概念，更好地防止了算法陷入局部最優的情況，以獲取更優的查詢路徑.類比實驗表明，該算法較傳統蟻群算法，在查詢方面，能獲得更好的查詢路徑.

關鍵詞：

分布式數據庫; 多蟻群; 遺傳算法; 查詢優化

中圖分類號： TP 311文獻標志碼： A文章編號： 1000-5137（2018）01-0037-06

Query optimization of distributed database based on

multiple ant colony genetic algorithm

Zhou Ying， Chen Junhua*

（The College of Information，Mechanical and Electrical Engineering，Shanghai Normal University，Shanghai 200234，China）

Abstract：

In the light of the defect of single algorithm of query optimization，this paper proposes a multiple ant colony genetic algorithm combining the advantages of ant colony algorithm and genetic algorithmwhich overcomes the blindness of early search of ant colony algorithm.Moreover the introduction of multi ant colony concept better prevents the algorithm falling into local optimal conditions as to obtain better query path..The final experiment results show that the improved optimization algorithm can find better query path in the query compared with the traditional ant colony algorithm.

Key words：

distributed database; multi ant-colony; genetic algorithm; query optimization

收稿日期： 2016-04-28

作者簡介： 周瑩（1991-），女，碩士研究生，主要從事數據庫方面的研究.E-mail：200865689@qq.com

導師簡介： 陳軍華（1968-），男，副教授，主要從事數據庫方面的研究.E-mail：chenjh@shnu.edu.cn

*通信作者

引用格式： 周瑩，陳軍華.基于多蟻群遺傳算法的分布式數據庫查詢優化 [J].上海師范大學學報（自然科學版），2018，47（1）：37-42.

Citation format： Zhou Y，Chen J H.Query optimization of distributed database based on multiple ant colony genetic algorithm [J].Journal of Shanghai Normal University（Natural Sciences），2018，47（1）：37-42.

分布式數據庫技術使數據在物理上呈現分布狀態，在邏輯上融為整體的數據庫技術.隨著數據量的日益增長，分布式數據庫技術的應用越來越廣泛.為了盡可能地降低該技術的整體開銷，需要尋找一個切入點對其進行優化.查詢操作是分布式數據庫中最常用，同時也是最有提升空間的一種操作，成為研究的重點.目前已經有許多學者提出了相關優化策略，如基于索引的SQL語句查詢優化[1]，基于禁忌GEP的查詢優化[2]，基于遺傳模擬退火的查詢優化[3]等策略.

考慮到單個算法的局限性及不足[4]，本文作者提出了一種遺傳算法與多蟻群算法相結合的混合算法，多蟻群算法是在普通蟻群基礎上進行改進的算法.該混合算法不但克服了蟻群算法前期搜索的盲目性，而且利用了平滑機制及多蟻群間互相學習機制來避免陷入局部最優和早熟現象，從而提高了整個算法的全局搜索能力.實驗表明，該算法有效地提高了分布式數據庫查詢的效率.

1算法模型

多蟻群遺傳算法的基本思想是：通過遺傳算法處理，產生初始的信息素分布，多蟻群算法利用這個初始信息素分布開始尋優，多個蟻群間先互相獨立尋優，當迭代數滿足條件時，依照平滑機制跳出局部最優，并利用學習機制獲得更好的全局最優解，這個解就是查詢路徑.

1.1遺傳算法

利用傳統遺傳算法的步驟對查詢問題初步求解.求解前需要根據待求解問題來設置各個參數和相關技術.其中幾個重要概念定義如下：

（1） 目標函數.目標函數指的是解決問題所要關心的目標與相關因素的函數關系.對于所遇到的一些分布式數據庫查詢優化問題來說，最需要關注的目標就是總通信費用的問題.目標函數公式如下：

C=∑ni=1Ai+∑mi=1Eij，（1）

其中，C表示總通信費用，Ai為查詢路徑上的節點i對應的通訊費用，Eij為查詢路徑上的節點i以及節點j之間對應的通訊費用，n為查詢路徑上節點總個數，m為查詢路徑上所有節點之間路徑的總條數.

（2） 適應度函數.適應度函數用來衡量一個解的好壞[5]，而在分布式數據庫查詢優化問題中，目的是獲得通訊費用最少的查詢路徑，所以適應度函數定義如下：

fitness=1C.（2）

（3）初始信息素分布.即為螞蟻搜索路徑前各條路徑上信息素濃度的分布，按照遺傳算法找到的最優路徑更新，產生多蟻群算法的初始信息素分布矩陣，螞蟻初次運動的路徑會受此影響.更新公式如下：

τij（0）=ρτij+Δτij（0）（3）

τij（0）是邊ij上的初始信息素值，ρ是遺傳算法優化信息素的更新因子，Δτij（0）是遺傳算法找到的最優路徑在邊ij上釋放的信息素值，

Δτij（0）=Q/l，（4）

其中，信息素總量值用Q進行表示，這個值是固定的;l是邊的長度.Q/l可以理解為在單位距離上所具有的信息素濃度.

1.2多蟻群算法

在大自然中，蟻群的覓食活動往往不是單個蟻群獨立進行的，通常在同一個環境中存在著多個蟻群，它們互相影響，互相學習，共同進化[6].在傳統蟻群的基礎上引入多蟻群的概念，這種概念指的就是采用劃分的方法對一個總的蟻群進行有效地處理，用不同的參數控制著各個子蟻群，子蟻群間獨立尋優，這樣在每個子蟻群中就會產生不同的信息素分布，有著不同的進化方向.當迭代一定次數后，子蟻群內可能會陷入停滯狀態，這時各個子蟻群間利用“學習算子”開始進行信息素的交流，打破停滯的僵局，推動蟻群再次進化，防止算法出現局部最優的現象.引入多蟻群的做法，意在讓算法更貼近大自然實際規律，多蟻群能夠實現互幫互助，共同進化，最終獲得最優解.

前期利用遺傳算法進行處理獲得初始信息素分布之后，利用初始信息素分布開始多蟻群算法的尋優，多蟻群算法優化分布式數據庫查詢操作的相關參數及技術的設置如下：

（1） 轉移概率.搜索時，螞蟻對于下一個要訪問節點的選擇是非常隨機的.螞蟻在兩個節點之間選擇概率

pij=

[τij（t）]α[ηij]β∑k∈allowed[τik（t）]α[ηik]β，

if j∈allowed

0，otherwise

，（5）

其中，在概率計算的過程中信息素τij（t）所具有的權重用α來進行表示，這個值越大，信息素所占據的作用就會越明顯.ηij為啟發信息，β代表ηij在轉移概率計算的過程中所占的權重，當這個值越大，螞蟻選擇節點時其所起到的作用就會越明顯，k表示螞蟻下一步允許走的節點.

（2） 目標函數.目標函數用來衡量蟻群找到的路徑是否優秀，在分布式數據庫中的設置與上述遺傳算法一樣，總通信費用多少就是衡量路徑好壞的標準.

（3） 信息素的更新機制[7].采用傳統的信息素更新機制，如果在循環的過程中每一個螞蟻都搜尋到了路徑，而且路徑是合法的，那么就可以開始進行信息素的全局更新.

τij（t+1）=ρτij（t）+Δτij（t，t+1），（7）

其中在t次循環時，邊ij上的信息素濃度用τij（t+1）表示;信息素維持因子用ρ表示，相應的信息素揮發因子用（1-ρ）表示.對于在邊ij上所有螞蟻所釋放的信息素用Δτij（t，t+1）表示，k為在時刻t的第k只螞蟻，m為爬過邊ij上螞蟻的總個數：

Δτij（t，t+1）=∑mk=1Δτkij（t，t+1）.（8）

（4） 信息素平滑機制.當各個子蟻群迭代了一定次數后，相比其他的路徑，某一條路徑上的信息素濃度會比較大[8]，信息素濃度通過正反饋傳遞給螞蟻，螞蟻感知到這個情況，會大概率地選擇這條路徑來覓食，對于這種情況可以使用信息素平滑機制來改變，計算方法為：

τij=τij-δ（τij-τmin），（9）

其中，在邊ij上當前的信息素濃度值用τij進行表示;δ是平滑系數，控制著信息素平滑機制的影響程度.當δ=0，平滑機制關閉;當δ=1，平滑機制影響力最大，信息素值等于τmin，τmin表示事先設置好的信息素濃度最小值.

（5） 學習算子.大自然里的生物一直在進行優勝劣汰的進化，沒有一種生物是可以依靠獨自的能力生存，不同種群間會相互影響，同一個種群內更會相互交流融合，學習對方的長處，改進自己的短處，朝著更優的方向進化.這里引入學習算子，當迭代一定次數后，根據學習算子，更新各個子蟻群的全局信息素.學習算子：

τmij=τmij+γ×τnij，（10）

其中，τmij代表著當前子蟻群m在邊ij上的信息素值，τnij是當前子蟻群n在邊ij上的信息素值，γ是學習算子，主要作用是用來控制蟻群之間信息素交流作用的大小.

1.3算法步驟

作者提出的多蟻群遺傳算法具體步驟如下：

（1） 對分布式數據庫網絡拓撲結構進行有效地設置;

（2） 初始化遺傳算法相關參數值;

（3） 從初始起點開始，隨機找下一個點，再找下一個點，如同人走路一樣，以此來產生初始染色體種群;

（4） 開始進行迭代，對當代的染色體按概率進行變異以及交叉操作，在這個過程中產生新個體;

（5） 解碼染色體，將染色體轉換成查詢路徑，計算目標函數（也就是通信費用），以此來計算出染色體具體的適應度值;

（6） 利用輪盤賭法，依據各個染色體具體的適應度值進行選擇操作，進入下一次迭代;

（7） 判斷結束條件是不是得到了滿足，如果滿足的話，就輸出最優路徑，進入下一步驟;不滿足，則返回步驟（4）;

（8） 用最優查詢路徑對信息素矩陣進行初始化處理;

（9） 初始化多蟻群算法相關參數值;

（10） 利用遺傳算法來對初始信息素分布進行有效確定;

（11） 多個蟻群分別開始進行步驟（12）～（17）;

（12） 設置開始的節點，相當于發出查詢請求的網絡節點;

（13） 按照轉移概率的公式進行節點的轉移，同時更新路徑;

（14） 判斷螞蟻是否已完成所有目的節點的搜索，如果是，再判斷是否蟻群內所有的螞蟻都已經完成，若沒有，返回步驟（12）.如果蟻群內所有螞蟻都進行了搜索，求得每條路徑的具體目標函數值.

（15） 判斷當前迭代數是否大于蟻群開始信息素平滑機制的迭代數，若是，則按照信息素平滑機制操作.

（16） 判斷當前迭代數是否大于蟻群間開始學習信息素的迭代數，若是，則按照學習算子規則進行操作.

（17） 判斷當前迭代數是不是符合了結束條件，如果沒有符合，返回步驟（11）;否則，輸出結果.

2實驗仿真與分析

2.1相關參數的設置

在Matlab中對以上模型進行了仿真測試，并在相同環境下用傳統蟻群算法測試來與之對比.通過翻閱相關文獻，設置如下參數：

（1） 傳統蟻群算法參數：蟻群的大小M=10，信息素的揮發因子ρ=0.1，信息素的重要程度因子α=2，啟發函數重要程度的因子為β=3，蟻群最大迭代數imax=50.

（2） 多蟻群遺傳算法參數：遺傳算法相關參數設置：種群的大小M=20，最大的遺傳代數為gmax=50，然后交叉率Pc=0.7，變異率Pm=0.1.

多蟻群算法設置相關參數的具體方法：蟻群大小M、信息素的重要程度因子α、啟發函數重要程度的因子β、蟻群最大迭代數imax均與傳統蟻群算法設置一致，遺傳算法優化信息素的更新因子為ρ=0.1，蟻群1的信息素揮發因子為ρ1=0.1，蟻群2的信息素揮發因子ρ2=0.05，學習因子μ=0.05，蟻群間開始學習信息素的代數Nset1=10，蟻群開始信息素平滑機制的代數Nset2=10，信息素總量Q=10，信息素最大值Imax=0.5，信息素最小值Imin=0.01.

2.2實驗結果及分析

利用改進的Salama開發平臺隨機產生數量具有30和60節點的網絡進行測試.預設發出查詢命令的網絡節點是3，即源節點S，完成該查詢命令所需要的所有查詢數據分布在4、6、8、10、12這5個節點內，即目標節點E.如何從S通過一定的路徑與E相連，且這個路徑能使通信費用最低，這就是本次實驗所要的結果.

2.2.130個節點的網絡拓撲關系

從圖1和2中可以看出，多蟻群遺傳算法比傳統蟻群算法找到解經過的路徑更短，多蟻群遺傳算法在經過遺傳算法生成的初始信息素分布的指引下，經過的節點個數更少，優于傳統蟻群算法.

圖1多蟻群遺傳算法最優解爬行路徑（30節點）

圖2傳統蟻群算法最優解爬行路徑（30節點）

從圖3和4中可以看出，多蟻群遺傳算法比傳統蟻群算法找到的解在通信費用上更少.傳統蟻群算法一開始通信代價是550左右，在算法初期下降的速度比較快，但是當迭代了4次之后，通信費用下降的速度明顯減慢，到了第5代左右，就已經接近于收斂狀態，陷入局部最優，通信費用已經不再下降了，為478左右.而多蟻群遺傳算法在一開始通信費用下降的速度雖沒有基礎蟻群快，在第3代的時候有短暫的算法停滯，隨著平滑機制和學習機制的運行，算法跳出停滯狀態，繼續搜尋，到了第10代左右才開始趨于收斂，此時的通信代價已經降低到了367，優于傳統蟻群算法.

圖3多蟻群遺傳算法查詢收斂曲線（30節點）

圖4傳統蟻群算法查詢收斂曲線（30節點）

（2） 60個節點的網絡拓撲關系

從圖5和圖6中看出，多蟻群遺傳算法與傳統蟻群算法找到解經過的路徑，相比在30個網絡節點下實驗得到的，沒有明顯優勢，是因為螞蟻搜索路徑存在一定的隨機性.從通信費用角度來看，多蟻群遺傳算法還是優于傳統蟻群算法，詳細見圖7、圖8.

從圖7和8可以看出，兩個算法開始的收斂速度是傳統蟻群表現得較好，但這也是傳統蟻群過早地陷入局部最優的表現.多蟻群算法經過第5、10、15代的短時間搜索停滯之后，在第23代得到最優解.在最終得到的最優路徑的通信費用方面來講，還是多蟻群遺傳算法表現得更優.

圖5多蟻群遺傳算法最優解爬行路徑（60節點）

圖6傳統蟻群算法最優解爬行路徑（60節點）

圖7多蟻群遺傳算法查詢收斂曲線（60節點）

圖8傳統蟻群算法查詢收斂曲線（60節點）

3總結

本文作者提出了一種多蟻群遺傳算法，該算法融合了遺傳算法及蟻群算法的優點，并利用多蟻群概念來防止算法陷入局部最優的情況，同時使用平滑機制來克服蟻群算法早熟的缺點.在模擬的分布式數據庫下進行仿真測試，結果表明該算法在查詢優化方面較傳統蟻群，有更好的表現.

參考文獻：

[1]張鵬宇.分布式數據庫查詢處理和優化算法 [J].計算機光盤軟件與應用，2014，1（19）：106-108.

Zhang P Y.Distributed database query processing and optimization algorithm [J].Computer Disk Software and Applications，2014，1（19）：106-108.

[2]鄧松，林為民，張濤，馬媛媛.基于禁忌GEP的分布式數據庫查詢優化算法 [J].計算機與數字工程，2013，41（10）：1552-1555.

Deng S，Lin W M，Zhang T，et al.A distributed query optimization algorithm based on tabu GEP database [J].Computer and Digital Engineering，2013，41（10）：1552-1555.

[3]劉亞欣.遺傳-模擬退火算法在數據庫查詢優化中的應用 [J].大連交通大學學報，2009（1）：85-87.

Liu Y X.Application of genetic simulated annealing algorithm in database query optimization [J].Journal of Dalian Jiaotong University，2009（1）：85-87.

[4]夏鴻斌，須文波，劉淵.融合遺傳算法改進的蟻群算法 [J].江南大學學報（自然科學版），2009（02）：149-153.

Xia H B，Xu W，Liu Y.Improved ant colony algorithm based on fusion genetic algorithm [J].Journal of Jiangnan University （Natural Science），2009（2）：149-153.

[5]李攀.基于遺傳算法的分布式多連接查詢優化系統設計與實現 [D].昆明：云南大學，2010.

Li P.Design and Implementation of a distributed multi join query optimization system based on genetic algorithm [D].Kunming：Yunnan University，2010.

[6]Zukhri Z，Paputungan I V.A hybrid optimization algorithm based on genetic algorithm and ant colony optimization [J].International Journal of Artificial Intelligence & Applications，2013，4（5）：63-75.

[7]Dorigo M，Gambardella L M.Ant Colony System：A cooperative learning approach to the traveling salesman problem [J].IEEE Transactions on Evolutionary Computation，1997，1（1）：53-66.

[8]Crawford B，Soto R，Johnson F，et al.A Max-Min Ant system algorithm to solve the software project scheduling problem [J].Information Systems & Technologies，2014，41（15）：1-4.