(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211109680.1 (22)申请日 2022.09.13 (71)申请人 南京开特信息科技有限公司 地址 211100 江苏省南京市江宁区秣周东 路12号4号楼902室 (72)发明人 何林浩　王晓春　尚翀　 (74)专利代理 机构 南京群迈知识产权代理有限 公司 32690 专利代理师 王敏 (51)Int.Cl. G06F 16/2453(2019.01) G06F 16/2455(2019.01) G06F 16/27(2019.01) G06N 3/00(2006.01) G06N 3/12(2006.01) (54)发明名称 一种基于蚁群遗传动态融合算法的数据库 查询优化方法 (57)摘要 本发明公开了一种基于蚁群遗传动态融合 算法的数据库查询优化方法， 属于数据库查询技 术领域， 综合运用多蚁群算法和遗传算法， 构建 动态多蚂蚁遗传混合算法， 可以解决现有蚁群遗 传融合搜索技术的局限性， 有效地提高了数据库 系统的查询速度， 降低数据库运行的整体成本。 本发明针对传统蚂蚁算法经常出现的局部最优 现象， 引入多蚂蚁算法和学习算子， 可 以获得全 局最优解； 针对蚂蚁遗传混合算法中常见的收敛 速度偏慢的问题， 引入动态迭代规则， 有效地提 高了算法的收敛速度。 权利要求书3页 说明书6页 附图1页 CN 115391385 A 2022.11.25 CN 115391385 A 1.一种基于蚁群遗传动态融合算法的数据库查询优化方法， 其特征在于， 包括如下步 骤： 步骤1： 对分布式数据库网络 拓扑结构进行设置； 步骤2： 针对分布式数据库多表关联查询问题的特点， 使用串结构式编码， 形成染色体； 步骤3： 初始化遗传算法， 设定 遗传算法的最大迭代次数和最小迭代次数； 步骤4： 开始进行遗传算法迭代， 对染色体进行变异以及交叉操作， 形成新的染色体， 将 染色体转换成查询路径， 计算 适应度值； 步骤5： 引入遗传算法迭代终止规则， 满足 终止条件则进入下一 步骤， 否则重复步骤3； 步骤6： 使用遗传算法的最优查询路径， 构建蚂蚁算法的初始信息素； 步骤7： 引入多个蚂蚁系统， 并在不同蚂蚁系统之间嵌入一个学习算子， 使得不同系统 之间可以相互学习， 更新信息素， 从而得到 搜索算法的全局最优解； 步骤8： 设置发出查询请求的网络节点； 步骤9： 按照多个蚂蚁系统中的转移概 率公式进行节点之间的转移； 步骤10： 判断蚂蚁算法搜索 是否符合终止条件， 如果没有， 返回步骤(11)； 否则， 输出结 果； 步骤11： 得出最优查询执 行计划； 步骤12： 模型测试。 2.根据权利要求1所述一种基于蚁群遗传动态融合算法的数据库查询优化方法， 其特 征在于： 步骤2中染色体分为三部分： 连接次序与站点选择编码段、 关系副本选择编码段和 半连接操作编码段。 3.根据权利要求1所述一种基于蚁群遗传动态融合算法的数据库查询优化方法， 其特 征在于： 步骤4中适应度函数的计算公式为： 其中， F为适应度函数， 值越大说明查询路径的成本越低， Ci为查询路径上节点i对应的 通讯费用， Sij为查询路径上的节点i与节点j之间对 应的通讯费用， n为查询路径上的节点总 数量， m为所有节点之间的总路径条 数。 4.根据权利要求2所述一种基于蚁群遗传动态融合算法的数据库查询优化方法， 其特 征在于： 步骤4中变异采用高斯变异方法， 交叉操作的交叉算子用均匀交叉方法， 按照概率 交换两个父辈个 体基因串。 5.根据权利要求1所述一种基于蚁群遗传动态融合算法的数据库查询优化方法， 其特 征在于： 遗传算法迭代终止规则包括适应度规则和进化率规则， 当满足任一规则终止条件， 终 止遗传算法； 适应度规则 为： 在设定的迭代次数范围内， 如果连续遗传n代， 都满足ΔFn<ΔFn‑1， 则结 束遗传操作， 生成信息素， 其中， 权　利　要　求　书 1/3 页 2 CN 115391385 A 2ΔFn表示第n代遗传种群的适应度差值， ΔFn‑1表示第n‑1代遗传种群的适应度差值， 表示第n代遗传种群的最大适应度值， 表示第n代遗传种群的平均适应度值； 进化率规则为： 在设定的迭代次数范围内， 连续迭代n代后， 子代 的进化率低于给定的 最小进化率 λ， 则终止 遗传算法， 并计算信息素。 6.根据权利要求1所述一种基于蚁群遗传动态融合算法的数据库查询优化方法， 其特 征在于： 步骤6中蚂蚁算法的初始信息素为： τij(0)＝γ1τij+Δ τij(0) 其中， Δ τij(0)＝I/L τij(0)表示查询 连接边(i,j)上的初始信息素值， γ2为信息素更新因子， I为信息素总 量， L为路径长度。 7.根据权利要求6所述一种基于蚁群遗传动态融合算法的数据库查询优化方法， 其特 征在于： 信息素的更新机制定义 为: τij(t+1)＝γ2τij(t)+Δ τij(t， t+1) 其中， τij(t)为路径连接边(i,j)上的信息素值， 信息素的滞后算子是γ2， Δτij(t， t+1) 为第t次循环时， 所有蚂蚁释放的信息素， m为蚂蚁总个数。 8.根据权利要求7所述一种基于蚁群遗传动态融合算法的数据库查询优化方法， 其特 征在于： 引入最大最小蚂蚁系统， 将所有路径的信息素限制在最大值τmax和最小值τmin之间， 高于或低于这 一区域都会被自动调整为 τmax或τmin， 以此来避免蚂蚁算法搜索停滞的现象。 9.根据权利要求8所述一种基于蚁群遗传动态融合算法的数据库查询优化方法， 其特 征在于： 不同蚁群之间的学习规则设定为： 其中， τijm为子蚁群m在连接边(i,j)上的信息素值， τijk为子蚁群k在连接边(i,j)上的 信息素值， δ 为蚁群间的学习算子， α 为子蚁群数量。 10.根据权利要求9所述一种基于蚁群遗传动态融合算法的数据库查询优化方法， 其特 征在于： 步骤9的转移概 率公式为： 其中， τij(t)为第t次搜索时在连接边(i,j)上的信息素值， α 为其在概率计算中的权重，权　利　要　求　书 2/3 页 3 CN 115391385 A 3