基于逐次適應蟻群優(yōu)化算法的個性化微學習推薦

趙 琴,陳 健,張月琴

(太原理工大學 計算機科學與技術(shù)學院,太原 030024)

0 概述

微學習是一種新的在線學習方式,首次出現(xiàn)于2005年[1]。與其他在線學習方式相比,微學習的最大區(qū)別,在于“微”特性?！拔ⅰ敝攸c體現(xiàn)在微學習中的學習單元相對較小,例如能在5 min～15 min內(nèi)完成視聽的視頻或音頻資料,以及圖片和文字資料,讓用戶可以在相對短暫的碎片時間內(nèi)完成學習。自2008年起,微學習開始受到我國學者的關(guān)注和研究,目前已取得了一定的研究成果[2]。

微學習主要有2個大的研究方向:理論研究和應用研究。在理論研究方向上,目前微學習尚未建立完善的理論體系,研究范圍多基于移動學習或遠程教育對微學習特性的探討[3-4];應用研究多借助其他平臺來搭建微學習環(huán)境[5-8],進而對微學習特性進行相關(guān)研究,或者將一些經(jīng)典算法改進后應用到微學習中[6,9-10]。

隨著信息化時代的到來,知識更新周期急劇縮短,人類已跨入終身學習時代。人們出于工作和生活的需要,必須隨時隨地進行學習。與此同時,現(xiàn)代生活也改變著人們的生活節(jié)奏,上下班路程的延長使人們在公交車上、在地鐵上擁有了更多的碎片時間。因此,研究如何利用這些碎片化時間來完成學習就尤為重要。

由于微學習的學習單元比其他在線學習方式的學習單元更短小精悍,對于同樣的學習內(nèi)容量來說,所需要的學習單元數(shù)量更多,學習單元間的關(guān)系也更為復雜。學習單元按照學習的先后順序排列到一起就構(gòu)成了學習路徑,因此在微學習中,學習路徑的組合就更為靈活復雜。由于存在個體差異,不同學習者適合不同的學習路徑。為學習者推薦適合的個性化學習路徑,可幫助其提高學習效率。

學習路徑推薦算法是實現(xiàn)個性化學習路徑推薦的關(guān)鍵[11]。其中,群智算法在解決學習路徑推薦問題中表現(xiàn)出良好的性能。文獻[12]提出一種學習對象關(guān)聯(lián)關(guān)系構(gòu)建方法,使用擴展的蟻群算法,綜合考慮學習者群體對學習路徑的評價、目標用戶在知識水平和學習風格上的特征,為用戶推薦個性化學習路徑。文獻[13]使用學習內(nèi)容對學習路徑進行構(gòu)建,使用蟻群算法,根據(jù)學習者知識水平、學習風格匹配度和學習效果評價,為學習者推薦最適合的學習路徑[13]。在上述算法中,由于其學習形式的局限,其推薦粒度皆為整條學習路徑。微學習的出現(xiàn)使對學習路徑的調(diào)整可以在更小的粒度上進行交互適應的調(diào)整,學習者對知識內(nèi)容的選擇也更為靈活。如何利用微學習的特性,滿足學習者的個性化需求,為學習者推薦個性化的學習路徑,成為一個新的問題。

基于以上研究,本文利用蟻群算法反饋性,提出一種通過學習者與系統(tǒng)的互動實現(xiàn)的信息素濃度逐次適應調(diào)整的蟻群算法。該算法通過在微學習過程中捕捉學習者的特征和學習狀態(tài)的變化,逐次調(diào)整學習路徑推薦策略,為學習者推薦個性化的學習路徑。

1 相關(guān)技術(shù)及基本概念

1.1 蟻群算法

蟻群算法是一種經(jīng)典的群智算法,具有高度并行性、正反饋性、協(xié)同性等優(yōu)點,在智能搜索和全局優(yōu)化方面體現(xiàn)出良好的性能[14]。在解決路徑問題中,也表現(xiàn)出良好的求解效率和尋優(yōu)效果[15]。

在蟻群算法解決旅行商問題(Travelling Salesman Problem,TSP)的過程中,可以領(lǐng)會到蟻群算法的基本思想。

TSP問題即尋找經(jīng)過N個城市,每個城市只經(jīng)過一次,最后回到起點的最短路徑。使用蟻群算法解決TSP問題的具體流程如下:

1)初始化算法中的各個參數(shù)。

2)判斷螞蟻訪問狀態(tài):若螞蟻一個城市的都未訪問,將螞蟻隨機放置在N個城市之一;否則,根據(jù)式(1)選擇下一個城市。

3)根據(jù)式(2)更新信息素濃度。

4)判斷是否滿足條件(達到最大迭代次數(shù)),記錄當前最優(yōu)解,若未達到,迭代次數(shù)加1,轉(zhuǎn)到步驟2);若已達到,轉(zhuǎn)到步驟5)。

5)輸出最優(yōu)解。

上述流程中涉及到的公式如下:

螞蟻根據(jù)式(1)對下一個城市進行選擇:

(1)

由式(1)可以得知,城市i與城市j之間的距離越近,信息素濃度越高,螞蟻k選擇路徑城市i到城市j的概率就越大。

假設(shè)從時間t到(t+1)有m個螞蟻通過路段i→j,對信息素濃度進行更新:

(2)

1.2 基本概念

本文算法基于基本蟻群算法,結(jié)合微學習的特征,為學習者提供個性化的學習路徑,以下是算法中涉及到的基本概念。

1.2.1 與學習單元相關(guān)的概念

學習單元是知識的主要載體,其中包含豐富的知識。在對學習單元特征的選取上,采用知識領(lǐng)域、知識水平等屬性對其進行描述。

1)學習單元知識領(lǐng)域

學習單元中包含的知識屬于相應的知識領(lǐng)域,知識領(lǐng)域是學習單元最重要的一個屬性。假設(shè)共有n個知識領(lǐng)域,使用向量A={a1,a2,…,an}表示學習單元所屬的知識領(lǐng)域。其中ai∈(0,1),若ai=1,代表學習單元屬于知識領(lǐng)域i;否則,不屬于學習領(lǐng)域i。

2)學習單元知識水平

知識單元中知識的難易水平是學習單元一個重要的屬性,用Ci(Ci∈0,1,2)來表示學習單元在知識領(lǐng)域i的知識水平。若Ci=0,代表學習單元知識水平為初級;若Ci=1,代表學習單元知識水平為中級;若Ci=2,代表學習單元知識水平為高級。

1.2.2 與學習者相關(guān)的概念

學習者是學習的主體,由于知識水平、興趣愛好、學習習慣等因素之間的差異,在學習單元的選擇上具有很大的不同。在對學習者的屬性描述上,本文采用知識領(lǐng)域、知識水平、學習目標、學習狀態(tài)等屬性來對學習者的特征進行描述。

1)學習者知識領(lǐng)域

該屬性用來表示學習者計劃學習的知識領(lǐng)域,使用R={r1,r2,…,rn}表示。其中ri∈(0,1),若ri=1,代表學習者愿意學習了解知識領(lǐng)域i;否則,對該學習領(lǐng)域i不感興趣。

2)學習者知識水平

學習者的知識水平是針對學習者感興趣的知識領(lǐng)域而言的,同一學習者在不同的知識領(lǐng)域內(nèi)學習水平可以不同。使用di(di∈(0,1,2))來表示在知識領(lǐng)域i中的知識水平,若di=0,學習者對于知識領(lǐng)域i中知識的了解幾乎為零;若di=1,學習者對于知識領(lǐng)域i內(nèi)的知識有一定的了解;若di=2,學習者對于知識領(lǐng)域i中的知識有熟悉的了解。

3)學習者學習目標

學習目標是依據(jù)學習者當前進行學習的知識領(lǐng)域?qū)闹R水平設(shè)定的,為不同學習水平的學習者,設(shè)定不同的學習目標。若當前學習目標達到,表明當前學習過程結(jié)束,此時完成一條完整的學習路徑的學習。

4)學習者學習狀態(tài)

學習狀態(tài)是描述學習者對當前學習路徑中的學習單元適應度的一個重要屬性,同時也是后續(xù)學習單元推薦策略選擇的重要依據(jù)。根據(jù)學習者對于當前學習路徑中學習單元的整體掌握情況,將學習狀態(tài)分為3種狀態(tài):初始態(tài),調(diào)整態(tài),變更態(tài)。其描述如下。

1)初始態(tài):學習者首次進行學習或者開始一條新的學習路徑。

2)適應態(tài):當前學習路徑比較適合學習者,根據(jù)已知的表征學習情況的調(diào)整因子對學習單元推薦策略進行調(diào)整。

3)變更態(tài):學習者不適合當前學習路徑,說明前期對于學習者在該學習領(lǐng)域中的知識水平判斷存在一定的誤差或者學習者在學習的過程中知識水平發(fā)生了變化。

1.2.3 學習路徑

學習路徑是學習單元按照學習時間先后順序排列而成的一組序列。按照其形成過程,學習路徑可以分為初始化學習路徑和個性化學習路徑。

初始化學習路徑是學習單元提供者根據(jù)對學習單元知識組成結(jié)構(gòu)的了解,為學習者提供的一條學習路徑。該條學習路徑對于每個學習者都一樣,不具有個性化。而且由于局限性,每條學習路徑中所有學習單元都屬于同一個學習單元提供者。學習單元提供者對于學習單元中的知識很熟悉,初始化學習路徑具有很高的參考價值。

個性化的學習路徑,是在初始化學習路徑的基礎(chǔ)上,根據(jù)學習者在學習過程中自身學習狀態(tài)的變化、學習的歷史記錄,在學習過程中動態(tài)形成的一條學習路徑,其能夠滿足學習者個性化的學習需求。

2 信息素逐次適應調(diào)整的蟻群算法

本文提出一種對信息素濃度進行逐次適應調(diào)整的蟻群算法,并以此對微學習中的學習者推薦學習路徑。利用蟻群算法的反饋性和自學習性,通過互動監(jiān)測學習者的學習狀態(tài),逐次調(diào)整學習路徑推薦策略,為學習者推薦個性化學習路徑。

本文提出的適應逐次調(diào)整蟻群算法將微學習特性與蟻群算法結(jié)合,為學習者推薦個性化學習路徑。算法步驟如下。

算法信息素逐次適應調(diào)整算法

輸入學習單元基本信息數(shù)據(jù),學習者基本信息數(shù)據(jù)

輸出推薦學習單元編號

1.init:啟發(fā)信息因子α,信息素濃度因子β,信息素揮發(fā)濃度ρ,初始化信息素濃度τij;

2.set:學習者學習領(lǐng)域i,學習者知識水平d,學習狀態(tài)信息t;

3.switch(t)

case 1:t=初始態(tài),推薦策略1(式(7));

case 2:t=適應態(tài),推薦策略2(式(8));

case 3:t=變更態(tài),推薦策略3(式(9));

4.output:學習單元編號;

5.update:局部信息素濃度(式(4));

6.update學習狀態(tài) t;

7.if (達成學習目標)

update全局信息濃度(式(5));

else goto 3

結(jié)束處理

本文算法的系統(tǒng)結(jié)構(gòu)如圖1所示,主要由用戶信息更新模塊、信息素濃度更新模塊、參考學習組抽出模塊、推薦模塊等4個模塊組成。

圖1 逐次適應微學習路徑推薦的系統(tǒng)結(jié)構(gòu)

2.1 用戶信息更新模塊

該模塊完成的工作主要有:1)對首次進行學習的學習者,將其學習狀態(tài)設(shè)立為初始態(tài),同時還需要確定其知識領(lǐng)域和知識水平;2)根據(jù)當前學習情況更新學習者的學習狀態(tài)。學習狀態(tài)是本文算法的核心部分,主要通過測驗成績來判斷當前學習者的學習狀態(tài);3)根據(jù)學習者的基本信息及學習記錄,判斷學習者是否達成學習目標。

圖2 學習者知識水平判定流程

對于已經(jīng)學習過數(shù)次的學習者,本模塊的主要任務(wù)是根據(jù)其用戶信息以及學習記錄判斷其是否達成學習目標。如果學習目標已經(jīng)達成,結(jié)束當前學習路徑,將整條學習路徑記錄放入學習路徑集合中,存入用戶信息庫中。該數(shù)據(jù)將被信息素濃度更新模塊用于對學習路徑上的信息素濃度進行全局更新,同時用戶信息更新模塊則將當前學習者的學習狀態(tài)更新為初始態(tài)。如果學習目標未達成,用戶信息更新模塊將根據(jù)學習者的用戶信息以及學習記錄來判斷當前學習狀態(tài)。

(3)

根據(jù)學習者的用戶信息以及學習記錄可判斷學習者是否達成學習目標。學習者的學習目標是否達成是根據(jù)學習者的學習狀態(tài)進行判定的。若學習者連續(xù)Θ次學習狀態(tài)為適應態(tài),則可以認為學習目標已經(jīng)達成,其中Θ的數(shù)值取決于其該條學習路徑參照學習路徑中的學習單元個數(shù)。

2.2 信息素濃度更新模塊

本模塊主要負責對信息素濃度進行局部和全局更新。學習者完成當前學習單元的學習后,根據(jù)學習單元包含的知識組成,為學習者提供對應的測試題。根據(jù)測試成績和學習者掌握該學習單元的情況,進行信息素局部更新。

信息素濃度是蟻群算法中進行反饋性調(diào)節(jié)的重要因素,也是蟻群算法中最重要的一個屬性。路徑上的信息素濃度越高,選擇該條路徑的概率就越大;反之,越小。測試成績作為表征學習者在學習路徑上學習情況的重要特性,在本文算法中用來對信息素濃度進行局部更新。

(4)

其中,τij(t)代表t時刻學習單元Li到學習單元Lj上的信息素濃度,τij(t+1)代表t+1時刻學習單元Li到學習單元Lj上的信息素濃度,ρ代表信息素的揮發(fā)系數(shù)。

學習者完成某條學習路徑的學習后,根據(jù)學習者的測試結(jié)果對該條路徑上的信息素進行全局更新。當某個學習者Sk完成學習路徑J的學習后,信息素濃度按照式(5)進行全局更新。

τij(t+1)=

(5)

其中,τij(t)代表t時刻學習單元Li到學習單元Lj上的信息素濃度,τij(t+1)代表t+1時刻學習單元Li到學習單元Lj上的信息素濃度,ρ代表信息素的揮發(fā)系數(shù)。

2.3 參考學習組的抽出模塊

學習者的參考學習組由學習者之間的相似度確定。其中,學習相似度由以下2個方面決定:學習者的基本信息和學習記錄。表征學習者Sk和St之間相似度的相關(guān)系數(shù)Fkt由式(6)確定。

(6)

根據(jù)上述公式,相似度較高的學習者將選取作為目標學習者的參考學習組,為學習狀態(tài)為初始態(tài)的學習者提供主要的推薦依據(jù),用于確定學習路徑中的第1個學習單元。同時,參考學習組的學習記錄將用于調(diào)整目標學習者學習路徑中的局部信息素濃度,幫助目標學習者提高和改善學習效率。

2.4 推薦模塊

本模塊是系統(tǒng)的核心部分,根據(jù)學習者的學習狀態(tài),調(diào)整學習單元的推薦策略和學習路徑,其調(diào)整策略描述如下。

1)初始態(tài)

如果學習者So當前學習狀態(tài)為初始態(tài),由目標學習者的參考學習組信息,根據(jù)式(7)為學習者推薦學習單元。

(7)

其中,poi代表學習單元Li與學習者So的相似度,Sr屬于學習者So的參考學習組,λor代表學習者So與學習者Sr的相似度,θri代表學習者Sr與學習單元Li的相似度,學習者Sr為學習過學習單元Li的學習者。若學習單元Li與學習者So相似度poi最大,則為學習者So推薦學習單元Li。

2)適應態(tài)

如果學習者So當前學習狀態(tài)為適應態(tài),調(diào)整因子為ε,前一個學習單元為Li,根據(jù)式(8)為學習者推薦學習單元。

(8)

3)變更態(tài)

如果學習者So當前學習狀態(tài)為變更態(tài),前一個學習單元為Li,根據(jù)式(9)為學習者推薦學習單元。

(9)

3 實驗設(shè)計與結(jié)果分析

為進一步驗證本文提出的算法可以在微學習環(huán)境中為學習者提供個性化的學習路徑,提高學習效率,設(shè)計實驗對算法進行驗證。

3.1 實驗設(shè)計

3.1.1 學習單元和學習者的確定

為滿足微學習對于學習單元時間長度的要求,從網(wǎng)上下載篩選符合要求的學習資源,保證每個學習單元都可以在15 min內(nèi)學習完成。同時選取學習單元數(shù)量適中的初始化學習路徑,每個課程中包含的學習單元數(shù)量為8個～12個。

經(jīng)過篩選整理,共得到167個計算機應用技術(shù)相關(guān)的學習課程,包含1 685個學習單元,將其劃分為4個學習領(lǐng)域:前端開發(fā),后端開發(fā),移動開發(fā)和數(shù)據(jù)處理。根據(jù)學習課程的知識內(nèi)容難度,標記其知識水平。整理完成后,得到知識領(lǐng)域和知識水平標記完成的167條初始化學習路徑,其基本信息分布如表1所示。

表1 學習單元基本信息

在學習者選取上,共選用80名學習者用于實驗。為驗證改進蟻群算法可以切實提高學習者的學習效率,將80名學習者分為2組,一組為實驗組,另一組為對比組,每組為40名學習者。2組學習者40人同時參與,每人學習若干學習單元。為提高實驗結(jié)果的可信度與準確性,對80名學習者的基本信息進行前期調(diào)查統(tǒng)計,確保2組學習者在初始階段,知識領(lǐng)域和對應的知識水平分布情況差異性較小。學習者初始基本信息分布情況如表2所示。

表2 學習者基本信息

3.1.2 算法參數(shù)的確定

蟻群算法參數(shù)值的選取對于實驗結(jié)果有非常重要的影響。采用改進蟻群算法來實現(xiàn)微學習中的學習路徑推薦,如何設(shè)置各個參數(shù)值,確定合理的學習單元以及學習者數(shù)量,以更好地實現(xiàn)學習路徑推薦是首先要進行的工作。

在Matlab環(huán)境下,使用程序模擬學習者的學習過程,研究啟發(fā)信息因子、信息素濃度因子、信息素濃度揮發(fā)因子、迭代次數(shù)、學習單元數(shù)量以及學習者數(shù)量等參數(shù)對于結(jié)果的影響。通過多次實驗,分析研究信息素濃度分布變化過程,綜合考慮算法的時間復雜度,最終確定了算法的基本參數(shù)。其中,啟發(fā)信息因子α取值為1.4,信息素濃度的因子β的取值為1.1,信息素揮發(fā)濃度ρ取值為0.7,迭代次數(shù)取值為150。

3.1.3 對比實驗

準備工作完成后,使用JSP+MySQL創(chuàng)建微學習環(huán)境。實驗分為2個組:實驗組和對比組。對比組中的學習者按照初始化路徑學習,實驗組的學習者按照改進蟻群算法推薦的學習路徑學習,最終比較測試成績。

3.2 實驗結(jié)果分析

通過實驗,得到了2組學習者的測試成績。圖3顯示了實驗組和對比組分別在前端開發(fā)、后端開發(fā)、移動開發(fā)、數(shù)據(jù)處理4個學習領(lǐng)域,平均測試成績隨著學習單元數(shù)量增加的變化情況。其中,A01、B01分別代表實驗組和對比組在前端開發(fā)領(lǐng)域,A02、B02分別代表實驗組和對比組在后端開發(fā)領(lǐng)域,A03、B03分別代表實驗組和對比組在移動開發(fā)領(lǐng)域,A04、B04分別代表實驗組和對比組在數(shù)據(jù)處理領(lǐng)域。

圖3 學習單元個數(shù)與平均測試成績的關(guān)系

由實驗結(jié)果可以得出,實驗組的學習者在學習相同數(shù)量的學習單元后,得到的平均測試成績明顯較高,由此可以推斷本文提出的算法可以提高學習者在微學習環(huán)境下的學習效率。

由圖3可以推出:學習者的測試成績普遍得到了提高,平均測試成績隨學習單元數(shù)目呈線性增長;在學習初期,實驗組和對比組成績增長幅度相差不大;在學習中期,實驗組的學習者的測試成績增幅明顯優(yōu)于對比組;在學習后期,對比組仍保持一定的增幅,實驗組平均測試成績增幅較之前明顯放緩。

對于實驗結(jié)果分析如下:

1)在學習初期,實驗組中學習路徑的信息素濃度較低,選擇多數(shù)取決于學習單元的屬性,實驗組與對比組的相差較小;在學習中后期,信息素逐漸累積,實驗組中的優(yōu)勢逐漸顯示出來。

2)實驗組測試成績增幅在后期明顯放緩,經(jīng)過對信息素濃度的分析,推測此時算法可能陷入局部最優(yōu)。

3)在圖3中,縱坐標代表的是平均測試成績,表示測試成績的總體趨勢。對學習者測試成績分布情況進行分析,發(fā)現(xiàn)部分處于變更態(tài)學習者的測試成績特別高或者測試成績特別低,其對于平均測試成績有所影響,但是對測試成績總體的趨勢影響并不大。

4 結(jié)束語

本文提出了一種基于信息素濃度逐次適應調(diào)整的蟻群算法,用于實現(xiàn)微學習中的個性化學習路徑推薦。實驗結(jié)果表明,該算法可以優(yōu)化微學習路徑,有效提高學習效率。但該算法仍需進一步提高和改進。今后的工作將考慮將蟻群算法中參數(shù)自適應理論引入該算法中來改善局部最優(yōu)問題。對于蟻群算法應用領(lǐng)域的參數(shù)設(shè)置,目前尚無成熟的理論。對于本文所涉及到的參數(shù)設(shè)置,下一步考慮使用組合優(yōu)化算法進行參數(shù)選擇;對于本文算法的時間復雜度和空間復雜度的討論需要完善,目前蟻群算法此方面的相關(guān)研究較少,需要進一步研究分析。

[1] HUG T,LINDNER M,BRUCK P A.Microlearning:Emerging Concepts,Practices and Technologies After e-Learning[J].Proceedings of Microlearning,2005(5):45-53.

[2] 張振虹,楊慶英,韓 智.微學習研究:現(xiàn)狀與未來[J].中國電化教育,2013(11):12-20.

[3] 王佑鎂,祝智庭.從聯(lián)結(jié)主義到聯(lián)通主義,學習理論的新取向[J].中國電化教育,2006(3):5-8.

[4] BAUMGARTNER P.Educational Dimensions of Micro-learning-towards a Taxonomy for Microlearning[M].Innsbruck,Austria:Innsbruck University Press,2013.

[5] KOVACHEV D,CAO Y,KLAMMA R,et al.Learn-as-You-Go:New Ways of Cloud-based Micro-learning for the Mobile Web[C]//Proceedings of International Con-ference on Web-based Learning.Berlin,Germany:Springer,2011:51-61.

[6] BRUCK P A,MOTIWALLA L,FOERSTER F.Mobile Learn-ing with Micro-content:A Framework and Evaluation[C]//Proceedings of the 25th Bled Conference.Berlin,Germany:Springer,2012:17-20.

[7] GU X,GU F,LAFFEY J M.Designing a Mobile System for Lifelong Learning on the Move[J].Journal of Computer Assisted Learning,2011,27(3):204-215.

[8] 陶璐琳.基于智能手機的微學習設(shè)計研究[D].武漢:華中師范大學,2012.

[9] 史致遠,朱明放.微學習環(huán)境下基于語義的MASHUP架構(gòu)優(yōu)化[J].江蘇大學學報(自然科學版),2010,31(3):339-342.

[10] CHEN Jian,ZHANG Yueqin,SUN Jingyu,et al.Personalized Micro-learning Support Based on Process Mining[C]//Proceedings of International Conference on Information Technology in Medicine & Education.Washington D.C.,USA:IEEE Press,2016:511-515.

[11] 趙呈領(lǐng),陳智慧,黃志芳.適應性學習路徑推薦算法及應用研究[J].中國電化教育,2015(8):85-91.

[12] CHEN Chih-Ming.Intelligent Web-based Learning System with Personalized Learning Path Guidance[J].Computers and Education,2008,51(2):787-814.

[13] 張 松.學習內(nèi)容管理系統(tǒng)及其個性化推薦技術(shù)研究與實現(xiàn)[D].沈陽:東北大學,2013.

[14] 費 騰,張立毅,孫云山.基于DNA-蟻群算法的車輛路徑優(yōu)化問題求解[J].計算機工程,2014,40(12):205-208.

[15] 張 瀟,王江晴.混合蟻群算法在車輛路徑問題中的應用[J].計算機工程,2011,37(24):190-192.