基于遺傳算法的分組算法

李 峰， 王海英

（東北石油大學(xué) 計(jì)算機(jī)科學(xué)系，黑龍江 大慶 163311）

1 分組策略

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

1.1 組內(nèi)異質(zhì)，組間同質(zhì)[1]

組內(nèi)異質(zhì)指小組成員間在專業(yè)知識(shí)、年齡、性別、學(xué)習(xí)風(fēng)格、學(xué)習(xí)動(dòng)機(jī)等方面具有差異性，組間同質(zhì)指各小組之間大體均衡，這樣小組間才有可比性。組內(nèi)異質(zhì)可為小組成員之間的互助協(xié)作奠定基礎(chǔ)，而組間同質(zhì)又可為各小組間的公平競爭創(chuàng)造條件。

1.2 公平競爭、合理比較

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

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

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

具體分組過程：

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

2.1 初始種群

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

式中：W1，W2，W3，W4—— 權(quán)值，一般默認(rèn)每個(gè)權(quán)值為0.25，教師可以根據(jù)課程的側(cè)重點(diǎn)不同進(jìn)行更改設(shè)置。

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

2.2 適應(yīng)度函數(shù)計(jì)算

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

兩個(gè)學(xué)習(xí)者間的差異公式：

兩個(gè)小組間的差異公式為：

在進(jìn)行計(jì)算時(shí)，要分別計(jì)算一個(gè)分組序列整體的組內(nèi)差異和組間差異，組內(nèi)差異是小組內(nèi)部學(xué)習(xí)者之間各自差異和再進(jìn)行匯總，公式為：

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

適應(yīng)度函數(shù)定義為組內(nèi)差異與組間差異的比值：

最后進(jìn)行歸一處理，讓適應(yīng)度函數(shù)在0到1之間。

2.3 遺傳算法操作

遺傳算法操作有選擇、交叉和變異，初始設(shè)定交叉概率為95%，變異概率為5%。一般的選擇算子有“輪盤賭選擇”、“排序選擇”、“最優(yōu)個(gè)體保存”和“隨機(jī)聯(lián)賽選擇”，文中采用輪盤賭選擇。選擇概率等于個(gè)體適應(yīng)度值與總適應(yīng)度值的比例。每次轉(zhuǎn)動(dòng)圓盤待圓盤停止后指針停靠扇區(qū)對(duì)應(yīng)的個(gè)體為選中的個(gè)體，選擇復(fù)制它成為子代個(gè)體。顯然，個(gè)體在圓盤中所占的面積越大，其被選中的機(jī)會(huì)也就越大。

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

變異算子是隨機(jī)生成一個(gè)概率，若小于變異概率，進(jìn)行變異。隨機(jī)生成兩個(gè)位置（組長位置除外），將學(xué)生的學(xué)號(hào)進(jìn)行互換，遺傳算法中變異發(fā)生的概率很低。變異為新個(gè)體的產(chǎn)生提供了機(jī)會(huì)。

上述操作按順序進(jìn)行，每操作一次得到一個(gè)新的種群。每次循環(huán)通過3種操作后生成k個(gè)子代。子代與父代共2k個(gè)個(gè)體，采用競爭策略，取適應(yīng)度函數(shù)值大的k個(gè)個(gè)體保留作為下一代，進(jìn)行循環(huán)迭代，當(dāng)滿足結(jié)束條件時(shí)算法結(jié)束。

2.4 收斂條件

終止結(jié)束有兩個(gè)條件：由小到大排序的適應(yīng)度函數(shù)中，后60%的適應(yīng)度值基本保持不變，或小于差異值θ；到達(dá)限定的最大迭代次數(shù)。

2.5 算法描述

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

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

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

步驟4：P1＝P1，轉(zhuǎn)步驟2。

算法以迭代的方式重復(fù)執(zhí)行，迭代一定次數(shù)后，種群中的很多個(gè)體都具有很強(qiáng)的適應(yīng)度，適應(yīng)度最強(qiáng)的一個(gè)個(gè)體就是我們認(rèn)為最合理的分組序列，將此個(gè)體按照順序轉(zhuǎn)換一個(gè)m×n的矩陣，所在列表示具體某個(gè)學(xué)生，所在行表示此學(xué)生被分到的組。

2.6 實(shí)驗(yàn)結(jié)果與分析

算法在以下兩方面進(jìn)行了優(yōu)化：對(duì)初始種群進(jìn)行了優(yōu)化，減少了迭代次數(shù)，提高了收斂速度；組長選出位置后在個(gè)體左側(cè)不參與遺傳運(yùn)算，減少了運(yùn)算量。

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

表1 成績對(duì)比表（每一項(xiàng)滿分為100）

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

3 結(jié) 語

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

[1]黃榮懷.關(guān)于協(xié)作學(xué)習(xí)的組態(tài)結(jié)構(gòu)模型研究[C]／／2001全球華人資訊與教育會(huì)議.臺(tái)灣：[出版者不詳]，2001.

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

[3]李杰，王臧偉，李克東.協(xié)作學(xué)習(xí)中協(xié)作小組分組系統(tǒng)的設(shè)計(jì)與開發(fā)研究[J].華南師范大學(xué)學(xué)報(bào)，2007（3）：62－68.

[4]張春玲.基于遺傳算法的協(xié)作學(xué)習(xí)自動(dòng)分組[J].中國信息技術(shù)教育，2011，19：67－69.

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

[6]郭海湘，諸克軍，劉濤.基于 MATLAB采用遺傳算法確定最優(yōu)聚類數(shù)目[J].長春工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，25（1）：12－14.

[7]王婷婷，吳慶麟.學(xué)習(xí)風(fēng)格理論綜述及其教育啟示[J].寧波大學(xué)學(xué)報(bào)：教育科學(xué)版，2006，28（4）：47－50.

[8]謝舒瀟，黎景培.網(wǎng)絡(luò)環(huán)境下基于問題的協(xié)作學(xué)習(xí)模式的構(gòu)建與應(yīng)用[J].電化教育研究，2002（8）：44－47.