融入粒子群与蚁群算法对xml群体概率搜索智能分析

《融入粒子群与蚁群算法对xml群体概率搜索智能分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、http://www.paper.edu.cn融入粒子群与蚁群算法对XML群体概率1搜索智能分析1121刘波，杨路明，雷刚跃，谢东1中南大学信息学院，长沙（410083）2湖南信息职业技术学院，长沙（410200）E-mail：ltbo99@yahoo.com.cn摘要：针对XML文档进行群体搜索的特点与不足，提出利用群智能算法的概率变换规则对其进行改进，采用粒子群算法快速生成信息素分布,利用蚁群算法精确求解,对搜索目标依次进行分解、动态群体选择、自适应群体变化、杂交、多次编码、迭代选择等,不仅可以提高数据搜索的范围、精度和收敛的效率，而且可以避

2、免早熟、降低算法的复杂度，通过仿真与其它XML搜索算法比较，证明这种方法的有效性与可靠性。关键词：粒子群算法，蚁群算法，杂交算子，XML概率查询，群体中图分类号：TP311.5文献识别码：AXML已经成为事实上的数据表示和数据交换的标准,因为它的自描述和特定可扩展性等核心特性提供了不同应用程序之间消息传输所需的灵活性,特别是随着近年来WebService的蓬勃发展，XML越来越多地活跃在数据交换和存储领域，用XML表示的半结构化数据越来越普遍，相应的文档越来越多,也越来越大,面对XML数据量的指数级增长,必然要求更有效的数据管理能力和更快、更精确

3、的查询,因此如何从XML数据源中准确有效地查询所需信息也就变得越来越重要。许多传统的搜索方法大多是单点搜索，这种点对点的搜索方法，对于多峰分布的搜索空间常常会陷入局部的单个单峰的极值点，相反群智能算法采用的方法是同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估，这一特点使群智能算法具有较好的全局搜索性能，也使得群智能算法本身易于并行化。根据群智能算法的这些特征,利用它们构建XML群体搜索模型,即在搜索XML文档时间最短的情况下，使得搜索目标时各种资源尽可能均衡分布,以减少搜索成本与比较成本,同时通过结点添加概率属性方法,提出一种针

4、对XML群体进行优选优生进化算法,有助于XML搜索的快捷与稳定。1.问题描述设N={N，N，…，N}表示XML相关结点的集合，E={E，E，…，E}表示12n12mXML相关连接点的集合,P={P，P，…，P}表示每个结点概率的集合，如图1所示，那12n么对于给定的一系列查询要求或多次查询要求，采用什么有效方法经过根结点能快速定位到要查找的结点？如何组合才能使查询过程代价最小？对于多次查询的一组结点，如何设计其查询路径？对于不断变化的XML树结构，如何维护其边值概率？本文将对这些问题进行讨论。1本课题得到湖南信息职业学院科技创新项目（编号：108

5、652006011）和湖南省教育厅科研基金05c671（项目编号：05c671）的资助。-1-http://www.paper.edu.cnroot根E1E13E7aP1aP13a元素E2E8E14E15P2E3P3E9P9N1结点及值N1bN4bbN8,N9E4E10E17P4E5P5E11P11E16P17N2cN5ccN10,N11E6P6E12P12E18P18N3N6,N7N12,N13,N14图1XML树结构图1对应的xml文档如下：N1N

6、2N3>N4N5>N6,N7N8,N9N10,N11N12,N13,N14>本文针对XML查询优化主要贡献如下：1）针对XML查询，特别是利用树或图查询模式提出利用属性添加概率的方法，根据概率大小进行条件选择，这种方法不仅可用于XML文档的静态查询，也可以很好解决XML动态结点查询问题；2）针对XML群体优化查询，构建多种资源受限情况下可分解的启发式多目标查询模型，通过依次融入粒子群算法和蚁群算法，在没有集中控制且不提供

7、全局模型的前提下,不仅解决XML概率属性初期分布慢的问题，而且为寻找复杂的XML分布式问题求解方案提供了基础，同时利用相应的编码规则及变化的概率值进行有条件的选择，可以去掉无意义的比较次数，加快查询收缩的力度；3）利用粒子群算法与蚁群算法的杂交算子，不仅解决局部极小解的问题，也避免路径选择的唯一性，保证全局的有效搜索；4）在已有XML概率搜索研究基础上，利用群智能算法从另一个角度说明了XML搜索概率问题，更详细说明了怎样计算XML概率的方法。2.相关工作XML技术经过多年的发展，越来越成熟，使用也越来越广，相应地吸引了更多科研公司与研发人员投入到

8、这项有广泛前途的工作中，也取得了许多卓有成效的成果，针对XML[1][2][3]查询就有XPath查询、XQuery查询、X-RESTO