李國慶, 鄢靖豐

（許昌學院計算機科學與技術學院,河南許昌 461000）

0 引言

隨著網(wǎng)絡技術的飛速發(fā)展,人們越來越習慣于借助網(wǎng)絡媒介工作和學習。不同用戶使用瀏覽器訪問的數(shù)據(jù)大都有用戶自己的偏好。用戶長時間使用瀏覽器,會在Web服務器中積累大量的用戶訪問數(shù)據(jù),通過對這些數(shù)據(jù)進行采集和分析,就可以獲得用戶的瀏覽興趣和瀏覽習慣,從而獲得用戶上網(wǎng)的真實意圖。將免疫協(xié)同進化機制應用于Web服務的自動發(fā)現(xiàn)與合成是一種新的方法,由Agent來完成用戶的要求。

雖然Web服務的發(fā)現(xiàn)與合成已經(jīng)很成功的使用了Agent[1],但在Web服務的管理過程中,如何向用戶提供主動的服務,以及數(shù)量眾多的Agent的產(chǎn)生、通信、消亡如何管理還沒有成熟的方法。這將是今后互聯(lián)網(wǎng)發(fā)展的主要瓶頸。對于今后Web的服務動態(tài)管理的發(fā)展趨勢,HaiZhuge[2]總結了主要特征:自動合成策略;服務訪問的分布性、自擴展性;服務變化自適應以及對服務合成自調(diào)整性等。遺傳進化與人工免疫協(xié)同進化都是模擬生物進化的算法,但是基于免疫協(xié)同的進化機制更加適合處理那些復雜的動態(tài)環(huán)境優(yōu)化問題。雖然遺傳進化算法可以使種群較快速收斂并獲得解,但也會失去種群的多樣性,人工免疫協(xié)同進化機制則在多樣性維持能力方面取得了較好的效果。Gasper等最先嘗試將人工免疫系統(tǒng)（SAIS）用于動態(tài)優(yōu)化[3],人工免疫算法設置了兩種自適應變化的抗體適應度評價策略,實驗結果表明人工免疫算法在魯棒性與收斂速度方面比遺傳算法要好。但是,由于免疫機理的繁復性,無論在模型建立還是算法設計等方面對免疫現(xiàn)象的描述都還不完善[4]。由于多Agent系統(tǒng)在求解復雜分布問題時的高效性,將人工免疫網(wǎng)絡與多Agent結合,利用多Agent的現(xiàn)有成果,為構建基于免疫協(xié)同的個性化瀏覽系統(tǒng)提供思路。

文中將人工免疫協(xié)同進化機制與多Agent系統(tǒng)（Multi-Agent System,MAS）相結合引入Web服務。在多A-gent系統(tǒng)中,模擬生物免疫中的抗體間的促進和抑制關系,采集和分析用戶的興趣愛好,用戶的興趣愛好間既有一定的排斥性,又有相互協(xié)作的關系,基于免疫調(diào)節(jié)的思想,免疫協(xié)同把單個Agent個體看作一個抗體,把網(wǎng)絡資源看作抗原,引入親和度調(diào)節(jié)機制,設計抗體適應度方案,對現(xiàn)有興趣模型中的Agent個體進行進化,并由進化后的個體組成新的興趣模型,實現(xiàn)抗體間促進和抑制的免疫調(diào)節(jié)作用關系[3],為用戶提供滿足需求的信息。

1 免疫協(xié)同進化的多Agent Web客戶端模型

多Agent的免疫協(xié)同進化原理如圖1所示。其中抗原代表所有的網(wǎng)絡資源,抗體對應用戶的興趣愛好、瀏覽偏好。Agent通過以下過程選擇抗原:

（1）用戶需要使用個人賬號登陸瀏覽器,Web服務器根據(jù)用戶以往的使用記錄,從興趣庫中提取用戶興趣項組成候選解。經(jīng)過多次迭代運行更新抗體集合和興趣庫。每次迭代時根據(jù)抗體和抗原之間的匹配程度計算各自的親和度;

（2）克隆增殖。其目的是根據(jù)用戶的瀏覽行為挖掘出用戶的興趣變化。用戶經(jīng)常瀏覽和檢索的內(nèi)容其興趣親和度增加,反之減少。并利用免疫協(xié)同進化機制將興趣項在多Agent之間克隆。

（3）變異。多Agent在搜索用戶的興趣項過程中,可能會限于局部最優(yōu),通過模擬免疫系統(tǒng)的變異,可以使Agent在更大范圍內(nèi)搜索最優(yōu)解。

（4）基因庫進化。選取親和度值高的興趣作為成熟抗體,刪除親和度值低的其它抗體,通過興趣庫更新的方式反饋回興趣基因庫,以期提高興趣基因庫的性能。

單個Agent所能代表的用戶的興趣比較有限,多個Agent采用協(xié)商機制就可以解決單個Agent的問題,以共同完成用戶多個興趣的檢索任務,顯現(xiàn)出智能的系統(tǒng)行為。在協(xié)商過程中,每一個Agent都試圖達到自己的目標或目的,當出現(xiàn)沖突時,通過協(xié)同進化或尋求其他的解決辦法來達成一致的意見[3]。

2 免疫協(xié)同進化的多Agent Web客戶端設計

圖1 多Agent的免疫協(xié)同進化原理圖

2.1 用戶興趣模型

用戶興趣模型包括用戶賬號、用戶興趣項、用戶興趣項親和度及更新日期等屬性。興趣模型使用二維表的結構。

對不同的用戶使用用戶賬號進行區(qū)分,每個用戶使用密碼登陸瀏覽器;興趣項用于表示用戶的興趣愛好和瀏覽習慣,可以包含表示相應興趣的關鍵字,用于檢索資源,一個興趣項可以有多個關鍵字;親和度用來表示用戶對相應興趣項的關注程度,親和度越高,表示該類資源對用戶越重要;日期時間用于記錄最近一次更新興趣項、親和度等信息的時間,用戶注冊賬號是日期為注冊時間,興趣項和親和度等均為空,系統(tǒng)根據(jù)用戶之后的瀏覽習慣分析用戶的興趣項和親和度,然后對用戶興趣項等進行更改。每次登陸系統(tǒng),用戶興趣模型都將被更新。

2.2 初始化興趣模型

當用戶第一次使用瀏覽器時需要注冊,系統(tǒng)會給用戶分配唯一的賬號,并初始狀態(tài)興趣項、關鍵詞、親和度等內(nèi)容為空或者0。用戶使用賬號登陸瀏覽器時,Agent會主動記錄并分析用戶的瀏覽和檢索操作,并對用戶興趣表進行初始設置。提取用戶的興趣項、檢索關鍵詞等信息內(nèi)容,并設置親和度,以此作為用戶以后使用賬號登陸瀏覽器時的初值。但是用戶興趣項要受到數(shù)量的限制。當用戶以后再次登陸瀏覽器時,協(xié)同Agent會根據(jù)用戶的興趣親和度匹配相應的網(wǎng)絡資源推薦給用戶。親和度越高,資源越接近用戶的需要。

2.3 動態(tài)更新興趣模型

用戶使用瀏覽器登陸時,系統(tǒng)會根據(jù)用戶興趣表中的興趣的親和度反饋相應的信息,并根據(jù)信息主動檢索用戶需要的資源推薦給用戶,從而可以節(jié)省大量的時間。用戶如果瀏覽了系統(tǒng)推薦的相關資源,則相應的興趣項的親和度會增加,如果用戶訪問了系統(tǒng)沒有推薦的資源,說明用戶的興趣可能發(fā)生了變化,無論哪種情況,用戶興趣模型都將被更新,通過免疫協(xié)同進化修改已有興趣項的親和度、刪除長時間沒有關注的興趣項、加入最近的興趣項?；诿庖邊f(xié)同進化的多Agent瀏覽系統(tǒng)通過采樣分析用戶的訪問數(shù)據(jù)來總結用戶的興趣,實現(xiàn)自主學習,自動更新。下面提出一種計算用戶興趣親和度的方法。

用戶經(jīng)常瀏覽的內(nèi)容就是用戶主要的興趣,相應親和度值應增加;長時間不訪問某一興趣項,說明相關內(nèi)容用戶已不再關注,相應興趣項親和度應減少,當小于某一設定值時則應刪除相應興趣項并使用新的興趣項替換。用戶興趣項親和度Di與用戶使用系統(tǒng)的瀏覽時間Hi、用戶檢索次數(shù)Si、登陸系統(tǒng)次數(shù) Ti等相關。系統(tǒng)對該興趣項的親和度Di設計公式如下:

公式的設計使計算出的用戶興趣項的興趣度Di在區(qū)間[0,1],當Di越接近1,表明用戶對該項興趣投入時間越多。

2.4 根據(jù)興趣模型過濾信息

在選擇最優(yōu)資源時,Agent首先把興趣項、親和度等內(nèi)容發(fā)送給服務器,查詢相應的資源與歷史記錄的相關程度,將相似度超過一定閾值的資源推薦給用戶。資源與用戶興趣相關度的計算公式如下:

其中:Di表示用戶興趣項i的親和度,Ti表示興趣項i在資源中的重要程度（可以用興趣項在資源中出現(xiàn)的詞頻或者次數(shù)表示）。相似度越高,資源對用戶的可用性越高。

3 系統(tǒng)設計

3.1 系統(tǒng)實現(xiàn)

系統(tǒng)開發(fā)利用Java語言設計實現(xiàn)。Java語言是一種跨平臺,適合于分布式計算環(huán)境的面向對象的程序編輯語言,具有可靠、安全、平臺無關、可移植、高性能、多線程、動態(tài)性等特點,用Java編程比較容易實現(xiàn)多Agent間的通訊及功能模塊的編程。興趣模型的屬性課操作被設計為相應的類,基于免疫協(xié)同進化的生物功能也設計在其中。系統(tǒng)利用自動網(wǎng)頁搜集程序（Robot）先在網(wǎng)絡搜尋所有資源,再利用用戶興趣模型將搜尋到的信息進行分類整理,并術建立相應的索引,當用戶使用瀏覽系統(tǒng)時,系統(tǒng)根據(jù)用戶興趣模型,參考用戶的興趣項和親和度等信息,通過智能檢索將檢索結果數(shù)據(jù)過濾排序并推薦給用戶。系統(tǒng)結構圖如圖2所示。

圖2 瀏覽系統(tǒng)結構圖

3.2 實驗仿真

實驗仿真采用美國德保羅大學網(wǎng)站的“在線資源”數(shù)據(jù)集進行處理。先對數(shù)據(jù)進行清洗,然后去除支持度大于80%的記錄以及會話長度小于4的記錄。最后把剩余的數(shù)據(jù)分為訓練集和測試集兩部分,訓練集trainingl0000條記錄,測試集test 1623條記錄。測試所采用的環(huán)境為Intel（R）Xeon（R）3.47GHz,內(nèi)存4G。從推薦系統(tǒng)的準確率、召回率和響應時間3個方面對系統(tǒng)進行評測。

（1）召回率（Recall,R）:召回率是待推薦頁面與被推薦頁面的比率。

其中Recommend表示測試集頁面中系統(tǒng)主動推薦給用戶并被用戶訪問的頁面數(shù)量,Miss表示被過濾掉的頁面數(shù)量。

（2）準確率（Precision）表示系統(tǒng)推薦的頁面推薦成功的比率:

False表示測試集中系統(tǒng)雖然推薦但是用戶沒有訪問的頁面數(shù)量。

在現(xiàn)實生活中很難對召回率和準確率這兩個指標進行平衡,如果推薦的頁面數(shù)量增加,則 Recall值將會增加,而Precision值卻減少。然而召回率和推薦精度都很重要。故而綜合考慮這兩方面是比較恰當?shù)?指標R通過設定采用相同的權重將召回率和準確率結合起來,在二者找到最佳的平衡。

（3）響應時間結果分析

用戶通過推薦系統(tǒng)訪問Web服務器,與用戶直接訪問Web服務器的延時差別主要體現(xiàn)為推薦系統(tǒng)與Web服務器之間信息傳遞和推薦系統(tǒng)生成信息的時間。前者和具體的網(wǎng)絡傳輸速度相關,不易于定量分析,然而推薦系統(tǒng)生成推薦信息的時間是可以把握的。推薦系統(tǒng)生成推薦信息的時間正是推薦算法所花費的時間。系統(tǒng)的平均推薦時間如圖4所示。

圖3 準確率仿真結果

圖4 系統(tǒng)的平均推薦時間

通過分析實驗結果可以看出,提出的基于免疫協(xié)同進化的多Agent技術實現(xiàn)Web的個性化服務,無論是從推薦時間還是推薦的準確度上,都有較大的改進。通過MAS技術優(yōu)勢,可以將大量計算在離線狀態(tài)下完成,對比實驗說明該系統(tǒng)模型是有效的。同時系統(tǒng)通過用戶反饋Agent可不斷收集更多的推薦和評價信息,隨著用戶使用時間的增加推薦質量會逐漸提高。

4 結束語

討論了基于免疫協(xié)同進化的多Agent技術實現(xiàn)Web的個性化服務,智能Agent通過學習自動建立用戶興趣模型,并以此模型通過模擬生物的免疫系統(tǒng)來實現(xiàn)個性化的服務:對用戶搜索的信息進行過濾,提高搜索的精確度,主動向用戶推薦信息,利用用戶反饋Agent不斷收集更多用戶推薦和評價信息,實現(xiàn)Agent自學習性,隨著用戶使用時間的增加,推薦質量會逐漸提高。對比實驗證實本系統(tǒng)模型的有效性。

[1] Sycara K,Paolucci M,Soudry J,et al.Dynamic Discovery and Coordination of Agent-Based Semantic Web Services[J].IEEE Internet Computing,2004,8（3）:66-73.

[2] Hai Zhuge.The Future Interconnection Environment[J].IEEE Computer,2005,38（4）:27-33.

[3] GRSPAR A,COLLARD P.Two models of immunization for time dependent optimization[C]//IEEE International Conference on Systems,Man and Cybernetlcs,New York:IEEE,2000,1:113-118.

[4] 焦李成,杜海峰,劉芳,等.免疫優(yōu)化算法、學習與識別[M].北京:科學出版社,2007:316-325.

[5] 張泊平,王睿.基于網(wǎng)頁結構相關性的個性化推薦技術研究[J].許昌學院學報,2007,26（5）90-95.