楊超

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

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

楊超

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

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

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

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

1 問題定義

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

2 貪心算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

[5] 張愛文，樊紅蓮. 自適應(yīng)遺傳算法用于自動(dòng)組卷中的數(shù)學(xué)模型設(shè)計(jì)[J]. 哈爾濱理工大學(xué)學(xué)報(bào)，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—），男，講師，碩士，安徽六安人，主要研究方向?yàn)橛?jì)算機(jī)軟件與理論.