基于遺傳算法的自動組卷系統的分析與設計

蔣　哲(湖北工業大學, 武漢430068)

基于遺傳算法的自動組卷系統的分析與設計

蔣哲
(湖北工業大學, 武漢430068)

自動組卷系統中的關鍵環節在于組卷算法的選擇，算法的好換直接關系著組卷的質量以及效率。本文對三種常用的組卷算法進行了分析，并將改進的遺傳算法應用于自動組卷問題中，有效提高了組卷質量和效率。本文詳細闡述了基于遺傳算法的自動組卷算法的實現流程。

遺產算法；自動組卷；算法設計

0　引言

自動組卷指的是計算機考試系統自動從預先設定的題庫中按照用戶的特點需求抽取試題從而組成一套完整的試卷。自動組卷得到的試卷既要滿足用戶設定的要求，同時也需要具有合理性、隨機性，這對組卷算法提出了很高的要求。目前已經有了一些自動組卷系統，然而由于科目眾多、各專業的課程重點不同等因素的影響，這些自動組卷系統還無法有效滿足用戶的需求。

1　自動組卷算法分析

組卷算法的設計是影響組卷系統組卷質量的關鍵因素，目前現有的自動組卷系統采用的組卷算法主要包括三種類型：回溯試探法、隨機算法以及遺傳算法。

回溯試探法的思想是：首先隨機抽取一個試題，對該試題進行分析，判斷是否滿足抽題要求，若滿足條件則抽出該試題進入試卷，否則重新選題。當組卷未完成時，采用回溯的方法試探之前的操作進行繼續組卷?；厮莘ú僮鲝U棄的頻率較低，有效減少了無效組卷操作。因此，回溯試探法的組卷成功率很高，但需要花費大量的時間作為代價。隨機組卷法是指計算機根據預先設定的隨機函數從題庫中抽取符合條件的試題組成一套完整的試卷。這種方法實現起來比較簡單方便，在實踐中得到了廣泛的應用。然而隨機組卷法組成的試卷一旦某個條件達不到要求時（如試卷的預期答題時間超標），則整套試卷作廢，從而導致出現大量的無效試卷，極大地降低了組卷的成功率和效率。遺傳算法是一種基于自然界進化理論的優化算法，它遵循優勝劣汰的自然法則。遺傳算法中的編碼技術可以表示各種復雜的現實問題，它通過對編碼的遺傳操作即可確定算法的學習方向和策略。遺傳算法是以種群為操作對象的，對種群中的每個個體進行適應度評價、篩選、交叉和變異操作，從而實現個體的優勝劣汰。

2 　基于改進的遺傳算法的組卷算法設計

2.1目標函數的確定

試卷組織過程中應綜合考慮題目類型、知識點分布、試題難度等因素，用戶給定這些指標的參考值后，對自動組卷系統得到的試卷的指標值進行比較，將指標誤差加權求和，得到目標函數。

2.2 個體編碼的確定

確定好遺傳算法的目標函數后，需要對自動組卷問題進行編碼。組卷問題的求解就是篩選試題組成合理的試卷。因此，首先將試題根據進行分類，如分為選擇題、填空題、計算題等，然后將試題按題型分段編碼，不同題型的編碼相互獨立。試卷個體則按照分庫編號進行染色體編碼，所選中的試題按照順序排列好后，其試題代碼則為試卷個體的代碼。

2.3 種群初始化

遺傳算法是基于種群的方法，因此需要設定初始種群，然后在初始種群的基礎上不斷進化。種群是所有試卷個體的集合，初始試卷個體通過計算機隨機生成。隨機生成初始試卷個體時，試卷總分、題型、均滿足要求。

2.4 適應度函數設計

適應度函數是遺傳算法中個體進化操作的依據，因此在設計適應度函數時，應當使得遺傳算法的群體位于解空間內，同時方便其搜索方向接受指導。一個良好的適應度函數應當能反應每個個體本身質量的好壞。在組卷算法中，適應度函數可通過目標函數轉換得到，本文采用的適應度函數如下：

式中，f為目標函數，F為適應度。從上式可知，f越小，則適應度值越高，即試卷評價指標的誤差越校，試卷個體的適應度越高，即試卷更符合組卷要求。

2.5 組卷算法的選擇操作

遺傳算法以試卷個體為遺傳操作的對象，具體過程為：首先計算種群中每個試卷個體的適應度值，并找出適應度最高的個體，用它直接替代本代群體遺傳操作后生產的適應度最小的個體，即遵循“精英保留”原則。其他的試卷個體則使用輪盤法完成選擇工作。將種群中每個個體的適應度值求和得到種群的整體適應值，然后計算每個試卷個體的選擇概率，同時生產一個0~1之間的隨機數，若選擇概率小于隨機數，則該試卷個體不選擇。

2.6 組卷算法的交叉操作

個體交叉的概率使用自適應交叉概率。由于試卷個體最終應該符合題量以及題型的規定，因此試卷個體在完成交叉操作時應當在各自的編碼組中進行，例如A個體與B個體進行交叉時，選擇題只能與選擇題交叉，而不同的題型不能混合交叉。對上一步篩選出的個體進行兩兩交叉操作。在進行交叉時，各題型編碼段隨機生成一個交叉點，然后將交叉點之后的編碼互相交換，當各題型均完成交叉后，則表示兩個個體之間的交叉操作完成。由于交叉之后可能出現編碼重復的情況，因此需要將重復的編碼替換為隨機抽取非重復編碼。

2.7 組卷算法的變異操作

個體變異的概率使用自適應變異概率。由自然法則可知，變異是小概率事件，其發生的情況較少，只有少部分個體會發生變異，每個試卷個體的變異概率決定了個體是否發生變異。每個個體隨機產生一個0~1之間的隨機數，若個體變異概率大于隨機數，則該個體進行變異操作。變異操作具體如下：每個題型段隨機產生一個變異位置，移除該位置上原有的試題編碼，并補入新的未被選中的試題編碼。當各題型均完成變異后，即產生新的變異個體。

2.8 組卷算法的迭代終止條件

本算法迭代終止判定：（1）平均適應度達到最高適應度值的95%；（2）迭代次數達到預定最大次數，則結束迭代循環。

3　 結束語

我們研究的熱點和難點，遺傳算法本身具有全局尋優和智能搜索的特性，將遺傳算子自適應改進后的遺傳算法應用于組卷中，能夠很好地解決組卷的多重目標尋優問題。

[1]李玲.基于遺傳算法的自動組卷系統設計[J].軟件導刊,2013,04:52-54.

[2]劉慧梅.基于遺傳算法的自動組卷算法的設計[J].價值工程,2012,20:223-224.

[3]董園.基于改進遺傳算法的自動組卷系統的研究[J].三明學院學報,2012,06:17-22.

[4]施俊,繆勇.基于遺傳算法的自動組卷研究與應用[J].電腦知識與技術,2014,34:8160-8162.

蔣哲(1986-)，男,江蘇常州人，本科,研究方向：計算機方向。