搜索引擎中遺傳模擬退火算法的應(yīng)用略論

李一鑫

(咸陽(yáng)職業(yè)技術(shù)學(xué)院，陜西 咸陽(yáng) 712000)

0 引言

搜索引擎技術(shù)已經(jīng)成為計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)發(fā)展的關(guān)鍵內(nèi)容，對(duì)人們使用網(wǎng)絡(luò)的體驗(yàn)感產(chǎn)生著重要的影響。由于不同的搜索引擎具有不同的算法與搜索策略，在英文搜索中不存在分詞與詞義模糊的概念、語(yǔ)義解析等問題，但是中文搜索引擎的發(fā)展一直存在著一定的問題，往往會(huì)存在語(yǔ)義解析錯(cuò)誤與無法識(shí)別新詞等相關(guān)的問題，如何有效地解決這些問題，就需要采用新的算法來解決這些問題，才能提高搜索引擎的效率。遺傳算法與模擬退火算法在搜索引擎中的應(yīng)用，可以提高搜索引擎的精度，滿足人們快速搜索的要求。

1 搜索引擎的發(fā)展概述

搜索引擎(Search Engine)主要運(yùn)用一定的主題詞策略、采用特定的計(jì)算機(jī)程序?qū)W(wǎng)絡(luò)中的信息進(jìn)行搜集，在經(jīng)過組織與處理后，為用戶提供完善的信息檢索服務(wù)，并將檢索的結(jié)果呈現(xiàn)給用戶。搜索引擎的工作流程如下：用戶輸入關(guān)鍵詞，搜索引擎工具自動(dòng)匹配詞語(yǔ)程序，對(duì)用戶的詞語(yǔ)進(jìn)行聯(lián)想，并在數(shù)據(jù)庫(kù)中進(jìn)行搜尋，將搜尋到與該詞語(yǔ)匹配的信息與網(wǎng)站信息，然后通過匹配算法計(jì)算詞語(yǔ)的排名，并按照一定順序顯示出來。因此，越是精確搜索到的信息，就顯示在最前端，說明分詞技術(shù)就十分重要。由于中文的文法、詞性比較特殊，在字與詞之間有著深層次的關(guān)系，一個(gè)好的搜索引擎，其關(guān)鍵技術(shù)在于分詞算法的優(yōu)劣。在分詞技術(shù)的應(yīng)用中，基于詞典的分詞策略、統(tǒng)計(jì)的分詞策略、規(guī)則的分詞策略是當(dāng)前比較常用的技術(shù)，一般情況下是將3種技術(shù)結(jié)合在一起使用，以提高搜索的效率。

2 遺傳模擬退火算法

2.1 遺傳算法

遺傳算法也稱為基因算法或者進(jìn)化算法(genetic algorithms，簡(jiǎn)稱GA)，對(duì)一些非線性的問題處理，采用遺傳算法非常有效。在搜索引擎中，為了提高遺傳算法的優(yōu)越性，具有很強(qiáng)的全局搜索控制能力，就是將其他算法引入其中，可以將內(nèi)點(diǎn)法、退火算法等與遺傳算法結(jié)合，從而提高解決非線性問題的效率。除了應(yīng)用算法混合策略來提高遺傳算法的性能外，還可以采用多種方法對(duì)遺傳算法進(jìn)行改進(jìn)，拓展遺傳算法的功能，以保證群體在空間上的多樣性。遺傳算法具有過程智能化、算法成熟、高效性、復(fù)雜問題簡(jiǎn)單抽象化等特點(diǎn)，它被用在搜索引擎中的分詞部分，可以智能地根據(jù)詞性的變化，隨機(jī)搜索符合要求的詞語(yǔ)，即使沒有龐大的數(shù)據(jù)庫(kù)、詞庫(kù)也實(shí)施查詢一些新詞或者一些歧義性的詞語(yǔ)，遺傳算法可以對(duì)搜索問題的進(jìn)行抽象化處理，并能利用計(jì)算機(jī)語(yǔ)言來描述當(dāng)前的實(shí)際問題。

2.2 模擬退火算法

模擬退火算法(simulate annealing，SA)的原理與遺傳算法的原理類似，在數(shù)據(jù)搜索上具有強(qiáng)大的功能，主要是采用物理學(xué)中的固體退火原理，先設(shè)置一個(gè)最高溫度，隨著溫度參數(shù)不斷的變化下降，就可以在該空間內(nèi)搜索最優(yōu)解，并不斷搜索溫度變化的臨界狀態(tài)，搜索退火的最優(yōu)解，結(jié)合概率在解空間的跳躍與變化分布情況，達(dá)到對(duì)目標(biāo)函數(shù)的求解，將其與遺傳算法結(jié)合在一起，可以完美解決搜索分詞階段的準(zhǔn)確性。它的構(gòu)成要素包括搜索空間Ω，能量變化函數(shù)E(x)、函數(shù)的空間狀態(tài)轉(zhuǎn)移規(guī)則P以及空間能量變化冷卻進(jìn)度表T(x)等幾個(gè)部分，采用模擬退火算法可以針對(duì)降溫不明確的區(qū)域進(jìn)行快速處理，具有很強(qiáng)的局部數(shù)據(jù)能力。將其應(yīng)用到搜索引擎中信息檢索時(shí)，可以按照最佳路徑實(shí)現(xiàn)最優(yōu)解。如果搜索過程在局部點(diǎn)A達(dá)到最優(yōu)，獲取搜索到的詞語(yǔ)或者分析，就要求搜索過程脫離A點(diǎn)而達(dá)到C點(diǎn)，就必須使得系統(tǒng)在C點(diǎn)的能量要高于A點(diǎn)的能量，滿足數(shù)據(jù)查詢最優(yōu)解的臨界值；假設(shè)在狀態(tài)A點(diǎn)時(shí)，系統(tǒng)在接受到某種能量使其狀態(tài)變化為C，這時(shí)整個(gè)系統(tǒng)的能量也從E(A)變化為E(C)，這樣系統(tǒng)由狀態(tài)A變化為狀態(tài)C時(shí)的可接受概率，可以利用Meteopolis規(guī)則進(jìn)行計(jì)算：

其中，Δ(x)是系統(tǒng)從能量A點(diǎn)(E(A))躍遷到C點(diǎn)(E(C))能量變化，T為系統(tǒng)約化單位的退火溫度，該計(jì)算法說明，在系統(tǒng)進(jìn)入到新的狀態(tài)時(shí)，能量的躍遷分布主要是以高斯形式分布，當(dāng)能量發(fā)生變化，新狀態(tài)促使能量的函數(shù)值增加，C點(diǎn)的位置明顯地要優(yōu)越于A的位置，系統(tǒng)才會(huì)在某一概率的情況下接受該狀態(tài)(C狀態(tài))，從而能夠在該空間內(nèi)可以查詢到最優(yōu)解，避免局部搜索陷入到最優(yōu)解的循環(huán)中。模擬退火算法也存在著明顯的不足：要求搜索時(shí)間足夠長(zhǎng)，新狀態(tài)可以保證以1.0的概率收斂于空間全局的最優(yōu)點(diǎn)，導(dǎo)致整個(gè)搜索過程時(shí)間過長(zhǎng)，由于優(yōu)化效果與計(jì)算時(shí)間存在一定的矛盾，如果系統(tǒng)的規(guī)模過大，就難以保證計(jì)算結(jié)果的最優(yōu)化。

3 遺傳算法與模擬退火算法在搜索引擎中的應(yīng)用

在搜索引擎技術(shù)中，將遺傳算法與模擬退火算法結(jié)合在一起形成一種新的優(yōu)化算法，而遺傳算法的局部搜索能力比較差，不能有效地解決局部搜索的問題，采用模擬退火算法可以增強(qiáng)局部搜索能力，將遺傳算法與退火算法結(jié)合在一起，避免搜索過程陷入到局部最優(yōu)解的循環(huán)中，提高了搜索引擎的查詢效率。

3.1 模型擾動(dòng)

通過對(duì)遺傳算法與模擬退火算法的優(yōu)勢(shì)、特點(diǎn)進(jìn)行分析，將二者結(jié)合在一起，應(yīng)用到搜索引擎中，將局部與全局搜索結(jié)合在一起，提高搜索引擎的效率，可以采用Canchy-Lorentz半?yún)^(qū)域式的躍遷分布來構(gòu)建搜索引擎模型，Canchy-Lorentz分布的概率函數(shù)比較如圖1所示。

圖1 Canchy-Lorentz分布概率函數(shù)分布比較圖

通過二者的對(duì)比，它們的概率密度函數(shù)曲線(T=1)分布也十分明顯：Cauchy曲線分布在原點(diǎn)處的峰值比Gaussian曲線的分布小，說明曲線變化不大，比較適合全局搜索，而Cauchy曲線兩端長(zhǎng)扁平形狀趨于0的速度比Gaussian分布慢，在大范圍內(nèi)的搜索比較好。而Gaussian曲線分布狀態(tài)的發(fā)生器，主要集中在局部信息變換中，能有效地提高局部搜索能力，而產(chǎn)生大擾動(dòng)的概率幾乎為0，在大范圍內(nèi)的搜索中，難以脫離平坦區(qū)和多峰區(qū)，也就影響著局部搜索的效率；基于Cauchy分布的狀態(tài)發(fā)生器優(yōu)勢(shì)比較明顯，在全局范圍內(nèi)進(jìn)行數(shù)據(jù)搜索，相對(duì)Gaussian分布中的局部信息搜索能力，對(duì)較大范圍內(nèi)的抗干擾能力比較強(qiáng)，將Canchy-Lorentz二者結(jié)合在一起，可以優(yōu)化局部與全局優(yōu)化的效果。根據(jù)二者之間的特點(diǎn)，設(shè)計(jì)如下的Cauchy分布計(jì)算的新模型：

(1)

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

(2)

(3)

采用這種模型的優(yōu)勢(shì)是，在較高頻率內(nèi)可以進(jìn)行大范圍的搜索，在低頻率時(shí)，Gaussian模型的算法能在附近搜索，提高了搜索效率，而Cauchy分布有一平坦的“尾巴”，在搜索的過程中，可以跳出局部的搜索，采用這種算法改進(jìn)了退火算法的收斂速度，在同樣搜索范圍內(nèi)，增強(qiáng)搜索引擎的功能。

3.2 降溫方式

在構(gòu)建遺傳模擬快速退火算法時(shí)，需要合理地處理退火降溫的計(jì)算方法，才能滿足數(shù)據(jù)處理的要求，一般情況下，退火降溫計(jì)算如下：

(4)

其中，K0為降火的初始溫度，K為退火過程中的迭代次數(shù)，C為系統(tǒng)給定的常數(shù)，整數(shù)N為系統(tǒng)迭代過程中的待反演參數(shù)的個(gè)數(shù)。通過次數(shù)的迭代計(jì)算，上式可以改寫為：

T(K)=T0αk1/N)

(5)

在日常計(jì)算中，規(guī)定0.7≤α≤1，在具體算法處理中，采用1/N的取值為可以是0.5或者1，最終按Cauchy函數(shù)分布處理數(shù)據(jù)，構(gòu)建新的擾動(dòng)模型，并按Metropolis準(zhǔn)則接收數(shù)據(jù)處理過程中的變化方式，完成整改數(shù)據(jù)的處理過程。

3.3 搜索引擎中的遺傳退火算法的應(yīng)用

將遺傳算法與退火算法結(jié)合在一起，構(gòu)成遺傳模擬退火算法，同時(shí)還要結(jié)合搜索引擎的功能需求，合理的對(duì)分詞技術(shù)、模糊詞語(yǔ)進(jìn)行處理，才能提高搜索引擎的效率。

定義：設(shè)L為全體搜索空間、網(wǎng)站的鏈接集合，在該集合中包含著若干個(gè)搜索的詞語(yǔ)或者詞條，VL(value)為搜索處理的鏈接價(jià)值空間，能保證搜索引擎的重要性，l為詞語(yǔ)的鏈接。為了使得數(shù)據(jù)之間產(chǎn)生對(duì)應(yīng)關(guān)系，令：全體鏈接的集合到鏈接價(jià)值空間的映射v，存在l∈L→v(1)∈VL，將其稱為鏈接的價(jià)值函數(shù)。在具體的搜索過程中，算法流程如下。

1)初始化控制參數(shù)設(shè)置。根據(jù)降火溫度的要求，首先需要初始化鏈接優(yōu)先權(quán)隊(duì)列，為數(shù)據(jù)處理提供基礎(chǔ)條件，退火初始溫度T0，降火冷卻參數(shù)0≤C≤1，在從初始溫度T0達(dá)到平衡狀態(tài)Ti時(shí)，系統(tǒng)經(jīng)過S次經(jīng)循環(huán)，采用計(jì)數(shù)標(biāo)識(shí)變量的方法為：Loop←0。

2)在退火降溫處理的過程中，如果鏈接優(yōu)先權(quán)隊(duì)列為空，對(duì)系統(tǒng)的循環(huán)次數(shù)進(jìn)行處理，轉(zhuǎn)入步驟9)執(zhí)行；否則，隊(duì)頭鏈接出隊(duì)，并指向下一個(gè)搜索過程，完成第一次搜索過程。

3)如果頁(yè)面是主題相關(guān)頁(yè)面，并與用戶輸入的關(guān)鍵詞相匹配，則保存以備索引，否則丟棄本次搜索，進(jìn)入下一次的搜索。

4)處理頁(yè)面。將搜索數(shù)據(jù)與用戶進(jìn)行匹配，并提取頁(yè)面中未訪問過的鏈接URL，送入鏈接優(yōu)先權(quán)隊(duì)列，并提取鏈接文本信息和Web中的詞語(yǔ)，送入鏈接價(jià)值計(jì)算器，從而形成一個(gè)完整的搜索引擎過程。

5)結(jié)合步驟4)，鏈接價(jià)值計(jì)算器對(duì)搜索的詞匯進(jìn)行統(tǒng)計(jì)，計(jì)算每個(gè)鏈接的價(jià)值，循環(huán)統(tǒng)計(jì)搜索過程中的次數(shù)。

7)如果temp

8)如果Loop>S，k←k++，針對(duì)最大鏈接價(jià)值變化情況，需要調(diào)整退火溫度T(K)=T0αk1/N，這時(shí)，可以令α=0.8，1/N=0.5，則Loop←0，進(jìn)行下一步搜索。

9)在開始下一次搜索時(shí)，將Loop←Loop+1，轉(zhuǎn)入步驟2)。

10)循環(huán)搜索，直到整個(gè)搜索過程結(jié)束。

其中，步驟6)里面的value函數(shù)是鏈接評(píng)價(jià)函數(shù)，是保證搜索引擎有效性的關(guān)鍵，是計(jì)算每個(gè)鏈接評(píng)價(jià)值的函數(shù)，結(jié)合隨機(jī)數(shù)的變化，完成多次搜索過程。它可以采用多種方法來設(shè)計(jì)函數(shù)，如采用空間向量模型計(jì)算鏈接文本與搜索詞相似度的方法，并以此作為鏈接評(píng)價(jià)值函數(shù)value，完成整個(gè)搜索過程。

4 結(jié)語(yǔ)

采用遺傳模擬退火算法可以有效解決搜索引擎中出現(xiàn)的一些新詞、語(yǔ)法，即在遺傳算法中加入模擬退火算法，可以解決在局部收斂的地方陷于最優(yōu)解中，即控制跳出，利用多次循環(huán)的策略進(jìn)行搜索，提高了搜索引擎的效率，也提高搜索的準(zhǔn)確度，模擬退火算法可以彌補(bǔ)遺傳算法上的一些缺陷，消除了局部收斂的情況。