搜索引擎系统中的蚁群算法分析

朱 婧

(福建船政交通职业学院 信息工程系，福州 350001)



搜索引擎系统中的蚁群算法分析

朱 婧

(福建船政交通职业学院 信息工程系，福州 350001)

分析当前搜索引擎系统设计中应用蚁群算法的相关问题，以确保运用蚁群算法优化设计搜索引擎系统.结果证实，在搜索引擎系统中应用蚁群算法，仿真证明该算法在设计系统应用中具有有效性与优越性.结论表明，在搜索引擎系统中，应用蚁群算法，不仅能够优化搜索引擎系统中的搜索代价,还可以发挥蚁群算法的开放性与自我动态调整性，发挥积极应用价值.

算法；搜索引擎；蚁群算法

在当前信息网络化时代，人们在浏览网络信息过程中，迫切需求一种优化的搜索引擎系统，以满足人们高效获取网络信息、大量获取网络信息的需求[1].优化设计搜索引擎系统，基于蚁群算法优化设计搜索引擎算法，将会有助于提升搜索引擎系统性能，产生积极影响.

1 蚁群算法概述

蚁群算法是由国外Marco Dorigo学者提出的，他在观察分析蚂蚁的觅食行为后受到启发，从而设计制定的一种基于群智能的优化算法[2].蚁群算法是继模拟退火算法、遗传算法以及禁忌搜索等算法后的又一种优化算法，可以解决组合优化问题中的随机搜索问题，是具备启发式的算法[3-6].不仅能应用蚁群算法实现智能搜索，应用蚁群算法也可对引擎系统进行全局优化，提升算法在计算过程中的鲁棒性，发挥分布式计算优点[7].用蚁群算法能够求解TSP问题，处理搜索引擎分配的问题，也可以用来解决job-shop调度的问题.虽然我国在当前关于蚁群算法方面的研究时间不长，但是基于现在我国相关学者的研究结果中，显示出在求解复杂问题时应用蚁群算法发挥一定优势，蚁群算法在搜索引擎系统设计中是一种有应用价值的算法[8].

2 优化设计搜索引擎系统的需求分析

在当前信息化时代，网上的资源信息往往具有数据量庞大、信息组织结构多样、信息分布不均匀以及网络信息动态更新速度快的特点[9]，导致搜索引擎获得的信息呈现出的准确性偏低、信息错误等弊端，降低Internet上资源利用率，降低搜索引擎系统的信息检索性能[10-11].在优化设计搜索引擎系统之中，必须要确保该系统具备搜集信息的功能，也可以实时处理引擎搜索到的信息，并可同时为系统用户提供查询服务.基于蚁群算法，优化设计搜索引擎系统,提出蚁群搜索引擎算法，可以优化引擎系统在实际应用中的搜索代价,可以分散局部搜索引擎的负载,提升搜索引擎系统应用性能.

3 设计实现基于蚁群算法的搜索引擎系统

3.1 搜索引擎系统结构

图1 搜索引擎系统

在本次设计的搜索引擎系统中，系统工作结构主要包括搜集信息、整理信息以及接受检索三大部分.如图1所示.

信息搜集：主要是网络爬虫爬取网页和网站，其过程是自动完成.理论上网页的大部分超链接，爬虫都能将其遍历.

信息整理：可以将爬取搜索引擎网络中的信息，根据一定规则进行筛选，并制定出索引.

检索：该结构部分能够根据用户输入到系统中的检索信息，查找搜索引擎系统中的索引数据库，并能够按一定的排序算法，将检索结果返回给用户.

3.2 蚁群算法

广义蚁群算法如下：

其中：ηij(t)表示启发函数，ηij(t)=1/dij，就是代表一种期望，是蚂蚁能够从节点i转移成j节点期望的程度；allowk(k=1,2,3,…,m)是蚂蚁k对于待访问节点的集合，在开始之时，allowk中一共有(n-1)个元素，往往包括除蚂蚁出发k节点以外的所有节点，并且随着时间的不断推进，allowk中的元素也会不断减少到空，所有节点也均可访问完毕；α就是信息素中的重要程度因子，若是α的值越大，则在转移中表示信息素发挥了越大的作用；β则是表示启发函数的重要程度因子.

信息素更新，包括蚂蚁释放信息素，有3种模型：

模型一：“ant cycle system”

在其中Q是常数，可以表示在蚂蚁循环一次后释放信息素的总量；Lk是第k只蚂蚁经过的路径长度.

模型二：“ant quanlity system”

模型三：“ant density system”

应用模型一来计算释放出的信息浓度，也就是蚂蚁经过的最短路径.

信息素挥发(evaporation)过程是信息素痕迹的浓度自动逐渐减弱的过程.挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展.

设ρ(0<ρ<1)可以表示信息素挥发的程度，那么，可以在当所有的蚂蚁完成一次循环之后，需要实时更新各个节点搜索引擎间连接路径中信息的浓度：

3.3 基于蚁群算法设计实现搜索引擎算法

搜索引擎系统中，其不同网络服务器之间彼此相互连接,构成一个全连接图网络；并且对特定用户可以提供单个服务器的引擎检索服务,构成服务器与用户间的C/S架构.在搜索引擎中，对于网络搜索引擎系统设计中，搜索网络能够应用无向图G(V，E)来表示，V就表示网络内所有的节点集合，E则是代表网络链路的集合.故此，可以将寻找搜索引擎系统中最佳资源路径的问题，转换成在无向图G内寻找满足约束条件最佳路径的算法.整个搜索引擎系统中，由数目可变的多个搜索服务器组成,系统中的多个服务器之间又相互是彼此的客户端,构成P2P (Peer-to-Peer)的对等网络.

图2 搜索引擎系统应用算法的步骤

搜索引擎系统应用算法的步骤如图2所示.首先，初始化参数，需要对与搜索引擎算法相关的参数初始化.其次，可以将各个蚂蚁随机放置在不同的出发点，对每个蚂蚁k(k=1,2,…，m)，计算出转换概率，确定其下一个搜索引擎待访问的节点.然后，可以新信息素，计算出在各蚂蚁经过后的路径长度Lk，并记录在当前蚁群算法迭代中的最短路径.并且可以在最后，如果iter

4 仿真应用分析

对于本次设计的搜索引擎系统，仿真分析其应用蚁群算法后的系统应用效果.分析其搜索引擎性能.

查准率：就是相关信息在所有查出信息中所占的比例，其计算公式如下：

其中的Relevant 表示相关信息集， Retrieved 表示返回的结果集.

在本次搜索引擎系统的应用仿真中，分别应用 Google搜索引擎、百度搜索引擎以及本次设计的搜索引擎系统，随机查询关于计算机领域方面的 20 个关键词.并且选取每次返回的前 50 个搜索结果进行统计分析，对得出的 1 000 个结果统计其查准率.得出的查准率结果如表1所示.

表1 比较查准率结果

在本次设计的搜索引擎系统中，当查询“搜索”这个关键字时，搜索引擎就会出现与计算机领域信息对应的相关网页；并且该搜索引擎系统相对于百度以及Google引擎，不仅会提升查准率，提升搜索引擎系统的应用性能.在搜索引擎系统中应用蚁群算法，仿真证明该算法在设计系统应用中具有有效性与优越性，发挥应用优势.

5 结论

综上所述，在搜索引擎系统中应用蚁群算法，优化设计搜索引擎系统，实现基于蚁群算法的搜索引擎算法.该算法发挥积极应用优势，提升搜索引擎系统应用性能，值得在实践中推广应用.

[1] 王海鹰,魏颖.基于蚁群算法的多目标网页综合评价策略[J].计算机工程与应用,2011,47(4):223-225.

[2] 刘晋佩.融合蚁群算法的用户浏览路径推荐系统研究[D].厦门：厦门大学,2014.

[3] 崔晓艳,霍中刚,辛中华，等.应用理性优化蚁群算法提高激光三维复制的重现度[J].光谱学与光谱分析,2013,33(7):1873-1876.

[4] 何小锋,马良.带时间窗车辆路径问题的量子蚁群算法[J].系统工程理论与实践,2013,33(5):1255-1261.

[5] 李积英,党建武.基于量子空间的蚁群算法及应用[J].系统工程与电子技术,2013,35(10):2229-2232.

[6] 曹庆奎,赵斐.基于遗传蚁群算法的港口集卡路径优化[J].系统工程理论与实践,2013,33(7):1820-1828.

[7] 陈英武,姚锋,李菊芳，等.求解多星任务规划问题的演化学习型蚁群算法[J].系统工程理论与实践,2013,33(3):791-801.

[8] 邢立宁,陈英武,姚锋，等.求解双层CARP优化问题的知识型蚁群算法[J].系统工程理论与实践,2012,32(11):2540-2549.

[9] 鲁强,周新.基于在线检测动态一维下料问题的GPU并行蚁群算法[J].仪器仪表学报,2015,36(8):1774-1782.

[10]郭浩,邱涤珊,伍国华，等.基于改进蚁群算法的敏捷成像卫星任务调度方法[J].系统工程理论与实践,2012,32(11):2533-2539.

[11]李冰岩,黄地龙,郝园，等.基于Web的搜索引擎算法的研究[J].电脑与电信,2010(5):29-31.

[责任编辑 王新奇]

Analysis of Ant Colony Algorithm in Search Engine System

ZHU Jing

(Department of Information Engineering, Fujian Chuanzheng Communications College, Fuzhou 350001, China)

In this paper, the related problems of application of ant colony algorithm in the current search engine system is analyzed to ensure that the use of ant colony algorithm to optimize the design of search engine system. The results show that the ant colony algorithm is used in the search engine system, and the simulation results show that the algorithm is effective and superior to the design system. The results show that ant colony algorithm can be applied in the search engine system, it can not only optimize the search cost in the search engine system, but also play the openness and self dynamic adjustment of the ant colony algorithm, and play a positive application value.

algorithm; search engine; ant colony algorithm

1008-5564(2016)04-0044-04

2016-02-18

朱 婧(1981—)，女，江西南昌人，福建船政交通职业学院信息工程系讲师，主要从事计算机网络技术研究.

TP391.3

A