基于免疫協(xié)同進(jìn)化的多Agent輔助瀏覽系統(tǒng)研究

李國(guó)慶, 鄢靖豐

（許昌學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南許昌 461000）

0 引言

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

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

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

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

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

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

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

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

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

單個(gè)Agent所能代表的用戶的興趣比較有限,多個(gè)Agent采用協(xié)商機(jī)制就可以解決單個(gè)Agent的問題,以共同完成用戶多個(gè)興趣的檢索任務(wù),顯現(xiàn)出智能的系統(tǒng)行為。在協(xié)商過程中,每一個(gè)Agent都試圖達(dá)到自己的目標(biāo)或目的,當(dāng)出現(xiàn)沖突時(shí),通過協(xié)同進(jìn)化或?qū)で笃渌慕鉀Q辦法來達(dá)成一致的意見[3]。

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

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

2.1 用戶興趣模型

用戶興趣模型包括用戶賬號(hào)、用戶興趣項(xiàng)、用戶興趣項(xiàng)親和度及更新日期等屬性。興趣模型使用二維表的結(jié)構(gòu)。

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

2.2 初始化興趣模型

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

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

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

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

公式的設(shè)計(jì)使計(jì)算出的用戶興趣項(xiàng)的興趣度Di在區(qū)間[0,1],當(dāng)Di越接近1,表明用戶對(duì)該項(xiàng)興趣投入時(shí)間越多。

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

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

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

3 系統(tǒng)設(shè)計(jì)

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

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

圖2 瀏覽系統(tǒng)結(jié)構(gòu)圖

3.2 實(shí)驗(yàn)仿真

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

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

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

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

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

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

（3）響應(yīng)時(shí)間結(jié)果分析

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

圖3 準(zhǔn)確率仿真結(jié)果

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

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

4 結(jié)束語

討論了基于免疫協(xié)同進(jìn)化的多Agent技術(shù)實(shí)現(xiàn)Web的個(gè)性化服務(wù),智能Agent通過學(xué)習(xí)自動(dòng)建立用戶興趣模型,并以此模型通過模擬生物的免疫系統(tǒng)來實(shí)現(xiàn)個(gè)性化的服務(wù):對(duì)用戶搜索的信息進(jìn)行過濾,提高搜索的精確度,主動(dòng)向用戶推薦信息,利用用戶反饋Agent不斷收集更多用戶推薦和評(píng)價(jià)信息,實(shí)現(xiàn)Agent自學(xué)習(xí)性,隨著用戶使用時(shí)間的增加,推薦質(zhì)量會(huì)逐漸提高。對(duì)比實(shí)驗(yàn)證實(shí)本系統(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)化算法、學(xué)習(xí)與識(shí)別[M].北京:科學(xué)出版社,2007:316-325.

[5] 張泊平,王睿.基于網(wǎng)頁結(jié)構(gòu)相關(guān)性的個(gè)性化推薦技術(shù)研究[J].許昌學(xué)院學(xué)報(bào),2007,26（5）90-95.