蔣 然

(揚州市職業(yè)大學(xué)信息工程學(xué)院 揚州 225000)

?

基于小生境遺傳算法的SDD-1分布式查詢優(yōu)化算法*

蔣 然

(揚州市職業(yè)大學(xué)信息工程學(xué)院 揚州 225000)

SDD-1算法是一種分布式數(shù)據(jù)庫的查詢優(yōu)化算法,遺傳算法已經(jīng)在許多領(lǐng)域得到了成功的應(yīng)用。針對基于遺傳算法的SDD-1算法中,遺傳算法存在“早熟收斂”的問題,提出一種基于小生境遺傳算法的SDD-1分布式查詢優(yōu)化算法,該算法能在盡可能短的時間內(nèi)求解通信費用最小的查詢計劃。實驗結(jié)果表明,該算法比單獨使用SDD-1算法、基于遺傳算法的SDD-1算法均有更優(yōu)的性能。

小生境技術(shù); 遺傳算法; SDD-1算法; 早熟收斂; 查詢優(yōu)化; 分布式數(shù)據(jù)庫

Class Number TP391

1 引言

在分布式數(shù)據(jù)庫中,查詢優(yōu)化包括查詢策略優(yōu)化和局部處理優(yōu)化[1]兩個內(nèi)容,其中查詢策略優(yōu)化尤為重要。查詢執(zhí)行開銷主要包括I/O代價+CPU代價+通信代價。全局查詢涉及多個站點的數(shù)據(jù),為了執(zhí)行全局查詢和確定一個好的查詢策略,首先需進行查詢分解,然后再確定操作執(zhí)行的次序,最后確定操作的執(zhí)行方法,其中關(guān)鍵是確定操作執(zhí)行的次序,即主要是確定連接操作的順序。

2 研究現(xiàn)狀

連接操作是影響分布式查詢效率的關(guān)鍵因素。為了使分布式數(shù)據(jù)庫能有效地處理連接操作,國內(nèi)外學(xué)者一直在進行這方面的研究,形成了各種不同的算法。一般可分為兩類：基于半連接策略的查詢優(yōu)化算法和基于直接連接策略的查詢優(yōu)化算法[2]。隨著人工智能和各種工程優(yōu)化方法的發(fā)展成熟,人們把很多新的算法引入到分布式數(shù)據(jù)庫的查詢領(lǐng)域。文獻[3～11]中都提出用遺傳算法對分布式數(shù)據(jù)庫查詢過程進行優(yōu)化,其中文獻[12]提出了一種改進的SDD-1算法(簡稱I-SDD-1算法),即把遺傳算法引入進來,在基于半連接操作的基礎(chǔ)上重新構(gòu)造生成查詢計劃的方法。利用遺傳算法的快速全局搜索能力,在較短的時間內(nèi)求解最佳的半連接執(zhí)行序列。但遺傳算法存在“早熟收斂”的缺點,小生境技術(shù)是解決早熟收斂的一個有效方法,因此本文在基于遺傳算法的SDD-1算法的基礎(chǔ)上,結(jié)合小生境進化的優(yōu)勢構(gòu)造了小生境混合遺傳算法,提出一種基于小生境遺傳算法的SDD-1分布式查詢優(yōu)化算法(簡稱NGA-SDD-1算法),有效地克服了遺傳算法的“早熟”現(xiàn)象。

3 NGA-SDD-1算法

3.1 NGA-SDD-1算法基本思想

NGA-SDD-1算法試圖用小生境遺傳算法去尋找通信費用最小的查詢計劃。用通信費用作為衡量染色體優(yōu)劣的指標；通過構(gòu)造合適的遺傳算子,對小生境群體進行一系列的選擇、交叉和變異操作；以收斂率作為迭代結(jié)束的條件,有效縮減查詢時間。算法的最終結(jié)果是一個通信費用最小的半連接序列。

為方便描述,引入定義如下：

定義1 相似度S,是指形態(tài)各異的染色體上的基因排列順序的相似程度,以S(x,y)表示初始種群中某一個體的x和y兩個染色體上的基因排列順序的相似度；(2M-1)表示每條染色體所含基因的總量；x[N]表示在染色體x中位置N處的基因,y[N]表示在染色體y中位置N處的基因。則相似度S用如下公式表示[13]：

(1)

定義2 染色體的總相似度Sx,將該染色體與其他所有的染色體之間的相似度求和,用S(Ax,Ay)表示某一條染色體與另一條染色體的相似度,如果初始種群為M,假設(shè)存在2M個染色體,則某一條染色體的總相似度Sx用如下公式表示：

(2)

定義3 個體之間的距離dij,在解個體的n維空間內(nèi),令xi=(xi1,xi2,…,xin),xj=(xj1,xj2,…,xjn),其中M表示群體大小,則兩者之間的距離用如下公式表示：

(3)

定義4 適應(yīng)度函數(shù)f(x),適應(yīng)度函數(shù)定義為

f(x)=104/g(x)

(4)

(5)

(6)

定義7 小生境群體的變異概率pim(1≤i≤N),f為參與變異操作的個體適應(yīng)值,其余符號同定義6,則變異概率用如下公式表示[14]：

(7)

定義8 收斂率α,∑Imax表示群體中含有最大適應(yīng)度的個體數(shù)目,∑I表示群體中的個體數(shù)目,則收斂率α用如下公式表示：

(8)

3.2 NGA-SDD-1算法具體描述

NGA-SDD-1算法就是將半連接操作和小生境遺傳算法結(jié)合起來,在有效縮減通信費用的同時,兼顧查詢計劃的生成效率,即在盡可能短的時間內(nèi)找到通信費用最小的查詢計劃。本文算法的步驟如下：

2) 初始種群的構(gòu)造。為了將小生境遺傳算法和SDD-1算法有效地結(jié)合,并使得所構(gòu)造的初始種群具有多樣性,從而進一步提高小生境技術(shù)的作用,為此引入了定義1及式(1),若初始種群的數(shù)量用M來表示,假設(shè)存在2M個染色體,利用式(2)求出2M個總相似度,并將2M個總相似度以升序的形式排序,選取前M個相似度較小的染色體構(gòu)造初始種群。

3) 小生境群體的構(gòu)造。小生境群體的大小,決定著遺傳進化的效率。首先給出小生境的半徑σ、小生境的容量Smax,任意選取一個元素xo,作為小生境群體的中心O,利用式(3)分別計算出該個體與其它個體xi之間的距離d,當(dāng)d≤σ且小生鏡群體中個體數(shù)小于其容量Smax時,把個體xi歸為第一個小生鏡群體中；在余下的群體個體中,選出一個個體作為另一個小生境群體的中心,構(gòu)造第二個小生境群體,依次類推,直到所有的個體分配到相應(yīng)的小生境群體中。計生成的小生境群體總數(shù)為N(N

6) 對相關(guān)聯(lián)的小生境群體作最優(yōu)個體替換。對相關(guān)聯(lián)的小生境群體進行調(diào)整,具體方法是用一個群體內(nèi)函數(shù)值最大的個體去替換另一個小生境群體中函數(shù)值最小的個體。這種方法使得優(yōu)勢個體資源得到了共享,加快了小生境群體的進化速度。

7) 對各個小生境群體進行獨立的遺傳操作。選擇操作采用最佳個體保存方法,即當(dāng)前群體中個體適應(yīng)度最高的個體不參與交叉和變異運算,而是用它來替換掉本代群體中經(jīng)過交叉、變異等操作后所產(chǎn)生的適應(yīng)度最低的個體；利用式(6)進行交叉操作；利用式(7)進行變異操作。

8) 終止條件判斷：滿足條件結(jié)束運算,否則,繼續(xù)迭代。收斂率是保障遺傳算法收斂的一個重要依據(jù),利用式(8)進行計算,當(dāng)α值較大時(α>0.9)時,說明遺傳算法己經(jīng)收斂,可選擇其最優(yōu)個體為全局最優(yōu)解。否則,繼續(xù)迭代。

4 實驗

4.1 實驗內(nèi)容及參數(shù)確定

根據(jù)SDD-1算法、I-SDD-1算法和NGA-SDD-1算法的流程,對它們分別進行了實驗仿真,目的是對比SDD-1算法、I-SDD-1算法和NGA-SDD-1算法生成查詢計劃的時間和所生成查詢計劃的通信費用。程序的開發(fā)環(huán)境為VC++6.0,程序的測試環(huán)境為INTEL酷睿i5雙核1.70GHzCpU,4GB內(nèi)存,Microsoft Windows8操作系統(tǒng)。

本文實驗中算法的參數(shù)設(shè)置為：種群規(guī)模為100,交叉概率和變異概率采用動態(tài)自適應(yīng)技術(shù),根據(jù)種群的實際情況隨機調(diào)整大小,當(dāng)收斂率大于0.9時算法終止。

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

針對相同的查詢,在同樣的實驗條件下,對SDD-1算法、I-SDD-1算法和NGA-SDD-1算法所生成的半連接執(zhí)行策略進行仿真實驗測試。實驗設(shè)計了6組數(shù)據(jù),第1組到第6組數(shù)據(jù)涉及的半連接數(shù)目分別是6、10、20、50、100和1000,每一組數(shù)據(jù)中都包含50個代表不同站點屬性的記錄。

首先記錄三種算法的仿真程序生成查詢計劃的時間,對每組數(shù)據(jù)中的50個結(jié)果求平均值。三種算法根據(jù)上述6組實驗數(shù)據(jù)得到實驗結(jié)果,每組數(shù)據(jù)生成查詢計劃所用時間平均值的情況如圖1所示。

由圖1的結(jié)果可以看出,SDD-1算法生成查詢

計劃的時間增長較快,特別是在半連接數(shù)為100時,是生成查詢計劃時間迅速增長的一個轉(zhuǎn)折點,而I-SDD-1算法和NGA-SDD-1算法生成查詢計劃的時間增長比較緩慢,由于NGA-SDD-1算法較I-SDD-1算法引入了小生境技術(shù),因而在尋求最優(yōu)解的時間上略有增加。

然后記錄三種算法的仿真程序所生成查詢計劃的通信費用,根據(jù)上述6組實驗數(shù)據(jù),三種算法所生成的查詢計劃的通信費用平均值的情況如表1所示。

表1 三種算法的通信費用對比情況

由表1可以看出,NGA-SDD-1算法生成的查詢計劃的通信費用的平均值要比SDD-1算法和I-SDD-1算法都要小。

最后在上述實驗的基礎(chǔ)上,對每組數(shù)據(jù)中的每條記錄都重復(fù)10次,這10次實驗中,若NGA-SDD-1算法和I-SDD-1算法所得的通信費用小于SDD-1算法,則記該算法收斂于最優(yōu)解,用收斂于最優(yōu)解的次數(shù)除以10,得到該記錄收斂于最優(yōu)解的概率。取每一組數(shù)據(jù)50個記錄收斂概率的平均值為算法的收斂概率,結(jié)果如圖2所示。

圖2 兩種算法在不同連接數(shù)下的收斂概率

由圖2可知,隨著連接數(shù)的增多,兩種算法的收斂概率都呈下降趨勢,主要原因是隨著半連接數(shù)目的增多,初始種群的多樣性受到限制,但NGA-SDD-1算法由于采用小生境遺傳算法,應(yīng)用定義1及采用自變異算子有利于進化過程中群體中個體的多樣化,有效地克服了遺傳算法的提前收斂。實驗結(jié)果顯示,NGA-SDD-1算法的收斂概率都在0.9以上,明顯優(yōu)于I-SDD-1算法的收斂概率。

綜上所述,NGA-SDD-1算法生成查詢計劃的時間比SDD-1算法要短,而比I-SDD-1算法時間略長,但通信費用卻比SDD-1算法和I-SDD-1算法小很多,因而NGA-SDD-1算法的綜合查詢效率要優(yōu)于SDD-1算法和I-SDD-1算法。

5 結(jié)語

本文在以半連接操作為基礎(chǔ)的分布式查詢優(yōu)化算法SDD-1算法和遺傳算法相結(jié)合的基礎(chǔ)上,引入小生境技術(shù),結(jié)合小生境進化的優(yōu)勢構(gòu)造了小生境混合遺傳算法,提出一種基于小生境遺傳算法的SDD-1分布式查詢優(yōu)化算法,該算法改變了遺傳算法內(nèi)部的搜索結(jié)構(gòu)。實驗表明,相比SDD-1算法和I-SDD-1算法,本文算法具有更優(yōu)的性能。

[1] Patrik ONeil,Elizabeth ONeil.數(shù)據(jù)庫原理、編程與性能[M].第2版.北京：機械工業(yè)出版社,2004. Patrik ONeil,Elizabeth ONeil.Database theory,programming and performance[M].Second Edition.Beijing：Machinery Industry Press,2004.

[2] 李芳萍.基于半連接策略的分布式數(shù)據(jù)庫查詢優(yōu)化理論研究及應(yīng)用[D].長沙：中南大學(xué),2008. LI Fangping. Research and Application of Distributed Database Query Optimization Theory Based On Semi Join Strategy [D].Changsha：Centural South University,2008.

[3] 吳洋,溫佩芝,鄧星,等.一種改進的分布式數(shù)據(jù)庫查詢優(yōu)化遺傳算法[J].桂林電子科技大學(xué)學(xué)報,2015,35(3)：217-221. WU Yang, WEN Peizhi, DENG Xing, et al. An improved genetic algorithm for optimization of distributed database query[J].Journal of Guilin University of Electronic Technology,2015,35(3)：217-221.[4] 陳復(fù)興.分布式數(shù)據(jù)庫查詢算法的改進與應(yīng)用[D].南昌：江西師范大學(xué),2014. Chen Fuxing. Improvement and Application an Query Algorithm of Distributed Database[D].Nanchang：Jiangxi Normal University,2014.

[5] 錢磊.分布式數(shù)據(jù)庫多連接查詢優(yōu)化算法研究[D].哈爾濱：燕山大學(xué),2011. QIAN Lei. A study of Multi-join Query Optimization Algorithm In Distributed Databse[D].Harbin：Yanshan University,2011.

[6] 李攀.基于遺傳算法的分布式多連接查詢優(yōu)化系統(tǒng)設(shè)計與實現(xiàn)[D].昆明：云南大學(xué),2010. LI Pan.Design and Implementation of Distributed Multi-join Query Optimization System Based On Genetic Algorithm[D].Kunming：Yunnan University,2010.

[7] 帥訓(xùn)波,馬書男,周相廣,等.基于遺傳算法的分布式數(shù)據(jù)庫查詢優(yōu)化研究[J].小型微型計算機系統(tǒng),2009,30(8)：1600-1604. SHUAI Xunbo, MA Shunan, ZHOU Xiangguang, et al. Research of Query Optimization Based on Genetic Algorithm in Distributed Database[J].Journal of Chinese Computer Systems,2009,30(8)：1600-1604.

[8] 潘潁.自適應(yīng)遺傳算法的在分布式數(shù)據(jù)庫查詢優(yōu)化中的應(yīng)用[J].內(nèi)蒙古師范大學(xué)學(xué)報,2016,45(1)：94-97. PAN Ying. Application of Query Optimization Based on Adaptive Genetic Algorithm in Distributde Database[J].Journal of Inner Mongolia Normal University,2016,45(1)：94-97.

[9] 牛園園.分布式數(shù)據(jù)庫有關(guān)連接查詢優(yōu)化算法的研究[D].長沙：長沙理工大學(xué),2010. NIU Yuanyuan. Researth on Join Query Optimization Algorithm in Distributed Database[D].Changsha：Changsha University of Science & Technology,2010.

[10] 林基明,班文嬌,王俊義,等.基于并行遺傳-最大最小蟻群算法的分布式數(shù)據(jù)庫查詢優(yōu)化[J].計算機應(yīng)用,2016,36(3)：675-680. LIN Jiming, BAN Wenjiao, Wang Junyi. Query optimization for distributed database based on parallel genetic algorithm and max-min ant system[J].Journal of Computer Applications,2016,36(3)：675-680.

[11] 曾瑩瑩.基于異構(gòu)數(shù)據(jù)庫的查詢優(yōu)化算法的改進[D].長春：吉林大學(xué),2011. ZENG Yingying. An Improved Query Optimization Algorithm Based on Heterogeneous Database[D].Changchun：Jilin University,2011.

[12] 宋倩.SDD-1算法的改進及其應(yīng)用研究[D].西安：西安電子科技大學(xué),2010. SONG Qian. Researth of the SDD-1 Algorithm’s Improvement and its Appliation[D].Xi’an：XiDian University,2010.

[13] 鄒汪平.基于NGSAA算法的分布式數(shù)據(jù)庫查詢優(yōu)化研究[J].長江大學(xué)學(xué)報(自然版),2013,10(25)：46-52. ZOU Wangping. Research on Query Optimization of Distributed Database Based on NGSAA Algorithm[J].Journal of Yangtze University(Nat Sci Edit) ,2013,10(25)：46-52.

[14] 王亞子.小生境與并行遺傳算法研究[D].鄭州：中國人民解放軍信息工程大學(xué),2006. WANG Yazi. Research on the Niche and parallel Genetic Algorithm[D].Zhengzhou：Chinese people’s The PLA Information Engineering University,2006.

[15] 王亞子,賈利新.遺傳算法的小生境技術(shù)改進[J].河南教育學(xué)院學(xué)報(自然科學(xué)版),2008,17(1)：28-29. WANG Yazi, JIA Lixin. Improvement of Niche Skill On Genetic Algorithm[J].Journal of Henan Institute of Education (Natural Science) ,2008,17(1)：28-29.

SDD-1 Distributed Query Optimization Algorithm Based on Niche Genetic Algorithm

JIANG Ran

(Faculty of Information Engineering,Yangzhou Ploytechnic College, Yangzhou 225000)

SDD-1 algorithm is a distributed query optimization algorithm,the genetic algorithm has been successfully applied in many fields .In the SDD-1 algorithm based on genetic algorithm, genetic algorithm has a problem of “premature convergence”.To solve this problem,SDD-1 distributed query optimization algorithm based on niche genetic algorithm is proposed in this research.This algorithm can solve the query plan of minimum communication cost in possible time.Experimental results show that this algorithm has a better performance than SDD-1 algorithm and SDD-1 algorithm based on genetic algorithm.

niche technique, genetic algorithm, SDD-1 algorithm, premature convergence, query optimization, distributed database

2016年5月20日,

2016年6月27日

蔣然,女,碩士研究生，講師，研究方向：數(shù)據(jù)庫、信息檢索、查詢優(yōu)化。

TP391

10.3969/j.issn.1672-9722.2016.11.007