搜索引擎中遗传模拟退火算法的应用略论

2022-03-24李一鑫

技术与市场 2022年3期

李一鑫

(咸阳职业技术学院，陕西咸阳 712000)

0 引言

搜索引擎技术已经成为计算机网络技术发展的关键内容，对人们使用网络的体验感产生着重要的影响。由于不同的搜索引擎具有不同的算法与搜索策略，在英文搜索中不存在分词与词义模糊的概念、语义解析等问题，但是中文搜索引擎的发展一直存在着一定的问题，往往会存在语义解析错误与无法识别新词等相关的问题，如何有效地解决这些问题，就需要采用新的算法来解决这些问题，才能提高搜索引擎的效率。遗传算法与模拟退火算法在搜索引擎中的应用，可以提高搜索引擎的精度，满足人们快速搜索的要求。

1 搜索引擎的发展概述

搜索引擎(Search Engine)主要运用一定的主题词策略、采用特定的计算机程序对网络中的信息进行搜集，在经过组织与处理后，为用户提供完善的信息检索服务，并将检索的结果呈现给用户。搜索引擎的工作流程如下：用户输入关键词，搜索引擎工具自动匹配词语程序，对用户的词语进行联想，并在数据库中进行搜寻，将搜寻到与该词语匹配的信息与网站信息，然后通过匹配算法计算词语的排名，并按照一定顺序显示出来。因此，越是精确搜索到的信息，就显示在最前端，说明分词技术就十分重要。由于中文的文法、词性比较特殊，在字与词之间有着深层次的关系，一个好的搜索引擎，其关键技术在于分词算法的优劣。在分词技术的应用中，基于词典的分词策略、统计的分词策略、规则的分词策略是当前比较常用的技术，一般情况下是将3种技术结合在一起使用，以提高搜索的效率。

2 遗传模拟退火算法

2.1 遗传算法

遗传算法也称为基因算法或者进化算法(genetic algorithms，简称GA)，对一些非线性的问题处理，采用遗传算法非常有效。在搜索引擎中，为了提高遗传算法的优越性，具有很强的全局搜索控制能力，就是将其他算法引入其中，可以将内点法、退火算法等与遗传算法结合，从而提高解决非线性问题的效率。除了应用算法混合策略来提高遗传算法的性能外，还可以采用多种方法对遗传算法进行改进，拓展遗传算法的功能，以保证群体在空间上的多样性。遗传算法具有过程智能化、算法成熟、高效性、复杂问题简单抽象化等特点，它被用在搜索引擎中的分词部分，可以智能地根据词性的变化，随机搜索符合要求的词语，即使没有庞大的数据库、词库也实施查询一些新词或者一些歧义性的词语，遗传算法可以对搜索问题的进行抽象化处理，并能利用计算机语言来描述当前的实际问题。

2.2 模拟退火算法

模拟退火算法(simulate annealing，SA)的原理与遗传算法的原理类似，在数据搜索上具有强大的功能，主要是采用物理学中的固体退火原理，先设置一个最高温度，随着温度参数不断的变化下降，就可以在该空间内搜索最优解，并不断搜索温度变化的临界状态，搜索退火的最优解，结合概率在解空间的跳跃与变化分布情况，达到对目标函数的求解，将其与遗传算法结合在一起，可以完美解决搜索分词阶段的准确性。它的构成要素包括搜索空间Ω，能量变化函数E(x)、函数的空间状态转移规则P以及空间能量变化冷却进度表T(x)等几个部分，采用模拟退火算法可以针对降温不明确的区域进行快速处理，具有很强的局部数据能力。将其应用到搜索引擎中信息检索时，可以按照最佳路径实现最优解。如果搜索过程在局部点A达到最优，获取搜索到的词语或者分析，就要求搜索过程脱离A点而达到C点，就必须使得系统在C点的能量要高于A点的能量，满足数据查询最优解的临界值；假设在状态A点时，系统在接受到某种能量使其状态变化为C，这时整个系统的能量也从E(A)变化为E(C)，这样系统由状态A变化为状态C时的可接受概率，可以利用Meteopolis规则进行计算：

其中，Δ(x)是系统从能量A点(E(A))跃迁到C点(E(C))能量变化，T为系统约化单位的退火温度，该计算法说明，在系统进入到新的状态时，能量的跃迁分布主要是以高斯形式分布，当能量发生变化，新状态促使能量的函数值增加，C点的位置明显地要优越于A的位置，系统才会在某一概率的情况下接受该状态(C状态)，从而能够在该空间内可以查询到最优解，避免局部搜索陷入到最优解的循环中。模拟退火算法也存在着明显的不足：要求搜索时间足够长，新状态可以保证以1.0的概率收敛于空间全局的最优点，导致整个搜索过程时间过长，由于优化效果与计算时间存在一定的矛盾，如果系统的规模过大，就难以保证计算结果的最优化。

3 遗传算法与模拟退火算法在搜索引擎中的应用

在搜索引擎技术中，将遗传算法与模拟退火算法结合在一起形成一种新的优化算法，而遗传算法的局部搜索能力比较差，不能有效地解决局部搜索的问题，采用模拟退火算法可以增强局部搜索能力，将遗传算法与退火算法结合在一起，避免搜索过程陷入到局部最优解的循环中，提高了搜索引擎的查询效率。

3.1 模型扰动

通过对遗传算法与模拟退火算法的优势、特点进行分析，将二者结合在一起，应用到搜索引擎中，将局部与全局搜索结合在一起，提高搜索引擎的效率，可以采用Canchy-Lorentz半区域式的跃迁分布来构建搜索引擎模型，Canchy-Lorentz分布的概率函数比较如图1所示。

图1 Canchy-Lorentz分布概率函数分布比较图

通过二者的对比，它们的概率密度函数曲线(T=1)分布也十分明显：Cauchy曲线分布在原点处的峰值比Gaussian曲线的分布小，说明曲线变化不大，比较适合全局搜索，而Cauchy曲线两端长扁平形状趋于0的速度比Gaussian分布慢，在大范围内的搜索比较好。而Gaussian曲线分布状态的发生器，主要集中在局部信息变换中，能有效地提高局部搜索能力，而产生大扰动的概率几乎为0，在大范围内的搜索中，难以脱离平坦区和多峰区，也就影响着局部搜索的效率；基于Cauchy分布的状态发生器优势比较明显，在全局范围内进行数据搜索，相对Gaussian分布中的局部信息搜索能力，对较大范围内的抗干扰能力比较强，将Canchy-Lorentz二者结合在一起，可以优化局部与全局优化的效果。根据二者之间的特点，设计如下的Cauchy分布计算的新模型：

(1)

yi=Tsgn(u-0.5)[1+1/T]|2u-1|]

(2)

(3)

采用这种模型的优势是，在较高频率内可以进行大范围的搜索，在低频率时，Gaussian模型的算法能在附近搜索，提高了搜索效率，而Cauchy分布有一平坦的“尾巴”，在搜索的过程中，可以跳出局部的搜索，采用这种算法改进了退火算法的收敛速度，在同样搜索范围内，增强搜索引擎的功能。

3.2 降温方式

在构建遗传模拟快速退火算法时，需要合理地处理退火降温的计算方法，才能满足数据处理的要求，一般情况下，退火降温计算如下：

(4)

其中，K0为降火的初始温度，K为退火过程中的迭代次数，C为系统给定的常数，整数N为系统迭代过程中的待反演参数的个数。通过次数的迭代计算，上式可以改写为：

T(K)=T0αk1/N)

(5)

在日常计算中，规定0.7≤α≤1，在具体算法处理中，采用1/N的取值为可以是0.5或者1，最终按Cauchy函数分布处理数据，构建新的扰动模型，并按Metropolis准则接收数据处理过程中的变化方式，完成整改数据的处理过程。

3.3 搜索引擎中的遗传退火算法的应用

将遗传算法与退火算法结合在一起，构成遗传模拟退火算法，同时还要结合搜索引擎的功能需求，合理的对分词技术、模糊词语进行处理，才能提高搜索引擎的效率。

定义：设L为全体搜索空间、网站的链接集合，在该集合中包含着若干个搜索的词语或者词条，VL(value)为搜索处理的链接价值空间，能保证搜索引擎的重要性，l为词语的链接。为了使得数据之间产生对应关系，令：全体链接的集合到链接价值空间的映射v，存在l∈L→v(1)∈VL，将其称为链接的价值函数。在具体的搜索过程中，算法流程如下。

1)初始化控制参数设置。根据降火温度的要求，首先需要初始化链接优先权队列，为数据处理提供基础条件，退火初始温度T0，降火冷却参数0≤C≤1，在从初始温度T0达到平衡状态Ti时，系统经过S次经循环，采用计数标识变量的方法为：Loop←0。

2)在退火降温处理的过程中，如果链接优先权队列为空，对系统的循环次数进行处理，转入步骤9)执行；否则，队头链接出队，并指向下一个搜索过程，完成第一次搜索过程。

3)如果页面是主题相关页面，并与用户输入的关键词相匹配，则保存以备索引，否则丢弃本次搜索，进入下一次的搜索。

4)处理页面。将搜索数据与用户进行匹配，并提取页面中未访问过的链接URL，送入链接优先权队列，并提取链接文本信息和Web中的词语，送入链接价值计算器，从而形成一个完整的搜索引擎过程。

5)结合步骤4)，链接价值计算器对搜索的词汇进行统计，计算每个链接的价值，循环统计搜索过程中的次数。