资源描述：
《融合粒子群算法与蚁群算法对xml概率查询策略的改进》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、融合粒子群算法与蚁群算法对XML概率查询策略的改进//.paper.edu.cn-1-融合粒子群算法与蚁群算法对XML概率查询策略的改进1刘波1，杨路明1，雷刚跃2，谢东11中南大学信息学院，湖南长沙（410083）2湖南信息职业技术学院，湖南长沙（410200）摘要：粒子群算法具有快速随机的全局搜索能力,但无法利用反馈信息,而蚁群算法通过信息素的累积和更新收敛于最优路径上,具有分布式并行全局搜索能力，但初期信息素匮乏,求解速度慢；本文根据以上算法的特征，采用启发式方法，结合XML半结构化的特点，将粒子算法与蚁群算法融入于XML概率查询上，并进行相应的改
2、进，采用粒子群算法快速生成信息素分布,利用蚁群算法精确求解,达到优势互补，提高数据查询的范围和收敛的效率，仿真实验表明这种融合方法具有更好的查询效果。关键词：粒子群算法，蚁群算法，信息素，杂交算子，XML概率查询中图分类号：TP311.5文献识别码:A引言XML是用来描述数据结构的一种语言，具有开放的、可扩展的、可自描述的语言结构，已经成为网络中数据和文档传输的标准，它不仅使得结构化数据的定义更加容易，而且借助它与其它应用程序进行数据查询与交换更加方便。在电子商务高速发展的今天，这种需求会越来越多，因此对XML数据库有不少操作需要在复杂而庞大的数据空间中
3、寻找最优解,在解决此类任务时,若不能利用问题的固有知识来缩小搜索范围,则可能产生爆炸的组合，针对XML半结构化的特点,希望XML查询能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制查询过程从而得到最优解一直是令人注目的课题，特别是查询最小化和概率优化选择更成为一个研究新课题；本论文借鉴群智能中的粒子群与蚁群优化算法改进XML概率查询方法。1.问题描述设N={N1，N2，…，Nn}表示XML相关结点的集合，E={E1，E2，…，Em}表示XML相关连接点的集合,P={P1，P2，…，Pn}表示每个结点概率的集合，如图1所示，那么对于给定的一系
4、列要查询的结点如何经过根结点能快速定位到要查找的结点？如何组合才能使查询过程代价最小？对于多次查询的一组结点，如何设计其查询路径？对于不断变化的XML树结构，如何维护其边值概率？本文将对这些问题进行讨论。1本课题是湖南信息职业学院科技创新项目（编号108652006011，名称：基于XML数据库压缩算法与概率查询分析及实现），同时本课题得到湖南省教育厅科研基金（编号05c671，名称：遗传算法参数设计）的资助。//.paper.edu.cn-2-rootabcN1N2N3aabbccN4N5N6,N7N8,N9N10,N11N12,N13,N14根元素N
5、1结点及值E1E2E3E4E5E6E7E8E9E10E11E12E13E14E15E16E17E18P1P2P3P4P5P6P13P17P18P9P11P12图1XML树结构图1对应的xml文档如下：<?xmlversion=“1.0”encoding=“UTF-8”?><root><a>N1<b>N2<c>N3></c></b></a><a>N4<b>N5><c>N6,N7</c></b>
6、;</a><a>N8,N9<b>N10,N11<c>N12,N13,N14></c></b></a></root>本文针对XML查询优化主要贡献如下：1）针对XML查询，特别是利用树查询模式提出利用概率的方法，根据概率大小进行有条件的选择，同时也探讨动态查询问题；2）引入粒子群算法，不仅解决初期概率分布慢的问题，为后续引入蚁群算法打下基础，而且在没有集中控制且不提供全局模型的前提下,为寻找复杂的XML分布式问题求解方案提供了基础；3）引入蚁群算法，不仅解
7、决边值计算的困难，而且利用概率的方法，有条件的选择，以此为依据，可以去掉无意义的比较次数，加快查询收缩的力度；4）利用粒子群算法与蚁群算法的杂交算子，不仅解决局部极小解的问题，也避免路径选择的唯一性，保证全局的有效搜索。2.相关工作经过多年的发展，根据XML的特征提出了许多查询算法，如XPath查询最小化、X-RESTORE的XML视图查询等，特别是利用概率进行查询，有助于减小XML查询的搜索空间、循环比较次数，从而提高查询的效率。在文献[1]中，作者根据树的半结构化特点及DTD语法规则，利用条件概率对XML概率查询进行统计分析，并提出概率关系式A=（N
8、,∑,R,ρ,P）,其中N表数据状态集合，∑表标志集，R表操作规则，ρ表对应关系
