個(gè)性化搜索引擎推薦算法研究

1、 收稿日期 :2009203227; 修回日期 :2009205215 基金項(xiàng)目 :國(guó)家教育部科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目 (108168, 2008. 0122010. 01 作者簡(jiǎn)介 :陳華 (19812 , 男 , 江蘇鹽城人 , 碩士 , 主要研究方向?yàn)樾畔⒕W(wǎng)絡(luò) (chenhua1028 ; 李仁發(fā) (19572 , 男 , 教授 , 博導(dǎo) , 主要研究 方向?yàn)闊o(wú)線網(wǎng)絡(luò) 、 嵌入式計(jì)算和嵌入式軟件 、 數(shù)字媒體 ; 劉鈺峰 (19742 , 男 , 博士 , 主要研究方向?yàn)榉植际綄?shí)時(shí)操作系統(tǒng)、 信息網(wǎng)絡(luò) ; 練琪 (19822 , 女 , 江蘇鹽城人 , 碩士 , 主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò) .

2、個(gè)性化搜索引擎推薦算法研究3陳 華 , 李仁發(fā) , 劉鈺峰 , 練 琪(湖南大學(xué) 計(jì)算機(jī)與通信學(xué)院 , 長(zhǎng)沙 410082摘 要 :將個(gè)性化引入搜索引擎出現(xiàn)了稀疏性、 精確性、 擴(kuò)展性等新問(wèn)題。 針對(duì)以上問(wèn)題 , 提出了一種基于 S VD(單值分解 影響集的協(xié)作過(guò)濾推薦算法 , 在利用矩陣相關(guān)技術(shù)以及擴(kuò)大影響的基礎(chǔ)上 , 將用戶潛在感興趣的資源推薦給用戶。 實(shí)驗(yàn)表明 , 該算法可有效解決以上存在的問(wèn)題 , 顯著提高個(gè)性化系統(tǒng)的推薦質(zhì)量。 關(guān)鍵詞 :推薦系統(tǒng) ; 協(xié)同過(guò)濾 ; 單值分解 ; 相似性中圖分類(lèi)號(hào) :TP311. 5 文獻(xiàn)標(biāo)志碼 :A 文章編號(hào) :100123695(2010 0120

3、048203doi:10. 3969/j . issn . 100123695. 2010. 01. 013A lgorith m s recommend research on pers CHE N Hua, L I Ren 2fa, L IU Q i(School of Co m puter &Co mm unication, , Abstract:The intr oducti on of pers int o s of a s parse, accuracy, scalability . I n vie wof the above p r oblem, this p r on

4、algorith m s based on the i m pact of S VD t o recommend res ources matrix 2related technol ogies and expanding its influence . The experi 2ment shows s olve the above p r oblem s, significantly i m p r ove the recommendati on quality of the pers onalizati on Key words:syste m s; collaborative filte

5、ring; single value decompositi on (S VD ; si m ilarity 以 Google 、 Baidu 為代表的搜索引擎已為人們熟知 , 具有基 于關(guān)鍵字 、 通用性等特點(diǎn) 。 而對(duì)于如何為不同興趣 、 背景的用 戶提供更高效率 、 更專(zhuān)業(yè)的服務(wù) , 使得個(gè)性化搜索引擎技術(shù)成 為目前的研究熱點(diǎn)之一 。個(gè)性化搜索引擎就是針對(duì)用戶的不 同需求 , 在查詢(xún)關(guān)鍵字相同時(shí) , 根據(jù)用戶背景和其用戶群喜好 主動(dòng)為用戶推薦滿足用戶潛在興趣的資源 。如果用戶 1喜歡 去關(guān)于探險(xiǎn)的地方旅游 , 而用戶 2則喜歡去浪漫的地方旅游 , 則兩者的需求不同 。而現(xiàn)有的搜索引擎在輸

6、入相同關(guān)鍵字 “ 旅游 ” 時(shí) , 返回的結(jié)果是沒(méi)有區(qū)別的 。本文的研究則是針對(duì) 需求的不同 , 為用戶提供不同的更專(zhuān)業(yè)的服務(wù) 。目前存在許多不同的推薦系統(tǒng) , 個(gè)性化搜索引擎使用的最 主要的技術(shù)是推薦技術(shù) , 根據(jù)所采用的技術(shù)不同 , 分別有基于 規(guī)則的 、 基于項(xiàng)目的 、 基于用戶的推薦等 , 但是最主要的還是基 于用戶的推薦 。 相關(guān)工作現(xiàn)有的推薦大都采用基于項(xiàng)目推薦 、 基于用戶推薦 。 項(xiàng)目 推薦簡(jiǎn)單 、 有效 , 但是只能發(fā)現(xiàn)與用戶已有興趣相似的信息 ; 用 戶推薦可以為用戶發(fā)現(xiàn)新的潛在感興趣的資源 , 但是具有稀疏 性和擴(kuò)展性等缺點(diǎn) 。 本文是在考慮如何利用現(xiàn)有技術(shù)解決稀 疏性和

7、擴(kuò)展性而展開(kāi)的 。 1 用戶與資源描述 用戶與資源的關(guān)系1建模 (表 1 用 m ×n 階矩陣表示 。 其中 , m 個(gè)用戶 , n 個(gè)項(xiàng)目 , R i , j 代表用戶 i 對(duì)項(xiàng)目 j 的評(píng)分 。表 1 用戶項(xiàng)目矩陣ratingite m 1 ite m j ite m nuser 1R 1, 1R 1,jR 1, n user i R i , 1R i ,jR i , n user mR m , 1R m ,jR m , n1 推薦算法信息過(guò)濾技術(shù)可分為如下三種 :a 基于規(guī)則過(guò)濾 。 規(guī)則其實(shí)是用一些 if 2else 語(yǔ)句 , 可以利用用戶靜態(tài)屬性或動(dòng)態(tài)信息來(lái)建立 。 可以由

8、用戶定制規(guī)則 , 也 可以利用關(guān)聯(lián)規(guī)則挖掘規(guī)則 2, 根據(jù)當(dāng)前用戶感興趣的內(nèi)容 , 通過(guò)規(guī)則推出用戶還沒(méi)有閱讀過(guò)的感興趣的內(nèi)容 。規(guī)則推薦依賴(lài)規(guī)則的質(zhì)量和數(shù)量 , 基于規(guī)則的缺點(diǎn)是隨著 規(guī)則的數(shù)量增多 , 系統(tǒng)將變得難以管理 。b 基于內(nèi)容過(guò)濾 (content 2based filtering ?；趦?nèi)容的推薦 3的基本思想是根據(jù)用戶以前的興趣來(lái)推測(cè)用戶以后的興 趣 。 基于內(nèi)容過(guò)濾系統(tǒng)的優(yōu)點(diǎn)是簡(jiǎn)單 、 有效 , 缺點(diǎn)是難以區(qū)分 資源內(nèi)容的品質(zhì)和風(fēng)格 , 而且不能為用戶發(fā)現(xiàn)新的感興趣的資 源 , 只能發(fā)現(xiàn)與用戶已有興趣相似的資源 。首先找到對(duì)兩個(gè)項(xiàng)目共同評(píng)分的用戶 , 將用戶評(píng)分形成向 量

9、, 然后利用相似度公式進(jìn)行計(jì)算 。 這樣系統(tǒng)就可以根據(jù)用戶 先前的興趣來(lái)預(yù)測(cè)用戶對(duì)目標(biāo)項(xiàng)目的興趣程度 , 可以用式 (1來(lái)計(jì)算 :第 27卷第 1期 2010年 1月 計(jì) 算 機(jī) 應(yīng) 用 研 究App licati on Research of Computers Vol . 27No . 1Jan . 2010P u, j = nj si m (i, j ×R u, j nj =1si m (i, j (1其中 :R u, j 是用戶 u 對(duì)資源項(xiàng)目 j 的評(píng)分 ; si m (i, j 是項(xiàng)目 i 和 j 的相似度 。c 協(xié) 作 過(guò) 濾 (collaborative filter

10、ing ?；?于 協(xié) 同 的 推 薦 (CF 4又稱(chēng)為合作過(guò)濾或社會(huì)過(guò)濾 (s ocial filtering 。 協(xié)作推 薦實(shí)現(xiàn)的基本思想是找到目標(biāo)用戶的若干最近鄰居 (與目標(biāo)用 戶有相似興趣的用戶 , 然后根據(jù)最近鄰居對(duì)目標(biāo)項(xiàng)目的評(píng)分產(chǎn) 生推薦。 這種推薦方法可以為用戶發(fā)現(xiàn)新的感興趣的資源。 基于協(xié)作過(guò)濾系統(tǒng)的優(yōu)點(diǎn)是能為用戶發(fā)現(xiàn)新的感興趣的 信息 , 缺點(diǎn)是存在兩個(gè)很難解決的問(wèn)題 :(a 稀疏性 , 即在系統(tǒng) 使用初期 , 由于系統(tǒng)資源還未獲得足夠多的評(píng)價(jià) , 系統(tǒng)很難利 用這些評(píng)價(jià)來(lái)發(fā)現(xiàn)相似的用戶 ; (b 可擴(kuò)展性 , 即隨著系統(tǒng)用 戶和資源的增多 , 系統(tǒng)的性能會(huì)越來(lái)越低 。計(jì)算目標(biāo)

11、用戶對(duì)未評(píng)分項(xiàng)目的評(píng)分時(shí) , 根據(jù)最近鄰居對(duì)項(xiàng) 目的評(píng)分產(chǎn)生推薦 。計(jì)算用戶 u 對(duì)項(xiàng)目 j 的評(píng)分為P u, j = nsi m (u, m , jnm =12其中 :R m , i 是用戶 m i (u, m 是用戶 u 和 m 的相似度 。 1 計(jì)算相似用戶度量用戶之間的興趣相似性實(shí)際上就是計(jì)算向量之間的 相似性 , 一般有三種方法 1:a 余弦相似性 。 把用戶評(píng)分看做是 n 維項(xiàng)目空間上的向 量 , 如果用戶對(duì)某個(gè)項(xiàng)目沒(méi)有評(píng)分 , 則將此評(píng)分假設(shè)為 0。通 過(guò)計(jì)算兩個(gè)向量之間的夾角余弦來(lái)度量?jī)蓚€(gè)用戶之間的相似 性 。 計(jì)算公式如下 :si m (i, j = nR i , k 

12、15;R j , k n =1R 2i , k × nk =1R 2j , k(3其中 :R i , k 、 R j , k 是用戶 i 、 j 對(duì)項(xiàng)目 k 的評(píng)分 。b 相關(guān)相似性 。 通過(guò) peas on 相關(guān)系數(shù)來(lái)度量?jī)蓚€(gè)用戶的 相似性 。 計(jì)算時(shí) , 首先找到兩個(gè)用戶共同評(píng)分過(guò)的項(xiàng)目集 , 然 后計(jì)算這兩個(gè)向量的相關(guān)系數(shù) 。 計(jì)算公式如下 :si m (i, j = c I (R i , c -R i (R j , c -R j c I i , j (R i , c -R i 2× c I i , j (R i , c -R j 2(4其中 :I i , j 是用戶

13、 i 和 j 共同評(píng)分過(guò)的項(xiàng)目集 ; R i , c 是用戶 i 對(duì)項(xiàng) 目 c 的評(píng)分 ; R i 是用戶 i 對(duì)資源的平均評(píng)分 。c 修正的余弦相似性 。在余弦相似性中沒(méi)有考慮不同用 戶的評(píng)分尺度問(wèn)題 , 修正的余弦相似性通過(guò)減去項(xiàng)目的平均評(píng) 分來(lái)彌補(bǔ)這種不足 。 計(jì)算公式如下 :si m (i, j = c I (R i , c -R c (R j , c -R c c I i , j (R i , c -R c 2× c I i , j (R i , c -R c 2(5其中 :R c 是項(xiàng)目 c 的平均評(píng)分 。 推薦算法優(yōu)化在現(xiàn)有的搜索引擎技術(shù)基礎(chǔ)上 , 結(jié)合當(dāng)前個(gè)性化服務(wù)思

14、 想 , 考慮到推薦系統(tǒng)的擴(kuò)展性 5和稀疏性 6等問(wèn)題 , 從影響集 的概念出發(fā) , 采用 S VD 、 k NN 和 Rk NN 等技術(shù) , 提出一種基于用戶過(guò)濾的推薦算法以提高推薦系統(tǒng)的推薦質(zhì)量 。將用戶潛在感興趣的資源推薦給用戶 , 以達(dá)到為不同需求的用戶提供不同 的高效的專(zhuān)業(yè)服務(wù)效果 。 1矩陣簡(jiǎn)化推薦技術(shù)在個(gè)性化系統(tǒng)中已經(jīng)取得了巨大的成功 , 但同時(shí) 它的一些技術(shù)包括協(xié)同過(guò)濾的缺點(diǎn)暴露無(wú)疑 , 存在有稀疏性 、 擴(kuò)展性等問(wèn)題 , 初步可以使用 S VD 處理 。S VD 又叫做單值分解7, 8, 是一種矩陣分解技術(shù) , 它可將一個(gè) m ×n 的矩陣 R 分解為三個(gè)矩陣 。R

15、 0=T 0S 0D 0, S 0=diag (1, , r 其中 :T 0和 D 0分別是 m ×r 和 r ×n 的正交矩陣 , r 是矩陣 R 0的秩 ; S 0是一個(gè) r ×r 的對(duì)角矩陣 , 1r 0, 稱(chēng)為單值 (singular value 。算法 1 輸入 :R 0;:、 D a 0r i (相 代替 。r ij -r i 代替原來(lái)的 r ij , 得到矩陣 R 1; R 1經(jīng)過(guò)單值分解 , 得到 T 1、 S 1、 D 1。c 將 S 1簡(jiǎn)化 , 將對(duì)角線上小于 1的值用 0代替 , 將相應(yīng)的 全為 0的列或行刪除得到 S , 即維數(shù)為 s 的對(duì)

16、角矩陣 。d 根據(jù) S 簡(jiǎn)化 T 1、 D 1, 得到 T 、 D , 則有 R =TSD , 且 R R 0。e 計(jì)算 S 的平方根得到 S 1/2; 計(jì)算兩個(gè)相關(guān)矩陣 TS1/2、S1/2D 。采用向量空間方法計(jì)算相似性 , 這里分析的對(duì)象是經(jīng)過(guò)S VD 分解后的 m ×s 矩陣 TS1/2, 它描述的是用戶在 k 維空間中的關(guān)系 。 因?yàn)榻?jīng)過(guò)單值分解 , 大大降低了它的數(shù)據(jù)稀疏性 , 可 以產(chǎn)生比較精確的最近鄰居集和相應(yīng)的 t op 2N 推薦集 。基于 維數(shù)簡(jiǎn)化的算法 1較好地解決了數(shù)據(jù)稀疏性的問(wèn)題 。1 與評(píng)分矩陣經(jīng)過(guò)矩陣簡(jiǎn)化以后 , 尋找相似用戶或相似項(xiàng)目應(yīng) 該來(lái)說(shuō)更加簡(jiǎn)

17、單精確 , 但是如果原來(lái)矩陣是稀疏的 , 即相似用 戶或相似項(xiàng)目本來(lái)就很少 , 在經(jīng)過(guò)矩陣簡(jiǎn)化以后 , 相似用戶就 會(huì)變得更少 。 對(duì)于這樣的情況 , 本文引入 k NN 與 Rk NN, 增加 用戶的影響集來(lái)為其進(jìn)行預(yù)測(cè)評(píng)分 。最近鄰及其檢索算法是計(jì)算機(jī)科學(xué)的主要核心問(wèn)題之一 。 近年來(lái) , k 2最 近鄰的逆問(wèn)題逐漸得到人們廣泛關(guān)注 。所謂逆 k 2最近鄰 9, 10, 就是在給定的數(shù)據(jù)集 S 中 , 查詢(xún)特定點(diǎn) q 被其他 哪些點(diǎn)視為最近鄰并從中選取有重要影響的點(diǎn) , 可以通過(guò) k NN算法的逆算法 Rk NN (reverse k 2nearest neighbor 來(lái)解決 。給定數(shù)據(jù)

18、集 S, D (p, q 表示 p 、 q 兩點(diǎn)間的距離 。RkNN (q =q kNN (p |p S 值得注意的是 , k NN 和 Rk NN 不是對(duì)稱(chēng)的 , 即 p k NN (q 不能推出 q Rk NN (p 。算法 2 基于 k NN 和 Rk NN 的協(xié)作過(guò)濾推薦算法 輸入 :用戶項(xiàng)目評(píng)分矩陣 A (m , n , 用戶 i, 預(yù)測(cè)項(xiàng)目 j ; 輸出 :用戶 i 在項(xiàng)目 j 上的預(yù)測(cè)評(píng)分 。a 在 A (m , n 中計(jì)算用戶間的相似度 , 存入距離矩陣 。 b 對(duì)于每個(gè)用戶 i I, 根據(jù)距離矩陣找到 i 的最近鄰序 列 , 并按相似度從高到低進(jìn)行排序 , 得到的最近鄰 相似

19、性列94 第 1期陳 華 , 等 :個(gè)性化搜索引擎推薦算法研究 表 Tk NN 并保存 。c 掃描 Tk NN, 為每個(gè)項(xiàng)目 i I 尋求逆最近鄰序列 , 同樣 按相似度從高到低進(jìn)行排序 , 得到逆最近鄰 相似性列表 TRk NN 并保存 。d 在最近鄰 相似性列表 Tk NN 中找到用戶 i 所對(duì)應(yīng)的 行 , 順序取出前 k 個(gè)項(xiàng) i1, i 2, , i k 。e 在逆最近鄰 相似性列表 TRk NN 中找到用戶 i 所對(duì)應(yīng) 的行中 , 順序取出前 k 個(gè) 項(xiàng) 。f 根據(jù)推薦產(chǎn)生式 (2 選擇適當(dāng)?shù)膮?shù)值 , 計(jì)算用戶 i 在 項(xiàng)目 j 上的預(yù)測(cè)評(píng)分并輸出 。最近鄰一相似性列表和逆最近鄰

20、相似性列表只需定期離 線計(jì)算一次并保留下來(lái)即可 , 并不影響在線推薦產(chǎn)生的速度。 1 預(yù)測(cè)評(píng)分考慮到用戶給資源打分時(shí) , 用戶具有苛刻程度不等的情 況 , 將具體預(yù)測(cè)評(píng)分修改為R u, j =R u n(Ri , j/Ri ×si m (u, i ni =1si m (u, i (6其中 :Ri是用戶 i項(xiàng)目的平均評(píng)分 , si m (u, i iR u, j , 如式 (7 所示 :R u, j =R u ( (Ri , j i×si m (u, i ni k NN (u si m (u, i (7R u, j 是通過(guò)用戶 u 的 Rk NN 來(lái)計(jì)算的評(píng)分 , 如式 (8

21、 所示 :R u, j =R uni R k NN (u (Ri , j/Ri ×si m (u, i ni Rk NN (u si m (u, i (8 在算法 2中 , 綜合 kNN 和 Rk NN 的評(píng)分 , 按照推薦項(xiàng)目的 評(píng)分結(jié)合思想 , 用戶 u 對(duì)項(xiàng)目 j 最終預(yù)測(cè)評(píng)分如式 (9 所示 : P u, j =P u, j +(1- P u, j (9 其中 :是 k NN 和 Rk NN 分別控制影響最終評(píng)分的影響因子 。 1 基于 影響集的協(xié)作過(guò)濾推薦算法利用矩陣簡(jiǎn)化 , 擴(kuò)大 k NN 或 Rk NN 影響集等技術(shù)的基礎(chǔ) 上 , 解決矩陣稀疏和相似用戶難以確定等問(wèn)題

22、。算法 3 基于 S VD 影響集的協(xié)作過(guò)濾推薦算法輸入 :用戶 項(xiàng)目評(píng)分矩陣 R (m , n 。輸出 :推薦給用戶的項(xiàng)目序列 。a 將矩陣 R 單值分解 , 得到簡(jiǎn)化 T 、 S 、 D 。b 計(jì)算用戶相關(guān)矩陣 TS 1/2(m , k , 記做 A 。c 在 A (m , n 中計(jì)算用戶間相似度 , 并存入距離矩陣 。d 對(duì)于用戶 i I, 找到 i 的 Tk NN 和 TRk NN 并保存 。e 在列表 TkNN 中找到用戶 i 所對(duì)應(yīng)的行 , 順序取出前 k 個(gè)項(xiàng) i1, i 2, , i k 以及 TRk NN 的前 k 個(gè) 項(xiàng) 。f 分別根據(jù)推薦產(chǎn)生式 (7 (9 并選取適當(dāng)參數(shù)

23、 , 計(jì)算 用戶 i 對(duì)項(xiàng)目 j 上的預(yù)測(cè)評(píng)分 , 并計(jì)算產(chǎn)生用戶的項(xiàng)目推薦序 列 。 實(shí)驗(yàn)結(jié)果和分析本文實(shí)驗(yàn)數(shù)據(jù)采用 Movie Lens data sets 。 Gr oupLens 是一個(gè) 在 M innes ota 大學(xué)計(jì)算機(jī)科學(xué)與工程系的研究實(shí)驗(yàn)室 , 其研究 領(lǐng)域包括推薦系統(tǒng) 、 在線社區(qū) 、 移動(dòng)技術(shù) 、 數(shù)字圖書(shū)館 、 當(dāng)?shù)氐?理信息系統(tǒng) 。 Movie Lens 是一個(gè)研究推薦系統(tǒng) , 本文使用的具 體實(shí)驗(yàn)的數(shù)據(jù)是 6040個(gè)用戶對(duì) 3900個(gè)電影的一百萬(wàn)的評(píng)價(jià) 記錄的原始數(shù)據(jù) , 這個(gè)是極其稀疏的 。推薦質(zhì)量的評(píng)價(jià)標(biāo)準(zhǔn)采用平均絕對(duì)偏差 MAE 11, 12, 如式 (10

24、所示 , 值越小 , 推薦效果越好 。 其中 , pi是評(píng)測(cè)分?jǐn)?shù) , q i 是 用戶實(shí)際評(píng)分 。MAE =N|p i -q i |N(10 本文采用修正的余弦相似性進(jìn)行實(shí)驗(yàn) 。這里 k = 200, =0. 5。如圖 1所示 , 基于 S VD 和影響集的協(xié)作過(guò)濾算法比最近 鄰集合的協(xié)作過(guò)濾算法取得了較低的 MAE, 取得了更好的推 薦效果 。 本實(shí)驗(yàn)證明 , 基于 S VD 和影響集的協(xié)作過(guò)濾算法不 但能夠解決稀疏性和擴(kuò)展性 , 。 使 用 S VD , , 處理后的矩陣 S 的秩 r <, 但是如果原來(lái)矩陣 , 在經(jīng)過(guò)矩陣簡(jiǎn) , 。而在擴(kuò)大 k NN 或 Rk NN 后 , 使推薦

25、的結(jié)果更加精確 , 即提高了精確性 。算法 3中存在影響因子 , 鄰居集 k 的動(dòng)態(tài)參數(shù) , 當(dāng) k > 200時(shí) ,MAE 基本沒(méi)有變化 , k =200, 如圖 1所示 ; 當(dāng) =0. 5時(shí) , 推薦效果達(dá)到最優(yōu) , 如圖 2所示 。 結(jié)束語(yǔ)個(gè)性化系統(tǒng)越來(lái)越多地應(yīng)用在各個(gè)領(lǐng)域中 , 隨之原有的 推薦算法就會(huì)暴露出一些問(wèn)題 , 本文從矩陣的先縮后放角度 較好地解決了稀疏性擴(kuò)展性問(wèn)題 。然而將個(gè)性化引入搜索 引擎 , 將需要維護(hù)一個(gè)龐大的用戶資源矩陣 , 而且也是要考 慮計(jì)算時(shí)間成本 。本文僅考慮了協(xié)同過(guò)濾 , 但是基于項(xiàng)目過(guò) 濾同樣也有其優(yōu)點(diǎn) 。下一步工作就是考慮如何處理好一個(gè) 龐大的

26、矩陣 , 以及如何利用基于項(xiàng)目過(guò)濾和協(xié)同過(guò)濾兩者優(yōu) 點(diǎn)共同提高推薦效果 。參考文獻(xiàn) :1曾春 , 邢春曉 , 周立柱 . 個(gè)性化服務(wù)技術(shù)綜述 J .軟件學(xué)報(bào) , 2002, 13(10 :195321955.2ADOMAV I C I U S G, T UZH I L I N A. U ser p r ofiling in pers onalizati on app licati ons thr ough rule discovery and validati on C /Proc of the 5th I nternati onal Conference on Data M ining an

27、d Knowledge D iscove 2 ry . New York:AC M Press, 1999:3772381.3J I N X, ZHOU Y, MOBASHER B. A unified app r oach t o pers onaliza 2 ti on based on p r obabilistic latent semantic models of W eb usage and contentC /Proc of the AAA IWorkshop on Se mantic W eb Pers ona 2 lizati on . San Jose:AAA I, 200

28、4:26234.4HERLOCKER J, K ONST AN J, R I E DL J. Exp laining collaborative filtering recommendati onsC /Proc of AC M Conference on Compu 2 ter Supported Cooperative Work . Ne w York:AC M Press, 2000:2412 250. (下轉(zhuǎn)第 53頁(yè) 5 計(jì) 算 機(jī) 應(yīng) 用 研 究 第 27卷第 j 個(gè)元素 , P (B C ij 的信息素值表示為 pher P (B C ij , inc 表示螞 蟻根據(jù)蟻巢到食物源

29、距離來(lái)增加的信息素 。蟻群尋找 Hopfield 網(wǎng)絡(luò)參數(shù)的步驟如下 :a 初始化各組元素 P (B C ij 的信息素值 pher P (B C ij , M 只螞蟻位于蟻巢 。b 蟻群根據(jù)路徑選擇規(guī)則各自選擇元素 。路徑選擇規(guī)則是對(duì)各組 B C i , 每只螞蟻根據(jù)下式隨機(jī)選擇 元素 :P k (B C ij =pher P (B N i j =1pher P (B C ij (5c 重復(fù)步驟 b , 直到全部螞蟻到達(dá)食物源 。d 對(duì)每只螞蟻 , 根據(jù)它所選擇的元素來(lái)計(jì)算能量函數(shù) , 并調(diào)整信息素值 。信息素調(diào)整規(guī)則為每只螞蟻根據(jù)能量函數(shù) E TSP 和式 (6 選擇信息素 。pher P

30、 (B C ij (t +4 = pher P (B C ij (t +inc (B C ij (6其中 :是信息殘留系數(shù) , (1-表示時(shí)刻 t 到 t +4消逝程度 。inc (B C ij =mk 1C ij (7其中 :inc k (B C ij +4P (B C ij 上的信息量 , 8 :inc k (B ij E kTSP 第 k 只螞蟻在時(shí)間 t 和 t +4之間 選擇了參數(shù) P (B ij 0否則(8其中 :Q 是正常數(shù) , 它用于調(diào)節(jié)信息素調(diào)節(jié)速度 。e 重復(fù)步驟 b d , 全部螞蟻收斂到同一路徑 , 或達(dá)到給定的計(jì)算次數(shù) , 則結(jié)束計(jì)算 。 仿真實(shí)驗(yàn)結(jié)果與分析設(shè)空間機(jī)器

31、人在艙外工作時(shí) , 需要訪問(wèn) k 個(gè)空間站 ?？臻g 機(jī)器人出發(fā)的空間站為 S, 空間機(jī)器人最終到回到空間站 S 。 空間機(jī)器人需要訪問(wèn)最短的路徑 , 從而節(jié)省寶貴的燃料 , 延長(zhǎng) 它的在軌壽命 。上述基于 Hopfield 神經(jīng)網(wǎng)絡(luò)的蟻群算法用于 5和 15空間 站問(wèn)題 。 圖 5是 15空間站問(wèn)題的計(jì)算路徑 ; 圖 6是每一代計(jì) 算結(jié)果中最佳輸出結(jié)果 ; 圖 7是結(jié)果的平均輸出結(jié)果 ; 經(jīng) 50次 計(jì)算得到的平均值如表 1所示 。實(shí)驗(yàn)結(jié)果與用標(biāo)準(zhǔn) Hopfield 神經(jīng)網(wǎng)絡(luò)得到的結(jié)果進(jìn)行了比 較 , 5空間站問(wèn)題的 50次實(shí)驗(yàn)中 , 兩種方法都得到了最優(yōu)解 ;15空間站問(wèn)題的 50次計(jì)算中

32、, 本文提出的方法得到 43(86%次最優(yōu)解 , 最優(yōu)解為 348m 。 用傳統(tǒng)方法得到了 35(70% 次有 效解 , 最優(yōu)解為 353m 。從上述數(shù)據(jù)中可以看出 , 基于蟻群算 法的 Hopfield 神經(jīng)網(wǎng)絡(luò)計(jì)算次數(shù)要少于 Hopfield 神經(jīng)網(wǎng)絡(luò) , 陷 入局部極值的幾率要少于 Hopfield 神經(jīng)網(wǎng)絡(luò) , 走過(guò)的路徑長(zhǎng)度 比 Hopfield 神經(jīng)網(wǎng)絡(luò)短 。表 1 仿真結(jié)果算法cities ant sizefeasible best op ti m u m HNN ith ant syste m353348 結(jié)束語(yǔ)本文利用基于蟻群算法的 Hopfield 神經(jīng)網(wǎng)絡(luò)對(duì)解決空間 機(jī)器

33、人多空間站訪問(wèn)問(wèn)題進(jìn)行了討論 , 仿真結(jié)果顯示該算法可 以有效地克服 Hopfield 神經(jīng)網(wǎng)絡(luò)陷入局部極小點(diǎn)的現(xiàn)象 , 有利于實(shí)際應(yīng)用 。 蟻群算法的研究剛剛起步 , 還沒(méi)有形成系統(tǒng)的分 析方法和堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ) , 但仿真結(jié)果顯示了蟻群算法在解決 路徑規(guī)劃等優(yōu)化問(wèn)題方面的良好前景 。 參考文獻(xiàn) :1HWANG Y K, AHUJA N. Potential field app r oach t o path p lanningJ .I EEE Tran s o n Robo ti c s a nd Aut om a ti o n, 1992, 8(1 :23232.2G UPTS K K .

34、 Fast collisi on avoidance formani pulat or ar m s:a sequen 2tial search strategy C /Proc of I EEE I nternati onal Conference on Robotics and Aut omati on . 1990:172421729.3DOR I G O M, MAN I EZZ O V, COLORN IA. Ant syste m:op ti m izati onby a col ony of cooperating agent J .I EEE Tra ns o n S ys t

35、em s,M a n, a nd C ybe rne ti c s, 1996, 26(1 :29241.4ELLAB I B I, CALARMA I P . Exchange strategies f or multi p le ant col o 2ny system J .I nf o r m a ti o n S c i e nce s, 2007, 177(5 :124821264. 5ALBA E, LEG U I Z ARMON G, ORDONEZ G . Parallel ant algorithm sf or the m ini m um tardy task p r oblem C /Proc of Congres o A rgentino de Ciencias de la Computaci on . 2004:183521846.(上接第 50頁(yè) 5S ARWAR B, K ARYP I S G, K ONST AN J. App l