基于web考試系統(tǒng)的智能組卷算法的研究與實現(xiàn)

楊 潔，郭喜鳳，馮貴良

（河北北方學院信息科學與工程學院，河北 張家口 075000）

1 引 言

考試是教學活動中必不可少的一個環(huán)節(jié)，通過考試可以檢驗學生掌握知識的情況。隨著計算機技術的發(fā)展以及網(wǎng)絡的普及，對傳統(tǒng)的教學方式產(chǎn)生了根本性的變革。很多課程已經(jīng)開始采用在線考試方式，很多出卷方式也由計算機自動完成代替教師手工組卷。衡量一個考試系統(tǒng)最重要的標準就是其自動組卷算法的好壞。合理的組卷算法能夠按一定要求由計算機自動從題庫中選擇題目，組合成一套覆蓋全部知識點范圍、難易適中、符合要求題量和分值等約束條件的試卷。

試卷質(zhì)量的好壞直接影響考試成績是否能反映學生的學習成果。在線考試系統(tǒng)中組卷算法是決定組卷質(zhì)量的核心因素，組卷質(zhì)量決定了試卷的質(zhì)量。因此，組卷算法的性能是本文所要討論的內(nèi)容。

2 組卷算法概述

目前國內(nèi)外考試系統(tǒng)種類繁多，常用的組卷算法有以下四種：

2.1 隨機抽取算法

這種算法基本思想主要采取兩種隨機策略，一種是由計算機隨機抽取，滿足條件的試題放入試題庫，此過程不斷重復，直到組卷完畢為止。另一種是根據(jù)既定的指標，隨機從試題庫中尋找試題和指標比較，符合的放入試卷中，不符合的則放棄，重新抽取試題，如此循環(huán)，直到組卷完畢或者宣告此次組卷失?。?］。該方法實現(xiàn)簡單，對于單道題的抽取運行速度較快，應用廣泛。但是對于整個組卷過程來說組卷成功率低，只能尋找滿足約束條件的題目，沒有優(yōu)化試卷的功能。尤其是當題庫中各類型平均出題量較低時，組卷往往以失敗而告終。

2.2 基于項目反映的自動組卷算法

這種算法是由適用性測試方法發(fā)展而來的，該方法的思想是盡可能的選擇符合被測試者實際水平的試題。該自動組卷算法需要先評估被測試者的能力，在組卷過程中按照能力約束條件找出符合其平均能力的試題，然后通過循環(huán)修正試題的總體難度以達到最終的測試目的。該方法在實踐運用中由于教師水平不同，試題庫范圍不同，很難確定各種試題的難度和分值等屬性，不能得到一個標準的約束條件，使得組卷的成功率下降。

2.3 回溯試探法

該算法是對隨機抽取算法的改進，是以深度優(yōu)先的方式搜索問題解的過程。根據(jù)事先約定的約束條件隨機的在試題庫中抽取試題進行取舍?；厮葸x取法把產(chǎn)生的每一個狀態(tài)類型紀錄下來，當搜索失敗時釋放上次紀錄的狀態(tài)類型，然后再重新進行試探，通過不斷的回溯試探直到試卷生成完畢或退回出發(fā)點為止［2］。當試卷題量和試題庫規(guī)模比較小時，該算法效率較高，避免了隨機抽取法的盲目性，組卷成功率較高。但是如果試題庫比較大，回溯試探法可能會進行多次無效的試探，導致組卷時間過長，而且該算法選取的試題缺乏隨機性，不能作為理想的智能組卷算法。

2.4 遺傳算法

遺傳算法是一種并行的、能夠有效優(yōu)化的算法。它從解釋自然界中生物的進化論入手，模擬達爾文的自然進化模型，從代表問題潛在解集的一個種群開始，按照優(yōu)勝略汰的原則，逐步演化出更好的最優(yōu)解［3］。運用遺傳算法，需要在每代通過適應度挑選最優(yōu)個體，然后通過選擇、交叉、變異、遷移等操作進行不斷的所謂 “生存選擇”，最后收斂到一個最適應約束條件的個體上，產(chǎn)生出最接近問題的解。遺傳算法逐漸被用于求解最優(yōu)化的問題中，該算法容錯性強，搜索空間沒有特殊要求，適用范圍廣。但在進化過程中容易陷入局部最優(yōu)解，發(fā)生 “早熟”現(xiàn)象。

3 組卷建模

3.1 試題屬性約束

組卷工作要考慮多方面的因素：要覆蓋教學大綱覆蓋的知識點，明確考試目標，試題的數(shù)量和題型分布。同時，題庫中的每個試題都由屬性值約束。根據(jù)教育測量理論，試題的屬性約束包括：難度 （D）、區(qū)分度 （Q）、知識點 （K）、題型 （TY）、認知度 （S）、章節(jié) （U）、時間 （T）。其中，影響試題質(zhì)量的主要因素是試題難度和區(qū)分度。

試題的難度就是被測試者對該試題的失分率。難度系數(shù)用公式表達如下：

其中，D表示試題的難度系數(shù)，T表示該題的分值，表示被測試者在該題目的平均得分。從上式可以看出，平均分越大，該題目的難度系數(shù)越小。當平均分為滿分時，難度系數(shù)為0，當平均分為0時，難度系數(shù)為1，難度系數(shù)的取值范圍為：0≤D≤1。

試題的區(qū)分度是為了區(qū)分被測試者掌握知識水平的高低。高區(qū)分度的題目，如果被測試者能回答正確，說明水平就高，反之說明水平不高。根據(jù)研究，區(qū)分度的估算方法是：將學生按題目的得分成績排序，將排名前25%的平均成績記為H，排名后25%的平均成績記為L，F(xiàn)記為該題目的總成績，則區(qū)分度用Q表示為：

當區(qū)分度高于0.5時，認為該題目區(qū)分度很好；低于0.2時該區(qū)分度較差，該題目不能使用；區(qū)分度位于二者之間則認為區(qū)分度一般，需要改進題目質(zhì)量。

作為試卷的評分指標，試題難度D越大，試題區(qū)分度就越小。當D＝0.5時，區(qū)分度Q最大，說明試題分數(shù)分布比較廣泛。

3.2 組卷問題數(shù)學模型

智能組卷的數(shù)學模型相當于是一個多目標和多約束條件組合的優(yōu)化問題。根據(jù)以上約束條件，可以將試卷題目做一個二維矩陣：

其中，n為試題總量，每一行代表一個試題，每一列都是該題目的屬性約束。目標函數(shù)是將多個目標依照各自權重組合成單一目標來優(yōu)化處理以期找到問題的近似最優(yōu)解。故能否成功組卷就是在一個試題庫A＝ ｛a1，a2，…，an｝中能否找到一個接滿足試卷的所有約束條件，其目標函數(shù)為：

其中，權重w1＋w2＋…＋w7＝1。

4 基于分層遺傳算法的實現(xiàn)

在傳統(tǒng)遺傳算法中，因為種族多樣性過早喪失，交叉操作的搜索能力減弱，當種族出現(xiàn)過早收斂時，很難有效的增加種群多樣性，會導致早熟現(xiàn)象發(fā)生［4］。為了保持種群的多樣性，我們采用分層次種群協(xié)同進化的策略。該策略就是隨機生成多個種群，每個種群有多個個體，種群獨立操作，隔多代之后，各種群再進行遷移操作以保持種群的多樣性，這樣可以得到質(zhì)量更高的解。該算法和一般的遺傳算法類似，只是在初始種群的時候進行了分化處理，生成多個子種群，這樣，每個子種群有各自的樣本，可以得到更優(yōu)的結果，自適用度更高。

分層次的遺傳算法主要由編碼、選擇、交叉和變異組成［5］。

4.1 編碼

在求解過程中將問題進行編碼主要是為了提高搜索性能。已有大量數(shù)據(jù)表明，在多約束條件下，采用整數(shù)編碼的遺傳算法效率較高，因此，本算法中采用整數(shù)編碼的方式。將每套試卷的結果映射到一個染色體上，即一個試題代表一個染色體基因。根據(jù)試題的類型設置段數(shù)，每段編碼的基因個數(shù)正好等于該類型試題庫中的序號。同時，染色體采用長編碼策略處理，染色體中的基因個數(shù)即為試卷中試題的總數(shù)，且題型間的編碼方式是獨立的。

4.2 選擇

改進的遺傳算法的選擇操作在子種群內(nèi)部進行，根據(jù)其平均適應度對子種群進行選擇。其中，適應度高的子種群被選擇進入下一次迭代過程，反之則被淘汰。

4.3 交叉算子

該算法的交叉不僅是種群內(nèi)部的交叉，子種群間和子種群內(nèi)也同時進行交叉。種群內(nèi)部進行交叉操作后，兩子種群間也要進行段間交叉算子的方法。完成交換后子種群數(shù)增加一倍，為了保證種群數(shù)目的不變，在做交叉算子的兩種群間進行適應度比較，適應度較大的保留，反之淘汰。

4.4 變異算子

因為變異算子是有小概率事件產(chǎn)生的，為了提高搜索速度在改進算法中采用單點變異算子。隨機選取一個染色體，然后生成0-1的隨機數(shù)r，當r小于其變異概率則在每段隨機生成一個變異點，即在該類題型段中隨機選取一個未被選中的題目并標記為選中，同時該題置換成未選中，反之不進行變異操作。

5 數(shù)據(jù)分析

下表1為傳統(tǒng)遺傳算法和改進后的算法在考試系統(tǒng)中組卷成功率數(shù)據(jù)的對比，其中1表示傳統(tǒng)算法，2表示改進后的遺傳算法：

表1 個題型平均約束條件對比

通過以上數(shù)據(jù)表明，實際應用中遺傳算法中易出現(xiàn)收斂速度慢、穩(wěn)定性差、易早熟的特點。通過修改遺傳算法中的算子以及對適應度函數(shù)進行尺度變化可以避免早熟現(xiàn)象的發(fā)生。但在單種群基礎上的改進只能控制個體進化，很難達到理想結果，選擇多種群進化可以改善遺傳算法的全局收斂性，控制早熟度。改進的遺傳算法在全局搜索性能和收斂速度上都有明顯的優(yōu)勢，組卷質(zhì)量較高。能夠滿足實際的需求。

6 總 結

隨著計算機技術的發(fā)展和普及，計算機輔助教學已經(jīng)作為一門新的教學方式越來越受到廣大教育工作者的關注。智能組卷作為計算機輔助教學的核心也是大家關注的焦點。組卷算法是評價一個組卷好壞的重要因素［6］。

分層次的遺傳算法由于種群的多樣性，提高了局部收斂度和全局的搜索能力，基于該算法的自動組卷系統(tǒng)組卷質(zhì)量高，知識點分布均勻，試題難易適中，降低了試卷的重復率，同時降低了人工組卷中由于人為因素所造成的失誤。真正實現(xiàn)了教考分離和考務自動化。

［1］路平，王敏娟，萬昆.試題庫自動組卷策略研究［J］.電腦開發(fā)與應用，2001，14（02）：9-11.

［2］王宇穎，侯爽，郭茂祖.題庫系統(tǒng)市局自動生成算法研究［J］.哈爾濱工業(yè)大學學報，2003，35（03）：342-346.

［3］趙忠平，楊浩.智能組卷系統(tǒng)的設計與實現(xiàn)［J］.山西師范大學學報：自然科學版，2008，22（02）：28-32.

［4］蘇小紅，楊博，王亞東.基于進化穩(wěn)定策略的遺傳算法［J］.軟件學報，2003，14（11）：1863-1868.

［5］劉彬等.智能組卷系統(tǒng)試題庫結構的研究［J］.信息技術，2002，3（07）：2-4.

［6］劉樹剛.一種 web測試中的組卷策略及其改進［J］.煙臺大學學報，2004，17（01）：59-64.