基于改進細菌覓食的協作學習分組算法

桑治平,何聚厚,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.