基于遺傳算法的分組算法

李 峰， 王海英

（東北石油大學 計算機科學系，黑龍江 大慶 163311）

1 分組策略

協作學習過程中，教師要依據學生個人特征和分組策略進行合理分組。學生通過測試可以得到一些個人特征，每次的學習活動也將被記錄檔案，這都是分組的重要依據。每小組一般以3～6人為宜，每組選一個組長。分組時，可以有意識的根據學習者特征進行優化組合，優差生共同進步。讓學生充分發揮自身優勢的同時，在某些弱勢方面教師也要分配其適量的任務，并加以輔導協助，循序漸進，使其得到鍛煉、增加自信心。經過教學分析和實踐檢驗，得到分組時應從以下兩方面考慮。

1.1 組內異質，組間同質[1]

組內異質指小組成員間在專業知識、年齡、性別、學習風格、學習動機等方面具有差異性，組間同質指各小組之間大體均衡，這樣小組間才有可比性。組內異質可為小組成員之間的互助協作奠定基礎，而組間同質又可為各小組間的公平競爭創造條件。

1.2 公平競爭、合理比較

組員間既存在協作也存在良性競爭，為了能讓小組取得好成績，組員們都會盡自己最大努力。組間的競爭使得學習者之間更具有凝聚力，能夠充分發揮出團隊的作用。在分組時，要注意公平合理，避免學生因感到人員分配不合理而喪失積極性。

2 基于遺傳算法的分組算法

前面已經介紹了分組的重要性，也介紹了一些理論及注意事項。若是教師對所教授班級的學生不算了解，分組則會帶來一定的風險。在研究了一些現有分組算法如楊友林[2]提出的“基于模糊C均值算法”、李杰[3]的“最優化理論算法”后，文中提出了“基于遺傳算法的自動分組”的算法。與張春玲[4]的遺傳算法分組不同，算法在編碼的定義、適應度函數的計算、遺傳操作等方面都有所改變。算法嚴格遵循“組間同質，組內異質”的分組原則，并在初始化序列、組長選擇方面做了一些優化。遺傳算法是一種通過模擬自然進化過程搜索最優解的方法，1975年，J.Holland教授首先提出并出版了頗有影響的專著《Adaptation in Natural and Artificial Systems》，GA這個名稱才逐漸為人所知，J.Holland教授所提出的GA通常為簡單遺傳算法（SGA）[5]。遺傳算法是一種基于自然選擇和自然遺傳的全局優化算法，用遺傳算法對多個個體組成的群體進行操作，通過遺傳算子可以使個體間的信息得以交換，這樣的群體中的個體一代一代地得以優化，并逐步逼近最優解[6]。遺傳算法分組效果的好壞關鍵是適應度函數的選取，而執行時間與初始序列有很大的關系，文中針對這兩方面在算法上做了一些優化改進。

具體分組過程：

依據每個學生的特征，本著“組內異質，組間同質”的原則進行分組，本次分組主要考慮學生特征中的學習風格、學習動機、學科背景和協作能力。學習風格通過附錄試卷測試測出學習者屬于“活躍型與沉思型、感悟型與直覺型、視覺型與言語型、序列型與綜合型[7]”中的哪4種類型（每組會得出一種類型）；學習動機通過附錄試卷測出學習者屬于“動機強”、“動機中”還是“動機弱”，并給出具體分值；學科背景則從學校教務系統中導出學生成績，將本次協作涉及到的學科成績取平均值作為學生的一個特征向量（百分制）；協作能力分值可以從上一次協作評價記錄中提取，若初次使用這種協作學習方式則默認為60分。這樣就可以用四元組對學習者進行描述：學習者（學習成績，學習風格，學習動機，協作能力）規定符號表示為L（A，S，M，C）。學習成績和協作能力我們已經量化，學習動機分數也可以從測試卷中得到（滿分36分，計算時可轉換為百分制），學習風格本身是用一個四維向量描述的，且各個向量沒有相互關系。為方便遺傳算法做差異計算，規定“活躍型、感悟型、視覺型、序列型”用“1”表示，“沉思型、直覺型、言語型、綜合型”用“0”表示，例如一個學習者是“活躍型、感悟型、視覺型、序列型”，可以用“10101010”表示，兩個學習者做“與運算”，可以通過累計“1”的數量來量化學習者間的風格差異。如果運算后沒有“1”，表示無差異，認為兩個學習者風格相同，若風格完全不同，則會出現4個“1”，差異值為100分。為了算法排序計算方便，將學習者風格“活躍型、感悟型、視覺型、序列型”設為標準，每個學習者與這個標準的風格差異值作為這個學習者的學習風格值，也就是學習者風格轉化的二進制數與“10101010”做“與運算”之后，將所得數列位上“1”的個數乘以“10”后加上“60”的值作為學習者風格量化后的值，例如經過“與運算”有3個“1”，則差異值為90分。最后加分值是為了避免分組因風格差異分值大而使分組變成以“學習風格”劃分為主。

2.1 初始種群

已知本遺傳算法中的一個因子可以用一個四元組表示，假設班級學生人數為n，要分成m組，前面已經說明每組以3～6人為宜，當小組人數不能平均分配時，若剩余人數多于正常小組人數一半時，則單獨劃分一個小組，否則選擇若干小組各多分配一人。第i（i＝1，2，…，n）個學生的基本情況作為一個因子用Li表示：Li＝（Ai，Si，Mi，Ci），不同于以往的遺傳算法編碼，由于要進行多個分組，文中提出用學生學號作為染色體上的一個基因，描述一次分組情況的序列作為一個染色體。良好的初始序列，將大大減少遺傳算法中的迭代次數，縮短運行時間。下面就開始初始化序列，先將描述基因個體四元組中元素用百分制表示出來，計算出每個個體的一個初始分值：

式中：W1，W2，W3，W4—— 權值，一般默認每個權值為0.25，教師可以根據課程的側重點不同進行更改設置。

將初始的m個值進行降序排列，需要強調的是，在分組前經過試卷調查和教師的確認，已經確定了各組組長，所以要將各組組長移到序列前端，并記錄好組長的位置。初始矩陣的前m個值為各組組長，并在后期不參與各種遺傳操作，但進行差異計算。對剩余的n－m個學習者進行初次分組，采取等間隔方法，就是將剩余學習者分為m組，L（1）至L（m）為各組組長，其他為組員。我們可以初始化給出k個個體，即染色體（執行分組前給出初始值），每個個體都是是由一組學號組成。其余k－1個個體的選擇，依然不動組長位置，將剩余的n－m個個體（降序排列）分為m份，若不能平均分配時，按前面敘述原則，有一組人數較其他組少成員或一些組將剩余人員各取1人。此時隨機從每份選擇1人形成一個組，一次重新分組序列作為一個種群個體。在這k－1個個體中，除組長位置，也可以留些個體，不排序劃分，隨機提取人員與組長組成一組，這樣會使得個體具有多樣化，有利于取得最優值。

2.2 適應度函數計算

對于每個學生都已經獲知了其初始分值，共n個值，在保證各組組長不換動的情況下，應盡量讓“組間同質”，即讓每組的平均分值大體相當；另外，經過遺傳操作使得“組內異質”，即同學間的差異度盡量大，可以通過前文提到的四元組進行量化比較，首先可以得到各組內部的平均特征量化公式：

兩個學習者間的差異公式：

兩個小組間的差異公式為：

在進行計算時，要分別計算一個分組序列整體的組內差異和組間差異，組內差異是小組內部學習者之間各自差異和再進行匯總，公式為：

組間差異是各組向量取得均值后，各組各自差異求和，公式為：

適應度函數定義為組內差異與組間差異的比值：

最后進行歸一處理，讓適應度函數在0到1之間。

2.3 遺傳算法操作

遺傳算法操作有選擇、交叉和變異，初始設定交叉概率為95%，變異概率為5%。一般的選擇算子有“輪盤賭選擇”、“排序選擇”、“最優個體保存”和“隨機聯賽選擇”，文中采用輪盤賭選擇。選擇概率等于個體適應度值與總適應度值的比例。每次轉動圓盤待圓盤停止后指針停靠扇區對應的個體為選中的個體，選擇復制它成為子代個體。顯然，個體在圓盤中所占的面積越大，其被選中的機會也就越大。

交叉算子是遺傳算法中最重要的遺傳算子。這里的交叉不是個體與個體的基因交叉，而是個體內部間的交叉，即將個體中的學號交叉互換，以保證每組人數相同，避免重復分配。各組組長的學號位置保持不變，個體后面相鄰位置兩兩搭配成對，對每一對用隨機生成的概率與交叉概率比較，若小于交叉概率則交換學號，交叉體現了信息交換的思想。

變異算子是隨機生成一個概率，若小于變異概率，進行變異。隨機生成兩個位置（組長位置除外），將學生的學號進行互換，遺傳算法中變異發生的概率很低。變異為新個體的產生提供了機會。

上述操作按順序進行，每操作一次得到一個新的種群。每次循環通過3種操作后生成k個子代。子代與父代共2k個個體，采用競爭策略，取適應度函數值大的k個個體保留作為下一代，進行循環迭代，當滿足結束條件時算法結束。

2.4 收斂條件

終止結束有兩個條件：由小到大排序的適應度函數中，后60%的適應度值基本保持不變，或小于差異值θ；到達限定的最大迭代次數。

2.5 算法描述

步驟1：初始化遺傳算法中的各個參數，給出總人數n和要分的組個數m（只考慮n%m＝0情況），初始種群數量k、交叉概率Po、變異概率Pb、差異閾值θ、最大迭代次數gmax，建立初始種群P1。

步驟2：計算種群P1中每個個體的適應度值Fi（i＝1，2，…，k），并按降序排列，取適應度大的前k個個體作為新的種群，如果滿足終止條件，則終止。

步驟3：執行基本遺傳算法的選擇、交叉（Po）、變異（Pb）操作，產生k個后代，得到新群體P2，存入下一代中。

步驟4：P1＝P1，轉步驟2。

算法以迭代的方式重復執行，迭代一定次數后，種群中的很多個體都具有很強的適應度，適應度最強的一個個體就是我們認為最合理的分組序列，將此個體按照順序轉換一個m×n的矩陣，所在列表示具體某個學生，所在行表示此學生被分到的組。

2.6 實驗結果與分析

算法在以下兩方面進行了優化：對初始種群進行了優化，減少了迭代次數，提高了收斂速度；組長選出位置后在個體左側不參與遺傳運算，減少了運算量。

為驗證此算法，文中隨機選取了軟件10－1班作為研究對象。布置了一個任務“做一個門戶網站，內容、風格、技術都不限，要求組長展示作品時上交完整的協作記錄，包括各成員的具體任務及完成情況、小組討論記錄和組長點評，為期一個月”。此次任務采用遺傳算法進行分組，與以往檔案中最近一次該班級任務記錄進行對比。為保證具有可比性，教學模式保持不變，各組組長人員不變。考慮到任務內容不同，只從“小組協作能力”方面給出了分值進行對比，見表1。

表1 成績對比表（每一項滿分為100）

評價分組優劣的一個重要指標就是看小組的協作能力[8]，每組的組員都應通力合作將任務完成。各小組應保證每組的組員參與度大體相當，避免出現“組內任務一人扛”的局面，這正是分組提倡的“組間同質”。試驗中，組員由原來的自由分組變成了利用遺傳算法分組，可以看出，本次任務協作成績比較均衡，且普遍高于以往。以往任務雖然有個別小組分值很高，但從“提升全班整體協作能力”角度看沒有經過遺傳算法分組的教學效果好。

3 結 語

利用遺傳算法自動分組，可以合理、快速地分配人員。同時能夠注意到，必須有相應的學生個人特征庫做支持，這就要求對學生進行合理多方面的特征測試并不斷更新，所有老師在進行分組活動時應給予及時記錄并進行小組和組員評價，學生個人特征數據庫的建立有待進一步建設和完善。

[1]黃榮懷.關于協作學習的組態結構模型研究[C]／／2001全球華人資訊與教育會議.臺灣：[出版者不詳]，2001.

[2]楊友林，丁碩.基于模糊C均值算法的協作學習分組系統研究[J].電子科技，2009，22（5）：84－86.

[3]李杰，王臧偉，李克東.協作學習中協作小組分組系統的設計與開發研究[J].華南師范大學學報，2007（3）：62－68.

[4]張春玲.基于遺傳算法的協作學習自動分組[J].中國信息技術教育，2011，19：67－69.

[5]周明，孫樹棟.遺傳算法原理及應用[M].北京：國防工業出版社，1999.

[6]郭海湘，諸克軍，劉濤.基于 MATLAB采用遺傳算法確定最優聚類數目[J].長春工業大學學報：自然科學版，2004，25（1）：12－14.

[7]王婷婷，吳慶麟.學習風格理論綜述及其教育啟示[J].寧波大學學報：教育科學版，2006，28（4）：47－50.

[8]謝舒瀟，黎景培.網絡環境下基于問題的協作學習模式的構建與應用[J].電化教育研究，2002（8）：44－47.