基于改進隨機抽取策略的智能組卷算法

王 東

(貴州師范學院 數學與計算機科學學院,貴州 貴陽 550018)

基于改進隨機抽取策略的智能組卷算法

王 東

(貴州師范學院 數學與計算機科學學院,貴州 貴陽 550018)

針對隨機抽題過程中出現的重復抽選問題，設計了一種優(yōu)化的數據結構，實現了無回溯快速組卷.基于該方式，抽題前預先評估已抽取試題的分布情況，確定待抽取試題的章節(jié)范圍，再從其候選集合中隨機抽選試題，進而有效解決組卷過程中試題分布不合理的問題.該算法已經在試題庫考試系統(tǒng)中得到成功應用.

自動組卷；試題庫系統(tǒng)；隨機組卷算法；組卷策略

自動組卷就是根據組卷策略指定的約束條件，從題庫中隨機抽取出試題，從而取代人工選題的過程.自動組卷的核心問題之一就是設計良好性能的組卷算法.由于組卷約束條件之間的相互牽制以及試題庫題量的限制，要生成一份符合要求的試卷不是一件容易的事件.目前，自動組卷過程中使用的組卷算法大致分為三類：隨機組卷算法[1-2]，回溯算法[3]和基于遺傳算法[4-7]的組卷方法.其中，隨機組卷算法易于理解，運行速度快，在實際的試題庫管理軟件系統(tǒng)中應用廣泛，并在實踐中得到不斷的改進，如金漢均等提出了分段隨機抽選法[2]，該方法在錄入試題時生成一個隨機數，在組卷時按順序從候選集合中抽取給定數量的試題.與傳統(tǒng)隨機算法相比，該方法效率有所提升，但隨機數的維護代價很大，對一條記錄的修改將導致與之相關記錄集的修改.王萌等提出集合隨機抽選法[8]，該方法使用備選集合來避免回溯，當從備選集合中抽取一個題后再重新生成一個不包含已選試題的備選集，再抽選試題時不會與已抽選試題產生重復.但該方法的主要問題是每抽選一個題就要重新生成備選集，降低了組卷算法的執(zhí)行效率.本文將通過設計高效的數據結構并對組卷算法進行優(yōu)化，實現無重復、無回溯隨機抽題，在抽題時借助章節(jié)可分配數組動態(tài)確定抽取試題的章節(jié)范圍，以期較好地解決試題分布不合理的問題，提高命題組卷的客觀性和科學性.

1 組卷算法數據結構

1.1 設置組卷策略

設置組卷策略就是為自動組卷設定組卷參數，構造試卷結構的過程.設置的組卷策略存儲在數據庫表中，一組組卷策略由存儲在數據庫表中的多條記錄組成，每條記錄表示試卷中的一種題型，包括題型號、試題數、單題分值、總分值、各難度試題數等.設置組卷參數時，部分參數由用戶明確設定，如每種題型的試題數、單題分值，部分參數可通過計算得到，如試題難度，文獻[9]中就提出了一種依據正態(tài)分布函數計算試卷中試題難度分布的方法，通過試卷平均難度推導出各難度題所占比例.文獻[10]提出了基于難度級別的分割遞歸算法.根據每類題型的難度級別和抽題總量，確定不同難度級別試題的抽題數量.

1.2 確定章節(jié)分值

組卷前設置試卷中各章節(jié)所占的分值是常見的約束條件之一.各章節(jié)所占的分值分配可根據命題者的經驗手動設定，或者根據各章節(jié)在課程大綱中所占的學時比例自動計算.對于后者，為提高組卷的成功率，各章節(jié)分配分值不宜設置為固定值，而采用浮動分配方式，即允許在標準分配的基礎上左右浮動一定比例.例如：某章按學時比例計算，若試卷滿分為100分，該章可分配標準分值為20分，按浮動比例5%計算，則該章組卷時實際分配分值在15到25分之間都是符合組卷要求的.

具體實現時，章節(jié)可分配分值用一個二維數組ChapterScore存儲.數組元素ChapterScore(i, 0)的值Si表示可分配標準分值，ChapterScore(i, 1)中的值Ci表示章號(見表1).

表1 章節(jié)分值分配數組

組卷時，首先計算每章的可分配分值，按分值大小降序排序存儲到ChapterScore數組中，下標為0的存儲單元中存儲的章節(jié)號為優(yōu)先抽題的試題范圍，若該章節(jié)范圍內沒有滿足條件的試題，則以下標為1的存儲單元存儲的章節(jié)號為抽題范圍，依此類推.當遍歷完ChapterScore數組中的所有單元后，仍沒有滿足條件的試題，則組卷失敗.當每抽選一個題后，根據試題所屬章節(jié)號修改ChapterScore數組對應元素的分值，再對ChapterScore進行排序, 保持ChapterScore數組按分值大小降序排序.

1.3 隨機抽題算法數據結構設計

確定了組卷的具體要求，將這些要求轉化成試卷中每類或每個題目的難度、知識點、分值等量化參數，然后根據一定的算法抽取試題.

抽題算法主要數據結構包括兩個部分，第一部分為章節(jié)結構向量，每個向量元素含3個信息，章節(jié)ID號、試題數、試題ID列表向量指針，第二部分為各章試題ID列表向量，每個元素存儲試題ID號.圖1為抽題算法數據結構.章節(jié)結構向量結點結構定義如下：

PublicStructurenode

DimchapterIDAsInteger

DimnumAsInteger

DimrefAsObject

EndStructure

圖1 抽題算法數據結構

2 隨機組卷算法描述

2.1 創(chuàng)建候選試題數據結構

組卷時，先將數據庫中的試題信息讀入內存中，生成供隨機選題用的候選試題數據結構(圖1)，生成該數據結構需完成以下步驟：(1)以題型、難度為參數，生成章節(jié)結構向量;(2)分別以題型、難度、章節(jié)ID為參數，生成各章節(jié)的試題ID列表向量.

創(chuàng)建候選試題數據結構的算法描述：

輸入：章節(jié)數row，題型qtypeID,難度系數diff

輸出：候選試題數據結構M

FunctioncreateM(ByValrowAsInteger,ByValdiffAsString,ByValqtypeIDAsInteger)AsArray

DimM(row- 1)Asnode‘聲明包含row個結點的章節(jié)結構向量

DimstrsqlAsString= ""

Dimdv,dv1AsDataView

DimdbAsDataBase=NewDataBase

‘給定難度和題型條件下獲取數據庫各章節(jié)試題數量

strsql= "selectchapterID,count(*)numfromquestionwheredifficult=@diffandquestiontypeID=@qtypeIDgroupbychapterID"

dv=db.RunSelectSQL(strsql)

DimiAsInteger

Fori= 0Todv.Count- 1

M(i).chapterID=dv(i)("chapterID")‘初始化章節(jié)ID

M(i).num=dv(i)("num") - 1‘試題數量

dv1 =db.RunSelectSQL("selectIDfromquestionwheredifficult=@diffandquestiontypeID=@qtypeIDandchapterID=@chapterID")‘給定難度、題型及章節(jié)條件下獲取數據庫試題ID

Dimqlist(dv1.Count- 1)AsInteger‘聲明試題向量

‘初始化試題向量

Forj= 0Todv1.Count- 1

qlist(j) =dv1(j)("ID")

Next

‘章節(jié)結點指針指向試題向量

M(i).ref=qlist

Next

ReturnM

EndFunction

2.2 無重復隨機抽題

抽題時，根據章節(jié)ID在章節(jié)結構向量中順序查找到對應的元素M(i)，取得試題數M(i).num,根據試題ID列表指針取得試題ID列表qlist.在qlist的下標0到M(i).num-1范圍內隨機產生一個下標，該下標的數組元素值為抽取的試題ID，把這個元素值跟M(i).num-1下標的元素值交換，把隨機產生過的位置替換為未被選中的值.并將M(i)的試題數域減1.使下一次隨機抽題在下標0到M(i) .num-2范圍內進行,保證每次隨機抽取的試題不重復.

無重復隨機抽題算法描述：

輸入：候選試題數據結構M，章節(jié)ID

輸出：隨機抽取的試題ID

FunctionsearchM(ByValM()Asnode,ByValchapterIDAsInteger)AsInteger

DimiAsInteger

DimqIDAsInteger= -1

DimIndexAsInteger

竣工后高層建筑變形監(jiān)測中應用GPS技術的價值探究……………………………………………………… 姚建東（6-30）

‘順序掃描候選試題數據結構M

Fori= 0ToM.count- 1

‘若章節(jié)向量章節(jié)域與章節(jié)ID相等且該章節(jié)候選試題數大于0，從中隨機抽取試題

IfM(i).chapterID=chapterIDAndM(i).num> 0Then

Randomize()

'在0到dv1.count-1之間隨機取下標

Index=CInt(Int((M(i).num) *Rnd()))

'在0到dv1.count-1之間隨機取下標CInt(Int((upperbound-lowerbound+ 1) *Rnd() +lowerbound))

DimqlistAsObject=M(i).ref

qID=qlist(Index)‘取得選擇試題ID

‘把這個元素值跟m-1下標的元素值交換，把隨機產生過的位置替換為未被選中的值

DimxxAsInteger=qlist(Index)

qlist(Index) =qlist(M(i).num)

qlist(M(i).num) =xx

M(i).num=M(i).num- 1‘將該章節(jié)候選試題數域減1

EndIf

Next

ReturnqID‘返回試題ID，未抽取成功返回-1

EndFunction

2.3 生成章節(jié)分配分值

ChapterScore數組用于存儲按課時比例生成的可分配分值，在執(zhí)行組卷算法前進行初始化，從數據庫中獲取當前題庫各章節(jié)的學時分布數據，進行統(tǒng)計后存儲到ChapterScore數組中，并對數組按可分配分值降序排序.

生成章節(jié)分配分值算法描述如下：

輸入：題庫ID，章節(jié)分配分值數組ChapterScore，章節(jié)數chapterCount

輸出：章節(jié)分配分值數組ChapterScore

SubCreateChapterScore(ByValquestionbankIDAsInteger,ByrefChapterScore(,)asinteger,byvalchapterCountasinteger)

'從數據庫中獲取課時分布

Dimksfb_dvAsDataView=db.RunSelectSQL("selectB.ks,A.chapterfromksfbAinnerjoinquestionbankoutlineBonA.questionbankID=B.questionbankIDandA.chapterID=B.IDwhereA.questionbankID=" &questionbankID)

DimiAsInteger

'累加各章課時，統(tǒng)計總課時

Dimks_sumAsInteger= 0

Fori= 0Torow- 1

ks_sum=ks_sum+ksfb_dv(i)("ks")

Next

'按課時比例計算可分配分值存儲到ChapterScore數組，ChapterScore(i, 0)表示可分配標準分值，ChapterScore(i, 1)表示章號，

Fori= 0Torow- 1

DimksAsDecimal=Convert.ToDecimal(ksfb_dv(i)("ks"))

ChapterScore(i, 0) =CInt(ks/ks_sum* 100)

ChapterScore(i, 1) =ksfb_dv(i)("chapterID")

Next

SelectSort(ChapterScore,chapterCount) '對可分配分值數組按可分配分值大小降序排序

Endsub

2.4 改進的隨機組卷算法

自動組卷按各種題型分別抽題的方式進行.優(yōu)先處理單題分值大的題型，如分析題較單選題優(yōu)先處理，因為題型的單題分值大小反應了知識點的教學要求和試卷平均難度系數的權重，按題型單題分值從大到小的順序進行各種題型的抽題組卷，有利于滿足組卷約束條件.抽題時根據ChapterScore數組優(yōu)先在可分配分值大的章節(jié)中抽題.分值大的試題將優(yōu)先分布到可分配分值大的章節(jié)中.而且，由于可分配分值隨抽題過程而不斷動態(tài)調整，抽取試題不斷跳躍分布到不同的章節(jié)中，從而使同一題型的試題均勻分布到各章節(jié)中.

隨機抽題組卷算法詳細描述如下：

'生成章節(jié)分配分值

CreateChapterScore(questionbankID,ChapterScore,chapterCount)

'從數據庫中查詢組卷策略明細，返回記錄集

DimdvAsDataView=db.RunSelectSQL("selectB.*fromstrategyAinnerjoinstrategydetailBonA.ID=B.paperstrategyIDwhereA.ID=@strategyorderbyB.singscoredesc")

'若組卷策略明細不為空，則執(zhí)行

Ifdv.Count> 0Then

Dimj,h,r,kAsInteger

'依次對每個題型進行抽題，優(yōu)先處理單題分值大的題型

Fori= 0Todv.Count- 1

'取得不同難度的試題數存儲到diff數組

DimdifficultpreAsString=dv(i)("difficultpre")

Dimdiff()AsString=difficultpre.Split(",")

DimdifstrAsString() = {"易", "中", "難"}

'聲明questionlist變量存儲已抽取的試題ID，試題ID之間用逗號分隔

DimquestionlistAsString= ""

'按“難”、“中”、“易”依次抽取試題

Forj= 0To2

'若當前難度下要抽取的試題數大于0，則執(zhí)行

Ifdiff(j) > 0Then

'聲明arr數組存儲要抽取的試題ID

Dimarr(diff(j) - 1)Asinteger

'創(chuàng)建候選試題數據結構

DimM()Asnode=createM(row,difstr(j),dv(i)("questiontypeID"))

'反復抽選試題

Forh= 0Todiff(j) - 1

' 根據ChapterScore數組依次檢測每章

Forr= 0Torow-1

' 隨機抽題，返回題號

DimIndexAsInteger=searchM(M,ChapterScore(r, 1))

DimkfpAsDecimal= (ChapterScore(r, 0) +ChapterScore(r, 0) *xs)

' 隨機抽題成功且可分配分值大于單題分值

IfIndex<> -1AndCInt(kfp) >=dv(i)("singscore")Then

' 更新ChapterScore數組

ChapterScore(r, 0) =ChapterScore(r, 0) -dv(i)("singscore")

' 對ChapterScore數組排序

SelectSort(ChapterScore,row)

arr(h) =Index

ExitFor

EndIf

Next

'結束本次循環(huán)

Ifr>row- 1Then

ExitFor

EndIf

Next

'形成試題號列表字符串

Fork= 0Toh

questionlist=questionlist+arr(k) + ","

Next

EndIf

Next

Ifquestionlist.Length> 0Then

questionlist=Left(questionlist,questionlist.Length- 1)

'將當前題型抽選的試題列表保存到試卷明細表

insert(dv(i)("questiontypeID"),dv(i)("num"),dv(i)("singscore"),dv(i)("description"),questionlist)

EndIf

Next

EndIf

上面的程序主要執(zhí)行以下幾步操作:(1)調用CreateChapterScore函數生成章節(jié)分值分配數組ChapterScore；(2)執(zhí)行數據庫訪問方法RunSelectSQL返回組卷策略記錄集；(3) 依次對每個題型進行抽題，優(yōu)先處理單題分值大的題型；(4)調用createM函數生成候選試題數據結構；(5)調用searchM函數生成不重復的試題；(6)生成試題號列表字符串questionlist；(7)調用insert方法將當前題型抽選的試題列表保存到試卷明細表.

3 算法分析

應用改進的隨機組卷與傳統(tǒng)算法在生成試卷的執(zhí)行效率上進行了比較, 其中試題科目為《數據庫原理與應用》和《高級語言程序設計》,試題庫題量分別為400個、1 200個， 試題庫試題構成如表2所示.

測試環(huán)境：處理器為i5-4200M2.5GHz,內存為4GB,操作系統(tǒng)為64位windows10.算法基于.NET框架，采用VB.NET語言實現, 試題存儲數據庫選用SQLServer2008R2.不同算法執(zhí)行的比較結果如表3所示.

表2 試題庫試題構成統(tǒng)計表 個

表3 兩種算法執(zhí)行效率的比較

測試結果中，當題量為400時，傳統(tǒng)算法抽取10套含30個題的試卷的平均用時為0.42s，改進的組卷算法平均用時0.14s.當題量為1 200時，傳統(tǒng)算法抽取10套含90個題的試卷平均用時0.76s，改進的組卷算法平均用時0.43s.可以看出，當題量較小時，由于抽題時發(fā)生重復而回溯降低了算法性能，對傳統(tǒng)算法的執(zhí)行效率影響較大，而改進的組卷算法在抽題過程中不會產生重復抽題現象，執(zhí)行效率的穩(wěn)定性較好.同時，兩組測試中，本文算法的組卷效率明顯優(yōu)于傳統(tǒng)算法.

此外，觀察每種題型的試題在各章節(jié)中的分布情況可知，傳統(tǒng)算法生成的20套試卷，其中有4套試卷出現試題分布不合理的情況，同類題型的試題過度集中到某個章節(jié)中.而使用改進的組卷算法生成的試卷，均未出現試題堆積現象，試題分布合理性較好.

4 結束語

組卷是試題庫建設和無紙化考試系統(tǒng)的核心內容.本文對組卷過程中的重復性抽題以及分布不合理的問題，提出了針對性的解決方案.

通過構造高效的數據結構，實現了無重復隨機抽題.使用可分配分值數組提供的信息，避免了相同題型試題過度集中于部分章節(jié)中，從而提高了試題分布的合理性.使用本算法的試題庫管理系統(tǒng)在實際應用中運行穩(wěn)定，完全滿足大批量在線組卷需求.

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

[2]金漢均,鄭世玨,吳明武.分段隨機抽取選法在智能組卷中的研究與應用[J].計算機應用研究,2003,20(9):102-103.

[3]李大輝.基于廣度優(yōu)先回溯算法的試題搜索算法[J].大慶石油學院學報,2006,30(3):100-101.

[4] 張琨，楊會菊.基于遺傳算法的自動組卷系統(tǒng)的設計與實現[J].計算機工程與科學，2012，34(5)：178-183.

[5] 朱婧, 戴青云,王美林.自適應遺傳算法在工程訓練在線考試中的應用[J].計算機工程與應用,2013,49(14):227-230.

[6] 肖桂霞,趙武初,朱偉,等. 基于遺傳算法智能組卷的去重題方法[J].計算機工程, 2012, 38(11): 150-152.

[7]陳國彬,張廣朱. 基于改進遺傳算法的快速自動組卷算法研究[J].計算機應用研究,2015,10(32):2 996-2 998.

[8]王萌, 金漢均,王曉榮. 集合隨機抽選法在智能組卷中的研究[J].計算機工程與設計, 2006, 18(27): 3 583-3 585.

[9]毛秉毅. 一種計算試卷中試題難度分布的有效方法[J].計算機工程, 2002, 28(6): 280-281.

[10]曾一，冉忠，郭永林. 試題庫中自動組卷的算法及試卷測評策略[J]. 計算機工程與設計, 2006, 27(16): 3 024-3 027.

(編輯：郝秀清)

Intelligent test paper generating algorithm based on improved random selection strategy

WANG Dong

(Mathematics and Computer Science Institute, Guizhou Education University, Guiyang 550018, China)

Aiming at the repeated problems in the process of random extraction, an optimized data structure is designed, which can realize the rapid test paper generation without backtracking. Based on this method, the distribution of the test questions is pre evaluated in advance, so as to determine the scope of the section to be extracted. Then questions are randomly selected from the candidates, so as to effectively solve the problem of the irrational distribution in test questions. The algorithm has been successfully applied in the examination question system.

auto-generating test paper; the examination question system; random generating paper algorithms; paper-making strategy

2016-09-23

貴州省2014年本科教學質量工程項目(黔教高發(fā)[2014]378號)

王東,男,wd_gz@163.com

1672-6197(2017)04-0019-05

TP

A