計算機輔助測試中自動組卷技術研究

摘要： 本文介紹了幾種常用的自動組卷技術的算法設計，同時對其中的基于遺傳算法的組卷算法進行了詳細的討論，并提出了改進的策略。

關鍵詞： 計算機輔助測試 自動組卷 組卷算法 遺傳算法

自動組卷是計算機輔助測試（CAT）中重要的組成部分。它綜合了教育學、教育測量學、教育統計學、考試學等多種學科并與人工智能技術進行有效的結合。當有了一個合適的試題庫并且有了足夠的題目數量之后，組卷最基礎的條件就已經具備，下面要考慮的就是組卷的要求。根據目前各類考試對于試卷的要求，我們可以歸納出以下幾個組卷中的基本要點：

A.各種題型中知識點分布符合制卷目標（即考試要求）；

B.試題、試卷難度符合制卷要求；

C.無內容重復和相近的試題。

由此可見，雖然是自動組卷，但在組卷之前，我們需要根據本次考試的類型或知識要求考查學生的程度趨勢線，設置好難度、區分度、知識點分布等基本的組卷要求，然后系統才能夠在此基礎上實現自動組卷。

1.組卷算法

常用的自動組卷方法大致可分為三類：

1.1隨機抽取法[1]

根據組卷狀態空間的控制指標，由計算機隨機抽取一道符合控制指標的試題放入組卷題庫，此過程不斷重復，直到組卷完畢或已無法從題庫中抽取滿足控制指標的試題為止。隨機抽取法的基本算法如下：

1）設置題目屬性，包括題型及該題型的題目數量M、難度、區分度、知識點分布；

2）產生一個隨機數K，1≤K≤n（n為此類題型下題目的總數）；

3）在試題庫中選取第K道題目，查看題目的抽取狀態，若狀態為1，則表示已抽取過該題，則回到第2步，若為0，則表示該題未被抽取，則繼續；

4）檢查該試題的抽取時間，若時間與當前時間間隔小于1年，則放棄抽取，回到第2步，否則繼續；

5）檢查試題的相近題目編號，搜索在已經選取的題目中有無相同編號的試題，若有，則放棄抽取，回到第2步，若沒有，則繼續；

6）將該試題的編號寫入已抽取試題的表中，并且將試題庫中該題的抽取狀態改寫為1，抽取時間寫作當前時間，一道題目抽取完畢，題目數L=L+1。

7）如果L≥M，該題型組卷完畢，否則，回到第2步繼續組卷。

該方法結構簡單，具有很大的隨意性和不確定性，無法從整體上把握題庫不斷變化的要求，不具有智能性。但是，這種方法實現起來較為容易，所以目前仍然是大多數組卷系統所首選的組卷方法之一。

1.2回溯試探法[2]

將隨機抽取法產生的每一狀態類型記錄下來，當搜索失敗時釋放上次記錄的狀態類型。然后按照一定的規律變換一種新的狀態類型進行試探，通過不斷地回溯試探直到試卷生成完畢或退回到出發點為止。該方法適用于類型和出題量都比較小的題庫系統，實際應用時程序結構相對復雜，而且選取試題隨機性差，組卷時間長。對于現在越來越流行的考生隨機即時調題的考試過程來說，它已不符合要求。

1.3遺傳算法求解自動組卷問題

遺傳算法（Genetic Algorithm，簡稱GA）是一種基于進化論優勝劣汰、適者生存的物種遺傳思想的搜索算法[3]。這一基本思想是20世紀70年代由美國密歇根大學的J.H.Holland提出并創立的[4]。在自然界中，各種生物處于不同的環境之下，那些具有適應所處環境特征的物種可以存活下來，而它的這種特征是由它內部的基因所決定的。生物的進化過程最終表現為基因的進化。而基因的進化發生在兩個父輩個體結合產生后代個體的過程中。父代染色體在向后傳遞時發生選擇和交換，從而導致生物群不斷演化，進而產生更有適應力的個體，這便是遺傳。

遺傳算法的名稱來源于自然界，與自然界的遺傳過程相類似。這種算法的處理對象是要搜索問題的一群潛在的可能解，通過使問題的解不斷地進化，最終求得最優解。與自然界相對照，生物對于環境的適應程度在遺傳算法中表現為解的一個適應值或者是評價值，反映了該解相對于其他解的好壞程度。也同自然界一樣，這種具有較高適應值的解就具有更大的生存性和再生性。在遺傳中還有一種現象就是突變，即生物體基因發生的偶然的突然的改變。遺傳算法中，這種現象也存在，即偶然、隨機的改變結果中某些數位值[5]。

2.傳統遺傳算法的問題求解

運用遺傳算法求解問題首先需將所要求解的問題表示成二進制編碼，然后根據環境進行基本的操作：選擇、交換、突變這樣進行不斷的所謂“生存選擇”，最后收斂到一個最適應環境條件的個體上，得到問題的最優解。將其用于自動組卷，可以在一定約束條件下對多目標參數進行優化，從而使組卷技術簡單、通用、收斂速度快、適于并行處理。

遺傳算法可以描述為如下幾個基本步驟：

1）隨機產生初始種群；

2）利用評價函數（適應度函數）對個體計算函數值；

3）按一定的概率對個體進行選擇、交叉、變異等操作產生新種群；

4）重復2、3兩步，直到收斂（找到最佳解或迭代次數足夠多）。

在自動選題時，選題的方式可采用父輩挑選和生存選擇兩種。父輩挑選就是采用不返回隨機抽樣，它使每個題目都有被選中的可能；生存選擇采用允許父輩和子代進行競爭，并讓其中的優良者進入下一輪競爭環境的二分之一擇優選擇。兩種選擇方式共同作用于選題保證了選題的順利完成。在選題的過程中，哪一道題目被選中是一個非均勻隨機事件，其概率依賴于上一次選題的過程。

正如前文所述，遺傳算法具有全局尋優和收斂速度快等優點，所以應該作為設計自動組卷的首選算法。

3.改進的遺傳算法

在傳統的遺傳算法中，初始種群的每個字符串中“1”的數目等于試題的數目s，可是進行遺傳操作（交換、突變）后，字符串中“1”的數目可能大于或小于s，從而變為非法解。此時必須對解進行修正，即進行相應的運算使字符串中“1”的數目為n。這個過程比較復雜，會增加運算量。另外，對于生成試卷的幾個屬性指標，我們的要求也不一樣。對于考試分數，我們希望沒有誤差，而對于其他屬性，如題型、知識點、難度、區分度等只要滿足一定的要求就可以了。因此，對傳統的遺傳算法做如下改進[7]。

3.1編碼的改進

在實際組卷中，假設在試卷中每種題型的數目是固定的，且相同的題型的分數和答題時間是相同的。這樣，可以將整個二進制串按照題目的類型劃分為不同的功能塊。每個功能塊采用獨立的二進制編碼。也就是說，每個功能塊對應一種特定的題型，而該功能塊中，“1”代表該題被選中，“0”代表該題未被選中，“1”的數目即該種題型的試題數目。顯然，按這種規則產生的初始種群已經滿足了試題對題型、分數和答題時間的要求。

3.2交換運算的改進

由于種群中每一個功能塊對應著一個題型，因此，為了保證每個題型的數目不變，交叉點的選擇不能破壞功能塊的完整性。假設交叉點位于第i個功能塊內，則前i個功能塊保持不變，從第i+1個功能塊開始逐位交換。

3.3突變運算的改進

由于在每個功能塊中，“1”的數目即是該題型試題的數目，因此在變異過程中應保證整個種群所有功能塊中“1”的數目不變。可執行如下過程，首先，由變異概率決定某位取反；然后檢查、修正字符串中“1”的數目，保證不發生變化。

3.4用全局最優解替換本次迭代的最差解

為保證好的字符串不至于流失，每次遺傳操作前記錄本次迭代的最優解，若該解優于全局最優解則替換全局最優解，否則全局最優解保持不變。此次遺傳操作后，用全局最優解替換本代的最差解。

4.結語

采用改進的遺傳算法，降低了問題的求解難度，提高了問題的求解效率。當使用傳統的遺傳算法在解決組卷問題上不能得到一個滿意的結果的時候，應該考慮用改進的遺傳算法對其進行改造。

參考文獻：

[1]尹柯等.隨機選題算法的設計與實現.河南大學學報（自然科學版），2004，VOL34，（1）.

[2]胡維華.多目標選題策略研究與應用[J].杭州電子工業學院學報，1999（2）：36—41.

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

[4]Holland J.Adaptation in Natural and Artificial Systems[M].AnnArbor：The University of Michigan Press，1975.

[5]程蕾.基于Agent技術的智能題庫系統的研究與設計.浙江大學碩士學位論文，2003.3：41—46.

[6]閉應州等.基于矩陣編碼的遺傳算法及其在自動組卷中的應用[J].計算機工程，2003（7）：73—75.

[7]楊青.基于遺傳算法的試題庫自動組卷問題的研究.濟南大學學報（自然科學版），2004，VOL18，（3）.