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

趙 琴,陳 健,張月琴

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

0 概述

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

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

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

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

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

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

1 相關技術及基本概念

1.1 蟻群算法

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

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

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

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

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

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

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

5)輸出最優解。

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

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

(1)

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

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

(2)

1.2 基本概念

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

1.2.1 與學習單元相關的概念

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

1)學習單元知識領域

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

2)學習單元知識水平

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

1.2.2 與學習者相關的概念

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

1)學習者知識領域

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

2)學習者知識水平

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

3)學習者學習目標

學習目標是依據學習者當前進行學習的知識領域對應的知識水平設定的,為不同學習水平的學習者,設定不同的學習目標。若當前學習目標達到,表明當前學習過程結束,此時完成一條完整的學習路徑的學習。

4)學習者學習狀態

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

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

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

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

1.2.3 學習路徑

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

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

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

2 信息素逐次適應調整的蟻群算法

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

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

算法信息素逐次適應調整算法

輸入學習單元基本信息數據,學習者基本信息數據

輸出推薦學習單元編號

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

2.set:學習者學習領域i,學習者知識水平d,學習狀態信息t;

3.switch(t)

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

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

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

4.output:學習單元編號;

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

6.update學習狀態 t;

7.if (達成學習目標)

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

else goto 3

結束處理

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

圖1 逐次適應微學習路徑推薦的系統結構

2.1 用戶信息更新模塊

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

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

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

(3)

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

2.2 信息素濃度更新模塊

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

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

(4)

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

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

τij(t+1)=

(5)

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

2.3 參考學習組的抽出模塊

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

(6)

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

2.4 推薦模塊

本模塊是系統的核心部分,根據學習者的學習狀態,調整學習單元的推薦策略和學習路徑,其調整策略描述如下。

1)初始態

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

(7)

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

2)適應態

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

(8)

3)變更態

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

(9)

3 實驗設計與結果分析

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

3.1 實驗設計

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

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

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

表1 學習單元基本信息

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

表2 學習者基本信息

3.1.2 算法參數的確定

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

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

3.1.3 對比實驗

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

3.2 實驗結果分析

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

圖3 學習單元個數與平均測試成績的關系

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

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

對于實驗結果分析如下:

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

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

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

4 結束語

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

[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] 張振虹,楊慶英,韓 智.微學習研究:現狀與未來[J].中國電化教育,2013(11):12-20.

[3] 王佑鎂,祝智庭.從聯結主義到聯通主義,學習理論的新取向[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] 陶璐琳.基于智能手機的微學習設計研究[D].武漢:華中師范大學,2012.

[9] 史致遠,朱明放.微學習環境下基于語義的MASHUP架構優化[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] 趙呈領,陳智慧,黃志芳.適應性學習路徑推薦算法及應用研究[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] 張 松.學習內容管理系統及其個性化推薦技術研究與實現[D].沈陽:東北大學,2013.

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

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