基于多目標優(yōu)化粒子群優(yōu)化算法的高校圖書推薦模型研究

白曉燕

(榆林學院, 陜西 榆林 719000)

0 引言

目前，高校圖書館大部分只有借書的功能，并沒有充分地利用圖書借書數(shù)據(jù)來挖掘潛在的信息.高校圖書館擁有大量的書籍，基本是按照學科來分類，學生尋找圖書基本是單一的檢索模式.因此，學生有時候很難知道自己需要什么樣的書籍，這樣一來，就會導致只有很少一部分圖書被借閱，而造成大量圖書處于空閑狀態(tài).

在大數(shù)據(jù)技術和數(shù)據(jù)挖掘技術飛速發(fā)展的今天，已經(jīng)可以挖掘出圖書與圖書、圖書和借閱者之間的關系，挖掘出學生的學習興趣，挖掘出哪些同學之間有相同的借閱圖書內(nèi)容.這樣一來，圖書館就不僅是被動地讓學生來查找書籍，而是主動地給學生推送一些書籍；還可以建立基于圖書借閱信息的學習群體，構(gòu)建大學生學習生態(tài)網(wǎng)絡，學生可以知道相同學習圈里其他同學在看什么樣的書籍.這種類型的高校圖書館，不僅具有提供借閱書籍的功能，更是可以主動地給大學生推薦其有可能感興趣的書籍，從而解決了高校圖書館個性化推薦水平不高、圖書利用率不均衡等一系列不利的問題.

學習群體[1-2]是協(xié)作學習的核心組成部分.本文針對大學生借閱圖書事件，構(gòu)建多目標優(yōu)化視角下大學生學習群體形成模型；然后，將大學生圖書借閱事件問題抽象為粒子群多目標優(yōu)化問題，分析了大學生借書事件的關聯(lián)度與親密度，并采用改進的多目標離散的粒子群優(yōu)化算法[3-4]，對大學生借書事件網(wǎng)絡進行優(yōu)化，從而得到多目標優(yōu)化[5]視角下的大學生學習群體社區(qū)，即可以有效地、有目的地把相關書籍推薦給相應學生的社區(qū).

1 粒子群優(yōu)化算法

粒子群優(yōu)化算法[6]是群智能算法的一種，其來源于對群居動物覓食和躲避捕食者的群體智能行為的人工建模與仿真[7].粒子群優(yōu)化算法具有快速有效性、參數(shù)少、精度高、容易實現(xiàn)等優(yōu)點，在單任務領域得到廣泛應用.PSO算法[8]作為一種基于群智能體的優(yōu)化算法，個體之間的協(xié)作[9]能涌現(xiàn)出智能行為.

粒子群算法是微粒群優(yōu)化算法，通過微粒子在粒子空間中搜索解來優(yōu)化一個問題，每個微粒子有兩個屬性：位置和速度，每個粒子通過記得自己最優(yōu)解和知道整個種群的最優(yōu)解來調(diào)整自己的速度和位置來到達全局最優(yōu).

假設一個種群有n個粒子，粒子的搜索空間的維數(shù)為d，令Vi={vi1,vi2,…,vid}表示第i個粒子的速度向量，令Xi={xi1,xi2,…,xid}表示第i個粒子的位置向量，則粒子更新自身狀態(tài)的規(guī)則可以表示為：

(1)

(2)

式(1)中：Pi={pi1,pi2,…,pid}和G={g1,g2,…,gd}，分別表示第i個粒子在飛行過程中的歷史最優(yōu)解和整個種群的最優(yōu)解；c1和c2分別為粒子加速系數(shù)[10]和社會系數(shù)[11]；r1和r2是0到1之間的隨機數(shù).

粒子群優(yōu)化算法是一個不斷重復的迭代計算算法，每個粒子根據(jù)公式(1)和公式(2)來不斷地調(diào)整本身粒子飛行軌跡，從而得到整個粒子空間中最優(yōu)的粒子，然后進行不斷地逼近.

2 基于粒子群優(yōu)化的借書網(wǎng)絡社區(qū)建立

2.1 算法框架

本文提出的離散粒子群優(yōu)化算法[11]通過重新定義粒子群算法操作算子，計算能量函數(shù)的最小值等來更新粒子的位置和速度[12-13].本文所提出算法的工作流程圖如圖1所示.

圖1 本文算法工作流程圖

2.2 粒子適應度函數(shù)

適應度函數(shù)用來評價粒子的優(yōu)秀程度，對于社交網(wǎng)絡的問題而言，適應度函數(shù)用來評價粒子的收斂程度是否合理，收斂速度怎么樣，文獻[14]提出了一種度量網(wǎng)絡平衡程度的能量函數(shù)H(s)，其定義如下：

H(s)=∑i,j(1-aijsisj)/2

(3)

式(3)中：aij∈{±1}是網(wǎng)絡鄰接矩陣的元素，si和sj分別表示節(jié)點i和節(jié)點j的符號.若節(jié)點i和節(jié)點j屬于同一個社區(qū)，則si·sj=1，若節(jié)點i和節(jié)點j屬于不在同一個社區(qū)，si·sj=-1.

該適應度函數(shù)[15]是根據(jù)網(wǎng)絡平衡結(jié)果來衡量其對應的能量函數(shù)，函數(shù)值越小代表網(wǎng)絡越接近于平衡.本文利用粒子群優(yōu)化算法來最小化該函數(shù)，從而很快地找到對應的網(wǎng)絡社區(qū)結(jié)構(gòu)，繼而找到對應的圖.

2.3 粒子的表示

本文基于字符串的編碼和解碼[16]對網(wǎng)絡進行編解碼，編解碼是優(yōu)化問題和優(yōu)化算法之間的橋梁.本文采用基于字符串的編碼，這種編碼操作簡單可靠，對后期的解碼有利，具體采用的粒子編碼如圖2所示.

圖2 粒子的表示示意圖

由圖2可知，粒子的位置采用整數(shù)序列來表示，序列中的每個數(shù)字代表粒子的對應位置，其對應的數(shù)字代表粒子分類的社區(qū)標號，進行解碼的時候，具有相同社區(qū)類標號的整數(shù)節(jié)點會被劃分到同一個社區(qū)里面.從而，采用整數(shù)進行編碼可以自動地預測網(wǎng)絡需要劃分為幾個社區(qū).

采用整數(shù)編碼的方法，在解碼的時候，如果節(jié)點i和節(jié)點j在同一個社區(qū)，則si·sj=1，如果節(jié)點i和節(jié)點j不在同一個社區(qū)，則si·sj=-1.

2.4 粒子的狀態(tài)更新規(guī)則

本文算法中粒子的位置采用整數(shù)來進行編碼，因此傳統(tǒng)的粒子狀態(tài)更新方程已經(jīng)不再適用本文問題的求解.為了更好地得到社區(qū)結(jié)構(gòu)，本文重新定義了粒子的狀態(tài)更新方程：

(4)

(5)

式(4)中：ω是慣性權(quán)值常數(shù)，符號⊕表示異或操作.

函數(shù)ζ(x)是一個二維向量函數(shù)，其目的是將變量x變?yōu)殡x散的二進制形式，便于其與位置向量進行公式(4)的操作.函數(shù)ζ(x)具體定義如下:

(6)

公式(5)中的?操作是粒子狀態(tài)更新的核心操作，該操作設置的好壞會直接影響算法挖掘社區(qū)的性能，還會影響算法的收斂程度.

對于一個圖書網(wǎng)絡而言，兩個節(jié)點之間的連接概率采用如下方法，本文定義的?操作如下:

(7)

式(7)中：rand(xit)表示的是從xit對應的節(jié)點的鄰居節(jié)點中隨機選取一個節(jié)點的社區(qū)標號.

2.5 算法過程

算法過程如下所示：

步驟1首先初始化種群W，設種群W中粒子數(shù)為N；

步驟2計算粒子I在不同任務上的適應值；

步驟3計算粒子的i的最優(yōu)因子ti,i屬于W；

步驟4對當前種群W引入擾動因子φ,產(chǎn)生新的個體形成新的種群W1;

步驟5將W1中的新個體用于求解特定的任務；

步驟6將原始種群W和新的種群合并形成一個新的臨時種群W2W2(W2=W∪W1)

步驟7更新W2中的最優(yōu)因子ti；

步驟8從當前臨時種群W2中挑選出適應值最優(yōu)的N個粒子形成新的種群W3；

步驟9對每個任務的當前值解實行局部搜索，以逼近全局最優(yōu).

步驟10循環(huán)步驟3～步驟9，直到滿足循環(huán)條件；

步驟11輸出所有的任務的全局最優(yōu)解.

3 實驗測試與分析

3.1 實驗設置

為了測試本算法的性能，將采用真實的圖書借閱書籍進行實驗測試.首先將本文算法命名為PSOSB，本文算法用到的參數(shù)做如下設置：慣性系數(shù)ω設置為0.718，本算法的加速系數(shù)c1和c2設置為1.510，粒子群的種群大小N設置為200，算法的循環(huán)迭代次數(shù)M設置為200.本文采用的算法對比文獻[17]提出算法MemeSB，該算法的交叉概率和變異概率分別設置為0.8和0.2，其種群規(guī)模N設為200,算法的迭代次數(shù)設置為300.

實驗中用到的數(shù)據(jù)為榆林學院圖書館四組不同的圖書借閱事件，該網(wǎng)絡由不同的節(jié)點組成，分別采用改進的粒子群優(yōu)化算法進行測試.高校圖書館借閱事件分別用(YLTSG1)、(YLTSG2)、(YLTSG3)、(YLTSG4)來表示.本文通過四組(YLTSG1)、(YLTSG2)、(YLTSG3)、(YLTSG4)圖書借閱真實數(shù)據(jù)進行測試，該四組圖書借閱事件網(wǎng)絡的屬性見表1所示.

表1 圖書借閱事件數(shù)據(jù)統(tǒng)計表

3.2 模擬數(shù)據(jù)測試

對本文算法運行30次，實驗中發(fā)現(xiàn)，在對YLTSG事件1和YLTSG事件2網(wǎng)絡進行測試時，可以得到不同的四個圖書事件社區(qū).

PSOSB算法和MemeSB算法30次獨立運行得到的能量函數(shù)H(s)的值均為0，說明兩種算法均找到了網(wǎng)絡的平衡結(jié)構(gòu).圖3和圖4分別展示了YLTSG事件1和YLTSG事件2的網(wǎng)絡結(jié)構(gòu)圖.從圖3和圖4可以看出，YLTSG事件1和YLTSG事件2網(wǎng)絡都被分成了三個社區(qū)，且每個社區(qū)內(nèi)部的節(jié)點都是正邊連接的，社區(qū)之間的節(jié)點均為負邊連接，可以得到哪些同學在讀相似的圖書，得到大學生學習群體社區(qū)[18].

圖3 YLTSG事件1結(jié)構(gòu)圖

圖4 YLTSG事件2結(jié)構(gòu)圖

3.3 模擬數(shù)據(jù)測試(Real data test)

在對真實網(wǎng)絡YLTSG3，YLTSG4進行測試時，PSOSB和MemeSB同樣獨立運行30次.表2記錄了實驗統(tǒng)計結(jié)果.

在網(wǎng)絡YLTSG事件3和YLTSG事件4上，兩個算法都得到了相同的結(jié)果，PSOSB和MemeSB均得到了最小的能量函數(shù)值，但PSOSB算法的計算速度要比MemeSB算法快0.8 s.

圖5和圖6分別展示了圖書借閱事件的真實社區(qū)結(jié)構(gòu)圖以及PSOSB算法得到的具有最小能量函數(shù)[19]的網(wǎng)絡拓撲結(jié)構(gòu)經(jīng)過改變非平衡邊得到的網(wǎng)絡的平衡結(jié)構(gòu)圖.通過圖5和圖6對比可以看出，為了實現(xiàn)網(wǎng)絡的結(jié)構(gòu)平衡[20]，節(jié)點SNS與DS和ZS-ESS之間的負邊變成了正邊，從而讓曾經(jīng)讀過和該書有相似的借閱事件大學生加入該社區(qū).

圖5 YLTSG圖書借閱事件3的真實社區(qū)結(jié)構(gòu)圖

圖6 YLTSG圖書借閱事件3的真實社區(qū)結(jié)構(gòu)變換非平衡邊得到的平衡結(jié)構(gòu)圖

在YLTSG圖書借閱事件1上，從表2可以看出，PSOSB比MemeSB得到了更小的H(s)的值，且PSOSB算法的計算速度仍然要比MemeSB算法快.圖7和圖8展示了YLTSG3網(wǎng)絡的真實社區(qū)劃分以及網(wǎng)絡通過改變非平衡的邊所得到的平衡結(jié)構(gòu).從圖7和圖8的對比可以看出，YLTSG圖書借閱事件3的四條正邊被變成了負邊，可以把不相關的借閱事件剔除出該社區(qū).

表2 真實網(wǎng)絡數(shù)據(jù)30次獨立測試結(jié)果統(tǒng)計表

圖7 事件4網(wǎng)絡真實社區(qū)結(jié)構(gòu)

圖8 事件4網(wǎng)絡變換非平衡邊得到的平衡結(jié)構(gòu)圖

在YLTSG事件3和YLTSG事件4上，本文提出的算法和對比算法的實驗結(jié)果一樣，這是因為這兩個網(wǎng)絡的規(guī)模太小，兩種算法均很容易找到問題的最優(yōu)解.雖然在YLTSG事件3和YLTSG事件4上，兩種算法得到了相同的實驗結(jié)果，但是本文算法比對比算法具有更快的收斂速度，本文算法的運行時間比對比算法要快兩個數(shù)量級.從表2所示的統(tǒng)計結(jié)果來看，本文提出的PSOSB算法在YLTSG事件3和YLTSG事件4網(wǎng)絡上的實驗性能要明顯優(yōu)于MemeSB算法，PSOSB不僅能夠得到比MemeSB算法更小的能量函數(shù)值，而且PSOSB算法的運行收斂時間明顯要快于對比算法MemeSB.

實驗中還發(fā)現(xiàn)，PSOSB算法比MemeSB算法具有更快的收斂速度.圖9和圖10分別展示了在YLTSG事件3網(wǎng)絡和YLTSG事件4網(wǎng)絡上兩種算法在迭代100次時，算法單次運行得到的收斂曲線.從收斂實驗的對比結(jié)果可以看出，PSOSB算法基本上在迭代40次的時候就已經(jīng)收斂，而MemeSB算法需要迭代大約80次才能達到收斂.

圖9 算法在YLTSG事件3網(wǎng)絡上的收斂情況對比

圖10 算法在YLTSG事件4網(wǎng)絡上的收斂情況對比

從圖9和圖10可以看出，本文提出的基于離散的粒子群優(yōu)化算法可以很快地向最優(yōu)方向逼近，另外，本文算法在結(jié)構(gòu)設計上充分考慮到圖書網(wǎng)絡本身的特點，在經(jīng)典的粒子群算法的基礎上，重新設計了粒子的狀態(tài)更新方程，該方程可以增加粒子的全局尋優(yōu)速度.對比MemeticSB算法，本文算法增加了擾動粒子，防止算法進入局部最優(yōu)，而MemeticSB算法采用貪婪算法容易使算法陷入局部最優(yōu)，而且貪婪算法的計算代價特別高.

由于本文算法和MemeSB算法都是隨機搜索算法，算法的運行受到很多實際參數(shù)的影響，而且算法在每次運行時結(jié)果都不一樣，因此探討算法的穩(wěn)定性是很有必要的.圖11是PSOSB算法和MemeSB算法在YLTSG事件3網(wǎng)絡數(shù)據(jù)、YLTSG事件4網(wǎng)絡數(shù)據(jù)上獨立運行200次得到的統(tǒng)計結(jié)果的箱圖展示.

圖11 在YLTSG事件3和YLTSG事件4上的算法穩(wěn)定性對比實驗

箱圖能夠反應算法的穩(wěn)定性情況，其長短反應的是算法的穩(wěn)定性.箱圖長度越長代表算法不穩(wěn)定，箱圖長度越短代表算法越穩(wěn)定.從圖11可看出，本文算法經(jīng)過200次的迭代運行，得到的箱圖長度比MemeSB的要短，同時說明本文算法相對于MemeSB算法在穩(wěn)定性方面更優(yōu)秀.從箱圖的數(shù)據(jù)分布情況可以看出，在不同大學生借閱圖書事件上本文算法優(yōu)化得到的最小的能量函數(shù)的函數(shù)值要比MemeSB算法的更小，從而證明了本文所提算法的有效性.

4 結(jié)論

本文以大學生圖書借閱事件為研究對象，建立了大學生圖書借閱事件網(wǎng)絡結(jié)構(gòu)圖.然后，以圖論知識為基礎，對大學生借閱圖書事件網(wǎng)絡結(jié)構(gòu)進行了深入研究，提出了一種基于粒子群優(yōu)化的求解大學生學習群體問題的方法.該方法不僅可以實現(xiàn)大學生學習群體網(wǎng)絡結(jié)構(gòu)圖，還可以挖掘網(wǎng)絡中隱藏的社團結(jié)構(gòu).

本文把大學生借閱事件看做粒子，粒子通過調(diào)整種群中解的表示方法、位置和速度的更新規(guī)則以及局部搜索策略，設計出離散粒子群算法，從而得到具有相同大學生借書事件網(wǎng)絡社區(qū).最后，將本文算法在真實的大學生借閱圖書事件上進行測試，較好地得到了大學生具有相同借閱事件的網(wǎng)絡結(jié)構(gòu)圖，從而發(fā)現(xiàn)大學生學習群體，驗證了該算法的有效性，并可以有針對性地把相關書籍推薦給大學生.根據(jù)真實實驗測試，本文推薦算法的準確率提高了11%，覆蓋率提升了13%，這對高校建立大學生學習社團具有很好的指導意義.