基于改進蟻群算法的協作學習分組研究

胡慧，何聚厚，2

1.陜西師范大學計算機科學學院，西安710062

2.陜西師范大學現代教學技術教育部重點實驗室，西安710062

1 引言

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

考慮學習者多個特征及根據活動類型的不同為不同特征賦予不同的權值，則協作學習中的分組問題變為多目標優化問題。本文在蟻群算法中將學習者特征相似度值作為啟發信息，并在初期融入判斷-回退機制構造分組，增加分組的多樣性，避免算法出現早熟收斂現象；在中后期對信息啟發因子和期望因子進行動態調整，避免尋優出現停滯現象。

2 分組問題描述

在協作學習中，基于學習者特征的量化值，將N個學習者分為K組，其目標是使每組學習者在協作學習中學習效率最高。

定義1 學習者特征集合A定義為：

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

定義2學習者集合S定義為：

引入特征權值控制不同特征在分組過程中的貢獻。

定義3 特征權值集合定義為：

且wL+wI+wU=1。wL、wI和wU分別是La、In和U l對應的權值。

學習者之間通過特征相似度進行量化比較。

定義4 學習者si和sj之間的特征相似度通過下式計算：

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

將N個學習者分為K組，則所有的分組方式構成分組空間。

定義5 分組空間為：

其中，M為分組方式的個數。對于每一種分組方式Gx，有：

其中，K為分組個數。對于某一分組方式Gx，若學習者si被分到了小組，為了敘述方便學習者記為，則。假定某一學習者只能被分到一個小組，且所有的學習者都會被分到某一分組，因此對于和，有：

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

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

定義7 協作學習中的分組問題定義為：

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

目標函數：

約束條件：

在目標函數表達式中，F值表示分組方式Gx中各小組均方差之和，該值越小，則說明在Gx中∈Gx的各組內均方差越小，即同一小組內學習者特征相似度越高。

約束條件（10）和（11）保證了N個學習者都會被分到某一小組中；約束條件（12）保證了每位學習者只能被分到某一個小組中；約束條件（13）限制了小組之間人數相差不超過一人。

故分組問題的求解即在滿足上述約束條件的前提下，在分組空間Groups中找到使目標函數值F最小的分組方式Gx，使分組后學習者的學習效率最優。

3 EACO算法分組過程描述

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

算法步驟：

步驟1 初始化參數。

獲取N個si∈S:{s1，s2，…，si，…，sN}，分別通過函數

將N個學習者個體的特征La、In、U l量化值變換到[0，1]；初始化相關參數：最大迭代次數t_max，螞蟻數R，信息素初始化矩陣Matrix1N×N，信息素揮發概率ρ等。

步驟2 計算學習者特征相似度。

根據定義4分別計算個體si與其他學習者的相似度值sim(si，sj)?，并存儲于矩陣Matrix2N×N中：

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

步驟3 選擇起始學習者個體。

采用數組p記錄每只螞蟻起始學習者的編號。為避免螞蟻個體尋優時對同一學習者重復選擇，采用禁忌表tabuk記錄已選學習者。偽代碼如下：

for每只螞蟻

{從集合S中任意選取學習者si作為起點；

if（si編號未在數組p中）

將si的編號存于起始數組p中；

p=[i]；

將si存于禁忌表tabuk中；

tabuk=[si]，以si為起點構造分組方式Gx；

else

從集合S中重新選取學習者sj；

跳轉到if語句重新判斷；

}

步驟4 根據轉移概率公式選擇路徑。

在狀態轉移概率公式中添加了兩個調節因子f1和f2，當相鄰兩代函數值F差值小于某一閾值q時，則通過f1和f2分別對啟發因子α和期望因子β進行動態調節。轉移概率公式如下：

螞蟻按照公式（14）選擇與當前學習者si相似度最大的sj移動。在螞蟻移動過程中，將對學習者sj分配小組號，其偽代碼如下：

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

步驟5 更新局部信息素。

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

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

步驟7 結合max-m in機制更新全局信息素。

按照公式（16）對全局信息素進行更新：

為避免某些路徑可能長時間沒有螞蟻經過導致信息素為0，使算法陷入局部最優，本文對信息素的最大最小值進行了限制，在保留優秀解的同時增加分組方式的多樣性。

步驟8 如果ΔF＜q，則調整f1'=f1+Δf1，f2'=f2+Δf2；否則，f1、f2保持不變。

步驟9 置t?:=t+1，若t＜t_max，信息素增量歸0，轉步驟3；否則，算法結束，并輸出F值最小的分組方式Gbest。

4 實驗及結果分析

4.1 參數設置

實驗采用M atlab7.0實現該算法。N∈[10，50]，小組人數為5人[9]，學習者特征La、In、U l的量化采用產生隨機數的方法，再通過函數f將量化值轉換到[0，1]區間；特征權重值為W={0.2，0.5，0.3}。EACO相關參數設置如表1所示。

信息素揮發概率：ρ=0.4；調節因子初值：f1=1，f2=1；增量值：Δf1=0.05，Δf2=-0.03；啟發因子：α=2；期望因子：β=2；信息增量初值Δτ=0；R=2/3×N[10]。

4.2 EACO性能分析

為驗證EACO算法分組的準確性，本文選取4.1節中的三組數據分別用窮舉法（EM）、隨機選擇法（Ran-dom）、基本蟻群算法（ACO）做對比實驗。

表1 實驗參數表

當N=10時，EM算法（實線）、ACO算法（虛線）和EACO算法（點畫線）的實驗結果如圖1所示。

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

由圖1可見，此時窮舉法得到的最佳分組方式中各小組的F值最小，組內學習者的特征相似度最高。但該方法只能應用于少數學習者，具有很大的局限性。而EACO算法獲得的最優分組方式中各小組的F值此時也極接近最優值。

當N=25和N=50時，Random算法（實線）、ACO算法（虛線）和EACO算法（點畫線）的實驗結果，分別如圖2和圖3所示。

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

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

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

表2 EM算法和EACO算法實驗結果

表3 Random算法和EACO算法實驗結果

表4 ACO和EACO算法實驗結果

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

5 結束語

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

[1]M cCombs B L，Pope J E.學習動機的激發策略[M].伍新春，秦憲剛，張潔，譯.北京：中國輕工業出版社，2002：70-85.

[2]李潔，李克東.CSCL中協作小組分組系統的設計與開發研究[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.