改進的遺傳算法在智能組卷中的應用研究

唐玲 尹珧人

摘 要：該文提出分段二進制編碼，對遺傳算法的選擇過程進行改進，并采用獨立題型題庫存放的方法來求解組卷問題。實驗結果表明，新方法的組卷成功率和收斂速度都得到明顯提高，較好的克服了早熟收斂現象，組卷質量明顯提高。

關鍵詞：改進遺傳算法 智能組卷 數學模型

中圖分類號：TP18 文獻標識碼：A 文章編號：1674-098X（2013）03（c）-00-02

隨著我國信息技術的飛速發展，計算機在教學領域有了廣泛應用，用計算機進行網上考試已經成為一種趨勢，因此怎么才能快速從試題庫中選出一份滿足用戶各項要求的試卷成為一個問題。目前常用的組卷方法有隨機選題法、回溯試探法、遺傳算法三種，而傳統的遺傳算法主要通過交叉算子繁衍后代，容易造成早熟收斂現象。因此目前已經有很多人為提高組卷效率，將遺傳算法的算子改進后再應用到智能組卷系統中。該文為加快算法的收斂速度，將遺傳算法的算子進行了改進，并應用于智能組卷系統中。

1 智能組卷的數學模型

將智能組卷問題視為從一定題量的數據庫中抽取滿足組卷要求的一組試題組合，就能夠將組卷問題轉化為一個多重約束目標問題。求解一份由m道試題且每道試題有n個屬性的試卷，相即構建一個m×n的目標矩陣S。

S=

試題常有如下屬性：⑴難度系數a1、⑵分數a2、⑶能力層次a3、⑷預計答題時間a4、⑸題型a5、⑹已出題次數a6。目標矩陣應滿足以下約束條件：

⑴試卷難度系數=1-/總分（由用戶給定）；

⑵試卷總分=（一般為100分）；

⑶答題總時間=（由用戶給定）；

⑷（為第p能力層次題分），能力層次類型和所占分數由用戶給定，即能力層次約束，其中

⑸題型題分=，第j題型題分，其中：c={，j為題型要求約束。題型分別為：判斷、單選、填空、多選等，具體組卷題型類別和每題分值由用戶給定。

組卷過程中，試題要根據數學模型中給出的各項指標來決定，即表示第i道試題中的第j項指標，其中i=1，2，…，m；j=1，2，…，n。

2 題庫建設

該文試題在存儲時采用各題型獨立試題庫的存儲方法，為了避免經常抽取同一道試題，我們將各題型題庫中試題根據已出題次數（a6）排序（初次抽取試題時，試題順序隨機產生），使a6小的試題下次被抽中的機率更大，以提高每次組卷產生的試卷

質量。

3 改進的遺傳算法在智能組卷中的

應用

3.1 編碼方案

將二進制數分段編碼，每段代表一個題型，k表示題型數量，題庫中試題數量決定了編碼的長度。設各題型題庫中共有t道試題，則編碼形式為b1b2…bt，隨機產生初始化種群（假設串長度是相同的）。

其中：bi={ i=1，2，…，t，且滿足=m，其中m是試題所含的題目數。=m1，=m2，…，=mk，=m，=t其中m1，m2，…，mk表示在試卷中各題型的試題數量，r1、…、rk表示各題庫中該題型的試題數量。

3.2 生成初始種群p（0）

為了降低問題難度，提高求解效率，我們隨機產生試卷的初始種群p（0），使初始種群滿足試卷總分的要求。

3.3 確定適應度函數

我們采用以下形式的適應度函數[1]：

F=1/（1+） i = 1，…，n

其中ei表示第i組卷因素對組卷目標造成的誤差，ki表示權值系數，且ki>0。

3.4 遺傳算子的改進

3.4.1 選擇算子

該文中每個個體的適應度值由適應度函數計算得來，并將種群代數t的初始值設置為0，將每代種群按其適應度值的降序進行排序，依次計算相鄰個體之間的廣義海明距離H，廣義海明距離[2]是指相同長度的兩個串中對應位不相同的數量，例如，某種群的某代進化種群中第i個個體和第j個個體分別為：

xi（t）=1111001010001，xj（t）=1100101011001

它們間的廣義海明距離H（x（t），xj（t））==4。比較H和參數d的大小，若H小于d，則依次用父代群體中的優秀個體替換適應度小的個體；否則保留這兩個個體，將其加入到新一代群體中，執行交叉操作。

3.4.2 交叉算子和變異算子

該文的交叉概率和變異概率是根據種群的進化情況用自適應函數來控制的，這樣可以加快遺傳算法搜索效率，有效防止算法陷入局部最優，從而保護優良試卷個體，所使用的適應度函數如下[3]：

pC=

式中：f取參與交叉的兩個個體中適應度值較大的一個；fmax、favg為上代群體中個體的最大適應度值、群體的平均適應度值；pc1=0.9，pc2=0.6。

pm=

式中：fmax、favg分別取上代群體中個體的最大適應度值、群體平均適應度值；f為要變異個體的適應度值；pm1=0.1，pm2=0.001。

該文交叉操作過程如下：隨機產生交叉位置i，該位置由挑選出的兩個個體的長度t決定，其中i取整數且1≤i≤t-1，按下面方式交叉：

為了避免交叉在基因段內進行導致同一題型試題重復的情況，我們限定交叉點位于第i個基因段內，前i個基因段保持不變，從第i+1個基因段開始逐位進行交換。并且在交叉后立刻評價新產生個體的適應度，將其與父代兩個體比較，如果適應度值相同，則將新個體視為無效個體刪除；否則將其連同父帶個體保留，使新個體直接執行變異操作。

為了保證各個題型、題數的要求，變異過程我們利用變異率決定隨機到哪位并將該位的值取反，同時在該位所在的基因段內，向前或向后搜索與該位最近并且值相反的位，將該位值也取反。

3.5 終止條件

我們將種群規模設置為200，算法執行的最大代數設置為500，當出現如下情況時算法終止：①達到要求的進化代數；②當進化中種群最大適應度值與之前各代種群最大適應度值近似時；③得到滿足用戶的組卷約束要求的種群或得到用戶滿意的試

卷時。

4 仿真試驗結果分析

為了驗證本算法可行，我們分別采用該文算法和傳統遺傳算法針對智能組卷系統進行了仿真。針對《C語言程序設計》的1000道試題進行組卷實驗，將試題按照單選、多選、填空、判斷題型分別建立4個庫文件，并規定每個庫中有250題，每類題型有5種難度。試卷滿分設置為100分；預計答題時間為120 min；試卷總體難度系數設置為0.8。仿真結果如圖1、圖2所示。

通過上面比較可以看出，該文算法能夠得到最優解，并且在進化代數和收斂速度上明顯優于傳統遺傳算法，提高了問題的求解效率，能有效地解決智能組卷問題，充分驗證了本算法可行。

參考文獻

[1] 楊路明，陳大鑫.改進遺傳算法在試題自動組卷中的應用研究[J].計算機與數字工程，2004（5）：77-78.

[2] 王麗芳，王楠，李新華.基于一種改進遺傳算法的智能組卷的研究[J].中北大學學報（自然科學版），2006（4）.

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

[4] 路景，周春艷.基于遺傳算法的混合優化策略研究[J].計算機技術與發展，2007，17（3）：144-146.

[5] 吳飛.自適應遺傳算法解決組卷問題的探討[J].重慶科技學院學報（自然科學版），2007（2）.