基于改进粒子群算法的个性化学习路径优化方法

摘要

本发明公开了基于改进粒子群算法的个性化学习路径优化方法，1）建立学习路径优化问题的数学模型；2）基于改进粒子群算法的学习路径优化；3）分析时间复杂度。本发明本算法通过对标准粒子群算法的改进，解决了标准粒子群算法在解决优化问题是易陷于局部最优的缺陷，同时在搜索准确度和搜索成功率方面也具有优势。

说明书

技术领域

本发明涉及粒子群算法技术领域，更具体地说涉及基于改进粒子群算法的个性化学习路径优化方法。

背景技术

在线学习系统是一种依托互联网等新兴媒介实现学习内容传递的知识服务方式。在信息技术的推动下，在线学习逐渐成为获取知识的一种主流方式。在线学习系统虽然积累了大量的学习资源，但学习者往往很难从海量的资源中快速找到合适的学习路径与学习内容。因此，在线学习系统的智能化、个性化成了国内外学者的研究热点。智能学习系统研究的一个关键问题是学习路径的优化，系统能够根据学习者的学习目标与知识掌握程度，对合适的资源进行内容重组，形成最优化学习路径，使学习者能够快速完成学习目标。

粒子群优化算法（Particle Swarm Optimization，PSO）PSO算法是通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种进化计算方法，该算法概念明确、易于实现，在解决复杂的优化问题方面已经取得了较好的效果。但是，由于学习路径优化问题是一个典型的离散型组合优化问题，传统的PSO算法难以处理其中的顺序约束关系。而且传统的PSO算法缺乏速度的动态调节，容易陷入局部最优，导致收敛精度低和不易收敛。因此，很难通过传统的PSO算法形成最优化的学习路径。

改进粒子群算法的学习路径优化设计一种基于改进粒子群优化算法并能解决学习路径的优化问题的方法，是智能学习系统研究中的必然需求。

本专利针对同类现有技术或产品要解决的问题：

目前，智能学习系统中为了取得最优化学习路径，大多采用的是粒子群（PSO）算法、二进制粒子群（BPSO）算法与标准遗传（GA）算法等。虽然粒子群算法（PSO）和遗传算法(GA)力图在自然特性的基础上模拟个体种群的适应性，采用一定的变换规则搜索空间求解，通过随机优化方法更新种群和搜索最优点。但是它们不能很好地解决高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，无法保证收敛到最优点。因此，这些算法并不能够高效且准确的获取智能学习系统中的最优学习路径。

针对同类现有技术本专利要解决问题有：

1、提出学习路径优化问题的数学模型建立方法，使之成为典型的组合优化问题；

2、在粒子群算法中融合邻域搜索算法和禁忌策略，弥补标准粒子群算法在解决优化问题时易陷于局部最优的缺陷；

3、提升此算法在在线学习系统中应用的搜索准确度和搜索成功率。

发明内容

为解决上述技术问题，本发明提供基于改进粒子群算法的个性化学习路径优化方法,本算法在于解决智能学习系统中基于PSO算法的最优化学习路径中的局部最优的缺陷，提高搜索准确度和搜索成功率。

为了实现上述技术目的，本发明采取如下技术方案：基于改进粒子群算法的个性化学习路径优化方法，其计算方法如下：

1）建立学习路径优化问题的数学模型：

2）基于改进粒子群算法的学习路径优化：

在标准粒子群算法的基础上，将基于禁忌的邻域搜索算法引入到粒子群的寻优过程中，形成了一种改进的粒子群算法——TB-PSO；TB-PSO包括有实数编码方法、基于禁忌的邻域搜索以及TB-PSO算法的步骤；

3）分析时间复杂度：

在标准PSO算法中，设种群中粒子的数量为N，种群的迭代次数为M₁，每个粒子完成一次迭代所需要的运算时间为T₁，则可以计算出，标准PSO速算法完成优化需要耗费的总的运算时间为N×M₁×T₁；

在TB-PSO算法中，设在M₁次迭代中达到邻域搜索条件的次数为M₂，每次邻域搜索执行的最大扩展次数为K，每执行一次邻域搜索需要的运算时间为T₂，则可以计算出，TB-PSO算法完成优化所需要耗费的总的运算时间为N×M₁×T₁(1+M₂(K×T2)/M₁)。

进一步地，步骤2的6个学习资源构成的粒子的位置向量为x={3.30，0.34，3.65，4.75，5.28，2.73}，算出结果，该粒子解中r₂没有被选取，而剩下的5个学习资源对应的学习路径为{r₆,>1,>3,>4,>5}，即资源的学习顺序为6-1-3-4；粒子解x={3.30，0.34，3.65，4.75，5.28，2.73}转化的变量为x₆₁=1，x₁₃=1，x₃₄=1，其余x_ij均为0。

进一步地，步骤1的学习路径优化问题问题的目标函数为：

(1)学习难度：推荐学习路径上的所有学习资源的学习难度同学习者的知识掌握水平差距；

(2)学习花费：推荐学习路径上的所有学习资源的学习花费；

(3)相关度：推荐学习路径上的所有学习资源同目标知识点的相关度差距；

学习路径优化问题问题的约束条件为：

保证了每个待学习的目标知识点上有且只能选择一个学习资源。

进一步地，步骤2的实数编码方法采用实数编码方法将连续的实数解转化成离散的整数解，粒子解{x₁,>2,>3···x_n}由整数和小数部分构成，表示为x_i=（I_i，D_i），其中，I_i表示是否选取此学习资源，当I_i为0时，说明不选择该资源；解的大小顺序表示学习资源的路径选择顺序；再将得出的离散解转化为数学模型中对应的变量。

进一步地，步骤2的基于禁忌的邻域搜索，其算法关键步骤如下：

1）邻域扩展

X为n维向量{x₁,>2,x₃…x_n}，设δ为任一正数，则开区间（x_i-δ，x_i+δ）为x_i的一个邻域，记作U（x_i,δ）；X在所有维度上的开区间（X-δ，X+δ）为X的δ邻域，记作U（X,δ）；x_i的δ邻域去掉中心点后，称为x_i的去心δ邻域U（x_i,δ）；

对当前解采用方式进行1次δ邻域扩展，随机在邻域内生成m个候选解，将当前解同m个候选解的适应度进行比较，评价这些候选解的适应值，并从中选择最佳候选解；如果没有搜索到符合条件的解，再继续进行1次δ邻域，直到达到条件或者达到扩展次数k；

2）禁忌策略设置

将邻域按上述方式进行δ邻域扩展后，从候选解中的最佳解，用来替代当前解和最好解，然后将该解加入禁忌表中；

3）藐视准则

若当前的禁忌对象对应的适应度优于历史最优解，则无视其禁忌属性，仍然将其作为当前选择，这种办法可以有效防止遗失最优解，提高算法的寻优效率。

进一步地，步骤2的TB-PSO算法步骤具体如下：

A：初始化粒子群，随机产生所有粒子的位置和速度

设粒子解空间变量X为{x₁,>2,x₃…x_n}，其中n为学习资源的数量，在x_i的取值区间(0,N)内随机生成一个初始化粒子以及速度；

B：粒子的适应度评价

首先，根据编码映射方法将连续型的变量X映射为离散的解；

其次，计算粒子群的个体最优解与全局最优解的前提是确定适应度函数，在目标函数f₁、f₂、f₃和约束条件的基础上，形成一个综合的适应度函数评价粒子群的个体最优解与全局最优解，其中：0<a<1；，，分别表示3个目标函数的权重；是将约束条件作为惩罚函数纳入到目标函数中；

C：更新粒子的速度和位置

粒子在解空间的速度和位置更新采用标准PSO算法的更新公式：

其中，为惯性权重；r₁,r₂为加速常数；rand（）为区间[0,1]上均匀分布的随机数；P_t和G_t分别为t时刻粒子的自身最好位置pbest和全局最好位置gbest；pbest为粒子自身分过的最好位置，而gbest为粒子所对应的全局最好位置，它是整个群体所经历的最好位置；与为时刻t的位置与速度；

D：判断是否满足迭代次数：如果满足，输出最优解；如果不满足，执行E；

E：如果全局最优解达到启动局部搜索的条件，执行基于禁忌的邻域搜索；否则，跳转到B。

本发明的技术特点和效果为：要想通过算法得到最优的学习路径，首先，应建立学习路径优化问题的数学模型；其次，通过对粒子群算法的改进，将邻域搜索算法和禁忌策略引入其中，得到最优学习路径；最后，通过在线学习系统中的应用试验结果证明，此算法在搜索准确度和搜索成功率上方面都有一定的优势；

通过与现有的求解最优值的粒子群（PSO）算法、二进制粒子群（BPSO）算法和标准遗传（GA）算法相比较，本算法通过对标准粒子群算法的改进，解决了标准粒子群算法在解决优化问题是易陷于局部最优的缺陷，同时在搜索准确度和搜索成功率方面也具有优势。

附图说明

图1是本发明知识点顺序关系图。

图2是本发明基于Memetic框架的混合粒子群算法流程。

图3本发明“空间与图形”部分10个知识点顺序关系。

图4为本发明实施例2的3种算法的寻优过程对比。

图5为本发明实施例2的3种算法的寻优成功次数对比。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

实施例1

本发明提供基于改进粒子群算法的个性化学习路径优化方法，其优化方法如下：

第一步：建立学习路径优化问题的数学模型

在线学习系统中，为了能够给学习者推荐个性化的学习资源与路径，一方面需要考虑到学习者自身的知识掌握情况与学习成本，另一方面需要考虑到目标知识点的学习顺序。现有的文献^[5,8,9]中，学者们建立学习路径优化问题的数学模型时，考虑到了概念相关度、学习难度、学习者知识水平等因素，但并未将顺序关系作为实质的约束关系考虑到数学模型中，在一定程度上影响了在线学习系统资源推荐的实用效果。

因此，学习路径的优化，需要建立在领域知识结构图的基础上。用户待学习的目标知识点及知识点之间的顺序关系能够构成一张知识点结构图，每个知识点都对应了若干个难度不同的学习资源，如图1所示。用户学习路径生成的过程需要根据用户已有的学习状态，结合知识点结构图之间的顺序关系，实现学习路径的个性化生成，形成覆盖目标知识点的最优化路径。学习路径优化算法需要基于用户的学习目标，根据知识点拓扑结构和学习者状态，计算得出最优的学习资源组合方案，以满足学习者的个性化需求，并且要遵循各类约束条件。

学习路径优化问题可以描述为：已知课程包含的所有知识点及对应的学习资源，学习者的学习目标及知识掌握水平。学习者从某一个学习资源开始，按知识点之间的顺序关系依次学习目标知识点对应的学习资源，并且每个知识点只能学习一次，在完成所有目标知识点的学习后，结束学习过程。该问题求解结果为一组由学习资源组成的学习路径，并使路径满足条件：（1）学习资源难度最合适；（2）总学习花费最小；（3）选取的学习资源同目标知识点相关度最大。

该问题的参数设置为：

r_i：表示第i个学习资源，1N，N为学习资源的总数；

k_p：表示第p个待学习知识点，1pM，M为待学习知识点的总数；

c_ip：表示第i个学习资源同第p个知识点的相关度，1iN，1p，0c_ip1；

s（r_i，r_j）：表示第i个学习资源与第j个学习资源之间的学习花费，也就是学习成本。如果学习资源r_i与学习资源r_j对应的知识点在知识结构图中是顺序关系，那么他们之间的学习花费记为1；如果是逆序关系，则学习成本为一个惩罚常数P_L。

d_i：表示第i个学习资源r_i的学习难度；

a_j：表示学习者对第j个知识点的掌握水平，其中0a_j1；

该问题的变量设置为：

设变量x_ij表示学习资源推荐路径，1iN，1N：

设变量y_i表示学习资源的选择情况：

该问题的目标函数为：

(1)学习难度：推荐学习路径上的所有学习资源的学习难度同学习者的知识掌握水平差距；

(4)学习花费：推荐学习路径上的所有学习资源的学习花费；

(5)相关度：推荐学习路径上的所有学习资源同目标知识点的相关度差距。

该问题的约束条件为：

公式4保证了每个待学习的目标知识点上有且只能选择一个学习资源。

第二步：基于改进粒子群算法的学习路径优化

在学习路径优化方面，本专利所提方案在标准粒子群算法的基础上，将基于禁忌的邻域搜索算法引入到粒子群的寻优过程中，形成了一种改进的粒子群算法——TB-PSO。该算法对粒子种群中已经陷入局部最优解的个体，通过禁忌策略将其屏蔽，在其邻域内搜索可能的更优解，从而增加算法解空间的多样性。

其中实数编码方法

由于粒子群算法是一种连续型优化算法，粒子的取值范围为实数，而本专利所提方案所建数学模型的取值为离散的整数，因此，本专利所提方案采用实数编码方法将连续的实数解转化成离散的整数解。粒子解{x₁,>2,>3···x_n}由整数和小数部分构成，可以表示为x_i=（I_i，D_i）。其中，I_i表示是否选取此学习资源，当I_i为0时，说明不选择该资源；解的大小顺序表示学习资源的路径选择顺序。

设置6个学习资源构成的粒子的位置向量为x={3.30，0.34，3.65，4.75，5.28，2.73}

可以算出，该粒子解中r₂没有被选取，而剩下的5个学习资源对应的学习路径为{r₆,>1,>3,>4,>5}，即资源的学习顺序为6-1-3-4。

最后，将得出的离散解转化为数学模型中对应的变量。

其中粒子解x={3.30，0.34，3.65，4.75，5.28，2.73}转化的变量为x₆₁=1，x₁₃=1，x₃₄=1，其余x_ij均为0。

基于禁忌的邻域搜索

禁忌搜索通过采用设置禁忌策略来限制搜索陷入局部最优点，是一种全局优算法。本文在通过邻域搜索来加速局部寻优的过程中，引入禁忌策略来避免粒子在局部最优点迂回搜索，进而保证多样化的有效搜索以实现全局优化，算法关键步骤如下：

邻域扩展

X为n维向量{x₁,>2,x₃…x_n}，设δ为任一正数，则开区间（x_i-δ，x_i+δ）为x_i的一个邻域，记作U（x_i,δ）；X在所有维度上的开区间（X-δ，X+δ）为X的δ邻域，记作U（X,δ）。x_i的δ邻域去掉中心点后，称为x_i的去心δ邻域U>i,δ）。

对当前解采用上述方式进行1次δ邻域扩展，随机在邻域内生成m个候选解，将当前解同m个候选解的适应度进行比较，评价这些候选解的适应值，并从中选择最佳候选解；如果没有搜索到符合条件的解，再继续进行1次δ邻域，直到达到条件或者达到扩展次数k。

禁忌策略设置

将邻域按定义（1）的方式进行δ邻域扩展后，从候选解中的最佳解，用来替代当前解和最好解，然后将该解加入禁忌表中。

藐视准则

如果当前的禁忌对象对应的适应度优于历史最优解，则无视其禁忌属性，仍然将其作为当前选择，这种办法可以有效防止遗失最优解，提高算法的寻优效率。

算法步骤

TB-PSO算法的步骤如图2所示，具体如下：

Setp1：初始化粒子群，随机产生所有粒子的位置和速度

设粒子解空间变量X为{x₁,>2,x₃…x_n}，其中n为学习资源的数量，在x_i的取值区间(0,N)内随机生成一个初始化粒子以及速度。

：粒子的适应度评价

首先，根据上述介绍的编码映射方法将连续型的变量X映射为离散的解；

其次，计算粒子群的个体最优解与全局最优解的前提是确定适应度函数，前文已经给出了该问题的3个目标函数f₁、f₂、f₃以及约束条件，因此，这里在3个目标函数以及约束条件的基础上，形成一个综合的适应度函数评价粒子群的个体最优解与全局最优解。

其中：

0<a<1；

，，分别表示3个目标函数的权重；

是将约束条件作为惩罚函数纳入到目标函数中。

：更新粒子的速度和位置

粒子在解空间的速度和位置更新采用标准PSO算法的更新公式：

其中，为惯性权重；r₁,r₂为加速常数；rand（）为区间[0,1]上均匀分布的随机数；P_t和G_t分别为t时刻粒子的自身最好位置pbest和全局最好位置gbest。pbest为粒子自身分过的最好位置，而gbest为粒子所对应的全局最好位置，它是整个群体所经历的最好位置。与为时刻t的位置与速度。

：判断是否满足迭代次数：如果满足，输出最优解；如果不满足，执行Step5

当粒子的解达到预设的运算精度或者迭代次数时，终止搜索；否则将跳转到第5步开始执行基于禁忌的局部邻域搜索。

：如果全局最优解达到启动局部搜索的条件，执行基于禁忌的邻域搜索；否则，跳转到Step2

如果粒子群的全局最优解在多次迭代后相差较小时，该算法认为粒子群疑似陷入了局部最优，达到了启动局部搜索的条件，因此，将采用第3.2小节的方法，采用基于禁忌的局部搜索。若对同一个当前解连续扩展到预先设定的k次后仍未寻找到比当前解更优的解，则算法结束。否则，算法将跳转到第2步。

第三步：分析时间复杂度

在标准PSO算法中，设种群中粒子的数量为N，种群的迭代次数为M₁，每个粒子完成一次迭代所需要的运算时间为T₁，则可以计算出，标准PSO速算法完成优化需要耗费的总的运算时间为N×M₁×T₁。

在TB-PSO算法中，设在M₁次迭代中达到邻域搜索条件的次数为M₂，每次邻域搜索执行的最大扩展次数为K，每执行一次邻域搜索需要的运算时间为T₂，则可以计算出，TB-PSO算法完成优化所需要耗费的总的运算时间为N×M₁×T₁(1+M₂(K×T2)/M₁)。

实施例2

选取了初中数学的10个知识点作为目标知识点，每个知识点下都有5个难度不同的学习资源，各知识点间的顺序关系、学习资源的难易度、学习资源同知识点的相关度，该学生对知识点对的掌握水平等都为已知条件，其详情如下所示。

（1）选择初中数学“空间与图形”部分的10个知识点作为实验数据，这10个知识点分别为：①直线与线段；②角度的度量与表示；③平行与垂直；④三角形的性质；⑤平行四边形的性质；⑥圆形的性质；⑦全等三角形；⑧相似三角形；⑨勾股定理；⑩圆的面积。

本文用｛k₁，k₂，…，k₁₀｝依次代表上述知识点，其知识点学习顺序图如图2所示。

例如，只有在学习k₁“直线与线段”之后，才能学习k₂“角度的度量与表示”，进而才能学习k₄,>5,>6等k₂的子知识点。

（2）学习者对这10个知识点的掌握程度设置在0~1的区间内，其中0表示完全未掌握，1表示完全掌握。本实验设置的值依次为{0.9，0.5，0.6，0.3，0.4，0.4，0.2，0.15，0.15，0.1}。

（3）在这10个知识点中，每个知识点对应了5个难度不同的资源，共有50个学习资源，r₁~r₅₀，每个知识点对应资源的难度以及资源同该知识点的相关度详细情况如表1所示。其中，表中前项为资源的难度，后项为资源同知识点的相关度：

表1 知识点及学习资源相关属性表

为了验证本文提出的改进粒子群算法TB-PSO的性能，我们将本文所提算法同二进制粒子群（BPSO）算法与标准遗传（GA）算法进行对比。二进制粒子群算法BPSO是在标准PSO算法上延伸出来的一种离散二进制版PSO算法，该算法在提出的模型中将粒子的每一维及粒子本身的解限定为1或0。在对粒子的位置进行更新位置时，将速度设定一个阈值，当粒子的速度高于该阈值时，粒子的位置取1，否则取0。二进制PSO与遗传算法在形式上很相似，但实验结果显示，在大多数测试函数中，二进制PSO比遗传算法速度快^[7]。标准GA算法是一种通过模拟自然进化过程搜索最优解的方法。在每进化出新的一代后，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。其末代种群中的最优个体可作为问题近似最优解。

本次仿真实验采用的平台为Windows XP，Matlab 7.0，所用计算机的硬件配置为CPU：Pentium E6500 2.93GHz；内存：2G RAM；硬盘：500G。

实验结果分析

三种算法的寻优过程对比分析

本次实验主要验证改进粒子群算法TB-PSO在算法运算性能方面较其他两种算法的提升，图4反映了单次实验中各算法迭代次数与其得到的全局最优解的寻优曲线，其中纵坐标为每次迭代后的适应度，横坐标是迭代次数，三个算法的迭代次数均设为100次。需要说明的是，TB-PSO算法的有50次迭代是标准PSO的优化过程，另外50次迭代是用禁忌搜索进行再优化的过程。

由图4可以看出，二进制PSO算法由于仍存在标准PSO收敛速度过快、易陷于局部最优的缺点，效果相对一般。本文提出的TB-PSO方法通过引入禁忌搜索，即在粒子的运动中加入随机扰动，增加了算法的“爬山”能力，从而使算法性能在引入禁忌搜索后进一步优化，有效地克服了PSO算法易于陷入局部最优解的问题，相比二进制PSO算法取得了更好的优化效果，增加了目标解的出现次数。而标准GA算法由于其所需的粒子数目和迭代次数都远高于PSO算法，致使在当前条件下，其搜索性能较差。

三种算法的优化成功次数对比分析

为了验证上述3种算法在粒子数、最大迭代数等参数均相同时的寻优性能，本文按照粒子群数量的逐渐递加，共设置了11组实验，各组实验之间设置的粒子数量不同，但是组内3种算法的粒子数量是相同的。各算法的迭代次数均为200次，若算法在达到迭代次数之后得到的适应度在指定阈值以下，便认为该次实验算法寻优成功。每组实验各重复10次，在试验中统计各算法能够寻优成功的次数。图5展示了3种算法在各组实验中的寻优成功次数对比。

可以发现，在粒子群数量偏低时，三种算法效果均不好。但是在粒子群的数量达到60以上后，由于粒子数量逐渐变得充分，本文提出的改进粒子群算法TB-PSO的搜索效果也明显提升，其优化性能也高于二进制PSO算法和标准GA算法。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。