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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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)個(gè)體[1]。在線學(xué)習(xí)路徑推薦是為在線學(xué)習(xí)者從海量知識(shí)庫中找到最適合學(xué)習(xí)者學(xué)情的學(xué)習(xí)路徑[2]，從而幫助學(xué)習(xí)者實(shí)現(xiàn)個(gè)性化學(xué)習(xí)需求[3]，達(dá)到因材施教的目的。

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

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

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

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

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

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

3.2 初始化種群

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

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

s=100；

pop=zeros（s，t）；

for i=1：s

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

end

3.3 選擇操作

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

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

[s，t]=size（pop）；

m1=（pop（：，t））； %建立一個(gè)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 %求出矩陣每條染色體被選擇的累計(jì)概率

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]操作對(duì)被選擇的相鄰兩條染色體進(jìn)行優(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）；%獲得進(jìn)行交叉操作的第二條染色體兩交叉點(diǎn)的所有課程序列

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

middle2=zeros（1，tc）；

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

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

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

采用隨機(jī)變異操作對(duì)被選擇的相鄰兩條色體進(jìn)行優(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ù)

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

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

4 實(shí)驗(yàn)結(jié)果分析

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

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

5 結(jié)語

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

參考文獻(xiàn)：

[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].情報(bào)資料工作，2007（3）：36-41.

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

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

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

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

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