基于改進(jìn)蟻群算法的協(xié)作學(xué)習(xí)分組研究

胡慧，何聚厚，2

1.陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，西安710062

2.陜西師范大學(xué)現(xiàn)代教學(xué)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，西安710062

1 引言

協(xié)作學(xué)習(xí)中根據(jù)學(xué)習(xí)者的特征進(jìn)行有效分組，對(duì)于提高學(xué)習(xí)者的學(xué)習(xí)效率具有重要影響[1-2]。傳統(tǒng)的分組方式有隨機(jī)選擇法和窮舉法[3]。隨機(jī)選擇法并未考慮學(xué)習(xí)者的特征差異與具體的活動(dòng)類型，易造成整體上的學(xué)習(xí)效率不高[4]。窮舉法在學(xué)習(xí)者個(gè)體數(shù)比較多且考慮學(xué)習(xí)者特征時(shí)，無法在短時(shí)間內(nèi)進(jìn)行有效分組[5]。為此，Graf和Bekele于2006年，針對(duì)組內(nèi)異質(zhì)分組模型通過蟻群算法來解決分組問題[6]；Hwanget等于2008年提出基于遺傳算法的分組模型[7]。這兩種方法雖然考慮了學(xué)習(xí)者的多個(gè)特征，但都沒有考慮活動(dòng)類型及特征的權(quán)值對(duì)分組的影響。Lin等于2010年提出基于改進(jìn)粒子群算法來解決分組問題[8]，該算法僅考慮了學(xué)生的理解水平和興趣愛好兩個(gè)特征。

考慮學(xué)習(xí)者多個(gè)特征及根據(jù)活動(dòng)類型的不同為不同特征賦予不同的權(quán)值，則協(xié)作學(xué)習(xí)中的分組問題變?yōu)槎嗄繕?biāo)優(yōu)化問題。本文在蟻群算法中將學(xué)習(xí)者特征相似度值作為啟發(fā)信息，并在初期融入判斷-回退機(jī)制構(gòu)造分組，增加分組的多樣性，避免算法出現(xiàn)早熟收斂現(xiàn)象；在中后期對(duì)信息啟發(fā)因子和期望因子進(jìn)行動(dòng)態(tài)調(diào)整，避免尋優(yōu)出現(xiàn)停滯現(xiàn)象。

2 分組問題描述

在協(xié)作學(xué)習(xí)中，基于學(xué)習(xí)者特征的量化值，將N個(gè)學(xué)習(xí)者分為K組，其目標(biāo)是使每組學(xué)習(xí)者在協(xié)作學(xué)習(xí)中學(xué)習(xí)效率最高。

定義1 學(xué)習(xí)者特征集合A定義為：

其中，La（Learning ability）學(xué)習(xí)能力，In（Interests）為興趣愛好，U l（Understanding level）為理解水平。對(duì)于某一學(xué)習(xí)者，通過測試過程f可以獲得對(duì)應(yīng)特征的量化值。

定義2學(xué)習(xí)者集合S定義為：

引入特征權(quán)值控制不同特征在分組過程中的貢獻(xiàn)。

定義3 特征權(quán)值集合定義為：

且wL+wI+wU=1。wL、wI和wU分別是La、In和U l對(duì)應(yīng)的權(quán)值。

學(xué)習(xí)者之間通過特征相似度進(jìn)行量化比較。

定義4 學(xué)習(xí)者si和sj之間的特征相似度通過下式計(jì)算：

若sim(si，sj)越小，則si和sj之間的特征相似度越高。

將N個(gè)學(xué)習(xí)者分為K組，則所有的分組方式構(gòu)成分組空間。

定義5 分組空間為：

其中，M為分組方式的個(gè)數(shù)。對(duì)于每一種分組方式Gx，有：

其中，K為分組個(gè)數(shù)。對(duì)于某一分組方式Gx，若學(xué)習(xí)者si被分到了小組，為了敘述方便學(xué)習(xí)者記為，則。假定某一學(xué)習(xí)者只能被分到一個(gè)小組，且所有的學(xué)習(xí)者都會(huì)被分到某一分組，因此對(duì)于和，有：

引入特征平均值作為度量分組準(zhǔn)確性的參考值。

定義6 對(duì)于分組方式Gx，其特征平均值集合Cx定義為：

定義7 協(xié)作學(xué)習(xí)中的分組問題定義為：

即分組過程為基于學(xué)習(xí)者特征集合A，特征權(quán)值集合W和學(xué)習(xí)者集合S在分組空間Groups中確定最佳分組方式Gx的過程。為此，Gx需滿足如下條件。

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

約束條件：

在目標(biāo)函數(shù)表達(dá)式中，F(xiàn)值表示分組方式Gx中各小組均方差之和，該值越小，則說明在Gx中∈Gx的各組內(nèi)均方差越小，即同一小組內(nèi)學(xué)習(xí)者特征相似度越高。

約束條件（10）和（11）保證了N個(gè)學(xué)習(xí)者都會(huì)被分到某一小組中；約束條件（12）保證了每位學(xué)習(xí)者只能被分到某一個(gè)小組中；約束條件（13）限制了小組之間人數(shù)相差不超過一人。

故分組問題的求解即在滿足上述約束條件的前提下，在分組空間Groups中找到使目標(biāo)函數(shù)值F最小的分組方式Gx，使分組后學(xué)習(xí)者的學(xué)習(xí)效率最優(yōu)。

3 EACO算法分組過程描述

算法首先初始化相關(guān)參數(shù)并根據(jù)定義4計(jì)算出N個(gè)學(xué)習(xí)者兩兩之間的相似度值。通過迭代選擇最優(yōu)分組的過程為：將R只螞蟻按照判斷-回退的機(jī)制從集合S中選擇起始學(xué)習(xí)者，并按照轉(zhuǎn)移概率公式選擇下一個(gè)學(xué)習(xí)者，直到將N個(gè)學(xué)習(xí)者遍歷完即形成R種分組方式，計(jì)算各組F值并獲得當(dāng)代最優(yōu)分組方式。按照max-m in機(jī)制更新全局信息素，并計(jì)算相鄰兩代之間最優(yōu)值的差值ΔF，如果小于某一閾值，則通過改變轉(zhuǎn)移概率公式中的f1和f2的值動(dòng)態(tài)調(diào)節(jié)啟發(fā)因子和期望因子。如果迭代次數(shù)大于最大迭代次數(shù)閾值t_max，停止迭代并輸出F值最小的分組方式Gbest。

算法步驟：

步驟1 初始化參數(shù)。

獲取N個(gè)si∈S:{s1，s2，…，si，…，sN}，分別通過函數(shù)

將N個(gè)學(xué)習(xí)者個(gè)體的特征La、In、U l量化值變換到[0，1]；初始化相關(guān)參數(shù)：最大迭代次數(shù)t_max，螞蟻數(shù)R，信息素初始化矩陣Matrix1N×N，信息素?fù)]發(fā)概率ρ等。

步驟2 計(jì)算學(xué)習(xí)者特征相似度。

根據(jù)定義4分別計(jì)算個(gè)體si與其他學(xué)習(xí)者的相似度值sim(si，sj)?，并存儲(chǔ)于矩陣Matrix2N×N中：

因Matrix2N×N具有對(duì)稱性，故只需填充矩陣上三角的相似度值。

步驟3 選擇起始學(xué)習(xí)者個(gè)體。

采用數(shù)組p記錄每只螞蟻起始學(xué)習(xí)者的編號(hào)。為避免螞蟻個(gè)體尋優(yōu)時(shí)對(duì)同一學(xué)習(xí)者重復(fù)選擇，采用禁忌表tabuk記錄已選學(xué)習(xí)者。偽代碼如下：

for每只螞蟻

{從集合S中任意選取學(xué)習(xí)者si作為起點(diǎn)；

if（si編號(hào)未在數(shù)組p中）

將si的編號(hào)存于起始數(shù)組p中；

p=[i]；

將si存于禁忌表tabuk中；

tabuk=[si]，以si為起點(diǎn)構(gòu)造分組方式Gx；

else

從集合S中重新選取學(xué)習(xí)者sj；

跳轉(zhuǎn)到if語句重新判斷；

}

步驟4 根據(jù)轉(zhuǎn)移概率公式選擇路徑。

在狀態(tài)轉(zhuǎn)移概率公式中添加了兩個(gè)調(diào)節(jié)因子f1和f2，當(dāng)相鄰兩代函數(shù)值F差值小于某一閾值q時(shí)，則通過f1和f2分別對(duì)啟發(fā)因子α和期望因子β進(jìn)行動(dòng)態(tài)調(diào)節(jié)。轉(zhuǎn)移概率公式如下：

螞蟻按照公式（14）選擇與當(dāng)前學(xué)習(xí)者si相似度最大的sj移動(dòng)。在螞蟻移動(dòng)過程中，將對(duì)學(xué)習(xí)者sj分配小組號(hào)，其偽代碼如下：

執(zhí)行上述四步，直到每只螞蟻將N個(gè)學(xué)習(xí)者遍歷完，則?si∈S都被分到某一小組g(x)y∈Gx中，形成分組空間Groups={Gx|x=1，2，…，R}。

步驟5 更新局部信息素。

對(duì)于?Gx∈Groups，根據(jù)式（9）計(jì)算出F值，按照公式（15）更新局部信息素：

步驟6 比較?Gx中F值的大小，獲得此次迭代的最佳分組方式Gx。

步驟7 結(jié)合max-m in機(jī)制更新全局信息素。

按照公式（16）對(duì)全局信息素進(jìn)行更新：

為避免某些路徑可能長時(shí)間沒有螞蟻經(jīng)過導(dǎo)致信息素為0，使算法陷入局部最優(yōu)，本文對(duì)信息素的最大最小值進(jìn)行了限制，在保留優(yōu)秀解的同時(shí)增加分組方式的多樣性。

步驟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。

4 實(shí)驗(yàn)及結(jié)果分析

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

實(shí)驗(yàn)采用M atlab7.0實(shí)現(xiàn)該算法。N∈[10，50]，小組人數(shù)為5人[9]，學(xué)習(xí)者特征La、In、U l的量化采用產(chǎn)生隨機(jī)數(shù)的方法，再通過函數(shù)f將量化值轉(zhuǎn)換到[0，1]區(qū)間；特征權(quán)重值為W={0.2，0.5，0.3}。EACO相關(guān)參數(shù)設(shè)置如表1所示。

信息素?fù)]發(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]。

4.2 EACO性能分析

為驗(yàn)證EACO算法分組的準(zhǔn)確性，本文選取4.1節(jié)中的三組數(shù)據(jù)分別用窮舉法（EM）、隨機(jī)選擇法（Ran-dom）、基本蟻群算法（ACO）做對(duì)比實(shí)驗(yàn)。

表1 實(shí)驗(yàn)參數(shù)表

當(dāng)N=10時(shí)，EM算法（實(shí)線）、ACO算法（虛線）和EACO算法（點(diǎn)畫線）的實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 和組內(nèi)F值(N=10)

由圖1可見，此時(shí)窮舉法得到的最佳分組方式中各小組的F值最小，組內(nèi)學(xué)習(xí)者的特征相似度最高。但該方法只能應(yīng)用于少數(shù)學(xué)習(xí)者，具有很大的局限性。而EACO算法獲得的最優(yōu)分組方式中各小組的F值此時(shí)也極接近最優(yōu)值。

當(dāng)N=25和N=50時(shí)，Random算法（實(shí)線）、ACO算法（虛線）和EACO算法（點(diǎn)畫線）的實(shí)驗(yàn)結(jié)果，分別如圖2和圖3所示。

圖3 ～組內(nèi)F值(N=50)

學(xué)習(xí)者之間的有效交互是提高協(xié)作學(xué)習(xí)效率的基本條件之一[11-12]。基于學(xué)習(xí)者的學(xué)習(xí)能力、興趣愛好和理解水平，采用EACO算法更準(zhǔn)確地將特征最相似的個(gè)體分在同一小組，促進(jìn)了學(xué)習(xí)者更充分地討論、交流，不會(huì)導(dǎo)致個(gè)別學(xué)習(xí)者因?qū)φn題缺乏興趣或者學(xué)習(xí)能力、理解水平太低而孤立[13]。此外，教育者可視各組學(xué)習(xí)者的興趣愛好、學(xué)習(xí)能力和理解水平的不同，為各組學(xué)習(xí)者安排不同類型、不同難易程度的協(xié)作活動(dòng)，這更加促進(jìn)了學(xué)習(xí)者之間交互的積極性[8]。從教育心理學(xué)角度而言，學(xué)習(xí)者往往更傾向于與興趣愛好相同的伙伴在一起學(xué)習(xí)[14]。因此在考慮學(xué)習(xí)者學(xué)習(xí)能力和理解水平的同時(shí)，結(jié)合其興趣愛好也是令學(xué)習(xí)者更滿意的分組方式。由圖2和圖3可見，EACO算法相對(duì)于傳統(tǒng)算法能夠獲得使各小組F值更小的分組方式Gx，使小組內(nèi)學(xué)習(xí)者的特征相似度更高，這有利于學(xué)習(xí)者之間更好的交流，提高學(xué)習(xí)效率。

為測試EACO算法的時(shí)間性能，對(duì)4.1節(jié)中的每組數(shù)據(jù)做10次測試，選取重復(fù)率最高的結(jié)果作為最終記錄，并分別與EM算法、Random算法和ACO算法做比較。結(jié)果如表2、表3和表4所示。

表2 EM算法和EACO算法實(shí)驗(yàn)結(jié)果

表3 Random算法和EACO算法實(shí)驗(yàn)結(jié)果

表4 ACO和EACO算法實(shí)驗(yàn)結(jié)果

基于學(xué)習(xí)者的學(xué)習(xí)能力、興趣愛好和理解水平，使用窮舉法和文獻(xiàn)[6]中提出的蟻群算法在時(shí)間性能上均不如EACO算法，而隨機(jī)選擇法雖分組速度很快，但因缺乏分組的教育學(xué)理論依據(jù)，導(dǎo)致分組性能太差。

5 結(jié)束語

基于學(xué)習(xí)者的學(xué)習(xí)能力、興趣愛好和理解水平，本文采用改進(jìn)蟻群算法對(duì)學(xué)習(xí)者進(jìn)行分組，分組性能通過組內(nèi)均方差來判斷，該值越小，則各小組內(nèi)個(gè)體特征相似度越高，即分組越有效。實(shí)驗(yàn)中選用了三組模擬數(shù)據(jù)集進(jìn)行測試，結(jié)果表明本文算法較傳統(tǒng)算法分組結(jié)果更準(zhǔn)確。此外，從教育學(xué)角度而言，通過EACO算法將學(xué)習(xí)能力、興趣愛好和理解水平接近的學(xué)習(xí)者分在同組，有助于學(xué)習(xí)者之間更充分、有效地交互進(jìn)而提高學(xué)習(xí)效率。教育者也可根據(jù)教學(xué)目標(biāo)的不同，基于EACO算法考慮多個(gè)不同的學(xué)生特征及其權(quán)值分配。但對(duì)于大規(guī)模學(xué)習(xí)者分組問題，本文算法需要的求解時(shí)間有待進(jìn)一步縮短。

[1]M cCombs B L，Pope J E.學(xué)習(xí)動(dòng)機(jī)的激發(fā)策略[M].伍新春，秦憲剛，張潔，譯.北京：中國輕工業(yè)出版社，2002：70-85.

[2]李潔，李克東.CSCL中協(xié)作小組分組系統(tǒng)的設(shè)計(jì)與開發(fā)研究[D].廣州：華南師范大學(xué)，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]段海濱.蟻群算法原理及其應(yīng)用[M].北京：科學(xué)出版社，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.