基于遺傳算法自動組卷問題的設計研究

［摘 要］根據目前考試多約束條件的需求，本文是在基于遺傳算法的基礎上，通過對編碼、適應度函數、遺傳算子、控制參數指標等方面來進行研究設計，對適應度函數的選擇，特別是在控制參數指標中建立相應的交叉概率和變異概率，有利于防止結果進入局部最優和克服未成熟現象的發生，從而確保的試卷的覆蓋范圍和準確性，提高組卷效率。

［關鍵詞］遺傳算法 編碼 適應度函數 遺傳算子 算法控制參數

一、引言

目前自動組卷的考試系統大多采用的算法都是隨機抽取法和回溯試探法。隨機抽取法不存在最優化這樣的思想，因為組卷前用戶會針對所需試卷的情況提出各種不同的制約條件，自動組卷完成后所生成的試卷，只要是能夠滿足給定條件要求的，都看作是可行的試卷。這種算法的策略就是在約束條件的限制下，讓計算機在試題庫中任意選取符合要求的試題，再不斷重復這樣的搜索選取過程，直到生成試題的操作結束或是無法搜索選取符合限制條件的試題為止?；厮菰囂椒▽嶋H上是采用基于隨機選取試題的基礎上，記錄下每次操作的狀態類型，讓這些類型與設定的條件相對比，再對滿足條件的進行抽取操作，就這樣循環到生成試卷或是重新開始組卷。

在相同限制條件與狀態空間下，分析兩種算法的優缺點，隨機抽取法由于算法結構簡單，對單一的某道試題的選取有較快的運行速度，因而此方法被許多人所采用。但對于組卷的整個過程來說，由于抽取的空間太大，即便組卷成功，也會用上讓人難以忍受的時間，或是最終發現選取的試題不能滿足某些要求，致使組卷的失敗。

二、遺傳算法

遺傳算法是一種優化搜索的算法，它具有一切生命與智能產生進化的模仿機制過程。它通過迭代過程中的遺傳變異理論和生物基因遺傳原理，引入編碼初始群體，針對構成群體的每個個體，按它們對環境的適應度來進行相關的操作，最終實現“優勝劣汰，適者生存”的演變進化過程。從優化尋優搜索的角度來說，遺傳的過程就是讓問題的解一代比一代優化，最終得出最優的解。基本工作流程如下圖2-1。遺傳算法具有全局搜索尋優能力；沒有函數連續性和求導的限制，能直接操作于結構對象；不需要確定規則，能自動獲取優化的搜尋空間，自動地來調整搜索尋優方向。與其它算法相比較，把遺傳算法應用于組卷系統具有如下特點優勢：

1.遺傳算法具有有向的搜索方式：不同于一般無向搜索法的傳統隨機搜索方式，遺傳算法是在進行著有向而高效的搜索。

2.遺傳算法具有良好的并行性：算法的操作對象非單個可行解，是一組可行解；搜索軌道非單條，有多條。

3.遺傳算法具有很強的通用性：算法無需利用高價值信息，只需利用目標函數信息，因而適用于任何不連續大規模函數的和目標函數的優化。

4.遺傳算法具有良好的全局優化穩健性：主要是利用其良好的并行性和對擇優機制的選擇。

5.遺傳算法具有良好的簡單可操作性：算法操作是通過編碼化的可行解，把編碼化的個體適應值解釋為目標函數。

6.遺傳算法形成了最優的問題求解方法：該算法在和其它技術(如神經網絡、信號處理、模糊推理、人工生命、機器學習和混沌行為等)相結合時比較容易。

三、遺傳算法設計

遺傳算法的特點用于處理智能自動組卷的問題，也就是先要生成一定規模的初始群體，按評價函數的條件進行個體的選擇復制，接著使其以一定的概率進行交叉與變異的遺傳操作，實現個體結構新的重組，這樣不斷循環迭代，最終搜索到符合全局的最優解，相應的算法步驟如下：

步驟 1 制定編碼方案

組卷問題中所要求得到的可行解是一份生成的試卷，采用分組實數編碼，把一份試卷映射為一個染色體，將組成試卷同類題型的試題映射成構成染色體的每個基因，再直接用各個試題的對應題號來表示基因的值，即染色體的基因編碼表示為：，其中(n為試卷總題型數，i= n-1)是試題的題號。

步驟 2 確定適應度函數

適應度函數是對問題求解的評價函數。通過確定在群體中的某個體相應的適應度函數值f(x)，作為來描述個體性能的主要指標，也是個體進行優勝劣汰的主要操作。目標函數和適應值之間的關系存在著多樣性，在函數優化問題中，將問題的目標函數與個體的適應度函數建立映射關系，保證映射后f(x)總是非負的，并且希望它的值在任何情況下越大越好。

步驟 3 設計遺傳算子

(1) 選擇算子 是為了提高群體的平均適應度值。由于它本身不具有產生新個體的行為，所以群體中最優個體的適應度值也不會因為選擇操作發生改變。遺傳算法的主要操作過程是通過選擇優異個體直接對下一代進行遺傳或是通過間接的配對交叉產生的新個體再遺傳給下一代，而淘汰劣質個體。如果初始群體大小為n，個體i的適應度值為，那么i被選擇的概率就為。因此，個體適應度值越大，被選擇的概率也就越高。

(2) 交叉算子 決定了在遺傳算法中的全局搜索能力，是新個體產生的主要方法。在兩個個體的各個相同題型段內來操作的，主要采用分段單點交叉策略：隨機選出的兩兩配對個體，它們的每個基因座上的基因按照交換后個體也是有意義組合的條件和給定的交叉概率，從而產生兩個新個體。具體操作采用隨機生成交叉位置上的單點，在某題型段內對兩個體點前和點后進行交叉交換，此操作可能導致段內題號的重復，但這不會使每種題型中的題量有所改變。若段內題號或知識點重復，須隨機生成一個隨機數j(j在題型數1～h中)，來重新對交叉點進行選擇。

(3) 變異算子 決定了在遺傳算法中的局部搜索能力，是新個體產生的輔助方法。它能以最小的概率來改變遺傳基因的值，采用在約束條件下為相同題型段內的單點變異進行操作，是在交叉操作后個體按照變異概率來進行的操作。由于早已確定在每個題型段中的題號范圍，必須考慮其它基因(試題)知識點與該個體基因知識點是否被選中多次、是否重復，在第i段題號范圍內的產生隨機數，其如被選中，就重新再產生，一直到是沒被選中的隨機數，用它代替該題型段中的任意題號。遺傳算法的變異算子可防止出現早熟現象，用來維持種群的多樣性。

步驟 4 選擇算法的控制參數指標

運用遺傳算法需要決定的控制參數有：群體規模、交叉概率和變異概率。種群規模是群體中含有個體的數量，群體規模 n < 30(過小)，可提高算法的運算速率，但降低了群體的多樣性，不容易求出最優解；n > 150 (過大)，會降低算法的運算速度，從而增加計算量最終延長算法的收斂時間，一般 n在30～150的范圍來取值。交叉概率控制并作用于交叉操作的頻率，決定了個體的更新和算法在解空間的全局搜索能力，所以通常應取較大值，但P 在0.85～1之間(過大)，容易破壞群體的高適應度值，在0～0.35之間(過小)，算法又退化成單純地隨機搜索，取值范圍應在0.35～0.85之間。變異概率可恢復群體在進化過程中所丟失的基因位信息，防止結果進入局部最優并克服未成熟現象的發生，變異概率在0～0.01之間(過小)，產生的新個體少，難以使新的基因塊產生，在0.2～1之間(過大)，又會使遺傳算法退化成單純的隨機搜索。它的范圍應在0.01～0.2之間。P ，P 的值仍須要經過反復的試驗才能確定，因為它們的值雖然都有可供選擇的相應范圍，但P ，P 被定為固定的參數，會導致算法的過早收斂。

步驟 5 確定算法的終止準則

在遺傳算法中，設定了目標適應度值與最大的迭代次數，從而把目標適應度值和每一代計算出的個體的最大適應度值相比較，當期望值小于或等于個體的最大適應度值時停止迭代，否則反復進行上述遺傳操作直至達到期望適應度值組卷成功。

步驟 6 算法的實現

完成上述工作以后，即可以按照深化計算的算法結構編程對問題進行求解。

四、實驗結果及分析

為驗證算法的可行性和有效性，以《計算機模擬考試》題庫為例，利用ASP環境編制相應程序。用戶對組卷的具體要求是：試卷總分值為100分，給定時間為120分鐘；試卷要求的題量分布為：選擇題210道，填空題130道，程序閱讀題100道，編程題114道。遺傳算法參數為：種群規模n=50，最大迭代次數=500。

在組卷約束條件較多，試題庫題量較大且分布合理的情況下，隨機選取法組卷成功率較低，且常常由于局部滿足約束條件而致使組卷失敗，而遺傳算法和回溯試探法都有較高的組卷成功率。

五、結束語

基于遺傳算法的智能組卷系統是適應當前考試組卷系統的重要組成。本文針對遺傳算法問題，結合隨機選取法和回溯試探法的優點，研究設計了該算法具體相關的各個方案，改善了自動組卷效率，提高了組卷成功率。但要讓自動組卷中的誤差精度得到進一步改進，還有待更深入的探討。

參考文獻：

[1]孫勇 柏云：基于遺傳算法的試題組卷策略[J]淄博學院學報（自然科學版）2002（3）27-28

[2]王小平 曹立明：遺傳算法-理論、應用于軟件實現[M].西安：西安交通大學出版社.2002