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

蔣 然

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

?

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

蔣 然

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

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

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

Class Number TP391

1 引言

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

2 研究現(xiàn)狀

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

3 NGA-SDD-1算法

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

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

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

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

(1)

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

(2)

定義3 個(gè)體之間的距離dij,在解個(gè)體的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為參與變異操作的個(gè)體適應(yīng)值,其余符號(hào)同定義6,則變異概率用如下公式表示[14]：

(7)

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

(8)

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

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

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

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

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

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

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

4 實(shí)驗(yàn)

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

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

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

4.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

表1 三種算法的通信費(fèi)用對(duì)比情況

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

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

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

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

綜上所述,NGA-SDD-1算法生成查詢計(jì)劃的時(shí)間比SDD-1算法要短,而比I-SDD-1算法時(shí)間略長(zhǎng),但通信費(fèi)用卻比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é)合小生境進(jìn)化的優(yōu)勢(shì)構(gòu)造了小生境混合遺傳算法,提出一種基于小生境遺傳算法的SDD-1分布式查詢優(yōu)化算法,該算法改變了遺傳算法內(nèi)部的搜索結(jié)構(gòu)。實(shí)驗(yàn)表明,相比SDD-1算法和I-SDD-1算法,本文算法具有更優(yōu)的性能。

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

[2] 李芳萍.基于半連接策略的分布式數(shù)據(jù)庫(kù)查詢優(yōu)化理論研究及應(yīng)用[D].長(zhǎng)沙：中南大學(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] 吳洋,溫佩芝,鄧星,等.一種改進(jìn)的分布式數(shù)據(jù)庫(kù)查詢優(yōu)化遺傳算法[J].桂林電子科技大學(xué)學(xué)報(bào),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ù)庫(kù)查詢算法的改進(jìn)與應(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ù)庫(kù)多連接查詢優(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è)計(jì)與實(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ù)庫(kù)查詢優(yōu)化研究[J].小型微型計(jì)算機(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ù)庫(kù)查詢優(yōu)化中的應(yīng)用[J].內(nèi)蒙古師范大學(xué)學(xué)報(bào),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ù)庫(kù)有關(guān)連接查詢優(yōu)化算法的研究[D].長(zhǎng)沙：長(zhǎng)沙理工大學(xué),2010. NIU Yuanyuan. Researth on Join Query Optimization Algorithm in Distributed Database[D].Changsha：Changsha University of Science & Technology,2010.

[10] 林基明,班文嬌,王俊義,等.基于并行遺傳-最大最小蟻群算法的分布式數(shù)據(jù)庫(kù)查詢優(yōu)化[J].計(jì)算機(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ù)庫(kù)的查詢優(yōu)化算法的改進(jìn)[D].長(zhǎng)春：吉林大學(xué),2011. ZENG Yingying. An Improved Query Optimization Algorithm Based on Heterogeneous Database[D].Changchun：Jilin University,2011.

[12] 宋倩.SDD-1算法的改進(jìn)及其應(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ù)庫(kù)查詢優(yōu)化研究[J].長(zhǎng)江大學(xué)學(xué)報(bào)(自然版),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].鄭州：中國(guó)人民解放軍信息工程大學(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ìn)[J].河南教育學(xué)院學(xué)報(bào)(自然科學(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ù)庫(kù)、信息檢索、查詢優(yōu)化。

TP391

10.3969/j.issn.1672-9722.2016.11.007