發(fā)布時間：2020-11-11 16:23

　　 隨著信息社會的發(fā)展,數(shù)據(jù)庫技術(shù)在組織與管理數(shù)據(jù)方面已經(jīng)發(fā)展為重要的技術(shù)手段。在數(shù)據(jù)庫所有操作中,查詢操作的使用頻率最高,那么作為一個非常重要的操作,查詢在處理大量信息的過程中擔(dān)任了不可忽視的角色。從數(shù)據(jù)庫的相關(guān)理論出發(fā),本文對查詢算法進行了研究和剖析。遺傳算法具備普遍性、通用性和收斂速度快等特點,但該算法的缺點是局部最優(yōu)解的出現(xiàn)概率較高;在尋求最優(yōu)解方面,蟻群算法效果良好,但在搜索路徑前期,由于只有少量信息素,算法缺乏信息素的引導(dǎo),螞蟻選擇路徑具有一定程度的盲目性與隨機性,導(dǎo)致算法消耗大量時間才能得到最優(yōu)解;遺傳蟻群算法的混合,即保證了快速收斂,也提高了尋求解的性能。在此基礎(chǔ)上,如何改進現(xiàn)有的遺傳蟻群混合算法來進一步提高數(shù)據(jù)庫多連接查詢優(yōu)化效率成為本文的研究重點。本文分別對以下情況進行了研究:通過研究種群多樣性,對選擇算子進行了分析,為避免在算法進化過程中,選擇效率隨著多樣性的降低而降低,本文提出了自適應(yīng)選擇策略,提高選擇算子效率,增加復(fù)雜后代個體的可能性;由于交叉位置的隨機性,算法容易出現(xiàn)無效交叉,降低算法求解效率,本文分析了二點交叉的原理,根據(jù)相關(guān)性原則,對交叉操作進行了改進;本文研究了遺傳算法和蟻群算法各自的求解趨勢,為避免因為盲目的固定迭代次數(shù)而錯過算法最佳銜接時刻,根據(jù)種群多樣性在算法進化過程中的變化趨勢,判斷遺傳算法收斂狀態(tài),對混合算法的銜接采用了自適應(yīng)方法;在種群迭代過程中,容易出現(xiàn)最優(yōu)個體沒有有效進化、局部收斂的現(xiàn)象,本文對子代種群生成方式進行了改進,以降低最優(yōu)個體被過濾的概率。綜上所述,本文從選擇策略、交叉操作、算法銜接點以及子代種群這幾方面對遺傳蟻群算法進行了改進,仿真實驗證明,改進算法的求解效率提升了17%,并且縮短了執(zhí)行時間和收斂代數(shù)。
【學(xué)位單位】：北京工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2019
【中圖分類】：TP18;TP311.13
【部分圖文】：

查詢原理庫都具備一個基于成本的查詢優(yōu)化器，用于從所有執(zhí)行方案中略，對于數(shù)據(jù)庫來說，適當(dāng)?shù)牟樵儓?zhí)行策略會大幅度提升系統(tǒng)的多連接查詢語句，數(shù)據(jù)庫可以為其生成多種執(zhí)行方案，那么所有執(zhí)行方案，然后找出代價成本最低，花費時間最少的執(zhí)行查詢優(yōu)化來說，它不僅是數(shù)據(jù)庫關(guān)鍵實現(xiàn)技術(shù)點，也是關(guān)系型于一個查詢來說，查詢優(yōu)化是優(yōu)化其關(guān)系代數(shù)級，查找出執(zhí)行表達式等價的方案，例如選擇執(zhí)行運算所采用的具體算法等[30L 語言的過程中，不需要考慮一系列復(fù)雜的情況，如數(shù)據(jù)集的存、存儲結(jié)果等，只需要用標準 SQL 語言來表達自己的意圖，關(guān)統(tǒng)的任務(wù)就是實現(xiàn)用戶的意圖。目前，有許多關(guān)系型數(shù)據(jù)庫系據(jù)庫各有優(yōu)勢，查詢語句格式、處理方案可能不同，但是查詢，查詢步驟如圖 2-1 所示：

圖 2-2 數(shù)據(jù)庫多連接查詢模型Figure 2-2 Database Multi-connection Query Model數(shù)據(jù)庫多連接查詢優(yōu)化的核心就是從 QEP 中找到最優(yōu)的執(zhí)行計劃，在 QEP的所有執(zhí)行計劃中，該連接順序執(zhí)行代價最小、復(fù)雜度最低。由上文可知，多連接查詢優(yōu)化原理和經(jīng)典 TSP 問題中查找最優(yōu)路徑的原理是相同的，其目的都是為了提高效率，降低時間成本。在對基本關(guān)系表優(yōu)化前，首先我們通過簡單的例子介紹一下如何把一個給定的查詢語句轉(zhuǎn)變成初步優(yōu)化后的關(guān)系代數(shù)表達式[34]。例如，有三張基本關(guān)系表，分別為 C（課程號 C#，課程名稱 Cname，代課老師 Teacher）、S（學(xué)號 S#，學(xué)生姓名 Sname，性別 Sex，年齡 Age）、SC（課程號 C#，學(xué)號 S#，分數(shù) Grade）。查詢語句為：班級所有女生選擇的課程。優(yōu)化前，該查詢語句的關(guān)系代數(shù)表達式為：πCname,Teacher(σSex="女"(S∞SC∞C))優(yōu)化前的語法樹如圖 2-3 所示：

圖 2-3 優(yōu)化前語法樹Figure 2-3 Pre-optimization Grammar Tree是，盡量提前做選擇操作，在每個操作后根性。所以優(yōu)化后的關(guān)系代數(shù)表達式為：ame,Teacher(C∞πC#(πS#,C#(SC)∞πS#(σSex=女(S)))如圖 2-4 所示：
【相似文獻】

相關(guān)期刊論文 前10條

1 歐陽普仁,楊叔子;一種改進的Marple算法[J];南京理工大學(xué)學(xué)報(自然科學(xué)版);1988年01期

2 黃小蓓;隆永紅;;分布式數(shù)據(jù)庫管理系統(tǒng)中的並發(fā)控制——算法及其性能分析[J];計算技術(shù)與自動化;1988年02期

3 馮成進;;0—1規(guī)劃新算法的改進[J];曲阜師范大學(xué)學(xué)報(自然科學(xué)版);1988年02期

4 曾秀;魏振華;;猴群算法及其改進綜述[J];電腦知識與技術(shù);2017年32期

5 許燦英;;算法合謀反競爭問題初探[J];合肥工業(yè)大學(xué)學(xué)報(社會科學(xué)版);2019年02期

6 段艷明;肖輝輝;林芳;;新授粉方式的花授粉算法[J];計算機工程與應(yīng)用;2018年23期

7 肖海軍;王芬艷;盧常景;曹穎;;一種有效的多峰優(yōu)化鳥群算法[J];中南民族大學(xué)學(xué)報(自然科學(xué)版);2018年04期

8 覃遠年;梁仲華;;蟻群算法研究與應(yīng)用的新進展[J];計算機工程與科學(xué);2019年01期

9 肖輝輝;段艷明;林芳;;新搜索策略的花授粉算法[J];電子測量與儀器學(xué)報;2019年07期

10 梁昔明;高超;龍文;;基于速度越界處理與高斯擾動的改進蝙蝠算法[J];數(shù)學(xué)的實踐與認識;2019年19期

相關(guān)博士學(xué)位論文 前10條

1 周凌云;幾種典型群智能算法及其更新機制研究[D];武漢大學(xué);2018年

2 張代雨;多學(xué)科優(yōu)化算法及其在水下航行器中的應(yīng)用[D];西北工業(yè)大學(xué);2017年

3 鐘林峰;復(fù)雜網(wǎng)絡(luò)中關(guān)鍵節(jié)點的挖掘算法研究[D];電子科技大學(xué);2018年

4 邱實;多光譜衛(wèi)星遙感影像云及云陰影精準檢測算法研究[D];電子科技大學(xué);2018年

5 孫寧;人工免疫優(yōu)化算法及其應(yīng)用研究[D];哈爾濱工業(yè)大學(xué);2006年

6 陸楠;關(guān)聯(lián)規(guī)則的挖掘及其算法的研究[D];吉林大學(xué);2007年

7 胡銦;基于單目視覺的運動目標檢測與跟蹤算法研究[D];南京理工大學(xué);2008年

8 王玨;生物地理學(xué)優(yōu)化算法的研究及應(yīng)用[D];哈爾濱工程大學(xué);2013年

9 黃松;面向多應(yīng)用場景的粒子群優(yōu)化算法研究[D];江南大學(xué);2017年

10 安琦;信號偵收中的識別與分類理論與算法研究[D];電子科技大學(xué);2017年

相關(guān)碩士學(xué)位論文 前10條

1 鄭亞東;基于布谷鳥算法的北斗治安巡防系統(tǒng)的研究與實現(xiàn)[D];江蘇科技大學(xué);2019年

2 陳明義;基于自適應(yīng)LMS算法的滾動軸承故障診斷[D];石家莊鐵道大學(xué);2019年

3 翟展;基于CAD-DCF的運動目標魯棒跟蹤算法研究[D];華中科技大學(xué);2019年

4 王海羽;基于節(jié)點序約束的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法研究[D];燕山大學(xué);2019年

5 莊杰鵬;求解約束凸優(yōu)化問題的修正Cauchy-Barzilai-Borwein算法[D];福州大學(xué);2018年

6 蘇建楠;部分學(xué)習(xí)機的概念、算法及應(yīng)用[D];福州大學(xué);2018年

7 李莉;一種改進的ID3算法及其在銀行信用卡違約評估中的應(yīng)用[D];華中科技大學(xué);2019年

8 袁潔;三支決策聚類算法的改進及應(yīng)用研究[D];山東科技大學(xué);2018年

9 楊超杰;粒子群優(yōu)化算法的改進及應(yīng)用研究[D];云南大學(xué);2019年

10 羅久桓;基于背景感知濾波器的集成跟蹤算法研究[D];云南大學(xué);2019年

本文編號：2879436