自動組卷系統試題難度和知識點覆蓋控制算法

柳浪濤，谷 林

（西安工程大學 計算機科學學院，陜西 西安710048）

0 引 言

題庫管理系統的自動組卷功能在教學活動中可以減輕教師出卷的工作負擔，能夠科學、全面考核學生的學習成績，及時反饋學生對知識的掌握情況，提高教學質量［1－4］.自動組卷通常需要按照組卷人對試卷的要求設置基本信息（題型，各題型對應題目的數量，題型的難易等級，每道題目的分值），然后依照設置生成一套符合要求的試卷［5－6］.

題庫管理系統中能夠實現自動組卷的核心是自動組卷的算法.目前已有不少學者對此類算法進行了研究，文獻［7］以分類的方法將試題庫全集劃分成若干個子集，并且把將要生成試卷的試題按一定的規則分解成不同的試題子集，然后針對不同的試題子集隨機抽取指定數量的試題，此算法縮小了隨機抽題的范圍，并且在一定條件下提高了組卷的效率，但是在約束條件變少，導致劃分的試題子集也減少的情況下，對試題的抽取難以實現精確控制；文獻［8］提出了基于線性遞減系數粒子群優化算法策略，試圖避免粒子群優化算法在組卷過程中陷入局部最優的困局，但本質上是調整了粒子群優化算法的慣性系數，使得算法中的步長減小，這只會減小組卷過程中出現局部最優問題的概率，但不能從根本上避免粒子群優化算法中的局部最優問題；文獻［9］在實現組卷的過程中依靠蟻群算法的快速和智能搜索能力，先對建立的數學模型進行求解，然后得到最優組卷方案進行組卷.

文中研究的組卷算法綜合考慮了組卷人對試卷各指標（難度、章節、知識點）的設置，在組卷過程中系統依照“卷內分塊、組塊分層”的機制將被組的試卷按照題目的類型分成若干個題型塊，并且在算法實現過程中將每一個塊分成數據層、處理層、存儲層.系統會在處理層完成每一個題型塊的所有組卷操作，每當一個題型塊的組卷動作完成，系統會將被組卷模塊的難易等級與設置的參數進行比較，如果分析的結果和設置的參數一樣則此模塊的組卷完成，進行下一個模塊的組卷動作，否則系統要不斷調整處理層數據的難易等級，向被設置的參數逐漸逼近直到相等為止.

1 設計思想

將題目的知識點和難易程度作為組卷過程的兩個因素，為了對其進行有效控制，所定義的題庫信息如表1所示.其中，知識點用于說明題目所屬章節信息，它是出卷時進行知識點覆蓋規則匹配的一個重要參數.將試卷本身看成一個整體研究對象，其組卷過程如式（1）所示：

表1 題目信息表Table 1 Title information

式中，P表示一個對象的組卷，Q表示成功組成一套試卷的所有動作，F表示只考慮難易程度（H），知識點（K），題目類型（T）3因素的組卷動作，f1（H，K，T）表示對此模塊進行第一次有關難易程度（H）、知識點（K）、題目類型（T）的驗證操作，Qt表示對同種類型題目的知識點和難易程度進行平衡操作，其中fs（H，K，T）中s由其迭代的次數決定.依照此方法實現系統的組卷，由于要將題型、知識點、難易等級綜合考慮在內，所以涉及的內容廣，實現起來對程序員的要求高，并且由于程序的嵌套導致系統的效率不高.

按卷內分塊和組塊分層的機制把一套完整的試卷按照題目類型分成若干個模塊，再將每一個模塊看成一個對象，其次再把每個對象分成3個層次：首先，處理層根據隨機函數從數據層取出對應數量的題目（數量的大小在試卷的指標信息表里獲取，其中試卷的指標設置如表2所示），再將當前題型塊的難易等級（其中難易等級的計算如式（4）所示）與試卷指標里設置的難易等級進行比較，如果相等表示此模塊的組卷動作完成，并且將處理層數據存入到存儲層，否則執行處理層的組卷均衡動作，如式（2）所示.

表2 試卷指標信息Table 2 Papers index information

式（2）所描繪的是單個對象在處理層的驗證過程，G表示此次組卷的所有動作，g1（H，U）表示對此模塊進行一次有關難易程度（H）、知識點（K）的驗證操作，gn（H，K）表示對當前模塊信息進行n次查詢然后與組卷要求進行比較，如果不符合組卷要求則要剔除相應題目，然后重新來組織此模塊，其中n的大小是由驗證次數決定.要想依照此設計思想完成組卷，關鍵點就在于對試卷難易等級的測量.

2 難易等級測量

為了衡量大多數人的學習情況，難易等級是按照正態概率分布思想來劃分的，各個等級的概率分布如圖1所示.圖1中不同難易等級的值是將標準正態分布在－2σ，－σ，σ，2σ處分割成5塊，分別取各塊所占面積的近似值，其中容易和難各占2.5%，較易和較難各占13.5%，中等占68%.同時，在估計某種題目類型的難易程度時依照統計學中均值的思想，以百分制為例，系統分別給這5個等級賦予一組不同的估計系數，其系數的估計公式如式（3）所示：

圖1 等級概率分布圖Fig.1 Level probability distribution

式中，Yn表示第n等級的估計系數，Xk表示第k等級在概率分布圖中所占的比重.圖1中從右往左5個等級的估計系數分別是0.987 5，0.917 5，0.51，0.092 5，0.012 5.系統通過計算所有題目的分數所對應的均值來估計同一試卷的難易等級.其估計公式如式（4）所示：

式中，Xk表示第k個題目的分數，Yn表示當前題目的難易等級系數，Z是最終計算獲得的一個統計分值，通過查看Z值落在的等級區間即可獲得試卷的難易等級.其中試卷的等級區間是依靠難易程度所占的比重來計算的.以總分為百分制的試卷為例，易等級所占比重為2.5%，所以它的分值的區間就是［0，2.5］，其他等級依次類推.

3 算法實現

本算法優先考慮組卷人對試卷的指標設置，在滿足試卷指標設置的情況下，通過難易等級分析公式對組成的試卷進行難易等級分析，如果分析的結果不滿足組卷要求則調用均衡難易等級的方法調整組成的試卷，否則執行下一模塊的組卷.算法主要過程如下：

（1）初始化數組a［4］［4］用于存放組卷人對試卷的指標設置信息，初始化標簽i設置初始值0，用于訪問第i行指標a［i］［0］到a［i］［3］的數據.初始化3個緩沖區tempor List、title List、examation List分別用于存儲組卷過程中數據層、處理層、存儲層數據.

（2）從a［i］［0］到a［i］［3］中取出第i行的數據，按照取出數據的要求（試卷指標）從數據庫里面獲取對應的題目（此題目類型中，不同知識點的不同難易等級題目各兩道）信息存入tempor List，然后從tempor List里隨機獲取指定數量（在存儲指標的數組中獲取）的試題存入title List.

（3）調用式（4）估算title List中試題的難易等級，如果比要求高（低）執行步驟（4），否則執行步驟（5）.

（4）從title List中剔除高于或等于（低于或等于）的一道試題，從tempor List里面找出難易等級為次高（次低）的且title List中沒有此知識點的試題.如果還高（低）跳轉到步驟（3）.如果出現低（高）跳轉到步驟（6），表示試題不足不能組卷.

（5）將title List數據存入examation List（就是存放整個試卷的試題），如果標簽i的值小于4（題目類型只有4種），標簽i的值加1，然后跳轉到步驟（1），否則跳轉到步驟（7）.

（6）輸出提示，試題不足不能完成組卷.

（7）將titleList中試卷打出組卷完成，結束.

3.1 算法的關鍵代碼

3.2 實驗結果與組卷結果分析

實驗針對一般隨機算法和文中描述算法，在同一難易等級的題目數量不變，組卷中分別取題目數量為15，19，20，21，25的條件下完成.實驗結果統計如圖2和圖3所示，根據數據表明，依靠一般隨機算法實現組卷成功與否只取決于題庫里試題的數量，但是組卷結果符合組卷要求的概率比較低.圖3中實驗五的成功率沒有達到100%，究其原因發現，在題庫中只有20道題目的難易等級為“容易”，不能組成具有25道題目且難易等級為“容易”的試卷，從而造成組卷失敗.但是在真實的組卷環境下，題庫中題目數量會遠遠大于要組試題的數量，所以不會出現類似于圖3中實驗五的情況.

圖2 一般隨機算法實驗結果圖Fig.2 General stochastic algorithm test results

圖3 文中描述算法實驗結果圖 Fig.3 Algorithmic test results

表3是使用一般隨機算法和文中所述算法實現要求難度為“較難”的組卷結果分析表.由表3看出，一般隨機算法的試卷難易等級為“中等”，不符合組卷中難度的等級要求，并且存在知識點重復（同一章節號的多道題目）的現象，而文中描述算法的組卷結果，難度等級為“較難”符合組卷要求，并且克服了知識點重復現象.因此綜合對以上2種算法的實驗結果與組卷結果可知，文中描述的組卷算法，組卷結果更加合理.

表3 結果分析Table 3 Result analysis

4 結束語

本文采用“卷內分塊、組塊分層”的組卷機制，設計了一套完整的自動組卷算法.經過實驗并與一般隨機算法對比分析，證明此算法在試卷難度和知識點覆蓋控制方面具有良好的改進效果，并且系統運行速度較快、組卷效率較高.

［1］ 李麗，陳未如，王翠青.通用職能題庫管理系統的研究與實現［J］.沈陽化學學院學報，2005，19（3）：236－240.LI Li，CHEN Weiru，WANG Cuiqing.Study and realization of general intelligentItem bank system［J］.Journal of Shenyang Institute of Chemical Technology，2005，19（3）：236－240.

［2］ 夏萬東，藏玉紅，齊曉旭，等.通用試庫管理系統的設計與實現［J］.承德石油高等專科學校學報，2014，16（3）：44－47.XIA Wandong，ZANG Yuhong，QI Xiaoxu，et al.Design and implementation of general test questions library managenebt system［J］.Journal of Chengde Petroleum College，2014，16（3）：44－47.

［3］ 龍草芳，肖衡.試題庫建設與組卷算法研究［J］.電腦知識與技術，2013，13（9）：2955－2959.LONG Caofang，XIAO Heng.Research on design of test database and algorithm of examination paper［J］.Journal of Computer Knowledge and Technology，2013，13（9）：2955－2959.

［4］ 楊勛.在線考試系統的組卷算法研究［J］.電腦知識與技術，2014，10（32）：7621－7623.YANG Xun.Research on the test paper composition algorithm of online examination system［J］.Computer Knowledge and Technology，2014，10（32）：：7621－7623.

［5］ 趙靜雅，高斐，高震宇.在線考試系統自動組卷算法研究［J］.電子制作，2014（8）：282－283.ZHAO Jingya，GAO Pei，GAO Zhenyu.Research of auto generating test paper algorithm of online examination system［J］.Electronic Production，2014（8）：282－283.

［6］ 陳曉敏，梁靜，葛宇.基于改進遺傳算法的智能組卷研究［J］.西南師范大學學報：自然科學版［J］.2012，37（5）：98－101.CHEN Xiaomin，LIANG Jing，GE Yu.On intelligent test paper auto－generation based on improved genetic algorithm［J］.Journal of Southwest China Normal University：Natural Science Edition，2012，37（5）：98－101.

［7］ 呂東哲，蘇烈華.基于分類隨機算法的試卷生成算法研究［J］.計算機光盤軟件與應用，2014（8）：190－191.LYU Dongzhe，SU Liehua.Based on the papers random generation algorithm classification algorithm［J］.Computer CD Software and Applications，2014（8）：190－191.

［8］ 白雁.基于線性遞減系數粒子群優化算法的組卷實現［J］.現代電子技術，2014，37（24）：41－44.BAI Yan.Implementation of test paper generation based on particle swarm optimization algorithm with linear decreasing inertia weight［J］.Modern Electronics Technique，2013，37（24）：41－44.

［9］ 劉毅.人工智能在自動組卷建模中應用研究［J］.計算機仿真，2011，28（8）：385－388.LIU Yi.Auto－generating test paper based on artificial intelligence［J］.Computer Simulation，2011，28（8）：385－388.