周瑩 陳軍華

摘要：

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

關(guān)鍵詞：

分布式數(shù)據(jù)庫; 多蟻群; 遺傳算法; 查詢優(yōu)化

中圖分類號： TP 311文獻(xiàn)標(biāo)志碼： 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-），女，碩士研究生，主要從事數(shù)據(jù)庫方面的研究.E-mail：200865689@qq.com

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

*通信作者

引用格式： 周瑩，陳軍華.基于多蟻群遺傳算法的分布式數(shù)據(jù)庫查詢優(yōu)化 [J].上海師范大學(xué)學(xué)報（自然科學(xué)版），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.

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

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

1算法模型

多蟻群遺傳算法的基本思想是：通過遺傳算法處理，產(chǎn)生初始的信息素分布，多蟻群算法利用這個初始信息素分布開始尋優(yōu)，多個蟻群間先互相獨立尋優(yōu)，當(dāng)?shù)鷶?shù)滿足條件時，依照平滑機(jī)制跳出局部最優(yōu)，并利用學(xué)習(xí)機(jī)制獲得更好的全局最優(yōu)解，這個解就是查詢路徑.

1.1遺傳算法

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

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

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

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

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

fitness=1C.（2）

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

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

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

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

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

1.2多蟻群算法

在大自然中，蟻群的覓食活動往往不是單個蟻群獨立進(jìn)行的，通常在同一個環(huán)境中存在著多個蟻群，它們互相影響，互相學(xué)習(xí)，共同進(jìn)化[6].在傳統(tǒng)蟻群的基礎(chǔ)上引入多蟻群的概念，這種概念指的就是采用劃分的方法對一個總的蟻群進(jìn)行有效地處理，用不同的參數(shù)控制著各個子蟻群，子蟻群間獨立尋優(yōu)，這樣在每個子蟻群中就會產(chǎn)生不同的信息素分布，有著不同的進(jìn)化方向.當(dāng)?shù)欢ù螖?shù)后，子蟻群內(nèi)可能會陷入停滯狀態(tài)，這時各個子蟻群間利用“學(xué)習(xí)算子”開始進(jìn)行信息素的交流，打破停滯的僵局，推動蟻群再次進(jìn)化，防止算法出現(xiàn)局部最優(yōu)的現(xiàn)象.引入多蟻群的做法，意在讓算法更貼近大自然實際規(guī)律，多蟻群能夠?qū)崿F(xiàn)互幫互助，共同進(jìn)化，最終獲得最優(yōu)解.

前期利用遺傳算法進(jìn)行處理獲得初始信息素分布之后，利用初始信息素分布開始多蟻群算法的尋優(yōu)，多蟻群算法優(yōu)化分布式數(shù)據(jù)庫查詢操作的相關(guān)參數(shù)及技術(shù)的設(shè)置如下：

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

pij=

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

if j∈allowed

0，otherwise

，（5）

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

（2） 目標(biāo)函數(shù).目標(biāo)函數(shù)用來衡量蟻群找到的路徑是否優(yōu)秀，在分布式數(shù)據(jù)庫中的設(shè)置與上述遺傳算法一樣，總通信費用多少就是衡量路徑好壞的標(biāo)準(zhǔn).

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

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

其中在t次循環(huán)時，邊ij上的信息素濃度用τij（t+1）表示;信息素維持因子用ρ表示，相應(yīng)的信息素?fù)]發(fā)因子用（1-ρ）表示.對于在邊ij上所有螞蟻所釋放的信息素用Δτij（t，t+1）表示，k為在時刻t的第k只螞蟻，m為爬過邊ij上螞蟻的總個數(shù)：

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

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

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

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

（5） 學(xué)習(xí)算子.大自然里的生物一直在進(jìn)行優(yōu)勝劣汰的進(jìn)化，沒有一種生物是可以依靠獨自的能力生存，不同種群間會相互影響，同一個種群內(nèi)更會相互交流融合，學(xué)習(xí)對方的長處，改進(jìn)自己的短處，朝著更優(yōu)的方向進(jìn)化.這里引入學(xué)習(xí)算子，當(dāng)?shù)欢ù螖?shù)后，根據(jù)學(xué)習(xí)算子，更新各個子蟻群的全局信息素.學(xué)習(xí)算子：

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

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

1.3算法步驟

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

（1） 對分布式數(shù)據(jù)庫網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行有效地設(shè)置;

（2） 初始化遺傳算法相關(guān)參數(shù)值;

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

（4） 開始進(jìn)行迭代，對當(dāng)代的染色體按概率進(jìn)行變異以及交叉操作，在這個過程中產(chǎn)生新個體;

（5） 解碼染色體，將染色體轉(zhuǎn)換成查詢路徑，計算目標(biāo)函數(shù)（也就是通信費用），以此來計算出染色體具體的適應(yīng)度值;

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

（7） 判斷結(jié)束條件是不是得到了滿足，如果滿足的話，就輸出最優(yōu)路徑，進(jìn)入下一步驟;不滿足，則返回步驟（4）;

（8） 用最優(yōu)查詢路徑對信息素矩陣進(jìn)行初始化處理;

（9） 初始化多蟻群算法相關(guān)參數(shù)值;

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

（11） 多個蟻群分別開始進(jìn)行步驟（12）～（17）;

（12） 設(shè)置開始的節(jié)點，相當(dāng)于發(fā)出查詢請求的網(wǎng)絡(luò)節(jié)點;

（13） 按照轉(zhuǎn)移概率的公式進(jìn)行節(jié)點的轉(zhuǎn)移，同時更新路徑;

（14） 判斷螞蟻是否已完成所有目的節(jié)點的搜索，如果是，再判斷是否蟻群內(nèi)所有的螞蟻都已經(jīng)完成，若沒有，返回步驟（12）.如果蟻群內(nèi)所有螞蟻都進(jìn)行了搜索，求得每條路徑的具體目標(biāo)函數(shù)值.

（15） 判斷當(dāng)前迭代數(shù)是否大于蟻群開始信息素平滑機(jī)制的迭代數(shù)，若是，則按照信息素平滑機(jī)制操作.

（16） 判斷當(dāng)前迭代數(shù)是否大于蟻群間開始學(xué)習(xí)信息素的迭代數(shù)，若是，則按照學(xué)習(xí)算子規(guī)則進(jìn)行操作.

（17） 判斷當(dāng)前迭代數(shù)是不是符合了結(jié)束條件，如果沒有符合，返回步驟（11）;否則，輸出結(jié)果.

2實驗仿真與分析

2.1相關(guān)參數(shù)的設(shè)置

在Matlab中對以上模型進(jìn)行了仿真測試，并在相同環(huán)境下用傳統(tǒng)蟻群算法測試來與之對比.通過翻閱相關(guān)文獻(xiàn)，設(shè)置如下參數(shù)：

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

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

多蟻群算法設(shè)置相關(guān)參數(shù)的具體方法：蟻群大小M、信息素的重要程度因子α、啟發(fā)函數(shù)重要程度的因子β、蟻群最大迭代數(shù)imax均與傳統(tǒng)蟻群算法設(shè)置一致，遺傳算法優(yōu)化信息素的更新因子為ρ=0.1，蟻群1的信息素?fù)]發(fā)因子為ρ1=0.1，蟻群2的信息素?fù)]發(fā)因子ρ2=0.05，學(xué)習(xí)因子μ=0.05，蟻群間開始學(xué)習(xí)信息素的代數(shù)Nset1=10，蟻群開始信息素平滑機(jī)制的代數(shù)Nset2=10，信息素總量Q=10，信息素最大值Imax=0.5，信息素最小值Imin=0.01.

2.2實驗結(jié)果及分析

利用改進(jìn)的Salama開發(fā)平臺隨機(jī)產(chǎn)生數(shù)量具有30和60節(jié)點的網(wǎng)絡(luò)進(jìn)行測試.預(yù)設(shè)發(fā)出查詢命令的網(wǎng)絡(luò)節(jié)點是3，即源節(jié)點S，完成該查詢命令所需要的所有查詢數(shù)據(jù)分布在4、6、8、10、12這5個節(jié)點內(nèi)，即目標(biāo)節(jié)點E.如何從S通過一定的路徑與E相連，且這個路徑能使通信費用最低，這就是本次實驗所要的結(jié)果.

2.2.130個節(jié)點的網(wǎng)絡(luò)拓?fù)潢P(guān)系

從圖1和2中可以看出，多蟻群遺傳算法比傳統(tǒng)蟻群算法找到解經(jīng)過的路徑更短，多蟻群遺傳算法在經(jīng)過遺傳算法生成的初始信息素分布的指引下，經(jīng)過的節(jié)點個數(shù)更少，優(yōu)于傳統(tǒng)蟻群算法.

圖1多蟻群遺傳算法最優(yōu)解爬行路徑（30節(jié)點）

圖2傳統(tǒng)蟻群算法最優(yōu)解爬行路徑（30節(jié)點）

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

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

圖4傳統(tǒng)蟻群算法查詢收斂曲線（30節(jié)點）

（2） 60個節(jié)點的網(wǎng)絡(luò)拓?fù)潢P(guān)系

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

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

圖5多蟻群遺傳算法最優(yōu)解爬行路徑（60節(jié)點）

圖6傳統(tǒng)蟻群算法最優(yōu)解爬行路徑（60節(jié)點）

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

圖8傳統(tǒng)蟻群算法查詢收斂曲線（60節(jié)點）

3總結(jié)

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

參考文獻(xiàn)：

[1]張鵬宇.分布式數(shù)據(jù)庫查詢處理和優(yōu)化算法 [J].計算機(jī)光盤軟件與應(yīng)用，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的分布式數(shù)據(jù)庫查詢優(yōu)化算法 [J].計算機(jī)與數(shù)字工程，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]劉亞欣.遺傳-模擬退火算法在數(shù)據(jù)庫查詢優(yōu)化中的應(yīng)用 [J].大連交通大學(xué)學(xué)報，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ìn)的蟻群算法 [J].江南大學(xué)學(xué)報（自然科學(xué)版），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]李攀.基于遺傳算法的分布式多連接查詢優(yōu)化系統(tǒng)設(shè)計與實現(xiàn) [D].昆明：云南大學(xué)，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.