改进遗传蚁群算法在数据库查询优化的应用研究

发布时间：2020-11-11 16:23

　　 随着信息社会的发展,数据库技术在组织与管理数据方面已经发展为重要的技术手段。在数据库所有操作中,查询操作的使用频率最高,那么作为一个非常重要的操作,查询在处理大量信息的过程中担任了不可忽视的角色。从数据库的相关理论出发,本文对查询算法进行了研究和剖析。遗传算法具备普遍性、通用性和收敛速度快等特点,但该算法的缺点是局部最优解的出现概率较高;在寻求最优解方面,蚁群算法效果良好,但在搜索路径前期,由于只有少量信息素,算法缺乏信息素的引导,蚂蚁选择路径具有一定程度的盲目性与随机性,导致算法消耗大量时间才能得到最优解;遗传蚁群算法的混合,即保证了快速收敛,也提高了寻求解的性能。在此基础上,如何改进现有的遗传蚁群混合算法来进一步提高数据库多连接查询优化效率成为本文的研究重点。本文分别对以下情况进行了研究:通过研究种群多样性,对选择算子进行了分析,为避免在算法进化过程中,选择效率随着多样性的降低而降低,本文提出了自适应选择策略,提高选择算子效率,增加复杂后代个体的可能性;由于交叉位置的随机性,算法容易出现无效交叉,降低算法求解效率,本文分析了二点交叉的原理,根据相关性原则,对交叉操作进行了改进;本文研究了遗传算法和蚁群算法各自的求解趋势,为避免因为盲目的固定迭代次数而错过算法最佳衔接时刻,根据种群多样性在算法进化过程中的变化趋势,判断遗传算法收敛状态,对混合算法的衔接采用了自适应方法;在种群迭代过程中,容易出现最优个体没有有效进化、局部收敛的现象,本文对子代种群生成方式进行了改进,以降低最优个体被过滤的概率。综上所述,本文从选择策略、交叉操作、算法衔接点以及子代种群这几方面对遗传蚁群算法进行了改进,仿真实验证明,改进算法的求解效率提升了17%,并且缩短了执行时间和收敛代数。
【学位单位】：北京工业大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：TP18;TP311.13
【部分图文】：

查询原理库都具备一个基于成本的查询优化器，用于从所有执行方案中略，对于数据库来说，适当的查询执行策略会大幅度提升系统的多连接查询语句，数据库可以为其生成多种执行方案，那么所有执行方案，然后找出代价成本最低，花费时间最少的执行查询优化来说，它不仅是数据库关键实现技术点，也是关系型于一个查询来说，查询优化是优化其关系代数级，查找出执行表达式等价的方案，例如选择执行运算所采用的具体算法等[30L 语言的过程中，不需要考虑一系列复杂的情况，如数据集的存、存储结果等，只需要用标准 SQL 语言来表达自己的意图，关统的任务就是实现用户的意图。目前，有许多关系型数据库系据库各有优势，查询语句格式、处理方案可能不同，但是查询，查询步骤如图 2-1 所示：

图 2-2 数据库多连接查询模型Figure 2-2 Database Multi-connection Query Model数据库多连接查询优化的核心就是从 QEP 中找到最优的执行计划，在 QEP的所有执行计划中，该连接顺序执行代价最小、复杂度最低。由上文可知，多连接查询优化原理和经典 TSP 问题中查找最优路径的原理是相同的，其目的都是为了提高效率，降低时间成本。在对基本关系表优化前，首先我们通过简单的例子介绍一下如何把一个给定的查询语句转变成初步优化后的关系代数表达式[34]。例如，有三张基本关系表，分别为 C（课程号 C#，课程名称 Cname，代课老师 Teacher）、S（学号 S#，学生姓名 Sname，性别 Sex，年龄 Age）、SC（课程号 C#，学号 S#，分数 Grade）。查询语句为：班级所有女生选择的课程。优化前，该查询语句的关系代数表达式为：πCname,Teacher(σSex="女"(S∞SC∞C))优化前的语法树如图 2-3 所示：

图 2-3 优化前语法树Figure 2-3 Pre-optimization Grammar Tree是，尽量提前做选择操作，在每个操作后根性。所以优化后的关系代数表达式为：ame,Teacher(C∞πC#(πS#,C#(SC)∞πS#(σSex=女(S)))如图 2-4 所示：
【相似文献】

相关期刊论文 前10条

1 欧阳普仁,杨叔子;一种改进的Marple算法[J];南京理工大学学报(自然科学版);1988年01期

2 黄小蓓;隆永红;;分布式数据库管理系统中的並发控制——算法及其性能分析[J];计算技术与自动化;1988年02期

3 冯成进;;0—1规划新算法的改进[J];曲阜师范大学学报(自然科学版);1988年02期

4 曾秀;魏振华;;猴群算法及其改进综述[J];电脑知识与技术;2017年32期

5 许灿英;;算法合谋反竞争问题初探[J];合肥工业大学学报(社会科学版);2019年02期

6 段艳明;肖辉辉;林芳;;新授粉方式的花授粉算法[J];计算机工程与应用;2018年23期

7 肖海军;王芬艳;卢常景;曹颖;;一种有效的多峰优化鸟群算法[J];中南民族大学学报(自然科学版);2018年04期

8 覃远年;梁仲华;;蚁群算法研究与应用的新进展[J];计算机工程与科学;2019年01期

9 肖辉辉;段艳明;林芳;;新搜索策略的花授粉算法[J];电子测量与仪器学报;2019年07期

10 梁昔明;高超;龙文;;基于速度越界处理与高斯扰动的改进蝙蝠算法[J];数学的实践与认识;2019年19期

相关博士学位论文 前10条

1 周凌云;几种典型群智能算法及其更新机制研究[D];武汉大学;2018年

2 张代雨;多学科优化算法及其在水下航行器中的应用[D];西北工业大学;2017年

3 钟林峰;复杂网络中关键节点的挖掘算法研究[D];电子科技大学;2018年

4 邱实;多光谱卫星遥感影像云及云阴影精准检测算法研究[D];电子科技大学;2018年

5 孙宁;人工免疫优化算法及其应用研究[D];哈尔滨工业大学;2006年

6 陆楠;关联规则的挖掘及其算法的研究[D];吉林大学;2007年

7 胡铟;基于单目视觉的运动目标检测与跟踪算法研究[D];南京理工大学;2008年

8 王珏;生物地理学优化算法的研究及应用[D];哈尔滨工程大学;2013年

9 黄松;面向多应用场景的粒子群优化算法研究[D];江南大学;2017年

10 安琦;信号侦收中的识别与分类理论与算法研究[D];电子科技大学;2017年

相关硕士学位论文 前10条

1 郑亚东;基于布谷鸟算法的北斗治安巡防系统的研究与实现[D];江苏科技大学;2019年

2 陈明义;基于自适应LMS算法的滚动轴承故障诊断[D];石家庄铁道大学;2019年

3 翟展;基于CAD-DCF的运动目标鲁棒跟踪算法研究[D];华中科技大学;2019年

4 王海羽;基于节点序约束的贝叶斯网络结构学习算法研究[D];燕山大学;2019年

5 庄杰鹏;求解约束凸优化问题的修正Cauchy-Barzilai-Borwein算法[D];福州大学;2018年

6 苏建楠;部分学习机的概念、算法及应用[D];福州大学;2018年

7 李莉;一种改进的ID3算法及其在银行信用卡违约评估中的应用[D];华中科技大学;2019年

8 袁洁;三支决策聚类算法的改进及应用研究[D];山东科技大学;2018年

9 杨超杰;粒子群优化算法的改进及应用研究[D];云南大学;2019年

10 罗久桓;基于背景感知滤波器的集成跟踪算法研究[D];云南大学;2019年

本文编号：2879436