基于改進(jìn)細(xì)菌覓食的協(xié)作學(xué)習(xí)分組算法

桑治平,何聚厚,2

(1.陜西師范大學(xué)計算機科學(xué)學(xué)院,西安710062;2.現(xiàn)代教學(xué)技術(shù)教育部重點實驗室,西安710062)

基于改進(jìn)細(xì)菌覓食的協(xié)作學(xué)習(xí)分組算法

桑治平1,何聚厚1,2

(1.陜西師范大學(xué)計算機科學(xué)學(xué)院,西安710062;2.現(xiàn)代教學(xué)技術(shù)教育部重點實驗室,西安710062)

針對協(xié)作學(xué)習(xí)中基于學(xué)習(xí)者特征的分組方式對學(xué)習(xí)過程的影響,設(shè)計一種基于改進(jìn)細(xì)菌覓食的協(xié)作學(xué)習(xí)分組算法。在實現(xiàn)協(xié)作學(xué)習(xí)分組過程中,引入分組調(diào)節(jié)因子和特征權(quán)值,滿足不同教學(xué)活動對學(xué)習(xí)者多個特征及分組的要求。為構(gòu)成有效的分組空間,在細(xì)菌種群初始化中,細(xì)菌群體以實數(shù)編碼,并加入隨機擾動以增加細(xì)菌種群的多樣性;在算法后期加入二次變異操作,以避免細(xì)菌覓食算法可能出現(xiàn)的早熟收斂現(xiàn)象。仿真實驗結(jié)果表明,該算法在不同分組形式下,與傳統(tǒng)算法相比,具有較優(yōu)的分組性能和較高的準(zhǔn)確率,并且對于不同數(shù)據(jù)集規(guī)模具有良好的穩(wěn)定性。

協(xié)作學(xué)習(xí);評價準(zhǔn)則;學(xué)習(xí)分組;分組形式;多目標(biāo)優(yōu)化;細(xì)菌覓食優(yōu)化算法

1 概述

在協(xié)作學(xué)習(xí)中,根據(jù)學(xué)習(xí)者特征進(jìn)行有效分組可以創(chuàng)造更好的學(xué)習(xí)氛圍,激發(fā)學(xué)生進(jìn)行討論及提出問題,從而提高學(xué)習(xí)效果[1]。傳統(tǒng)的分組方法有隨機分組法和窮舉法[2]。但是隨機分組未考慮學(xué)習(xí)者特征容易造成學(xué)習(xí)者特征差異度過大,從而達(dá)不到學(xué)習(xí)目標(biāo)[3],而窮舉法在學(xué)習(xí)者人數(shù)過多且考慮到學(xué)習(xí)者特征時其時間復(fù)雜度呈指數(shù)級增大,所以無法在短時間內(nèi)有效分組[4]。為此,對于組內(nèi)同質(zhì)分組,文獻(xiàn)[4]通過遺傳算法解決分組問題,該算法雖然考慮到學(xué)習(xí)者的多個特征因素,但沒有考慮到不同活動類型和特征權(quán)值對分組的影響。文獻(xiàn)[5]通過改進(jìn)的粒子群算法解決分組問題,該算法僅考慮了學(xué)生的理解力水平和興趣愛好2個特征。對于組間同質(zhì)分組,文獻(xiàn)[6]通過改進(jìn)的遺傳算法解決分組問題,該算法在分組過程中沒有對學(xué)習(xí)者特征屬性進(jìn)行區(qū)分,不能滿足不同的分組要求。

在不同教學(xué)活動中通過調(diào)節(jié)因子對分組形式進(jìn)行調(diào)節(jié),對學(xué)習(xí)者的不同特征屬性加以區(qū)分并加入不同的特征權(quán)值調(diào)整對分組結(jié)果的影響,則協(xié)作學(xué)習(xí)中分組問題變?yōu)槎嗄繕?biāo)化問題。本文采用基于改進(jìn)細(xì)菌覓食的協(xié)作學(xué)習(xí)分組算法,以細(xì)菌種群構(gòu)成分組空間,通過算法在計算過程中的多次迭代尋優(yōu),從而找出滿足條件的準(zhǔn)確分組方式。

2 協(xié)作學(xué)習(xí)分組問題建模

2.1 學(xué)習(xí)者的特征屬性選取

在協(xié)作學(xué)習(xí)中通常學(xué)習(xí)者特征應(yīng)包含多個評價準(zhǔn)則[7],如:學(xué)習(xí)興趣,學(xué)習(xí)動機,理解力水平,知識水平,學(xué)習(xí)效能[8-11]等。由于學(xué)習(xí)者特征的特殊性,不同特征屬性對分組結(jié)果有著不同影響,由層次分析法[12]選取影響協(xié)作學(xué)習(xí)的個體因素和群體性因素。其中根據(jù)個體因素進(jìn)行組內(nèi)同質(zhì)分組,能促進(jìn)組內(nèi)的學(xué)習(xí)交互水平[13],而根據(jù)群體因素,進(jìn)行組間同質(zhì)分組不僅能保證整體學(xué)習(xí)計劃的完成,還能促進(jìn)學(xué)習(xí)者形成積極的學(xué)習(xí)對等關(guān)系,保證學(xué)習(xí)目標(biāo)的實現(xiàn)[14-15]。其特征屬性模型如圖1所示。

圖1 學(xué)習(xí)者特征屬性模型

由于在分組過程中學(xué)習(xí)活動的不同,引入特征權(quán)值調(diào)節(jié)學(xué)習(xí)者特征因素量化值大小。個體因素權(quán)值集合W與群體因素權(quán)值集合U分別用W={w1w2…wi…wn}和U={u1u2…uj…un}表示。其中,wi,uj分別是特征因素Ai和Bj對應(yīng)的權(quán)值,且w1+w2+…+wn=1,u1+u2+…+un=1。

2.2 分組問題形式化描述

基于學(xué)習(xí)者集合S={sk|k∈1 2…N}中sk的特征量化值,將N個學(xué)習(xí)者分入R個小組內(nèi),使其滿足不同的分組要求,則所有的分組方式構(gòu)成分組空間G。在分組過程中既要保證小組內(nèi)人數(shù)均勻,也要保證一個學(xué)習(xí)者只能分入一個小組。

定義1 分組空間定義為:

其中,M為分組方式個數(shù)。對于每一種分組方式Gz:

引入個體因素特征均值作為個體因素特征差異度的度量標(biāo)準(zhǔn)。

定義2 個體因素特征均值集合IM(y)定義為:

定義3 學(xué)習(xí)者sk的個體因素特征與小組均值的差異度定義為:

定義5 分組過程定義為:

分組過程是基于學(xué)習(xí)者特征集合A,B,學(xué)習(xí)者集合S,特征權(quán)值集合W,U在分組空間G中尋找最優(yōu)分組方式Gbest的過程,為此滿足的約束條件如下:

目標(biāo)函數(shù):

其中,調(diào)節(jié)因子α,β∈(0,1),α+β=1。

約束條件:

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

在目標(biāo)函數(shù)表達(dá)式中,C1值越小表示在學(xué)習(xí)小組gy內(nèi)學(xué)習(xí)者的個體因素集合A的差異度越小即同組內(nèi)學(xué)習(xí)者特征相似度越高,保證組內(nèi)同質(zhì)。C2值越小表示在分組方式Gz中各學(xué)習(xí)小組間的學(xué)習(xí)者的群體因素集合B的差異度越小即小組間的學(xué)生特征相似度越高,保證組間同質(zhì)。調(diào)節(jié)因子α,β可根據(jù)教學(xué)活動對分組的影響,調(diào)節(jié)對分組的要求。

約束條件式(8)保證了個N個學(xué)習(xí)者都會被分到某一小組內(nèi)。約束條件式(9)、式(10)保證每一個學(xué)生只能被分入一個小組且每組內(nèi)的學(xué)習(xí)者都不同。約束條件式(11)保證組內(nèi)人數(shù)相差不超過一人。

3 基于EBFO的協(xié)作學(xué)習(xí)分組算法

3.1 算法描述及流程

細(xì)菌覓食算法利用生物生存發(fā)展的原理解決優(yōu)化問題,其良好的尋優(yōu)性能已經(jīng)被廣泛應(yīng)用于各種優(yōu)化問題的解決[16]。算法的關(guān)鍵步驟有:細(xì)菌種群初始化,細(xì)菌趨向性操作、復(fù)制操作以及遷徙操作。所以本文將細(xì)菌覓食算法引入?yún)f(xié)作學(xué)習(xí)分組問題,并對其關(guān)鍵步驟進(jìn)行改進(jìn)形成EBFO算法。在EBFO算法初期細(xì)菌種群初始化中,以學(xué)習(xí)者編號以及組號結(jié)合分組問題的要求,作為算法中的細(xì)菌編碼,加入隨機擾動,構(gòu)成分組解空間并使分組多樣性增加。算法后期加入二次遷徙操作,更好的避免算法中可能出現(xiàn)的早熟收斂現(xiàn)象,從而得到更好的滿足要求的分組方式,EBFO算法流程如圖2所示。

圖2 EBFO算法流程

3.2 算法實現(xiàn)步驟

算法實現(xiàn)步驟如下:

第1步 學(xué)習(xí)者特征預(yù)處理和參數(shù)初始化。

第2步 細(xì)菌群體初始化改進(jìn)。

(1)對細(xì)菌群體采用實數(shù)編碼,用[0,R]之間的隨機整數(shù)產(chǎn)生N長編碼序列,其中一個細(xì)菌用N維向量表示為:

其中,i,j=1,2,…,N,θi,θj=1,2,…,R,θi,θj分別表示第i個和第j個學(xué)生被分入θi和θj組,即一個細(xì)菌代表一種分組方式Gz。編碼滿足分組模型中的約束條件,即每一個待分組學(xué)生只能被分入一個學(xué)習(xí)小組,避免對學(xué)習(xí)者的重復(fù)選擇。

(2)為確保分組方式Gz的多樣性,采用隨機擾動對細(xì)菌種群初始化,即對細(xì)菌θ′中的編碼位置按式(13)產(chǎn)生:

即新的細(xì)菌θ′由原細(xì)菌θ中編碼打亂形成。由于θ滿足分組模型的約束條件,因此θ′的編碼也同樣滿足。執(zhí)行M次操作,則?sk∈S都被分到某一小組gy∈Gz中,形成分組空間G={Gz|z=1,2,…,M}。

第3步 細(xì)菌趨向性操作。

定義細(xì)菌的游動步長c(i),則細(xì)菌遷徙操作按式(14)進(jìn)行:

第4步 細(xì)菌復(fù)制操作。

按照精英保留策略,即按適應(yīng)度對細(xì)菌群體M排序,淘汰排在后面的M/2個細(xì)菌,剩余的M/2個細(xì)菌進(jìn)行自我復(fù)制,各自生成一個與自己完全相同的新個體,新個體與原個體有相同的分組信息。

第5步 細(xì)菌遷徙操作的改進(jìn)。

復(fù)制周期完成后,對當(dāng)前細(xì)菌群體執(zhí)行遷徙及二次遷徙操作。增加的二次遷徙操作,更能使算法保持種群的穩(wěn)定性和多樣性,跳出局部最優(yōu)解,減少局部收斂的情況。

(1)對復(fù)制操作之后的細(xì)菌種群進(jìn)行遷徙操作,若種群中某個細(xì)菌個體滿足大于遷徙操作發(fā)生概率ped,則這個個體滅亡,并隨機在分組解空間內(nèi)隨機產(chǎn)生一個新個體,且可能與已滅亡的個體具有不同的位置,即具有不同的尋優(yōu)能力。

(2)增加二次遷徙操作,若種群中某個細(xì)菌個體滿足大于二次遷徙操作概率prd,則隨機產(chǎn)生兩個編碼中的位置p,q,二次遷徙操作前的細(xì)菌編碼表示為:

對細(xì)菌i和j位置之間的所有編碼進(jìn)行翻轉(zhuǎn),形成新的細(xì)菌,其編碼表示為:

二次遷徙操作既保證了細(xì)菌編碼中對所有學(xué)習(xí)者sk的選擇,又避免編碼中學(xué)習(xí)者sk的重復(fù),形成新的細(xì)菌個體θ′i,而且通過后期的二次遷徙操作可以豐富種群多樣性,更好的避免局部集優(yōu)。

第6步 對于?Gz∈G,根據(jù)(7)式計算出F值,并更新迭代變化后的細(xì)菌種群。

第7步 迭代循環(huán)結(jié)束條件判斷,若不滿足則更新發(fā)生變化的細(xì)菌種群并保存并繼續(xù)執(zhí)行第3步～第6步;若滿足則輸出結(jié)果,即最優(yōu)分組方式Gbest及其對應(yīng)的適應(yīng)度值F。

4 實驗仿真

4.1 參數(shù)設(shè)置

EBFO相關(guān)參數(shù)如表1所示。

表1 EBFO相關(guān)參數(shù)

細(xì)菌種群數(shù)目M=50,趨向性操作執(zhí)行次數(shù)Nc=20,細(xì)菌最大游動步長Ns=4,復(fù)制性操作次數(shù)Nre=4,遷徙及二次遷徙操作次數(shù)Ned=4,細(xì)菌發(fā)生遷徙概率Ped=0.25,二次遷徙概率prd=0.5。

4.2 仿真及結(jié)果分析

為測試EBFO算法的分組準(zhǔn)確性,選取表1中的5組數(shù)據(jù)集,取調(diào)節(jié)因子α=0.6,β=0.4,取30次迭代。分別用窮舉法(EM)、隨機法(RM)、細(xì)菌覓食算法(BFO)作為對比實驗并對每組數(shù)據(jù)運行10次求均值。實驗結(jié)果如表2所示。

表2 各算法實驗結(jié)果

當(dāng)N=10,N=50時,窮舉法(EM)得到的分組方式中F值最小,即組間與組內(nèi)特征相似度最高,但運行時間隨問題規(guī)模N增大其時間開銷過大,即不能用于大規(guī)模學(xué)生分組問題。隨機算法(RM)由于其隨機性,雖然分組速度很快,但是卻不能對分組模型進(jìn)行準(zhǔn)確的求解,導(dǎo)致分組性能太差。而EBFO算法中獲得的最優(yōu)分組方式中的F值此時也極接近最優(yōu)解。在5組數(shù)據(jù)集下,對于EBFO算法與基本BFO算法的比較,說明通過加入二次遷徙操作,使細(xì)菌種群多樣性在算法后期得以提高,更易于跳出局部集優(yōu)尋找最優(yōu)值,保證分組問題得到準(zhǔn)確解決。

為測試EBFO算法在分組形式不同時的分組性能,當(dāng)N=50時,在組間同質(zhì)情況下,即調(diào)節(jié)因子取α=0.1,β=0.9時用隨機法(RM),文獻(xiàn)[6]的遺傳算法(GA1)作為對比實驗。在組內(nèi)同質(zhì)情況下,即調(diào)節(jié)因子取α=0.9,β=0.1時用窮舉法(EM),隨機法(RM),文獻(xiàn)[4]中的遺傳算法(GA2),文獻(xiàn)[5]的粒子群算法(PSO)作為對比實驗。實驗結(jié)果如圖3、圖4所示。

圖3 ～中的小組均值(α=0.1,β=0.9)

圖4 ～中的小組均值(α=0.9,β=0.1)

由圖3可知,當(dāng)α=0.1,β=0.9,此時EBFO算法中小組均值曲線較RM算法與GA1算法曲線更平緩,即基于學(xué)習(xí)者的知識水平,學(xué)習(xí)效能的小組間差異度較小,小組獲得了更好的滿足分組要求的分組方式Gz,從教育學(xué)角度而言這更加保證學(xué)習(xí)計劃的完成和學(xué)習(xí)者共同達(dá)到學(xué)習(xí)目標(biāo)[15]。

由圖4可知,當(dāng)α=0.9,β=0.1,此時EBFO算法相對于RM算法、GA2算法和PSO算法獲得使各小組均值更小的分組方式Gz,使小組內(nèi)學(xué)習(xí)者基于學(xué)習(xí)者的學(xué)習(xí)興趣,學(xué)習(xí)動機,理解力水平的相似度更高,從教育學(xué)角度而言這更加提高學(xué)習(xí)者在學(xué)習(xí)過程中的積極性以便更好的交互[13]。

為測試EBFO算法對不同規(guī)模數(shù)據(jù)集的穩(wěn)定性,選取表1中的4組數(shù)據(jù)集,取調(diào)節(jié)因子α=0.6,β=0.4用偏差比作為收斂性的判斷標(biāo)準(zhǔn),即判斷迭代后函數(shù)值F與迭代過程中Fmax-Fmin的比值是否發(fā)生變化。

由圖5可知,本文EBFO算法對于4種不同數(shù)據(jù)集在一定的迭代次數(shù)后,均表現(xiàn)出一定的穩(wěn)定性。由此可得在學(xué)習(xí)者規(guī)模增加的情況下,EBFO算法也有很強的穩(wěn)定性。同時由偏差比的變化以及這4幅圖的結(jié)果,可以將EBFO算法的迭代次數(shù)定為30。

圖5 迭代次數(shù)偏差比對比

5 結(jié)束語

本文分析了學(xué)習(xí)者的特征屬性,考慮在協(xié)作學(xué)習(xí)分組過程中學(xué)習(xí)者的多個特征因素及其權(quán)值分配,采用改進(jìn)的細(xì)菌覓食算法對學(xué)習(xí)者進(jìn)行分組。實驗結(jié)果驗證了EBFO算法對分組問題求解的準(zhǔn)確性和穩(wěn)定性。此外,從教育學(xué)角度而言,由于教學(xué)活動的不同,通過EBFO算法調(diào)節(jié)組內(nèi)與組間同質(zhì)分組均獲得了良好的分組性能。但是在具體的教學(xué)活動中對學(xué)習(xí)者特征權(quán)值的確定,需要進(jìn)一步驗證。

[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.學(xué)習(xí)動機的激發(fā)策略[M].伍新春,譯.北京:中國輕工業(yè)出版社,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].北京:中國人民大學(xué)出版社,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

中央高校基本科研業(yè)務(wù)費專項基金資助項目(GK201002028,GK201101001);陜西師范大學(xué)學(xué)習(xí)科學(xué)交叉學(xué)科培育計劃基金資助項目。

桑治平(1988-),男,碩士研究生,主研方向:協(xié)作學(xué)習(xí):何聚厚(通訊作者),副教授、博士。

2013-10-22

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

中文引用格式:桑治平,何聚厚.基于改進(jìn)細(xì)菌覓食的協(xié)作學(xué)習(xí)分組算法[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.