Memetic算法在學(xué)習(xí)路徑推薦中的matlab求解分析

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

關(guān)鍵詞：Memetic算法；matlab軟件；在線學(xué)習(xí)

中圖分類號：TP391 文獻標(biāo)識碼：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算法相似的流程，結(jié)合局部搜索策略以期在群體中找尋到最優(yōu)個體[1]。在線學(xué)習(xí)路徑推薦是為在線學(xué)習(xí)者從海量知識庫中找到最適合學(xué)習(xí)者學(xué)情的學(xué)習(xí)路徑[2]，從而幫助學(xué)習(xí)者實現(xiàn)個性化學(xué)習(xí)需求[3]，達到因材施教的目的。

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

2 貪心Memetic算法學(xué)習(xí)路徑推薦模型

基于memetic算法的學(xué)習(xí)路徑推薦模型由三個模塊組成，分別是：學(xué)習(xí)風(fēng)格分析模塊、知識水平測試模塊和基于memetic算法的知識推理模塊。學(xué)習(xí)者登錄系統(tǒng)后進行信息錄入和學(xué)前測試，獲得學(xué)習(xí)者的知識目標(biāo)；學(xué)習(xí)風(fēng)格分析模塊和知識水平測試模塊分別獲得當(dāng)前學(xué)習(xí)者的學(xué)習(xí)風(fēng)格和知識水平?；趍emetic算法的知識推理模塊結(jié)合前面兩個模塊得出的個性化數(shù)據(jù)進行推理計算，從學(xué)習(xí)資源庫中提取知識點數(shù)據(jù)，形成個性化學(xué)習(xí)路徑推薦給當(dāng)前學(xué)習(xí)者。當(dāng)前學(xué)習(xí)者完成個性化學(xué)習(xí)路徑的學(xué)習(xí)后，由知識水平測試模塊對學(xué)習(xí)者進行課后測試并將測試結(jié)果反饋給教師。教師根據(jù)教學(xué)反饋不定期對學(xué)習(xí)資源庫進行更新維護和參數(shù)調(diào)整。

3 Matlab程序模型實現(xiàn)

3.1 學(xué)習(xí)路徑編碼

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

3.2 初始化種群

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

t=10； %學(xué)習(xí)資源庫中可供其選擇的知識點為10個。

s=100；

pop=zeros（s，t）；

for i=1：s

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

end

3.3 選擇操作

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

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

[s，t]=size（pop）；

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

mall=sum（m1）； %求出矩陣適應(yīng)度函數(shù)值的總和

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]操作對被選擇的相鄰兩條染色體進行優(yōu)化，以期獲得適應(yīng)度值更高的染色體。

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））%查找前染色體中重復(fù)基因

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））%查找前染色體中重復(fù)基因

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 變異操作

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

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））%查找前染色體中重復(fù)基因

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 適應(yīng)度函數(shù)

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

其中，[ci]是費用開銷，[wc]是費用開銷權(quán)重；[ti]是時間開銷，[wt]是時間開銷權(quán)重；[di]是知識點的難度值，[wd]是難度權(quán)重。將適應(yīng)度函數(shù)設(shè)為[1f]，即：開銷最小、知識點難度值最低的學(xué)習(xí)路徑其適應(yīng)度函數(shù)最大。

4 實驗結(jié)果分析

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

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

5 結(jié)語

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

參考文獻：

[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] 藺豐奇，劉益.網(wǎng)絡(luò)化信息環(huán)境中信息過載問題研究綜述[J].情報資料工作，2007（3）：36-41.

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

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

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

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

[7] 彭建偉.基于Memetic 算法的個性化學(xué)習(xí)路徑推薦的研究與實現(xiàn)[D].長沙：湖南大學(xué)，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.

【通聯(lián)編輯：王力】