基于免疫協同進化的多Agent輔助瀏覽系統研究

李國慶, 鄢靖豐

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

圖1 多Agent的免疫協同進化原理圖

2.1 用戶興趣模型

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

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

2.2 初始化興趣模型

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

2.3 動態更新興趣模型

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

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

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

2.4 根據興趣模型過濾信息

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

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

3 系統設計

3.1 系統實現

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

圖2 瀏覽系統結構圖

3.2 實驗仿真

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

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

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

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

False表示測試集中系統雖然推薦但是用戶沒有訪問的頁面數量。

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

（3）響應時間結果分析

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

圖3 準確率仿真結果

圖4 系統的平均推薦時間

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

4 結束語

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

[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] 焦李成,杜海峰,劉芳,等.免疫優化算法、學習與識別[M].北京:科學出版社,2007:316-325.

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