基于貪心策略自動生成高區(qū)分度試卷的方法

楊超

（合肥學(xué)院 基礎(chǔ)教學(xué)部，安徽 合肥 230601）

基于貪心策略自動生成高區(qū)分度試卷的方法

楊超

（合肥學(xué)院 基礎(chǔ)教學(xué)部，安徽 合肥 230601）

建立了以生成高區(qū)分度試卷為目標(biāo)的自動組卷問題的數(shù)學(xué)模型，針對該模型提出了基于貪心算法的試卷生成方法，將算法應(yīng)用于實際的考試系統(tǒng)中，并與禁忌搜索算法生成試卷的策略進(jìn)行比較，結(jié)果表明：貪心算法用更少的時間找到了更好的解.

試卷生成；貪心算法；區(qū)分度；禁忌搜索算法

隨著信息科技的蓬勃發(fā)展，以計算機題庫生成考卷的做法得到了廣泛應(yīng)用. 為了適應(yīng)各類考試的需求，各種約束條件下的智能化考試抽題組卷研究取得了一些有效的研究成果[1-4]. 諸如招聘等類型的考試，需要有效拉開不同水平應(yīng)試者的分?jǐn)?shù)距離，這種情況下區(qū)分度在選題中顯得尤為重要，現(xiàn)有的智能組卷算法雖能在保證區(qū)分度的同時兼顧試卷難度和知識覆蓋面，但算法復(fù)雜，且由于抽題過程在“強約束”下，經(jīng)常會出現(xiàn)無法滿足性能要求的試卷（即約束問題變成了一個NP問題）. 本文弱化其中的部分約束條件，以獲取最大平均區(qū)分度的試卷為組卷目標(biāo)，設(shè)計了一種基于貪心策略的試卷生成算法.

1 問題定義

假設(shè)題庫中題目數(shù)量為n，分別為Q1,Q2,…,Qn，題庫涵蓋了m個知識點C1,C2,…,Cm. 命題者在制作試卷時，要確定試卷內(nèi)容涵蓋的知識點和考試時間等約束條件，生成的試卷必須符合這些要求，且試卷中題目的平均區(qū)分度越大越好. 此組卷問題可以轉(zhuǎn)化為組合最佳化問題[5]，定義為一個目標(biāo)函數(shù)與一組考試約束條件的組合：

2 貪心算法設(shè)計

本文提出的貪心算法具體步驟描述如下.

1）初始化. 將題庫中的題目依區(qū)分度由大到小排序，挑選前10%的題目為候選題庫. 設(shè)置候選題庫中題目的選中狀態(tài)xi=0，試卷知識點相關(guān)度Rj與試卷答題時間T設(shè)為0.

2）計算試卷知識點相關(guān)度Rj與試卷答題時間T. 其中，

3）試題挑選階段. 首先計算如果題目Qi加入試卷后，知識點相關(guān)度的誤差值eRj與答題時間的誤差值eT，計算公式如下：

根據(jù)上面的計算結(jié)果，在沒有被選中的題目中挑選使知識點和答題時間誤差值總和最小的題目加入試卷，并將該題的選中狀態(tài)xi設(shè)為1，同時檢查試卷是否符合約束函數(shù)的要求，如果有一個條件滿足則進(jìn)行下一步驟，否則回到步驟2）繼續(xù)添加試題.

4）修正階段. 根據(jù)步驟3），當(dāng)挑選的試題數(shù)達(dá)到試卷要求時停止選題，但此時很有可能沒有滿足約束條件（1）或（2），修正階段是為了檢查試卷的考察知識點和時間限制是否已經(jīng)符合要求.如果不符合，則在候選題庫中按照區(qū)分度從大到小的順序選擇xi=0的試題與試卷中的試題逐一進(jìn)行交換，根據(jù)公式（4）和（5）計算兩題交換后的誤差值. 一般選擇誤差值遞減最大的兩題進(jìn)行交換，直到誤差值為0，即表示試卷滿足所有約束條件.

5）優(yōu)化階段. 為了生成最大區(qū)分度的試卷，對已經(jīng)初步完成的試卷進(jìn)行優(yōu)化. 即從候選題庫和試卷中各挑選1題，若二者的區(qū)分度最大且試卷的知識點覆蓋與時間限制都能符合要求，則將二者進(jìn)行交換，直到無法從候選題庫找到適合交換的題目，表示試卷已經(jīng)不能再優(yōu)化了，則貪心算法停止.

6）算法結(jié)束，生成試卷. 以上步驟結(jié)束后，所有在候選題庫中xi=1的題目，即為貪心算法挑選的題目，導(dǎo)出即可得到目標(biāo)試卷.

3 算法應(yīng)用與分析

本文提出的試卷生成策略在“合肥學(xué)院基礎(chǔ)部計算機文化基礎(chǔ)無紙化考試系統(tǒng)”中得到應(yīng)用，實驗程序以JAVA技術(shù)實現(xiàn)，測試平臺為個人計算機，CPU Intel CORE 2 DUO 3.0GHz、內(nèi)存2G DDRIII，操作系統(tǒng) Windows2000 server. 試題庫平臺為Microsoft SQL 2000，題庫試題數(shù)從2 000到20 000題. 從題庫中挑選題目生成試卷時，必須滿足所有知識點相關(guān)度的下限，總答題時間介于90～120 min（即T0=90，T1=120）. 為了驗證所提算法的有效性，在相同環(huán)境下我們還應(yīng)用文獻(xiàn)[7]提到的禁忌搜索算法生成試卷，并將二者進(jìn)行比較，結(jié)果如表1所示.

表1 貪心算法和禁忌搜索算法生成試卷情況比較

由表1可知：貪心算法求解所需的計算時間均小于禁忌搜索算法；當(dāng)題庫數(shù)量2 000～4 000時，貪心算法求得的平均區(qū)分度比禁忌搜索算法稍差，但題庫數(shù)量在5 000～20 000時，貪心算法所得的平均區(qū)分度比禁忌搜索算法理想. 此外，在貪心算法的設(shè)計中，首先需對題庫的內(nèi)容做篩選，即將區(qū)分度差的題目過濾，這樣既能保證從題庫中挑選的題目具有較好的區(qū)分度，又能節(jié)約大量的處理時間.

4 結(jié)束語

本文以生成高區(qū)分度試卷為目標(biāo)，提出一個基于貪心算法的解決策略，并在實際中加以應(yīng)用. 但本文定義的目標(biāo)函數(shù)具有一定的局限性：在此目標(biāo)函數(shù)下，只考慮題庫中區(qū)分度好的題目，區(qū)分度較差的題目被選中的機率很少甚至沒有，使區(qū)分度差的題目失去存在于題庫的意義. 如果在此算法中出加入認(rèn)知分類和難易度等因素，則可編制出更加精確的評價被測試者能力水平的試卷.

[1] 閻峰，安曉東. 基于粒子群優(yōu)化算法的智能抽題策略研究[J]. 中北大學(xué)學(xué)報：自然科學(xué)版，2008, 29(4):333-337.

[2] 唐朝舜，董玉德，熊蓉. 在線隨機組卷算法研究及實現(xiàn)[J]. 合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2006, 29(3): 296-299.

[3] 董敏，霍劍青，王曉蒲. 基于自適應(yīng)遺傳算法的智能組卷研究[J] .小型微型計算機系統(tǒng)，2004, 25(1): 82-85.

[4] 陳曉東，王宏宇. 一種基于改進(jìn)遺傳算法的組卷算法[J]. 哈爾濱工業(yè)大學(xué)學(xué)報，2005, 37(9): 1174-1176.

[5] 張愛文，樊紅蓮. 自適應(yīng)遺傳算法用于自動組卷中的數(shù)學(xué)模型設(shè)計[J]. 哈爾濱理工大學(xué)學(xué)報，2006, 11(5): 18-20.

[6] 董圣鴻，漆書青，戴海琦. 題目難度、區(qū)分度參數(shù)人工賦值方法的研究[J]. 考試研究，2005, 1(1): 25-32.

[7] HWANG Gwojen, YIN Pengyeng, YEH Shuheng. A tabu search approach to generating test sheets for multiple assessment criteria[J]. IEEE Transactions on Evolutionary Computation, 2006, 49(01): 89-97.

A Greedy Algorithm-based Method of High Discrimination Degree for Automatically Generating Test Papers

YANG Chao
(Department of Basic Sciences Teaching, Hefei University, Hefei 230601, China)

A mathematical model for automatic generating test papers with a high discrimination degree was designed. An automatic test paper generation method based on the greedy algorithm was proposed for the model. The algorithm was applied to the actual examination system. The experimental results showed that in most cases, the proposed greedy algorithm achieved a better solution in less time compared with the tabu search algorithm.

test paper generation; greedy algorithm; discrimination degree; tabu search algorithm

TP312

A

1006-7302（2011）01-0061-04

2010-09-17

楊超（1979—），男，講師，碩士，安徽六安人，主要研究方向為計算機軟件與理論.