基于改进细菌觅食的协作学习分组算法

桑治平,何聚厚,2

(1.陕西师范大学计算机科学学院,西安710062;2.现代教学技术教育部重点实验室,西安710062)

基于改进细菌觅食的协作学习分组算法

桑治平1,何聚厚1,2

(1.陕西师范大学计算机科学学院,西安710062;2.现代教学技术教育部重点实验室,西安710062)

针对协作学习中基于学习者特征的分组方式对学习过程的影响,设计一种基于改进细菌觅食的协作学习分组算法。在实现协作学习分组过程中,引入分组调节因子和特征权值,满足不同教学活动对学习者多个特征及分组的要求。为构成有效的分组空间,在细菌种群初始化中,细菌群体以实数编码,并加入随机扰动以增加细菌种群的多样性;在算法后期加入二次变异操作,以避免细菌觅食算法可能出现的早熟收敛现象。仿真实验结果表明,该算法在不同分组形式下,与传统算法相比,具有较优的分组性能和较高的准确率,并且对于不同数据集规模具有良好的稳定性。

协作学习;评价准则;学习分组;分组形式;多目标优化;细菌觅食优化算法

1 概述

在协作学习中,根据学习者特征进行有效分组可以创造更好的学习氛围,激发学生进行讨论及提出问题,从而提高学习效果[1]。传统的分组方法有随机分组法和穷举法[2]。但是随机分组未考虑学习者特征容易造成学习者特征差异度过大,从而达不到学习目标[3],而穷举法在学习者人数过多且考虑到学习者特征时其时间复杂度呈指数级增大,所以无法在短时间内有效分组[4]。为此,对于组内同质分组,文献[4]通过遗传算法解决分组问题,该算法虽然考虑到学习者的多个特征因素,但没有考虑到不同活动类型和特征权值对分组的影响。文献[5]通过改进的粒子群算法解决分组问题,该算法仅考虑了学生的理解力水平和兴趣爱好2个特征。对于组间同质分组,文献[6]通过改进的遗传算法解决分组问题,该算法在分组过程中没有对学习者特征属性进行区分,不能满足不同的分组要求。

在不同教学活动中通过调节因子对分组形式进行调节,对学习者的不同特征属性加以区分并加入不同的特征权值调整对分组结果的影响,则协作学习中分组问题变为多目标化问题。本文采用基于改进细菌觅食的协作学习分组算法,以细菌种群构成分组空间,通过算法在计算过程中的多次迭代寻优,从而找出满足条件的准确分组方式。

2 协作学习分组问题建模

2.1 学习者的特征属性选取

在协作学习中通常学习者特征应包含多个评价准则[7],如:学习兴趣,学习动机,理解力水平,知识水平,学习效能[8-11]等。由于学习者特征的特殊性,不同特征属性对分组结果有着不同影响,由层次分析法[12]选取影响协作学习的个体因素和群体性因素。其中根据个体因素进行组内同质分组,能促进组内的学习交互水平[13],而根据群体因素,进行组间同质分组不仅能保证整体学习计划的完成,还能促进学习者形成积极的学习对等关系,保证学习目标的实现[14-15]。其特征属性模型如图1所示。

图1 学习者特征属性模型

由于在分组过程中学习活动的不同,引入特征权值调节学习者特征因素量化值大小。个体因素权值集合W与群体因素权值集合U分别用W={w1w2…wi…wn}和U={u1u2…uj…un}表示。其中,wi,uj分别是特征因素Ai和Bj对应的权值,且w1+w2+…+wn=1,u1+u2+…+un=1。

2.2 分组问题形式化描述

基于学习者集合S={sk|k∈1 2…N}中sk的特征量化值,将N个学习者分入R个小组内,使其满足不同的分组要求,则所有的分组方式构成分组空间G。在分组过程中既要保证小组内人数均匀,也要保证一个学习者只能分入一个小组。

定义1 分组空间定义为:

其中,M为分组方式个数。对于每一种分组方式Gz:

引入个体因素特征均值作为个体因素特征差异度的度量标准。

定义2 个体因素特征均值集合IM(y)定义为:

定义3 学习者sk的个体因素特征与小组均值的差异度定义为:

定义5 分组过程定义为:

分组过程是基于学习者特征集合A,B,学习者集合S,特征权值集合W,U在分组空间G中寻找最优分组方式Gbest的过程,为此满足的约束条件如下:

目标函数:

其中,调节因子α,β∈(0,1),α+β=1。

约束条件:

其中,p=1,2,…,R;q=1,2,…,R且p≠q。

在目标函数表达式中,C1值越小表示在学习小组gy内学习者的个体因素集合A的差异度越小即同组内学习者特征相似度越高,保证组内同质。C2值越小表示在分组方式Gz中各学习小组间的学习者的群体因素集合B的差异度越小即小组间的学生特征相似度越高,保证组间同质。调节因子α,β可根据教学活动对分组的影响,调节对分组的要求。

约束条件式(8)保证了个N个学习者都会被分到某一小组内。约束条件式(9)、式(10)保证每一个学生只能被分入一个小组且每组内的学习者都不同。约束条件式(11)保证组内人数相差不超过一人。

3 基于EBFO的协作学习分组算法

3.1 算法描述及流程

细菌觅食算法利用生物生存发展的原理解决优化问题,其良好的寻优性能已经被广泛应用于各种优化问题的解决[16]。算法的关键步骤有:细菌种群初始化,细菌趋向性操作、复制操作以及迁徙操作。所以本文将细菌觅食算法引入协作学习分组问题,并对其关键步骤进行改进形成EBFO算法。在EBFO算法初期细菌种群初始化中,以学习者编号以及组号结合分组问题的要求,作为算法中的细菌编码,加入随机扰动,构成分组解空间并使分组多样性增加。算法后期加入二次迁徙操作,更好的避免算法中可能出现的早熟收敛现象,从而得到更好的满足要求的分组方式,EBFO算法流程如图2所示。

图2 EBFO算法流程

3.2 算法实现步骤

算法实现步骤如下:

第1步 学习者特征预处理和参数初始化。

第2步 细菌群体初始化改进。

(1)对细菌群体采用实数编码,用[0,R]之间的随机整数产生N长编码序列,其中一个细菌用N维向量表示为:

其中,i,j=1,2,…,N,θi,θj=1,2,…,R,θi,θj分别表示第i个和第j个学生被分入θi和θj组,即一个细菌代表一种分组方式Gz。编码满足分组模型中的约束条件,即每一个待分组学生只能被分入一个学习小组,避免对学习者的重复选择。

(2)为确保分组方式Gz的多样性,采用随机扰动对细菌种群初始化,即对细菌θ′中的编码位置按式(13)产生:

即新的细菌θ′由原细菌θ中编码打乱形成。由于θ满足分组模型的约束条件,因此θ′的编码也同样满足。执行M次操作,则∀sk∈S都被分到某一小组gy∈Gz中,形成分组空间G={Gz|z=1,2,…,M}。

第3步 细菌趋向性操作。

定义细菌的游动步长c(i),则细菌迁徙操作按式(14)进行:

第4步 细菌复制操作。

按照精英保留策略,即按适应度对细菌群体M排序,淘汰排在后面的M/2个细菌,剩余的M/2个细菌进行自我复制,各自生成一个与自己完全相同的新个体,新个体与原个体有相同的分组信息。

第5步 细菌迁徙操作的改进。

复制周期完成后,对当前细菌群体执行迁徙及二次迁徙操作。增加的二次迁徙操作,更能使算法保持种群的稳定性和多样性,跳出局部最优解,减少局部收敛的情况。

(1)对复制操作之后的细菌种群进行迁徙操作,若种群中某个细菌个体满足大于迁徙操作发生概率ped,则这个个体灭亡,并随机在分组解空间内随机产生一个新个体,且可能与已灭亡的个体具有不同的位置,即具有不同的寻优能力。

(2)增加二次迁徙操作,若种群中某个细菌个体满足大于二次迁徙操作概率prd,则随机产生两个编码中的位置p,q,二次迁徙操作前的细菌编码表示为:

对细菌i和j位置之间的所有编码进行翻转,形成新的细菌,其编码表示为:

二次迁徙操作既保证了细菌编码中对所有学习者sk的选择,又避免编码中学习者sk的重复,形成新的细菌个体θ′i,而且通过后期的二次迁徙操作可以丰富种群多样性,更好的避免局部集优。

第6步 对于∀Gz∈G,根据(7)式计算出F值,并更新迭代变化后的细菌种群。

第7步 迭代循环结束条件判断,若不满足则更新发生变化的细菌种群并保存并继续执行第3步～第6步;若满足则输出结果,即最优分组方式Gbest及其对应的适应度值F。

4 实验仿真

4.1 参数设置

EBFO相关参数如表1所示。

表1 EBFO相关参数

细菌种群数目M=50,趋向性操作执行次数Nc=20,细菌最大游动步长Ns=4,复制性操作次数Nre=4,迁徙及二次迁徙操作次数Ned=4,细菌发生迁徙概率Ped=0.25,二次迁徙概率prd=0.5。

4.2 仿真及结果分析

为测试EBFO算法的分组准确性,选取表1中的5组数据集,取调节因子α=0.6,β=0.4,取30次迭代。分别用穷举法(EM)、随机法(RM)、细菌觅食算法(BFO)作为对比实验并对每组数据运行10次求均值。实验结果如表2所示。

表2 各算法实验结果

当N=10,N=50时,穷举法(EM)得到的分组方式中F值最小,即组间与组内特征相似度最高,但运行时间随问题规模N增大其时间开销过大,即不能用于大规模学生分组问题。随机算法(RM)由于其随机性,虽然分组速度很快,但是却不能对分组模型进行准确的求解,导致分组性能太差。而EBFO算法中获得的最优分组方式中的F值此时也极接近最优解。在5组数据集下,对于EBFO算法与基本BFO算法的比较,说明通过加入二次迁徙操作,使细菌种群多样性在算法后期得以提高,更易于跳出局部集优寻找最优值,保证分组问题得到准确解决。

为测试EBFO算法在分组形式不同时的分组性能,当N=50时,在组间同质情况下,即调节因子取α=0.1,β=0.9时用随机法(RM),文献[6]的遗传算法(GA1)作为对比实验。在组内同质情况下,即调节因子取α=0.9,β=0.1时用穷举法(EM),随机法(RM),文献[4]中的遗传算法(GA2),文献[5]的粒子群算法(PSO)作为对比实验。实验结果如图3、图4所示。

图3 ～中的小组均值(α=0.1,β=0.9)

图4 ～中的小组均值(α=0.9,β=0.1)

由图3可知,当α=0.1,β=0.9,此时EBFO算法中小组均值曲线较RM算法与GA1算法曲线更平缓,即基于学习者的知识水平,学习效能的小组间差异度较小,小组获得了更好的满足分组要求的分组方式Gz,从教育学角度而言这更加保证学习计划的完成和学习者共同达到学习目标[15]。

由图4可知,当α=0.9,β=0.1,此时EBFO算法相对于RM算法、GA2算法和PSO算法获得使各小组均值更小的分组方式Gz,使小组内学习者基于学习者的学习兴趣,学习动机,理解力水平的相似度更高,从教育学角度而言这更加提高学习者在学习过程中的积极性以便更好的交互[13]。

为测试EBFO算法对不同规模数据集的稳定性,选取表1中的4组数据集,取调节因子α=0.6,β=0.4用偏差比作为收敛性的判断标准,即判断迭代后函数值F与迭代过程中Fmax-Fmin的比值是否发生变化。

由图5可知,本文EBFO算法对于4种不同数据集在一定的迭代次数后,均表现出一定的稳定性。由此可得在学习者规模增加的情况下,EBFO算法也有很强的稳定性。同时由偏差比的变化以及这4幅图的结果,可以将EBFO算法的迭代次数定为30。

图5 迭代次数偏差比对比

5 结束语

本文分析了学习者的特征属性,考虑在协作学习分组过程中学习者的多个特征因素及其权值分配,采用改进的细菌觅食算法对学习者进行分组。实验结果验证了EBFO算法对分组问题求解的准确性和稳定性。此外,从教育学角度而言,由于教学活动的不同,通过EBFO算法调节组内与组间同质分组均获得了良好的分组性能。但是在具体的教学活动中对学习者特征权值的确定,需要进一步验证。

[1] Beane W E,Lemke E A.Group Variables Influencing the Transfer of Conceptual Behavior[J].Journal of Educational Psychology,1971,62(3):215-218.

[2] Huxham M,Land R.Assigning Students in Group Work Projects.Can wedo BetterThan Random?[J]. Innovations in Education and Teaching International, 2000,37(1):17-22.

[3] Lou Y,Abrami P C,Spence J C,et al.Within-class Grouping:A Meta-analysis[J].Review of Educational Research,1996,66(4):423-458.

[4] Hwang G J,Yin P Y,Hwang C W,et al.An Enhanced Genetic Approach to Composing Cooperative Learning Groups for Multiple Grouping Criteria[J].Educational Technology&Society,2008,11(1):148-167.

[5] Lin Y T,Huang Y M,Cheng S C.An Automatic Group Composition System for Composing Collaborative Learning GroupsUsing Enhanced Particle Swarm Optimization[J].Computers&Education,2010,55(4): 1483-1493.

[6] Moreno J,Ovalle D A,Vicari R M.A Genetic Algorithm Approach for Group Formation in Collaborative Learning Considering Multiple StudentCharacteristics[J]. Computers&Education,2012,58(1):560-569.

[7] McCombs B L,Pope J E.学习动机的激发策略[M].伍新春,译.北京:中国轻工业出版社,2002.

[8] Meyer D.OptAssign——A Web-based Tool for Assigning Studentsto Groups[J].Computers& Education,2009,53(4):1104-1119.

[9] Tang T Y,Chan K C.Feature Construction for Student Group Forming Based on Their Browsing Behaviors in An E-learning System[M].Berlin,Germany:Springer, 2002.

[10] Wilkinson I A G,Fung I Y Y.Small-group Composition and Peer Effects[J].International Journal of Educational Research,2002,37(5):425-447.

[11] Saleh I,Kim S.A Fuzzy System for Evaluating Students’Learning Achievement[J].Expert Systems with Applications,2009,36(3):6236-6243.

[12] 王莲芬,许树柏.层次分析法引论[M].北京:中国人民大学出版社,1990.

[13] Michaelsen L K.Team-based Learning:Small Group Learning′s Next Big Step:New Directions for Teaching and Learning[M].[S.1.]:Jossey-Bass Publishes, 2011.

[14] Tinto V.Taking Student Success Seriously:Rethinking the First Year of College[C]//Proc.of the 9th Annual Intersession Academic Affairs Forum.Fullerton,USA: California State University Press,2005:605-611.

[15] Smith K A.Cooperative Learning:Making“Groupwork”Work[J].New Directions for Teaching and Learning, 1996,(67):71-82.

[16] Passino K M.Biomimicry of Bacterial Foraging for Distributed Optimization and Control[J].IEEE Control Systems,2002,22(3):52-67.

[17] Gall J P,GallM D.Outcomesofthe Discussion Method.Teaching and Learning Through Discussion: The Theory,Research and Practice of the Discussion Method[M].Springfield,USA:[s.n.],1990.

编辑 索书志

Grouping Algorithm for Collaborative Learning Based on Improved Bacterial Foraging

SANG Zhi-ping1,HE Ju-hou1,2
(1.School of Computer Science,Shaanxi Normal University,Xi’an 710062,China;
2.Key Laboratory of Modern Teaching Technology,Ministry of Education,Xi’an 710062,China)

The grouping form for collaborative learning group based on learners’characteristics is one of the factors that enhance the learning effectiveness.A new learning grouping algorithm based on enhanced bacterial foraging is proposed.In order to meet the requirements of different learning activity that is associated to the learners’characteristics, the regulatory factor and feature weights are used to grouping.At the initialization step of algorithm,there are two method which are used to ensure the effective grouping space,one is that the bacterial population is coded by real number coding, and another is that a random perturbation is used to increase the diversity of bacterial populations.And the algorithm is joined the second mutation to avoid the premature convergence at the later step.Simulation experimental results show that the proposed algorithm is advantage to increase the effectiveness and the accuracy for grouping form.And it has a good stability for data sets with different sizes

collaborative learning;evaluation criteria;learning grouping;grouping form;multi-objective optimization; bacterial foraging optimization algorithm

1000-3428(2014)10-0137-06

A

TP391.7

10.3969/j.issn.1000-3428.2014.10.027

中央高校基本科研业务费专项基金资助项目(GK201002028,GK201101001);陕西师范大学学习科学交叉学科培育计划基金资助项目。

桑治平(1988-),男,硕士研究生,主研方向:协作学习:何聚厚(通讯作者),副教授、博士。

2013-10-22

2013-12-16E-mail:juhouh@snnu.edu.cn.

中文引用格式:桑治平,何聚厚.基于改进细菌觅食的协作学习分组算法[J].计算机工程,2014,40(10):137-142.

英文引用格式:Sang Zhiping,He Juhou.Grouping Algorithm for Collaborative Learning Based on Improved Bacterial Foraging[J].Computer Engineering,2014,40(10):137-142.