胡慧,何聚厚,2
1.陜西師范大學計算機科學學院,西安710062
2.陜西師范大學現(xiàn)代教學技術(shù)教育部重點實驗室,西安710062
協(xié)作學習中根據(jù)學習者的特征進行有效分組,對于提高學習者的學習效率具有重要影響[1-2]。傳統(tǒng)的分組方式有隨機選擇法和窮舉法[3]。隨機選擇法并未考慮學習者的特征差異與具體的活動類型,易造成整體上的學習效率不高[4]。窮舉法在學習者個體數(shù)比較多且考慮學習者特征時,無法在短時間內(nèi)進行有效分組[5]。為此,Graf和Bekele于2006年,針對組內(nèi)異質(zhì)分組模型通過蟻群算法來解決分組問題[6];Hwanget等于2008年提出基于遺傳算法的分組模型[7]。這兩種方法雖然考慮了學習者的多個特征,但都沒有考慮活動類型及特征的權(quán)值對分組的影響。Lin等于2010年提出基于改進粒子群算法來解決分組問題[8],該算法僅考慮了學生的理解水平和興趣愛好兩個特征。
考慮學習者多個特征及根據(jù)活動類型的不同為不同特征賦予不同的權(quán)值,則協(xié)作學習中的分組問題變?yōu)槎嗄繕藘?yōu)化問題。本文在蟻群算法中將學習者特征相似度值作為啟發(fā)信息,并在初期融入判斷-回退機制構(gòu)造分組,增加分組的多樣性,避免算法出現(xiàn)早熟收斂現(xiàn)象;在中后期對信息啟發(fā)因子和期望因子進行動態(tài)調(diào)整,避免尋優(yōu)出現(xiàn)停滯現(xiàn)象。
在協(xié)作學習中,基于學習者特征的量化值,將N個學習者分為K組,其目標是使每組學習者在協(xié)作學習中學習效率最高。
定義1 學習者特征集合A定義為:
其中,La(Learning ability)學習能力,In(Interests)為興趣愛好,U l(Understanding level)為理解水平。對于某一學習者,通過測試過程f可以獲得對應特征的量化值。
定義2學習者集合S定義為:
引入特征權(quán)值控制不同特征在分組過程中的貢獻。
定義3 特征權(quán)值集合定義為:
且wL+wI+wU=1。wL、wI和wU分別是La、In和U l對應的權(quán)值。
學習者之間通過特征相似度進行量化比較。
定義4 學習者si和sj之間的特征相似度通過下式計算:
若sim(si,sj)越小,則si和sj之間的特征相似度越高。
將N個學習者分為K組,則所有的分組方式構(gòu)成分組空間。
定義5 分組空間為:
其中,M為分組方式的個數(shù)。對于每一種分組方式Gx,有:
其中,K為分組個數(shù)。對于某一分組方式Gx,若學習者si被分到了小組,為了敘述方便學習者記為,則。假定某一學習者只能被分到一個小組,且所有的學習者都會被分到某一分組,因此對于和,有:
引入特征平均值作為度量分組準確性的參考值。
定義6 對于分組方式Gx,其特征平均值集合Cx定義為:
定義7 協(xié)作學習中的分組問題定義為:
即分組過程為基于學習者特征集合A,特征權(quán)值集合W和學習者集合S在分組空間Groups中確定最佳分組方式Gx的過程。為此,Gx需滿足如下條件。
目標函數(shù):
約束條件:
在目標函數(shù)表達式中,F(xiàn)值表示分組方式Gx中各小組均方差之和,該值越小,則說明在Gx中∈Gx的各組內(nèi)均方差越小,即同一小組內(nèi)學習者特征相似度越高。
約束條件(10)和(11)保證了N個學習者都會被分到某一小組中;約束條件(12)保證了每位學習者只能被分到某一個小組中;約束條件(13)限制了小組之間人數(shù)相差不超過一人。
故分組問題的求解即在滿足上述約束條件的前提下,在分組空間Groups中找到使目標函數(shù)值F最小的分組方式Gx,使分組后學習者的學習效率最優(yōu)。
算法首先初始化相關(guān)參數(shù)并根據(jù)定義4計算出N個學習者兩兩之間的相似度值。通過迭代選擇最優(yōu)分組的過程為:將R只螞蟻按照判斷-回退的機制從集合S中選擇起始學習者,并按照轉(zhuǎn)移概率公式選擇下一個學習者,直到將N個學習者遍歷完即形成R種分組方式,計算各組F值并獲得當代最優(yōu)分組方式。按照max-m in機制更新全局信息素,并計算相鄰兩代之間最優(yōu)值的差值ΔF,如果小于某一閾值,則通過改變轉(zhuǎn)移概率公式中的f1和f2的值動態(tài)調(diào)節(jié)啟發(fā)因子和期望因子。如果迭代次數(shù)大于最大迭代次數(shù)閾值t_max,停止迭代并輸出F值最小的分組方式Gbest。
算法步驟:
步驟1 初始化參數(shù)。
獲取N個si∈S:{s1,s2,…,si,…,sN},分別通過函數(shù)
將N個學習者個體的特征La、In、U l量化值變換到[0,1];初始化相關(guān)參數(shù):最大迭代次數(shù)t_max,螞蟻數(shù)R,信息素初始化矩陣Matrix1N×N,信息素揮發(fā)概率ρ等。
步驟2 計算學習者特征相似度。
根據(jù)定義4分別計算個體si與其他學習者的相似度值sim(si,sj)?,并存儲于矩陣Matrix2N×N中:
因Matrix2N×N具有對稱性,故只需填充矩陣上三角的相似度值。
步驟3 選擇起始學習者個體。
采用數(shù)組p記錄每只螞蟻起始學習者的編號。為避免螞蟻個體尋優(yōu)時對同一學習者重復選擇,采用禁忌表tabuk記錄已選學習者。偽代碼如下:
for每只螞蟻
{從集合S中任意選取學習者si作為起點;
if(si編號未在數(shù)組p中)
將si的編號存于起始數(shù)組p中;
p=[i];
將si存于禁忌表tabuk中;
tabuk=[si],以si為起點構(gòu)造分組方式Gx;
else
從集合S中重新選取學習者sj;
跳轉(zhuǎn)到if語句重新判斷;
}
步驟4 根據(jù)轉(zhuǎn)移概率公式選擇路徑。
在狀態(tài)轉(zhuǎn)移概率公式中添加了兩個調(diào)節(jié)因子f1和f2,當相鄰兩代函數(shù)值F差值小于某一閾值q時,則通過f1和f2分別對啟發(fā)因子α和期望因子β進行動態(tài)調(diào)節(jié)。轉(zhuǎn)移概率公式如下:
螞蟻按照公式(14)選擇與當前學習者si相似度最大的sj移動。在螞蟻移動過程中,將對學習者sj分配小組號,其偽代碼如下:
執(zhí)行上述四步,直到每只螞蟻將N個學習者遍歷完,則?si∈S都被分到某一小組g(x)y∈Gx中,形成分組空間Groups={Gx|x=1,2,…,R}。
步驟5 更新局部信息素。
對于?Gx∈Groups,根據(jù)式(9)計算出F值,按照公式(15)更新局部信息素:
步驟6 比較?Gx中F值的大小,獲得此次迭代的最佳分組方式Gx。
步驟7 結(jié)合max-m in機制更新全局信息素。
按照公式(16)對全局信息素進行更新:
為避免某些路徑可能長時間沒有螞蟻經(jīng)過導致信息素為0,使算法陷入局部最優(yōu),本文對信息素的最大最小值進行了限制,在保留優(yōu)秀解的同時增加分組方式的多樣性。
步驟8 如果ΔF<q,則調(diào)整f1'=f1+Δf1,f2'=f2+Δf2;否則,f1、f2保持不變。
步驟9 置t?:=t+1,若t<t_max,信息素增量歸0,轉(zhuǎn)步驟3;否則,算法結(jié)束,并輸出F值最小的分組方式Gbest。
實驗采用M atlab7.0實現(xiàn)該算法。N∈[10,50],小組人數(shù)為5人[9],學習者特征La、In、U l的量化采用產(chǎn)生隨機數(shù)的方法,再通過函數(shù)f將量化值轉(zhuǎn)換到[0,1]區(qū)間;特征權(quán)重值為W={0.2,0.5,0.3}。EACO相關(guān)參數(shù)設置如表1所示。
信息素揮發(fā)概率:ρ=0.4;調(diào)節(jié)因子初值:f1=1,f2=1;增量值:Δf1=0.05,Δf2=-0.03;啟發(fā)因子:α=2;期望因子:β=2;信息增量初值Δτ=0;R=2/3×N[10]。
為驗證EACO算法分組的準確性,本文選取4.1節(jié)中的三組數(shù)據(jù)分別用窮舉法(EM)、隨機選擇法(Ran-dom)、基本蟻群算法(ACO)做對比實驗。
表1 實驗參數(shù)表
當N=10時,EM算法(實線)、ACO算法(虛線)和EACO算法(點畫線)的實驗結(jié)果如圖1所示。
圖1 和組內(nèi)F值(N=10)
由圖1可見,此時窮舉法得到的最佳分組方式中各小組的F值最小,組內(nèi)學習者的特征相似度最高。但該方法只能應用于少數(shù)學習者,具有很大的局限性。而EACO算法獲得的最優(yōu)分組方式中各小組的F值此時也極接近最優(yōu)值。
當N=25和N=50時,Random算法(實線)、ACO算法(虛線)和EACO算法(點畫線)的實驗結(jié)果,分別如圖2和圖3所示。
圖3 ~組內(nèi)F值(N=50)
學習者之間的有效交互是提高協(xié)作學習效率的基本條件之一[11-12]?;趯W習者的學習能力、興趣愛好和理解水平,采用EACO算法更準確地將特征最相似的個體分在同一小組,促進了學習者更充分地討論、交流,不會導致個別學習者因?qū)φn題缺乏興趣或者學習能力、理解水平太低而孤立[13]。此外,教育者可視各組學習者的興趣愛好、學習能力和理解水平的不同,為各組學習者安排不同類型、不同難易程度的協(xié)作活動,這更加促進了學習者之間交互的積極性[8]。從教育心理學角度而言,學習者往往更傾向于與興趣愛好相同的伙伴在一起學習[14]。因此在考慮學習者學習能力和理解水平的同時,結(jié)合其興趣愛好也是令學習者更滿意的分組方式。由圖2和圖3可見,EACO算法相對于傳統(tǒng)算法能夠獲得使各小組F值更小的分組方式Gx,使小組內(nèi)學習者的特征相似度更高,這有利于學習者之間更好的交流,提高學習效率。
為測試EACO算法的時間性能,對4.1節(jié)中的每組數(shù)據(jù)做10次測試,選取重復率最高的結(jié)果作為最終記錄,并分別與EM算法、Random算法和ACO算法做比較。結(jié)果如表2、表3和表4所示。
表2 EM算法和EACO算法實驗結(jié)果
表3 Random算法和EACO算法實驗結(jié)果
表4 ACO和EACO算法實驗結(jié)果
基于學習者的學習能力、興趣愛好和理解水平,使用窮舉法和文獻[6]中提出的蟻群算法在時間性能上均不如EACO算法,而隨機選擇法雖分組速度很快,但因缺乏分組的教育學理論依據(jù),導致分組性能太差。
基于學習者的學習能力、興趣愛好和理解水平,本文采用改進蟻群算法對學習者進行分組,分組性能通過組內(nèi)均方差來判斷,該值越小,則各小組內(nèi)個體特征相似度越高,即分組越有效。實驗中選用了三組模擬數(shù)據(jù)集進行測試,結(jié)果表明本文算法較傳統(tǒng)算法分組結(jié)果更準確。此外,從教育學角度而言,通過EACO算法將學習能力、興趣愛好和理解水平接近的學習者分在同組,有助于學習者之間更充分、有效地交互進而提高學習效率。教育者也可根據(jù)教學目標的不同,基于EACO算法考慮多個不同的學生特征及其權(quán)值分配。但對于大規(guī)模學習者分組問題,本文算法需要的求解時間有待進一步縮短。
[1]M cCombs B L,Pope J E.學習動機的激發(fā)策略[M].伍新春,秦憲剛,張潔,譯.北京:中國輕工業(yè)出版社,2002:70-85.
[2]李潔,李克東.CSCL中協(xié)作小組分組系統(tǒng)的設計與開發(fā)研究[D].廣州:華南師范大學,2005.
[3]Huxham M,Land R.Assigning students in Group Work projects:can we do better than random?[J].Innovations in Education and Training International,2000,37(1):17-22.
[4]Lou Y.within-class grouping:a meta-analysis[J].Review of Educational Research,1996,66(4):423-458.
[5]M oreno J,Ovalle D A,Vicari R M.A genetic algorithm approach for group formation in collaborative learning considering multiple student characteristics[J].Computers&Education,2012,58(1):560-569.
[6]Bekele G S.Forming heterogeneous group for intelligent collaborative learning systems with ant colony optimization[C]//Proceedings of the 8th International Conference on Intelligent Tutoring Systems,Taiwan,China,June 26-30,2006,4053(22):217-226.
[7]Hwang G J.An enhanced genetic approach to composing cooperative learning groups for multiple grouping criteria[J].Educational technology&Society,2008,11(1):148-169.
[8]Lin Y T.An automatic group composition system for composing collaborative learning groups using enhanced particle swarm optimization[J].Computers&Education,2010,55(4):1483-1493.
[9]Gall M D.Discussion method[M]//Dunkin M J.The International Encyclopedia of Teaching and Teacher Education.Oxford,England:University of Oxford,1987:232-237.
[10]段海濱.蟻群算法原理及其應用[M].北京:科學出版社,2005:108.
[11]Johnson D W.Cooperation in the classroom[M].Edina,MN:Interaction Book Company,1984:101-118.
[12]Slavin R E.Cooperative learning:theory,research,and practice[M].Boston:Allyn and Bacon,1995:180-195.
[13]Yang S JH.Context aware ubiquitous learning environments for peer-to-peer collaborative learning[J].Journal of Educational Technology&Society,2006,9(1):188-201.
[14]Wang D Y.DIANA:a computer-supported heterogeneous grouping system for teachers to conduct successful small learning groups[J].Computers in Human Behavior,2007,23(4):2-14.