Memetic算法在學習路徑推薦中的matlab求解分析

摘要：提出了在線學習路徑推薦模型，采用memetic算法，結合matlab軟件進行優化計算，闡明了程序的編碼與實現，并結合案例進行分析驗證了該模型有較快的收斂速度和較強的尋優能力，為在線學習路徑推薦提供了強有力的方法和工具。

關鍵詞：Memetic算法；matlab軟件；在線學習

中圖分類號：TP391 文獻標識碼：A

文章編號：1009-3044（2019）12-0198-03

Matlab Solution Analysis of Memetic Algorithms in Learning Path Recommendation

TAN Hui-lin1，2

（1.ShaoYang University， Shaoyang 42200， China；2.School of Mechanical and Electrical Engineering，Central South University，Changsha 410083， China）

Abstract： This paper proposes an online learning path recommendation model. It uses memetic algorithm and MATLAB software to optimize the calculation. It clarifies the coding and implementation of the program. It also verifies that the model has faster convergence speed and stronger optimization ability through case analysis. It provides a powerful method and tool for online learning path recommendation.

Key words： Memetic algorithm；Matlab software； online learning

1 引言

1989年，Memetic算法（又稱文化基因算法）首次由Pablo Moscato 教授提出，采用與GA算法相似的流程，結合局部搜索策略以期在群體中找尋到最優個體[1]。在線學習路徑推薦是為在線學習者從海量知識庫中找到最適合學習者學情的學習路徑[2]，從而幫助學習者實現個性化學習需求[3]，達到因材施教的目的。

本文以建構主義學習理論和自適應學習理論為指導構造了貪心Memetic算法學習路徑推薦模型，保留了每代種群中的最優個體，提高了搜索效率。實驗結果表明該貪心Memetic算法較采用爬山算法策略的Memetic算法有更快的收斂速度和更強的尋優能力。

2 貪心Memetic算法學習路徑推薦模型

基于memetic算法的學習路徑推薦模型由三個模塊組成，分別是：學習風格分析模塊、知識水平測試模塊和基于memetic算法的知識推理模塊。學習者登錄系統后進行信息錄入和學前測試，獲得學習者的知識目標；學習風格分析模塊和知識水平測試模塊分別獲得當前學習者的學習風格和知識水平。基于memetic算法的知識推理模塊結合前面兩個模塊得出的個性化數據進行推理計算，從學習資源庫中提取知識點數據，形成個性化學習路徑推薦給當前學習者。當前學習者完成個性化學習路徑的學習后，由知識水平測試模塊對學習者進行課后測試并將測試結果反饋給教師。教師根據教學反饋不定期對學習資源庫進行更新維護和參數調整。

3 Matlab程序模型實現

3.1 學習路徑編碼

為了高效地解決問題，學習路徑采用染色體整數編碼的形式。染色體的每位基因值代表要學習的知識點編號，染色體長度代表學習路徑的知識點數量。例：某學習路徑覆蓋了7個知識點，學習資源庫中可供其選擇的知識點為10個，學習路徑的起點為知識點1，終點為知識點10。即：學習路徑的長度為7，染色體每位基因值的取值范圍為[1-10]，學習路徑{1，2，3，5，6，7，10}為可能的學習路徑。

3.2 初始化種群

在matlab中可通過隨機函數randperm（）隨機生成可能存在的學習路徑作為初始種群，種群規模為100。在學習路徑的搜索過程中，為提高算法的收斂速度，可按照實際情況預先定義好學習路徑的起點和終點。

t=10； %學習資源庫中可供其選擇的知識點為10個。

s=100；

pop=zeros（s，t）；

for i=1：s

pop（i，1：t-1）=randperm（t-1）； %隨機生成從知識點1到知識點10的學習路徑

end

3.3 選擇操作

采用比例選擇算子（輪盤賭選擇）[6]來確定進行優化的染色體。

function [fpops]=select1（pop，k） %輪盤賭選擇K條染色體，k取值為20

[s，t]=size（pop）；

m1=（pop（：，t））； %建立一個1列t行的m11矩陣，其值為pop矩陣中所有行，第t列

mall=sum（m1）； %求出矩陣適應度函數值的總和

glm=m1/mall； %求出矩陣每條染色體被選擇的概率

lj=zeros（s，1）；

lj（1，1）=glm（1，1）；

for i=2：s

lj（i）=lj（i-1）+glm（i）；

end %求出矩陣每條染色體被選擇的累計概率

for i=1：k

r=rand；

for j=1：s

if r<=lj（j）

fpops（i，：）=pop（j，：）；

break；

end

end

end

end

3.4 交叉操作

采用順序交叉[7]操作對被選擇的相鄰兩條染色體進行優化，以期獲得適應度值更高的染色體。

function [fpopc]=cross（fpop） %cross.m

[sc，tc]=size（fpop）；

fpopc1=fpop；

fpopc=fpop；

for ic=1：2：sc % i從1開始以公差為2遞增至s

ac=round（rand*（sc-1））+1；

bc=round（rand*（sc-1））+1；

while ac==bc

bc=round（rand*（sc-1））+1；

end

fatherc1=fpop（ac，：）；

fatherc2=fpop（bc，：）；

kc=round（rand*（tc-2））+1；

if kc==1

kc=kc+1；

end

if kc==tc-1

kc=kc-1；

end

middle1=zeros（1，tc）；

middle1（1，1：kc-1）=fatherc2（1，1：kc-1）；%獲得進行交叉操作的第二條染色體兩交叉點的所有課程序列

middle1（1，kc：tc-1）=fatherc1（1，kc：tc-1）；%獲得進行交叉操作的第一條染色體所有課程序列

middle2=zeros（1，tc）；

middle2（1，1：kc-1）=fatherc1（1，1：kc-1）；%獲得進行交叉操作的第一條染色體兩交叉點的所有課程序列

middle2（1，kc：tc-1）=fatherc2（1，kc：tc-1）；%獲得進行交叉操作的第二條染色體所有課程序列

for j1=kc：tc-1

for jmd1=1：kc-1

while find（middle1（1，jmd1）==middle1（1，j1））%查找前染色體中重復基因

middle1（1，jmd1）=0；

end

end

end

for j2=kc：tc-1

for jmd2=1：kc-1

while find（middle2（1，jmd2）==middle2（1，j2））%查找前染色體中重復基因

middle2（1，jmd2）=0；

end

end

end

for j1=1：tc-1

while middle1（1，j1）==0

middle1=fatherc1；

break

end

end

for j1=1：tc-1

fpopc（ic，j1）=middle1（1，j1）；

end

for j2=1：tc-1

while middle2（1，j2）==0

middle2=fatherc2；

break

end

end

for j1=1：tc-1

fpopc（ic+1，j1）=middle2（1，j1）；

end

end

end

3.5 變異操作

采用隨機變異操作對被選擇的相鄰兩條色體進行優化，以期獲得適應度值更高的染色體。

function [fpopm]=mutate（fpop，kt） %mutate.m

[sm，tm]=size（fpop）；

kt=10；

fpopm=fpop；

fpopm1=fpop；

for im=1：sm

am=round（rand*（tm-2））+1；

if am<2

am=2；

end

if am>tm-2

am=tm-2；

end

mpop=randperm（kt）；

for jm=1：tm-1

for ktm=1：kt

while find（mpop（1，ktm）==fpopm（im，jm））%查找前染色體中重復基因

mpop（1，ktm）=0；

end

end

end

km=1；

while mpop（1，km）==0

km=km+1；

end

if km<=tm-1

fpopm（im，am）=mpop（1，km）；

else

km=1；

end

end

3.6 適應度函數

知識點學習開銷包括費用開銷[ci]和時間開銷[ti]；難度值[di]的初始值依據李特克氏5點量表[8] 預設，因此適應度函數可理解為：[f=i=1nwc×ci+wt×ti+wd×di] （1）

其中，[ci]是費用開銷，[wc]是費用開銷權重；[ti]是時間開銷，[wt]是時間開銷權重；[di]是知識點的難度值，[wd]是難度權重。將適應度函數設為[1f]，即：開銷最小、知識點難度值最低的學習路徑其適應度函數最大。

4 實驗結果分析

以涵蓋10個知識點的知識庫，學習路徑覆蓋8個知識點的實例在matlab2017a中實踐了基于memetic算法的知識推理模塊。實驗表明種群規模為60，交叉概率為0.6，變異概率為0.04時就可以得到比較好的結果。實踐中學習路徑適應度函數變化如圖3所示，實驗得到的最優學習路徑圖如圖4所示。

仿真結果表明，該模塊收斂速度較快，迭代不到30次即可獲得最優學習路徑：1→2→3→5→8→9→10，適應度函數值約為0.022，達到了預期的目標。相對于彭建偉學者提出的迭代30-80次找到最優解的知識推理模型[7]，實驗中提出的基于memetic算法的知識推理模塊收斂速度更快，具有更高的可行性。

5 結語

本文成功地實現了基于memetic算法的學習路徑推薦模型在matlab2017a的仿真，并通過實驗驗證了該學習路徑推薦模型具有良好的收斂性和較強的路徑尋優能力。針對本文中的實例，通過實驗找尋到了遺傳算子各參數的相對最優解。

參考文獻：

[1] Moscato P. On evolution，search，optimization，genetic algorithms and martial arts：towards memeticalgorithms[J].Caltech concurrent computation programs，C3P Report，1989，826：1989.

[2] 藺豐奇，劉益.網絡化信息環境中信息過載問題研究綜述[J].情報資料工作，2007（3）：36-41.

[3] 吳輝娟，袁方.個性化服務技術研究[J].計算機技術與發展，2006，16（2）：32 -34.

[4] 譚慧琳.基于遺傳算法的知識推理研究[J].電腦知識與技術，2011（31）：7731-7733.

[5] 譚慧琳.基于遺傳算法的知識推理研究[D].長沙：湖南師范大學，2011.

[6] 馬駿.遺傳算法TSP的matlab求解分析[J].科技視界2018（16）：38-39.

[7] 彭建偉.基于Memetic 算法的個性化學習路徑推薦的研究與實現[D].長沙：湖南大學，2009.

[8] Chen，C. M.， Lee， H. M.， & Chen， Y. H. Personalized e-learning system using Item Response Theory[J]. Computers & Education， 2005 （44）237-255.

【通聯編輯：王力】