论文部分内容阅读
摘要：提出了在线学习路径推荐模型，采用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.，
关键词：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.，