基于逐次适应蚁群优化算法的个性化微学习推荐

赵 琴,陈 健,张月琴

(太原理工大学 计算机科学与技术学院,太原 030024)

0 概述

微学习是一种新的在线学习方式,首次出现于2005年[1]。与其他在线学习方式相比,微学习的最大区别,在于“微”特性。“微”重点体现在微学习中的学习单元相对较小,例如能在5 min～15 min内完成视听的视频或音频资料,以及图片和文字资料,让用户可以在相对短暂的碎片时间内完成学习。自2008年起,微学习开始受到我国学者的关注和研究,目前已取得了一定的研究成果[2]。

微学习主要有2个大的研究方向:理论研究和应用研究。在理论研究方向上,目前微学习尚未建立完善的理论体系,研究范围多基于移动学习或远程教育对微学习特性的探讨[3-4];应用研究多借助其他平台来搭建微学习环境[5-8],进而对微学习特性进行相关研究,或者将一些经典算法改进后应用到微学习中[6,9-10]。

随着信息化时代的到来,知识更新周期急剧缩短,人类已跨入终身学习时代。人们出于工作和生活的需要,必须随时随地进行学习。与此同时,现代生活也改变着人们的生活节奏,上下班路程的延长使人们在公交车上、在地铁上拥有了更多的碎片时间。因此,研究如何利用这些碎片化时间来完成学习就尤为重要。

由于微学习的学习单元比其他在线学习方式的学习单元更短小精悍,对于同样的学习内容量来说,所需要的学习单元数量更多,学习单元间的关系也更为复杂。学习单元按照学习的先后顺序排列到一起就构成了学习路径,因此在微学习中,学习路径的组合就更为灵活复杂。由于存在个体差异,不同学习者适合不同的学习路径。为学习者推荐适合的个性化学习路径,可帮助其提高学习效率。

学习路径推荐算法是实现个性化学习路径推荐的关键[11]。其中,群智算法在解决学习路径推荐问题中表现出良好的性能。文献[12]提出一种学习对象关联关系构建方法,使用扩展的蚁群算法,综合考虑学习者群体对学习路径的评价、目标用户在知识水平和学习风格上的特征,为用户推荐个性化学习路径。文献[13]使用学习内容对学习路径进行构建,使用蚁群算法,根据学习者知识水平、学习风格匹配度和学习效果评价,为学习者推荐最适合的学习路径[13]。在上述算法中,由于其学习形式的局限,其推荐粒度皆为整条学习路径。微学习的出现使对学习路径的调整可以在更小的粒度上进行交互适应的调整,学习者对知识内容的选择也更为灵活。如何利用微学习的特性,满足学习者的个性化需求,为学习者推荐个性化的学习路径,成为一个新的问题。

基于以上研究,本文利用蚁群算法反馈性,提出一种通过学习者与系统的互动实现的信息素浓度逐次适应调整的蚁群算法。该算法通过在微学习过程中捕捉学习者的特征和学习状态的变化,逐次调整学习路径推荐策略,为学习者推荐个性化的学习路径。

1 相关技术及基本概念

1.1 蚁群算法

蚁群算法是一种经典的群智算法,具有高度并行性、正反馈性、协同性等优点,在智能搜索和全局优化方面体现出良好的性能[14]。在解决路径问题中,也表现出良好的求解效率和寻优效果[15]。

在蚁群算法解决旅行商问题(Travelling Salesman Problem,TSP)的过程中,可以领会到蚁群算法的基本思想。

TSP问题即寻找经过N个城市,每个城市只经过一次,最后回到起点的最短路径。使用蚁群算法解决TSP问题的具体流程如下:

1)初始化算法中的各个参数。

2)判断蚂蚁访问状态:若蚂蚁一个城市的都未访问,将蚂蚁随机放置在N个城市之一;否则,根据式(1)选择下一个城市。

3)根据式(2)更新信息素浓度。

4)判断是否满足条件(达到最大迭代次数),记录当前最优解,若未达到,迭代次数加1,转到步骤2);若已达到,转到步骤5)。

5)输出最优解。

上述流程中涉及到的公式如下:

蚂蚁根据式(1)对下一个城市进行选择:

(1)

由式(1)可以得知,城市i与城市j之间的距离越近,信息素浓度越高,蚂蚁k选择路径城市i到城市j的概率就越大。

假设从时间t到(t+1)有m个蚂蚁通过路段i→j,对信息素浓度进行更新:

(2)

1.2 基本概念

本文算法基于基本蚁群算法,结合微学习的特征,为学习者提供个性化的学习路径,以下是算法中涉及到的基本概念。

1.2.1 与学习单元相关的概念

学习单元是知识的主要载体,其中包含丰富的知识。在对学习单元特征的选取上,采用知识领域、知识水平等属性对其进行描述。

1)学习单元知识领域

学习单元中包含的知识属于相应的知识领域,知识领域是学习单元最重要的一个属性。假设共有n个知识领域,使用向量A={a1,a2,…,an}表示学习单元所属的知识领域。其中ai∈(0,1),若ai=1,代表学习单元属于知识领域i;否则,不属于学习领域i。

2)学习单元知识水平

知识单元中知识的难易水平是学习单元一个重要的属性,用Ci(Ci∈0,1,2)来表示学习单元在知识领域i的知识水平。若Ci=0,代表学习单元知识水平为初级;若Ci=1,代表学习单元知识水平为中级;若Ci=2,代表学习单元知识水平为高级。

1.2.2 与学习者相关的概念

学习者是学习的主体,由于知识水平、兴趣爱好、学习习惯等因素之间的差异,在学习单元的选择上具有很大的不同。在对学习者的属性描述上,本文采用知识领域、知识水平、学习目标、学习状态等属性来对学习者的特征进行描述。

1)学习者知识领域

该属性用来表示学习者计划学习的知识领域,使用R={r1,r2,…,rn}表示。其中ri∈(0,1),若ri=1,代表学习者愿意学习了解知识领域i;否则,对该学习领域i不感兴趣。

2)学习者知识水平

学习者的知识水平是针对学习者感兴趣的知识领域而言的,同一学习者在不同的知识领域内学习水平可以不同。使用di(di∈(0,1,2))来表示在知识领域i中的知识水平,若di=0,学习者对于知识领域i中知识的了解几乎为零;若di=1,学习者对于知识领域i内的知识有一定的了解;若di=2,学习者对于知识领域i中的知识有熟悉的了解。

3)学习者学习目标

学习目标是依据学习者当前进行学习的知识领域对应的知识水平设定的,为不同学习水平的学习者,设定不同的学习目标。若当前学习目标达到,表明当前学习过程结束,此时完成一条完整的学习路径的学习。

4)学习者学习状态

学习状态是描述学习者对当前学习路径中的学习单元适应度的一个重要属性,同时也是后续学习单元推荐策略选择的重要依据。根据学习者对于当前学习路径中学习单元的整体掌握情况,将学习状态分为3种状态:初始态,调整态,变更态。其描述如下。

1)初始态:学习者首次进行学习或者开始一条新的学习路径。

2)适应态:当前学习路径比较适合学习者,根据已知的表征学习情况的调整因子对学习单元推荐策略进行调整。

3)变更态:学习者不适合当前学习路径,说明前期对于学习者在该学习领域中的知识水平判断存在一定的误差或者学习者在学习的过程中知识水平发生了变化。

1.2.3 学习路径

学习路径是学习单元按照学习时间先后顺序排列而成的一组序列。按照其形成过程,学习路径可以分为初始化学习路径和个性化学习路径。

初始化学习路径是学习单元提供者根据对学习单元知识组成结构的了解,为学习者提供的一条学习路径。该条学习路径对于每个学习者都一样,不具有个性化。而且由于局限性,每条学习路径中所有学习单元都属于同一个学习单元提供者。学习单元提供者对于学习单元中的知识很熟悉,初始化学习路径具有很高的参考价值。

个性化的学习路径,是在初始化学习路径的基础上,根据学习者在学习过程中自身学习状态的变化、学习的历史记录,在学习过程中动态形成的一条学习路径,其能够满足学习者个性化的学习需求。

2 信息素逐次适应调整的蚁群算法

本文提出一种对信息素浓度进行逐次适应调整的蚁群算法,并以此对微学习中的学习者推荐学习路径。利用蚁群算法的反馈性和自学习性,通过互动监测学习者的学习状态,逐次调整学习路径推荐策略,为学习者推荐个性化学习路径。

本文提出的适应逐次调整蚁群算法将微学习特性与蚁群算法结合,为学习者推荐个性化学习路径。算法步骤如下。

算法信息素逐次适应调整算法

输入学习单元基本信息数据,学习者基本信息数据

输出推荐学习单元编号

1.init:启发信息因子α,信息素浓度因子β,信息素挥发浓度ρ,初始化信息素浓度τij;

2.set:学习者学习领域i,学习者知识水平d,学习状态信息t;

3.switch(t)

case 1:t=初始态,推荐策略1(式(7));

case 2:t=适应态,推荐策略2(式(8));

case 3:t=变更态,推荐策略3(式(9));

4.output:学习单元编号;

5.update:局部信息素浓度(式(4));

6.update学习状态 t;

7.if (达成学习目标)

update全局信息浓度(式(5));

else goto 3

结束处理

本文算法的系统结构如图1所示,主要由用户信息更新模块、信息素浓度更新模块、参考学习组抽出模块、推荐模块等4个模块组成。

图1 逐次适应微学习路径推荐的系统结构

2.1 用户信息更新模块

该模块完成的工作主要有:1)对首次进行学习的学习者,将其学习状态设立为初始态,同时还需要确定其知识领域和知识水平;2)根据当前学习情况更新学习者的学习状态。学习状态是本文算法的核心部分,主要通过测验成绩来判断当前学习者的学习状态;3)根据学习者的基本信息及学习记录,判断学习者是否达成学习目标。

图2 学习者知识水平判定流程

对于已经学习过数次的学习者,本模块的主要任务是根据其用户信息以及学习记录判断其是否达成学习目标。如果学习目标已经达成,结束当前学习路径,将整条学习路径记录放入学习路径集合中,存入用户信息库中。该数据将被信息素浓度更新模块用于对学习路径上的信息素浓度进行全局更新,同时用户信息更新模块则将当前学习者的学习状态更新为初始态。如果学习目标未达成,用户信息更新模块将根据学习者的用户信息以及学习记录来判断当前学习状态。

(3)

根据学习者的用户信息以及学习记录可判断学习者是否达成学习目标。学习者的学习目标是否达成是根据学习者的学习状态进行判定的。若学习者连续Θ次学习状态为适应态,则可以认为学习目标已经达成,其中Θ的数值取决于其该条学习路径参照学习路径中的学习单元个数。

2.2 信息素浓度更新模块

本模块主要负责对信息素浓度进行局部和全局更新。学习者完成当前学习单元的学习后,根据学习单元包含的知识组成,为学习者提供对应的测试题。根据测试成绩和学习者掌握该学习单元的情况,进行信息素局部更新。

信息素浓度是蚁群算法中进行反馈性调节的重要因素,也是蚁群算法中最重要的一个属性。路径上的信息素浓度越高,选择该条路径的概率就越大;反之,越小。测试成绩作为表征学习者在学习路径上学习情况的重要特性,在本文算法中用来对信息素浓度进行局部更新。

(4)

其中,τij(t)代表t时刻学习单元Li到学习单元Lj上的信息素浓度,τij(t+1)代表t+1时刻学习单元Li到学习单元Lj上的信息素浓度,ρ代表信息素的挥发系数。

学习者完成某条学习路径的学习后,根据学习者的测试结果对该条路径上的信息素进行全局更新。当某个学习者Sk完成学习路径J的学习后,信息素浓度按照式(5)进行全局更新。

τij(t+1)=

(5)

其中,τij(t)代表t时刻学习单元Li到学习单元Lj上的信息素浓度,τij(t+1)代表t+1时刻学习单元Li到学习单元Lj上的信息素浓度,ρ代表信息素的挥发系数。

2.3 参考学习组的抽出模块

学习者的参考学习组由学习者之间的相似度确定。其中,学习相似度由以下2个方面决定:学习者的基本信息和学习记录。表征学习者Sk和St之间相似度的相关系数Fkt由式(6)确定。

(6)

根据上述公式,相似度较高的学习者将选取作为目标学习者的参考学习组,为学习状态为初始态的学习者提供主要的推荐依据,用于确定学习路径中的第1个学习单元。同时,参考学习组的学习记录将用于调整目标学习者学习路径中的局部信息素浓度,帮助目标学习者提高和改善学习效率。

2.4 推荐模块

本模块是系统的核心部分,根据学习者的学习状态,调整学习单元的推荐策略和学习路径,其调整策略描述如下。

1)初始态

如果学习者So当前学习状态为初始态,由目标学习者的参考学习组信息,根据式(7)为学习者推荐学习单元。

(7)

其中,poi代表学习单元Li与学习者So的相似度,Sr属于学习者So的参考学习组,λor代表学习者So与学习者Sr的相似度,θri代表学习者Sr与学习单元Li的相似度,学习者Sr为学习过学习单元Li的学习者。若学习单元Li与学习者So相似度poi最大,则为学习者So推荐学习单元Li。

2)适应态

如果学习者So当前学习状态为适应态,调整因子为ε,前一个学习单元为Li,根据式(8)为学习者推荐学习单元。

(8)

3)变更态

如果学习者So当前学习状态为变更态,前一个学习单元为Li,根据式(9)为学习者推荐学习单元。

(9)

3 实验设计与结果分析

为进一步验证本文提出的算法可以在微学习环境中为学习者提供个性化的学习路径,提高学习效率,设计实验对算法进行验证。

3.1 实验设计

3.1.1 学习单元和学习者的确定

为满足微学习对于学习单元时间长度的要求,从网上下载筛选符合要求的学习资源,保证每个学习单元都可以在15 min内学习完成。同时选取学习单元数量适中的初始化学习路径,每个课程中包含的学习单元数量为8个～12个。

经过筛选整理,共得到167个计算机应用技术相关的学习课程,包含1 685个学习单元,将其划分为4个学习领域:前端开发,后端开发,移动开发和数据处理。根据学习课程的知识内容难度,标记其知识水平。整理完成后,得到知识领域和知识水平标记完成的167条初始化学习路径,其基本信息分布如表1所示。

表1 学习单元基本信息

在学习者选取上,共选用80名学习者用于实验。为验证改进蚁群算法可以切实提高学习者的学习效率,将80名学习者分为2组,一组为实验组,另一组为对比组,每组为40名学习者。2组学习者40人同时参与,每人学习若干学习单元。为提高实验结果的可信度与准确性,对80名学习者的基本信息进行前期调查统计,确保2组学习者在初始阶段,知识领域和对应的知识水平分布情况差异性较小。学习者初始基本信息分布情况如表2所示。

表2 学习者基本信息

3.1.2 算法参数的确定

蚁群算法参数值的选取对于实验结果有非常重要的影响。采用改进蚁群算法来实现微学习中的学习路径推荐,如何设置各个参数值,确定合理的学习单元以及学习者数量,以更好地实现学习路径推荐是首先要进行的工作。

在Matlab环境下,使用程序模拟学习者的学习过程,研究启发信息因子、信息素浓度因子、信息素浓度挥发因子、迭代次数、学习单元数量以及学习者数量等参数对于结果的影响。通过多次实验,分析研究信息素浓度分布变化过程,综合考虑算法的时间复杂度,最终确定了算法的基本参数。其中,启发信息因子α取值为1.4,信息素浓度的因子β的取值为1.1,信息素挥发浓度ρ取值为0.7,迭代次数取值为150。

3.1.3 对比实验

准备工作完成后,使用JSP+MySQL创建微学习环境。实验分为2个组:实验组和对比组。对比组中的学习者按照初始化路径学习,实验组的学习者按照改进蚁群算法推荐的学习路径学习,最终比较测试成绩。

3.2 实验结果分析

通过实验,得到了2组学习者的测试成绩。图3显示了实验组和对比组分别在前端开发、后端开发、移动开发、数据处理4个学习领域,平均测试成绩随着学习单元数量增加的变化情况。其中,A01、B01分别代表实验组和对比组在前端开发领域,A02、B02分别代表实验组和对比组在后端开发领域,A03、B03分别代表实验组和对比组在移动开发领域,A04、B04分别代表实验组和对比组在数据处理领域。

图3 学习单元个数与平均测试成绩的关系

由实验结果可以得出,实验组的学习者在学习相同数量的学习单元后,得到的平均测试成绩明显较高,由此可以推断本文提出的算法可以提高学习者在微学习环境下的学习效率。

由图3可以推出:学习者的测试成绩普遍得到了提高,平均测试成绩随学习单元数目呈线性增长;在学习初期,实验组和对比组成绩增长幅度相差不大;在学习中期,实验组的学习者的测试成绩增幅明显优于对比组;在学习后期,对比组仍保持一定的增幅,实验组平均测试成绩增幅较之前明显放缓。

对于实验结果分析如下:

1)在学习初期,实验组中学习路径的信息素浓度较低,选择多数取决于学习单元的属性,实验组与对比组的相差较小;在学习中后期,信息素逐渐累积,实验组中的优势逐渐显示出来。

2)实验组测试成绩增幅在后期明显放缓,经过对信息素浓度的分析,推测此时算法可能陷入局部最优。

3)在图3中,纵坐标代表的是平均测试成绩,表示测试成绩的总体趋势。对学习者测试成绩分布情况进行分析,发现部分处于变更态学习者的测试成绩特别高或者测试成绩特别低,其对于平均测试成绩有所影响,但是对测试成绩总体的趋势影响并不大。

4 结束语

本文提出了一种基于信息素浓度逐次适应调整的蚁群算法,用于实现微学习中的个性化学习路径推荐。实验结果表明,该算法可以优化微学习路径,有效提高学习效率。但该算法仍需进一步提高和改进。今后的工作将考虑将蚁群算法中参数自适应理论引入该算法中来改善局部最优问题。对于蚁群算法应用领域的参数设置,目前尚无成熟的理论。对于本文所涉及到的参数设置,下一步考虑使用组合优化算法进行参数选择;对于本文算法的时间复杂度和空间复杂度的讨论需要完善,目前蚁群算法此方面的相关研究较少,需要进一步研究分析。

[1] HUG T,LINDNER M,BRUCK P A.Microlearning:Emerging Concepts,Practices and Technologies After e-Learning[J].Proceedings of Microlearning,2005(5):45-53.

[2] 张振虹,杨庆英,韩 智.微学习研究:现状与未来[J].中国电化教育,2013(11):12-20.

[3] 王佑镁,祝智庭.从联结主义到联通主义,学习理论的新取向[J].中国电化教育,2006(3):5-8.

[4] BAUMGARTNER P.Educational Dimensions of Micro-learning-towards a Taxonomy for Microlearning[M].Innsbruck,Austria:Innsbruck University Press,2013.

[5] KOVACHEV D,CAO Y,KLAMMA R,et al.Learn-as-You-Go:New Ways of Cloud-based Micro-learning for the Mobile Web[C]//Proceedings of International Con-ference on Web-based Learning.Berlin,Germany:Springer,2011:51-61.

[6] BRUCK P A,MOTIWALLA L,FOERSTER F.Mobile Learn-ing with Micro-content:A Framework and Evaluation[C]//Proceedings of the 25th Bled Conference.Berlin,Germany:Springer,2012:17-20.

[7] GU X,GU F,LAFFEY J M.Designing a Mobile System for Lifelong Learning on the Move[J].Journal of Computer Assisted Learning,2011,27(3):204-215.

[8] 陶璐琳.基于智能手机的微学习设计研究[D].武汉:华中师范大学,2012.

[9] 史致远,朱明放.微学习环境下基于语义的MASHUP架构优化[J].江苏大学学报(自然科学版),2010,31(3):339-342.

[10] CHEN Jian,ZHANG Yueqin,SUN Jingyu,et al.Personalized Micro-learning Support Based on Process Mining[C]//Proceedings of International Conference on Information Technology in Medicine & Education.Washington D.C.,USA:IEEE Press,2016:511-515.

[11] 赵呈领,陈智慧,黄志芳.适应性学习路径推荐算法及应用研究[J].中国电化教育,2015(8):85-91.

[12] CHEN Chih-Ming.Intelligent Web-based Learning System with Personalized Learning Path Guidance[J].Computers and Education,2008,51(2):787-814.

[13] 张 松.学习内容管理系统及其个性化推荐技术研究与实现[D].沈阳:东北大学,2013.

[14] 费 腾,张立毅,孙云山.基于DNA-蚁群算法的车辆路径优化问题求解[J].计算机工程,2014,40(12):205-208.

[15] 张 潇,王江晴.混合蚁群算法在车辆路径问题中的应用[J].计算机工程,2011,37(24):190-192.