基于改進遺傳算法的自動組卷問題研究

摘要：為了解決傳統遺傳算法在自動組卷中容易出現未成熟收斂和收斂速度慢等問題，提出了一種基于改進遺傳算法的自動組卷方法。采用分段二進制編碼策略，對每個子空間進行初始種群選擇，保證了初始種群含有豐富的模式，從而增加搜索收斂于全局最優的可能性。并對交叉算子和變異算子進行了優化，實現了交叉和變異概率隨解的變化而自適應調整。實驗結果表明，改進的遺傳算法能有效地解決自動組卷問題，提高了收斂速度和組卷的成功率。

關鍵詞：遺傳算法；自動組卷；適應度函數；分段二進制編碼

中圖分類號：TN91134文獻標識碼：A文章編號：1004373X（2012）18008003

引言

自動組卷是實現網上考試系統的核心技術之一，國內外的許多學校機構、科研單位都對組卷系統進行了研究，要求生成的試卷能最大程度地滿足用戶的需要，并具有科學性、隨機性和合理性[1]。在題庫試題質量高的前提下，自動組卷的效率與質量完全取決于抽題算法的設計。如何設計一個高效、合理、科學的算法，是自動組卷的關鍵，涉及到一個全局尋優和收斂速度快慢的問題，具有很高的研究價值[2]。

1組卷問題的數學描述

只有滿足一定條件的試題才能參與組卷，因此試題組卷時需要給出以下約束條件：總時間、試卷平均難度、試卷總分、知識范圍、各種題型比例等[3]。組卷中決定一道試題，就要決定n項約束條件，決定一份試卷，就決定一個m×n的矩陣，其中m是試卷所含的題目數[4]。本模型中n簡化為5，即僅考慮總分、難度、題型、知識范圍和答題時間5項指標。s=d11d12…d15

d21d22…d25

………

dm1dm2…dm52改進遺傳算法的自動組卷設計

針對試題組卷的具體情況，對標準遺傳算法進行改進后用于求解組卷問題，以下給出具體解決方法。

2.1編碼方案

本系統采用了分段二進制編碼策略。將整個題庫劃分為不同的段，每一段反映一種題型，每一段長度由題庫中該題型的數目決定，每一種題型單獨進行傳統的二進制編碼，編碼長度由試題庫中所含試題數決定[5]。