分段組卷偽并行遺傳算法的研究與實現

方俊

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

關鍵詞： 遺傳算法； 適應度； 組卷； 種群多樣性； 偽并行

中圖分類號：TP181 文獻標志碼：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 引言

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

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

1.1 試題的屬性

1.2 試卷的約束條件

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟4 選擇運算

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

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

步驟5 交叉運算

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

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

步驟6 變異運算

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

在執行完以上步驟后，返回到第2步驟，對個體進行評價。如果滿足終止條件，即可輸出結果；如果不滿足終止條件，則繼續向下執行，循環往復，使各染色體段向最優解方向移動，從而使整條染色體逐漸接近最優解。

3 實驗條件和結果

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

4 結束語

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

參考文獻：

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

[2] 張琨，楊會菊，宋繼紅，趙學龍.基于遺傳算法的自動組卷系統的設計與實現[J].計算機工程與科學，2012.5（34）：178-183

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

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

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

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

[7] 饒樂三，王曉柳.教育統計學[M].南京大學出版社，1990.

[8] 魯萍，王玉英.多約束分級尋優結合預測計算的智能組卷策略[J].計算機應用，2013.33（2）.

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