APP下载

基于蚁群-粒子群混合算法的学习路径推荐策略研究

2020-12-23东苗

微型电脑应用 2020年11期
关键词:蚁群算法粒子群算法

东苗

摘 要:针对目前学习路径推荐方法存在学习路径匹配度不高的问题,建立学习者和学习对象模型,综合考虑学习者的认知水平、学习风格与学习对象的难度、类型、目标知识点关联度的匹配情况等因素,使用粒子群算法搜索到次优路径后,再使用蚁群算法搜索最短路径,有效解决了单一的蚁群算法初期搜索方向盲目性的缺点。仿真结果表明,算法的求解速度和寻优性能得到了有效提高。

关键词:蚁群算法;粒子群算法;学习路径

中图分类号:TP 18

文献标志码:A

文章编号:1007-757X(2020)11-0130-03

Abstract:The current method of learning path recommendationhas the problem that the learning path matching degree is not high enough. In this paper, alearner and the learning object model isestablished. The model deals with the factors like the cognitive level and the learning style of the learner, the difficulty and resource typeof the learning object, and the relevance degree of the target knowledge point,etc. After that, the particle swarm optimization algorithm is used to search for the suboptimal path, and then the ant colony algorithm is used to search for the shortest path. These techniqueseffectively solve the shortcoming of the blindness of the initial search direction of the single ant colony algorithm. The simulation results show that the convergence speed and optimization performance of the algorithm are effectively improved.

Key words:ant colony algorithm;particle swarm optimization algorithm;learning path

0 引言

在開展学习活动时,由于学习者学习风格的不同以及认知能力的差异,对学习对象的学习次序和内容组织方式也不尽相同。因此,利用人工智能技术提供个性化和自适应的学习服务功能,以提高个体学习者的学习效率,已成为在线智能学习领域重要研究内容之一。

学习路径推荐算法是实现个性化学习路径推荐的关键。应用于学习路径的智能优化算法主要有遗传算法、蚁群算法、粒子群算法、人工神经网络、AprioriAll算法、贝叶斯网络推理、语义本体和情景感知。每种推荐算法都具有各自的特点,有不同的数据处理方式和适用范围,推荐的效率也有区别[1]。相较于其他方法,蚁群算法具有反馈性和自学习性,可以通过互动监测学习者的学习状态,随时根据整体情况计算转移概率,在处理动态组合问题上有很大优势。但是传统蚁群算法具有搜索时间较长、易陷入局部最优的缺点,因此本文采用蚁群粒子群混合算法实现学习路径推荐。

1 个性化学习路径推荐问题的数学模型

个性化学习路径推荐问题关注学习者个体属性特征和学习对象特征,通过学习者与学习对象差异分析来为学习者提供与个体学习能力相匹配的学习对象序列。学习者属性特征包括认知水平、期望目标和学习风格等方面;学习对象特征包括学习对象的难度系数、覆盖的知识点以及对象间的约束关系等。个性化学习路径推荐是学习对象推荐与路径规划问题建模,问题模型是将学习者特征和学习对象特征进行匹配的公式化表达[2]。

1.1 学习对象模型的构建

1.2 学习者特征模型的构建

S={s1,s2,s3,s4}表示学习者U的学习风格。从Kolb学习风格类型得知,学习风格类型分为发散型、聚合型、同化型和调节型四种,学习风格的不同对学习对象类型的选择会有影响,发散型风格的学习者更喜欢富含图、表、动画等生动符号的学习对象;聚合型风格的学习者更喜欢文本型的学习对象;同化型风格的学习者更喜欢音、视频等富含语言讲解的学习对象;而调节型的学习者更倾喜欢通过经验来学习,比如操纵模拟软件[3]。同一个学习者会表现出多种学习类型的倾向,

s1、s2、s3、s4分别表示学习者U属于四种学习风格的倾向程度,

1.3 目标函数的构造

学习路径推荐问题可以看作是一个由多目标转化的单目标优化问题,目标包括:学习对象的难度是否与学习者的认知水平相匹配、学习对象的类型是否与学习者的学习风格相匹配、学习路径上各学习对象的次序是否合理等,最终找到最优路径使学习者完成学习路径上所有学习对象的学习。

将以上构建的四个函数配以相应的权重值,采用线性加权法构建学习路径的目标函数,如式(6)。

2 蚁群粒子群混合算法设计

蚁群算法(Ant Colony Optimization, ACO)在算法初期具有很强的盲目性和很慢的搜索速度,而粒子群(Particle Swarm Optimization, PSO)算法具有较强的并行搜索能力和较快的搜索速度。蚁群粒子群混合的思路是在算法的前期利用粒子群算法的快速性和全局性进行粗搜索,在进行一定次数的迭代后找到问题的次优解,然后用求得的次优解对蚁群算法的信息素矩阵进行初始分布,克服蚁群算法搜索具有盲目性的缺陷,使搜索空间减小,从而找到问题的最优解。混合算法的流程图,如图1所示。

蚁群粒子群算法中主要参数变量有适应度函数、各微粒的速度和位置更新公式、启发信息、信息素以及路径的选择概率。

1)适应度函数

将学习路径的目标函数作为适应度函数,如式(4)所示。

2)速度和位置更新公式

在每一次迭代中,粒子i在时间(t+1)速度和位置更新如式(7)、式(8)。

3)启发信息

将学习路径的目标函数作为启发信息,如式(4)所示。

4)信息素

根据粒子群算法得到的次优解初始化信息素τij,当经过n个时刻,学习者完成整条路径L的学习后,对各条路段上的信息素进行全局更新,如式(9)。

3 实验结果及分析

3.1 實验设计

本文利用 Matlab R2016a实现上述算法,为了观测本文算法的有效性和可行性,本节实验分别以ACO和本文提出的PSO-ACO混合算法做对比,分析算法性能的差别。

参数设置如下。

1)选取具有10个知识点{k1,k2,…,k10}的一个学习任务,它们之间的关系,如图2所示:

2)每个知识点分别对应了5个不同的学习对象,共50个,表示为{r1,r2,…,r50};每个学习对象同该知识点的相关度、难度系数,如表1所示。

3)学习者对这50个学习对象的认知水平0≤cn≤1,本实验中设置为:

4)学习者的学习风格设置为S={0.4,0.1,0.3,0.2};

3.2 实验结果及分析

算法的结束条件为达到最大迭代次数。在ACO算法中设定群体规模m=50、启发信息因子α=1、信息素浓度因子β=5、信息素挥发因子ρ=0.7、最大迭代次数iter=50;

在PSO-ACO算法中首先设定群体规模m=50、学习因子c1=2,c2=2、惯性权重ω=1.2、迭代次数iter=50;适应度函数中依据四个目标函数的重要程度设置其权重值为:ω1=0.3、ω2=0.2、ω3=0.2、ω4=0.2;得到次优解后再使用ACO算法迭代50次进行优化。

两种算法在运行30次后比较其性能指标,如表2所示。

ACO和PSO-ACO最优解随迭代次数的变化,如图3、图4所示。

图中上方折线为各代迭代的平均路径值,下方折线为各代迭代最短路径值,横坐标为迭代次数,纵坐标为路径长度。

由以上仿真结果可知,PSO-ACO算法与ACO算法相比,以牺牲时间效率为代价,取得了更好的路径指标,并且找到最优解的速度更快。

4 总结

本文针对目前学习路径推荐方法存在学习路径匹配度不高的问题,建立学习者和学习对象模型,综合考虑学习者的认知水平、学习风格与学习对象的难度、类型、目标知识点关联度的匹配情况等因素,使用粒子群算法搜索到次优路径后,然后使用蚁群算法搜索最短路径,有效解决了单一的蚁群算法初期搜索方向盲目性的缺点,使搜索空间减小,提高了算法的求解速度和寻优性能。在后续工作中将继续对学习者和学习对象模型进行完善,并考虑学习者群体的相似性来加入协同推荐,进一步提升路径推荐效果。

参考文献

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

[2] Robson da Silva Lopes. Adaptive Instructional Planning using Workflow and Genetic Algorithms[J]. Eighth IEEE/ACIS International Conference on Computer and Information Science Shanghai, 2009:87-92.

[3] 程岩. 在线学习中基于群体智能的学习路径推荐方法[J]. 系统管理学报, 2011,20(3):232-237.

[4] 吴雷, 方卿. 基于改进粒子群算法的学习路径优化方法[J]. 系统科学与数学, 2016, 36(12):2272-2281.

[5] 李浩君, 张鹏威, 张征, 等. 基于多维信息特征映射模型的在线学习路径优化方法[J]. 控制与决策, 2019, 36(6):1132-1140.

(收稿日期:2019.09.12)

猜你喜欢

蚁群算法粒子群算法
蚁群算法的运用及其优化分析
电力市场交易背景下水电站优化调度研究
基于粒子群算法的产业技术创新生态系统运行稳定性组合评价研究
CVRP物流配送路径优化及应用研究
云计算中虚拟机放置多目标优化
基于蚁群算法的一种无人机二维航迹规划方法研究
一种多项目调度的改进蚁群算法研究
无线传感器网络联盟初始结构生成研究
交通堵塞扰动下多车场车辆路径优化
基于混合算法的双向物流路径优化问题的研究