分段組卷偽并行遺傳算法的研究與實現(xiàn)

方俊

摘 要： 遺傳算法組卷存在收斂速度慢和未成熟收斂問題，難以滿足考核要求。已有較多算法采用了分段編碼、分段進(jìn)化的策略，以降低算法的復(fù)雜度，提高算法的性能，但均未實現(xiàn)分段組卷，沒能從根本上提高算法的性能。為此提出分段偽并行組卷的方法，即：分段組成符合要求的試卷段，再組合成一份完整的符合用戶需求的試卷。實驗證明，該方法能夠大大加快收斂速度，提高組卷質(zhì)量。

關(guān)鍵詞： 遺傳算法； 適應(yīng)度； 組卷； 種群多樣性； 偽并行

中圖分類號：TP181 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-8228（2014）07-37-03

Abstract： There exist problems of slow convergence speed and premature convergence in genetic algorithm， making it hard to meet the inspection requirements. Hence the block coding， and segmented evolution strategy are adopted in many algorithms in order to reduce the complexity of the algorithm， and improve the performance of the algorithm. However， none of them can realize composing test paper piecewise. The performance of the algorithm is failed to fundamentally be improved. To solve the above problems， a method of pseudo-parallel group volume is proposed. Test paper is composed individually， and assembled into a complete test paper. It meets the demand of the users. Experiments show that this method can greatly speed up the convergence and improve the quality of composing test paper.

Key words： genetic algorithm； fitness value； composing test paper； diversity of population； pseudo-parallel

0 引言

隨著人工智能技術(shù)的發(fā)展，出現(xiàn)了基于智能的計算機輔助教學(xué)系統(tǒng)。智能組卷是智能計算機輔助教學(xué)系統(tǒng)的重要組成部分，它的研究目的是使計算機代替人工出卷。能否快速地組成科學(xué)的、合理的和具有隨機性的高質(zhì)量試卷取決于組卷算法的設(shè)計。20世紀(jì)80年代中后期，國內(nèi)外研究者根據(jù)組卷問題的特點進(jìn)行了組卷算法的研究，相繼產(chǎn)生了多種組卷方法。其中具有代表性的有隨機抽題法、回溯試探法和遺傳算法等[1]。①隨機抽題法是根據(jù)組卷時定義的控制指標(biāo)，不斷從試題庫中隨機選取試題加入試卷中，直到組卷完成。該方法簡單，單次運行速度快，但成功率低。②回溯試探法的基本思想：判斷隨機抽取的試題是否滿足指定的約束條件，當(dāng)滿足約束條件時繼續(xù)向前搜索，并保存待生成試卷的狀態(tài)空間。當(dāng)組卷失敗時，則返回上次記錄，再按照預(yù)定策略進(jìn)行新的搜索試探，直到生成試卷或回到出發(fā)點為止。該方法組卷耗時長，且內(nèi)存空間占用量也較大。③遺傳算法作為一種優(yōu)秀的算法，已在很多領(lǐng)域得到應(yīng)用，與傳統(tǒng)的搜索算法不同，它是模仿自然選擇和遺傳進(jìn)化過程來搜索最優(yōu)解，特別適于處理傳統(tǒng)的搜索方法無法解決的復(fù)雜問題和非線性問題。智能組卷是一種多目標(biāo)約束問題[2]，受多種因素的影響，如總分、題型，每種題型的題量，每種題型所占的分值、時間、難度、區(qū)分度等，但遺傳算法利用適應(yīng)度值來指導(dǎo)搜索方向，使得采用遺傳算法解決多目標(biāo)約束的組卷問題具有明顯的應(yīng)用優(yōu)勢。它具有所組試卷隨機性強，質(zhì)量高的特點，但由于約束條件多，易出現(xiàn)未成熟收斂和收斂慢，多個目標(biāo)方向在收斂速度上存在不一致的現(xiàn)象，容易向一個方向上側(cè)重。在采用遺傳算法進(jìn)行組卷時，較多算法采用了分段編碼、分段進(jìn)化的策略[3-4]，以降低算法的復(fù)雜度，提高算法的性能，但并未實現(xiàn)分段組卷，沒能從根本上提高算法的性能。本文提出分段偽并行組卷的方法，即按題型分段成子群體，各子群體獨立進(jìn)行遺傳進(jìn)化。按題型組成符合要求的試卷段，再將其組合成一份完整的符合用戶需求的試卷。由于各子群體的進(jìn)化計算是在同一臺計算機上串行進(jìn)行的，所以稱為偽并行遺傳算法。該算法由于簡化了關(guān)系，使得進(jìn)化速度明顯提高，只需經(jīng)過幾代進(jìn)化即可取得符合用戶要求的試卷，而且精度也有較大的提高。

1 試題的屬性與試卷的約束條件

1.1 試題的屬性

1.2 試卷的約束條件

一份試卷往往要求同時滿足多個約束條件，但過多的約束條件增加了組卷的難度。本文采用分段偽并行組卷的方法，要求按題型分段組卷，按段組成滿足要求的試卷段，再組合成一份符合用戶要求的試卷。試卷及各段必須滿足下面的約束條件。

⑴ 試卷總分要求：試卷的各試題的分值之和與用戶設(shè)定的試卷總分相等。

⑵ 試卷難度要求：試卷的各段、整份試卷的難度值與用戶設(shè)定的試卷難度值相等。

⑶ 試卷區(qū)分度要求：試卷的各段、整份試卷的區(qū)分度值與用戶設(shè)定的試卷區(qū)分度值相等。

⑷ 考試時間：整份試卷的各試題的答題用時之和與用戶設(shè)定的試卷時長相等。

⑸ 各題型題量：各題型中的題目數(shù)量與用戶設(shè)定的每種題型的題目數(shù)量相等。

⑹ 各題型所占的分值：各題型所占的分值與用戶設(shè)定的每種題型占試卷總分值的百分比相等。

⑺ 各題型答題用時：各題型答題用時與用戶設(shè)定的每種題型答題用時相等。

2 分段組卷偽并行遺傳算法

對于分段組卷偽并行遺傳算法，給出相應(yīng)的算法步驟。

步驟1 染色體編碼及種群初始化

編碼是應(yīng)用遺傳算法時首先需要解決的問題，對于組卷來說常用編碼的有兩種，基于二進(jìn)制的編碼[5]和基于實數(shù)的編碼[6]。與實數(shù)編碼相比， 二進(jìn)制編碼的搜索效率更高，且二進(jìn)制編碼具有操作簡單易行，交叉、變異便于實現(xiàn)的特點，故本文采用二進(jìn)制編碼的方式。編碼按題型分段進(jìn)行，假設(shè)題庫中某一題型共有m道試題，則可用一個m位的二進(jìn)制串來表示，如果其中的題目被選中，則用“1”表示，未被選中，則用“0”表示。

初始化群體采用隨機方式產(chǎn)生。通常，種群規(guī)模將影響算法的性能，種群設(shè)置越大可以提供處理的模式越多，群體中個體多樣性越高，可以防止早熟收斂，但會增加計算量；種群設(shè)置過小則使遺傳算法的搜索空間受到限制，不能提供足夠的采樣點，一般可通過實驗確定。

步驟4 選擇運算

選擇是采用某一選擇策略挑選父代中的優(yōu)良個體進(jìn)行復(fù)制，以繁殖后代。選擇的方法有輪盤賭選擇、最優(yōu)保存策略、確定式采樣選擇、無回放隨機選擇、無回放余數(shù)隨機選擇、排序選擇、隨機聯(lián)賽選擇[9]。本文算法采用基于目標(biāo)函數(shù)值的排序選擇方法和最優(yōu)保存策略。選擇運算在各題型段內(nèi)獨自進(jìn)行，將目標(biāo)函數(shù)值按照從小到大的順序排列，目標(biāo)函數(shù)值越小，所對應(yīng)的個體越優(yōu)良。本文選取前面20%的優(yōu)良個體直接復(fù)制進(jìn)入下一代。

分段選擇運算相對于整條染色體的選擇運算具有更高的性能。比如，一條染色體由于某一染色體段的目標(biāo)函數(shù)值偏大就可能被丟棄，不會被復(fù)制進(jìn)入下一代。而分段選擇只是將目標(biāo)函數(shù)值大的染色體段淘汰，其他目標(biāo)函數(shù)值小的染色體段將被復(fù)制進(jìn)入下一代，從而減少了無效迭代，能夠提高選擇運算的效率。

步驟5 交叉運算

交叉操作是遺傳算法中最主要的操作，是產(chǎn)生新的優(yōu)良個體的主要方法。交叉操作要求既不破壞染色體中基因的優(yōu)良性狀，又能有效地產(chǎn)生出一些好的新個體。常用的交叉方式有單點交叉、多點交叉、均勻交叉和算術(shù)交叉[9]。本文采用單點交叉，在各自的題型段內(nèi)，隨機選取兩個相互配對的染色體段，隨機確定交叉點，在交叉點位置后面部分字符串相互交換而形成二個新的染色體段。具體的交叉方式如下。

由于交叉操作后生成的新染色體段中所包含的“1”的個數(shù)可能發(fā)生改變，為了確保題型段內(nèi)所包含的題目數(shù)與用戶設(shè)定的一致，因此需要檢查字符串中所包含的“1”的個數(shù)。這里只檢查交叉點后“1”的數(shù)目是否改變，如果增加了就隨機選擇其中的“1”將其反轉(zhuǎn)為“0”，如果減少了就隨機選擇其中的“0”將其反轉(zhuǎn)為“1”，以保證在題型段內(nèi)所包含的題目數(shù)與用戶設(shè)定一致。本文采用雜交產(chǎn)生子代60%的新個體。

步驟6 變異運算

遺傳算法中的變異算子是生物體進(jìn)化過程中染色體上的基因位發(fā)生突變的現(xiàn)象，它使染色體的結(jié)構(gòu)和性狀發(fā)生改變。它能改善遺傳算法的局部搜索能力和維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。在遺傳算法中，交叉算子因其全局搜索能力而作為主要算子，變異算子因其局部搜索能力而作為輔助算子，對于二進(jìn)制編碼而言，變異操作就是把某些基因位的值取反[9]。具體是在各題型段內(nèi)隨機確定變異點的位置，將其值取反。如果是“0”變?yōu)椤?”，則該題型段的題目數(shù)量增加了1題，因此需要隨機選取其他位置的“1”將其變?yōu)椤?”以保持該題型的題目數(shù)量與用戶設(shè)定的數(shù)量一致。如果是“1”變?yōu)椤?”，則該題型段的題目數(shù)量減少了1題，因此需要隨機選取該段其他位置的“0”值將其變?yōu)椤?”以保持該題型的題目數(shù)量與用戶設(shè)定的數(shù)量一致。實際編程可以隨機選取一個“1”和一個“0”，再分別變?yōu)椤?”和“1”，本文采用變異產(chǎn)生子代20%的新個體。

在執(zhí)行完以上步驟后，返回到第2步驟，對個體進(jìn)行評價。如果滿足終止條件，即可輸出結(jié)果；如果不滿足終止條件，則繼續(xù)向下執(zhí)行，循環(huán)往復(fù)，使各染色體段向最優(yōu)解方向移動，從而使整條染色體逐漸接近最優(yōu)解。

3 實驗條件和結(jié)果

表2數(shù)據(jù)為本文方法與排序方法的比較，此處的排序算法與本文算法惟一的不同是未采用偽并行的計算策略，其他條件相同。從表2可以看出，組卷50次，采用分段組卷偽并行遺傳算法時，在組卷約束條件較多的情況下，本文算法迭代次數(shù)明顯減少，算法的效率有了較大的提高。

4 結(jié)束語

組卷是一個多目標(biāo)約束問題，由于約束條件多、題量大，用原始遺傳算法進(jìn)行組卷易出現(xiàn)未成熟收斂和收斂速度慢問題。本文給出分段組卷偽并行遺傳算法，對于約束條件多的組卷問題，采用分段組成符合要求的試卷段，再組合成一份完整的符合用戶需求的試卷，該方法有明顯的優(yōu)勢。在進(jìn)化過程中，利用目標(biāo)函數(shù)值排序的選擇方法和最優(yōu)保存策略，保證了優(yōu)質(zhì)個體能夠被復(fù)制進(jìn)入下一代。利用較大的雜交、變異概率補充新個體，保持了種群多樣性。對在雜交、變異運算過程中所引起的題目數(shù)量的變化進(jìn)行檢查，并進(jìn)行處理，使其與用戶設(shè)定的數(shù)量相等。實驗證明，分段偽并行遺傳算法能夠大大加快收斂速度，提高組卷質(zhì)量，并可同時生成多份滿足要求的試卷。

參考文獻(xiàn)：

[1] 彭雪蓮.基于多策略改進(jìn)遺傳算法的智能組卷研究[D].廣西大學(xué)，2010.

[2] 張琨，楊會菊，宋繼紅，趙學(xué)龍.基于遺傳算法的自動組卷系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機工程與科學(xué)，2012.5（34）：178-183

[3] 魏平熊，偉清.用遺傳算法解組卷問題的設(shè)計與實現(xiàn)[J].微電子學(xué)與計算機，2002.4：48-50

[4] 孟朝霞.基于自適應(yīng)免疫遺傳算法的智能組卷[J].計算機工程，2008.34（18）：203-205

[5] 于淼，王日宏.改進(jìn)遺傳算法在智能組卷中的應(yīng)用[J].計算機工程與應(yīng)用，2008.44（25）：236-238

[6] 黃寶玲.自適應(yīng)遺傳算法在智能組卷中的應(yīng)用[J].計算機工程，2011.37（14）.

[7] 饒樂三，王曉柳.教育統(tǒng)計學(xué)[M].南京大學(xué)出版社，1990.

[8] 魯萍，王玉英.多約束分級尋優(yōu)結(jié)合預(yù)測計算的智能組卷策略[J].計算機應(yīng)用，2013.33（2）.

[9] 陳國良，王煦法，莊鎮(zhèn)泉，王東生.遺傳算法及其應(yīng)用[M].人民郵電出版社，2001.