基于蟻群-粒子群混合算法的學習路徑推薦策略研究

東苗

摘 要：針對目前學習路徑推薦方法存在學習路徑匹配度不高的問題，建立學習者和學習對象模型，綜合考慮學習者的認知水平、學習風格與學習對象的難度、類型、目標知識點關聯度的匹配情況等因素，使用粒子群算法搜索到次優路徑后，再使用蟻群算法搜索最短路徑，有效解決了單一的蟻群算法初期搜索方向盲目性的缺點。仿真結果表明，算法的求解速度和尋優性能得到了有效提高。

關鍵詞：蟻群算法;粒子群算法;學習路徑

中圖分類號：TP 18

文獻標志碼：A

文章編號：1007-757X（2020）11-0130-03

Abstract：The current method of learning path recommendationhas the problem that the learning path matching degree is not high enough. In this paper， alearner and the learning object model isestablished. The model deals with the factors like the cognitive level and the learning style of the learner， the difficulty and resource typeof the learning object， and the relevance degree of the target knowledge point，etc. After that， the particle swarm optimization algorithm is used to search for the suboptimal path， and then the ant colony algorithm is used to search for the shortest path. These techniqueseffectively solve the shortcoming of the blindness of the initial search direction of the single ant colony algorithm. The simulation results show that the convergence speed and optimization performance of the algorithm are effectively improved.

Key words：ant colony algorithm;particle swarm optimization algorithm;learning path

0?引言

在開展學習活動時，由于學習者學習風格的不同以及認知能力的差異，對學習對象的學習次序和內容組織方式也不盡相同。因此，利用人工智能技術提供個性化和自適應的學習服務功能，以提高個體學習者的學習效率，已成為在線智能學習領域重要研究內容之一。

學習路徑推薦算法是實現個性化學習路徑推薦的關鍵。應用于學習路徑的智能優化算法主要有遺傳算法、蟻群算法、粒子群算法、人工神經網絡、AprioriAll算法、貝葉斯網絡推理、語義本體和情景感知。每種推薦算法都具有各自的特點，有不同的數據處理方式和適用范圍，推薦的效率也有區別[1]。相較于其他方法，蟻群算法具有反饋性和自學習性，可以通過互動監測學習者的學習狀態，隨時根據整體情況計算轉移概率，在處理動態組合問題上有很大優勢。但是傳統蟻群算法具有搜索時間較長、易陷入局部最優的缺點，因此本文采用蟻群粒子群混合算法實現學習路徑推薦。

1?個性化學習路徑推薦問題的數學模型

個性化學習路徑推薦問題關注學習者個體屬性特征和學習對象特征，通過學習者與學習對象差異分析來為學習者提供與個體學習能力相匹配的學習對象序列。學習者屬性特征包括認知水平、期望目標和學習風格等方面;學習對象特征包括學習對象的難度系數、覆蓋的知識點以及對象間的約束關系等。個性化學習路徑推薦是學習對象推薦與路徑規劃問題建模，問題模型是將學習者特征和學習對象特征進行匹配的公式化表達[2]。

1.1?學習對象模型的構建

1.2?學習者特征模型的構建

S={s1，s2，s3，s4}表示學習者U的學習風格。從Kolb學習風格類型得知，學習風格類型分為發散型、聚合型、同化型和調節型四種，學習風格的不同對學習對象類型的選擇會有影響，發散型風格的學習者更喜歡富含圖、表、動畫等生動符號的學習對象;聚合型風格的學習者更喜歡文本型的學習對象;同化型風格的學習者更喜歡音、視頻等富含語言講解的學習對象;而調節型的學習者更傾喜歡通過經驗來學習，比如操縱模擬軟件[3]。同一個學習者會表現出多種學習類型的傾向，

s1、s2、s3、s4分別表示學習者U屬于四種學習風格的傾向程度，

1.3?目標函數的構造

學習路徑推薦問題可以看作是一個由多目標轉化的單目標優化問題，目標包括：學習對象的難度是否與學習者的認知水平相匹配、學習對象的類型是否與學習者的學習風格相匹配、學習路徑上各學習對象的次序是否合理等，最終找到最優路徑使學習者完成學習路徑上所有學習對象的學習。

將以上構建的四個函數配以相應的權重值，采用線性加權法構建學習路徑的目標函數，如式（6）。

2?蟻群粒子群混合算法設計

蟻群算法（Ant Colony Optimization， ACO）在算法初期具有很強的盲目性和很慢的搜索速度，而粒子群（Particle Swarm Optimization， PSO）算法具有較強的并行搜索能力和較快的搜索速度。蟻群粒子群混合的思路是在算法的前期利用粒子群算法的快速性和全局性進行粗搜索，在進行一定次數的迭代后找到問題的次優解，然后用求得的次優解對蟻群算法的信息素矩陣進行初始分布，克服蟻群算法搜索具有盲目性的缺陷，使搜索空間減小，從而找到問題的最優解。混合算法的流程圖，如圖1所示。

蟻群粒子群算法中主要參數變量有適應度函數、各微粒的速度和位置更新公式、啟發信息、信息素以及路徑的選擇概率。

1）適應度函數

將學習路徑的目標函數作為適應度函數，如式（4）所示。

2）速度和位置更新公式

在每一次迭代中，粒子i在時間（t+1）速度和位置更新如式（7）、式（8）。

3）啟發信息

將學習路徑的目標函數作為啟發信息，如式（4）所示。

4）信息素

根據粒子群算法得到的次優解初始化信息素τij，當經過n個時刻，學習者完成整條路徑L的學習后，對各條路段上的信息素進行全局更新，如式（9）。

3?實驗結果及分析

3.1?實驗設計

本文利用 Matlab R2016a實現上述算法，為了觀測本文算法的有效性和可行性，本節實驗分別以ACO和本文提出的PSO-ACO混合算法做對比，分析算法性能的差別。

參數設置如下。

1）選取具有10個知識點{k1，k2，…，k10}的一個學習任務，它們之間的關系，如圖2所示：

2）每個知識點分別對應了5個不同的學習對象，共50個，表示為{r1，r2，…，r50};每個學習對象同該知識點的相關度、難度系數，如表1所示。

3）學習者對這50個學習對象的認知水平0≤cn≤1，本實驗中設置為：

4）學習者的學習風格設置為S={0.4，0.1，0.3，0.2};

3.2?實驗結果及分析

算法的結束條件為達到最大迭代次數。在ACO算法中設定群體規模m=50、啟發信息因子α=1、信息素濃度因子β=5、信息素揮發因子ρ=0.7、最大迭代次數iter=50;

在PSO-ACO算法中首先設定群體規模m=50、學習因子c1=2，c2=2、慣性權重ω=1.2、迭代次數iter=50;適應度函數中依據四個目標函數的重要程度設置其權重值為：ω1=0.3、ω2=0.2、ω3=0.2、ω4=0.2;得到次優解后再使用ACO算法迭代50次進行優化。

兩種算法在運行30次后比較其性能指標，如表2所示。

ACO和PSO-ACO最優解隨迭代次數的變化，如圖3、圖4所示。

圖中上方折線為各代迭代的平均路徑值，下方折線為各代迭代最短路徑值，橫坐標為迭代次數，縱坐標為路徑長度。

由以上仿真結果可知，PSO-ACO算法與ACO算法相比，以犧牲時間效率為代價，取得了更好的路徑指標，并且找到最優解的速度更快。

4?總結

本文針對目前學習路徑推薦方法存在學習路徑匹配度不高的問題，建立學習者和學習對象模型，綜合考慮學習者的認知水平、學習風格與學習對象的難度、類型、目標知識點關聯度的匹配情況等因素，使用粒子群算法搜索到次優路徑后，然后使用蟻群算法搜索最短路徑，有效解決了單一的蟻群算法初期搜索方向盲目性的缺點，使搜索空間減小，提高了算法的求解速度和尋優性能。在后續工作中將繼續對學習者和學習對象模型進行完善，并考慮學習者群體的相似性來加入協同推薦，進一步提升路徑推薦效果。

參考文獻

[1]?趙呈領， 陳智慧， 黃志芳. 適應性學習路徑推薦算法及應用研究[J]. 中國電化教育， 2015（8）：85-91.

[2]?Robson da Silva Lopes. Adaptive Instructional Planning using Workflow and Genetic Algorithms[J]. Eighth IEEE/ACIS International Conference on Computer and Information Science Shanghai， 2009：87-92.

[3]?程巖. 在線學習中基于群體智能的學習路徑推薦方法[J]. 系統管理學報， 2011，20（3）：232-237.

[4]?吳雷， 方卿. 基于改進粒子群算法的學習路徑優化方法[J]. 系統科學與數學， 2016， 36（12）：2272-2281.

[5]?李浩君， 張鵬威， 張征， 等. 基于多維信息特征映射模型的在線學習路徑優化方法[J]. 控制與決策， 2019， 36（6）：1132-1140.

（收稿日期：2019.09.12）