周華君,丁愛芬,呂小俊

(云南大學(xué)旅游文化學(xué)院,云南 麗江 674100)

0 引 言

隨著高校信息化教學(xué)的推進，電子考試系統(tǒng)在高校教考過程的展開，自動組卷是電子考試系統(tǒng)中一個非常重要的組成部分，保證自動組卷的科學(xué)性、隨機性和高效性是自動組卷算法研究的一個難點[1-2]。當前自動組卷算法在研究組卷的隨機性上基本采用隨機洗牌算法[3-5]和模擬退火算法[6-8]，隨機洗牌算法在選題過程中較快，但是選擇方法較單一，錯誤率較高；模擬退火算法本質(zhì)上也是一種隨機算法，其在局部上作出了優(yōu)化改進，但仍然無法滿足組卷整體上的科學(xué)性。在研究組卷的科學(xué)性方面(如滿足試題的區(qū)分度、重復(fù)率、難易度比例、知識點分布)主要采用遺傳算法[7,9-13]、回溯算法[2]。遺傳算法在自動組卷的科學(xué)性主要體現(xiàn)為優(yōu)秀遺傳因子可以得到重用，即優(yōu)秀試題組合可以得到重用，但無法滿足題庫抽取的隨機性,且遺傳算法的時間復(fù)雜性為O(2n);回溯算法遍歷空間解的時間復(fù)雜度為O(n!)，算法難度大，適合小題量的組卷。可以看出單一的組卷算法在保證組卷的科學(xué)性、隨機性和高效性上都難以做到均衡。

自動組卷算法的隨機性和高效性是基本要求。組卷算法的科學(xué)性是最終目標，組卷算法的科學(xué)性和高效性兼顧是難點。然而由于科學(xué)性的評定標準多樣，通過制定構(gòu)成組卷題目的知識點分布函數(shù)，對目標集重復(fù)使用隨機算法和輪轉(zhuǎn)均衡策略，可以有效保證組卷質(zhì)量達到目標要求，滿足了組卷的科學(xué)性；在組卷的隨機抽取和輪轉(zhuǎn)均衡過程中及時運用剪枝策略，縮小題庫范圍，提高組卷效率，二者結(jié)合能夠有效滿足組卷算法的科學(xué)性和高效性。

本文提出一種基于策略集的概率縮域算法，實現(xiàn)對多目標隨機組卷問題的解決。首先通過對同組試題數(shù)據(jù)運用洗牌算法進行隨機化，構(gòu)成試題結(jié)果取值域，滿足試卷抽取的隨機性要求；其次通過構(gòu)造滿足用戶需求的試題數(shù)據(jù)分布函數(shù)，實現(xiàn)對試題數(shù)據(jù)的均衡性選??；再次在選取過程中通過策略集對取值域進行提前剪枝，通過一定的概率密度，不斷縮小取值域，直到結(jié)果集返回，滿足組卷的高效率要求；最后對結(jié)果集進行均衡性量化，以一定的深度權(quán)重進行結(jié)果集的均衡化輪轉(zhuǎn)處理[5]，使抽取試卷的質(zhì)量滿足用戶自定義策略要求，該算法的時間復(fù)雜性對試題數(shù)量的變化增量較小，適用于大規(guī)模題目的組卷工作。該算法與組卷份數(shù)存在著顯著相關(guān)性，實驗擬合結(jié)果符合二次曲線，即算法復(fù)雜度為O(n2)，在試題數(shù)量為100000個、組卷份數(shù)為1000份的條件下，耗時僅為127 s，符合現(xiàn)代較大規(guī)模(題庫量單位以萬計)題庫的自動組卷時效性要求。

1 組卷工作的基本模型

1.1 數(shù)據(jù)結(jié)構(gòu)的基本定義

定義1試題題目結(jié)構(gòu)定義為:

Q=

其中qid代表題目編號，qscore代表題目分值，qzid代表題目章節(jié)，qfacility代表題目難度，qfrequency代表題目抽取頻度，dkeyword代表題目關(guān)鍵字。

定義2題型結(jié)構(gòu)定義為:

T={txId,txScore,tmSize,tmList}

其中txId代表題型編號，txScore代表本題型構(gòu)成分數(shù)，tmSize代表本題型所需題目數(shù)量，tmList代表本題型已選擇題目隊列。題目隊列tmList={Qi},其中i屬于N。

定義3試卷結(jié)構(gòu)定義為:

E={eid,escore,Tlist}

其中Tlist={Ti}。

定義4題目庫定義為:

tk={Qi},其中i屬于N。將題目庫劃分為選中集TKchoose，待選集TKrest，剪枝集TKleft。

定義5策略結(jié)構(gòu)定義為:

S={W,F1(TKchoose,TKrest,TkDelete,depth),F2(TKchoose,TKrest,TkDelete,depth),F3(TKchoose,TKrest,TkDelete,depth)}

其中W為策略權(quán)重，TKchoose為選中集和，TKrest為剩余集和，TKDelete為被剪枝集和，depth為回溯深度。F1，F(xiàn)2，F(xiàn)3為以depth深度對TKchoose,TKrest,TkDelete采用一定的策略進行選取、剪枝和調(diào)整操作。

定義6策略結(jié)合定義為：

Seqs={Si}

其中i屬于N，Si代表單個策略。

1.2 概率分布密度函數(shù)的離散化

對任意概率密度函數(shù)Y=F(x)在x(a b)之內(nèi)進行均勻取值，其中a，b分別對應(yīng)試題某一屬性的最小值和最大值，根據(jù)試題屬性區(qū)間逐個取x得出Y對應(yīng)的分布權(quán)重，通過權(quán)重需求構(gòu)造分布區(qū)間，使抽取時按照該分布進行試題的抽取，滿足試題抽取的策略性，具體構(gòu)造算法過程如下：

1)通過SQL的Select distinct命令獲取屬性區(qū)間list，將list中最小值和最大值分別復(fù)制給min，max。

2)計算list各元素的最小間距l(xiāng)。

3)以l為距離單位，構(gòu)造min，max間序列x1…xi…xn。

4)序列x1…xi…xn映射到a，b密度范圍，分別求解對應(yīng)密度序列y1…yi…yn。

5)yi即為任意分布函數(shù)對應(yīng)的離散化密度序列。

2 組卷過程

2.1 試題自定義分布處理方法

1)如果是連續(xù)性分布，執(zhí)行連續(xù)概率分布的離散化處理。

3)分布同樣大小的數(shù)組Array。

4)填寫yi個xi到數(shù)組Array。

5)對Array運用隨機洗牌算法。

6)將洗牌后的Array加入指定策略集，等待策略集進行數(shù)據(jù)選取。

2.2 基本縮域算法

1)查詢數(shù)據(jù)庫獲取組卷題目庫，將試題取值域加入列表LinkedListmTiKuList。

2)對mTiKuList進行快速排序，運用二叉排序樹按分值大小進行降序排列，定義回溯深度depth。

3)初始化TKchoose為空，TKrest為全集，TkDelete為空。

4)定義組卷剩余分值restScore為題型分數(shù)txScore。

5)當restScore>0且TKrest.size()>0，則執(zhí)行6)否則執(zhí)行10)，表明本試題分值不夠且還有待選集。

6)應(yīng)用策略函數(shù)在剩余集里隨機取一個題目項tmp。

7)當tmp.getTimuscore()≤restScore，表明選中題目項的分值小于或等于剩余分值。

8)執(zhí)行剩余分值調(diào)整，剩余分值=剩余分值-選擇題目項分值。將題目項加入TKchoose,并從TKrest刪除題目項。執(zhí)行5)。

9)應(yīng)用策略函數(shù)對TKrest執(zhí)行一次剪枝，縮小選擇域，將剪枝題目項放入TkDelete，執(zhí)行5)。

10)判定題目數(shù)量TKrest.size()是否為0，如果是則執(zhí)行11)，否則，depth=depth-1。

11)判定回溯深度是否為0，如果是則返回false,否則執(zhí)行3)。表明進行下一次的試探抽取，否則應(yīng)用策略函數(shù)進行試題平衡化處理。平衡成功返回true,否則返回false。

2.3 基本剪枝策略

基本剪枝策略分為2種，一種是對試題抽取過程的盡快返回，一種是對選擇區(qū)域的盡快縮小。

對試題抽取過程的盡快返回條件包括但不限于以下條件：

1)已抽取分值+剩余分值<題型需求分值；

2)已抽取試題個數(shù)+剩余試題個數(shù)<題型需求個數(shù)；

3)剩余題目不滿足策略函數(shù)需求；

4)當前的剩余試題集不滿足分布需求抽取要求。

對試題抽取域的縮小包括但不限于以下條件：

1)當前題目分值大于restScore，可以剔除待選序列；

2)當前策略集和已經(jīng)滿足，剩余滿足的選項可以剔除待選序列。

通過定義策略集列表和策略處理響應(yīng)邏輯，能夠更快地實施對試題組的深度剪枝，加快算法對較大題庫的快速求解，同時能夠?qū)崿F(xiàn)對算法處理過程的擴展。

2.4 自定義深度的均衡化輪轉(zhuǎn)處理

均衡化輪轉(zhuǎn)分為題型的選中題目個數(shù)與題型需求一致和不一致2種情形。一般先將不一致調(diào)整為一致，再進行后續(xù)調(diào)整，試題個數(shù)一致性調(diào)整過程如下：

1)定義測試深度outsizedeep。

2)當T.tmSize

3)開始合并,當TKrest.size≥2且outsizedeep>0則執(zhí)行4)，否則返回false。false代表本次調(diào)整失敗。

4)在TKchoose集和的前1/2片段隨機抽取題目A，B。

5)在TkDelete應(yīng)用策略集抽取題目C，滿足C.qscore=A.qscore+B.qscore;抽取到則執(zhí)行6),否則outsizedeep=outsizedeep-1，執(zhí)行3)。

6)在TKchoose集和中刪除A,B，添加C。

7)開始分解,從TKchoose中隨機選擇A。

8)應(yīng)用策略集在TkDelete和TKrest中找到題目B，C，滿足A.qscore=B.qscore+C.qscore;否則outsizedeep=outsizedeep-1，執(zhí)行3)。

9)從TKChoose中刪除A,添加B,C；并從TkDelete和TKrest中刪除B，C，執(zhí)行3)。

3 實 驗

3.1 實驗條件

在處理器為Intel(R) Core(TM) i7-4770CPU@3.40 GHz，內(nèi)存為8 GB的Windows7 64位系統(tǒng)下，試題項的組成為每個試題的分值不超過20分，試卷分值為100分，每份試卷題目組題數(shù)為20個。使用Eclipse開發(fā)環(huán)境和Java語言，內(nèi)存限制為500 MB，組卷份數(shù)以10為間距，題庫題目數(shù)量以100為間距運行算法。實現(xiàn)結(jié)果如表1所示。

表1 不同題量與組卷份數(shù)耗時對比(ms)

抽取題目數(shù)量/道生成試卷份數(shù)/份14015016017018019020010057596472838383200313843465054593006470796274788540069769010110912313250070829410011312613560073809210611312413570072819310311112514180076849510411812914090079891011131191381451000829010211512413014711008997107117130138157120094104113125140161159130097106120131142154162140098109123131141157171150011611513614014816517416001081181281401551661821700113126137149163178190180011913113915416818419119001261361521651731912172000146161169181198208232

3.2 實驗結(jié)果分析

在題庫題目數(shù)2000，抽取200份試卷的計算機耗時僅有230 ms左右,在本算法下，題庫題目數(shù)量對組卷耗時的影響因子較小，相關(guān)因子為0.407，組卷份數(shù)對算法耗時影響較大，相關(guān)因子為0.861。

對組卷時間與組卷份數(shù)作回歸分析，其二次、三次、復(fù)合函數(shù)描述散點圖如圖1所示。

圖1 回歸分析描述散點圖

注：在題目量相同的情況下，v2代表組卷份數(shù)(份)，v3代表消耗時間(ms)，實線代表二次和三次曲線(兩類曲線重合，根據(jù)調(diào)整后的R方的值，這里選擇二次曲線)，虛線代表復(fù)合曲線。

如圖1所示，算法的組卷時間與組卷份數(shù)的變化趨勢符合二次、三次曲線。結(jié)合調(diào)整后的R和方差檢驗，二次曲線更符合數(shù)據(jù)擬合要求。即算法效率與組卷份數(shù)呈現(xiàn)二次函數(shù)的變化趨勢。算法效率與題庫題目數(shù)量的變化較小，表明算法在題庫題目數(shù)量增加較多的情況下變化不顯著,算法適合較大題庫的組卷要求。在增加內(nèi)存為1 GB,題庫量為100000個，組卷份數(shù)為1000份情況下，算法耗時為127 s。所以，基于策略集的概率縮域算法在解決多目標隨機組卷問題上是可行的，能夠同時滿足時效性、均衡性要求。

4 結(jié)束語

本文提出了一種基于策略集的概率縮域算法對多目標組卷問題的解決方案。通過應(yīng)用隨機洗牌算法實現(xiàn)對試題數(shù)據(jù)選取的隨機性，保證了試題抽取的隨機性和均衡性；使用策略集實現(xiàn)對隨機抽題的題項限定，達到試題選取符合用戶指定分布的目標；運用策略集對目標待選集進行快速縮域，保證了算法執(zhí)行的效率；運用策略集對結(jié)果進行輪轉(zhuǎn)調(diào)整，既簡化了試題組合效率，又使最終結(jié)果符合用戶目標策略需求。最后以較大的題目量和一定的組卷步長，運用基于策略集的概率縮域算法檢驗抽題效率，實驗結(jié)果符合較大規(guī)模題目的組卷實時性需求。

實驗結(jié)果表明算法效率與組卷份數(shù)呈現(xiàn)二次函數(shù)的變化趨勢,算法效率隨題庫題目數(shù)量的變化較小。即算法對組卷份數(shù)的時間復(fù)雜程度為O(n2);題庫題目數(shù)量對組卷效率影響較小，算法適合較大題目量的組卷應(yīng)用。由于算法的解決問題情景同樣也可以應(yīng)用于多目標的整數(shù)規(guī)劃，研究多目標整數(shù)規(guī)劃的快速解決方案是該算法的一般性應(yīng)用研究方向。

[1] 袁桂霞. 自動組卷的建模和仿真研究[J]. 計算機仿真, 2011,28(11):370-373.

[2] 高興媛,古輝. 在線考試系統(tǒng)自動組卷技術(shù)的研究與實現(xiàn)[J]. 計算機與現(xiàn)代化, 2011(3):156-158.

[3] 曹樹國. 基于洗牌算法的快速個性化組卷方法的研究[J]. 計算機與信息技術(shù), 2007(10):71-72.

[4] 徐波,胡玉濤. 醫(yī)藥考試系統(tǒng)A1及A2題型的隨機組卷算法研究[J]. 計算機與網(wǎng)絡(luò), 2016,42(21):63-65.

[5] 魏波,喻飛,徐星,等. 基于改進輪盤賭策略的交互式演化算法[J]. 計算機與數(shù)字工程, 2014,42(10):1763-1767.

[6] 吳煥,張琪君. 基于遺傳退火算法的智能組卷系統(tǒng)研究[J]. 工業(yè)控制計算機, 2017,30(1):112-113.

[7] 張辰,張艷群. 基于遺傳和模擬退火算法的自動組卷系統(tǒng)設(shè)計與實現(xiàn)[J]. 計算機工程與科學(xué), 2004,26(11):65-68.

[8] 吳煥.張琪君. 基于遺傳退火算法的智能組卷系統(tǒng)研究[J]. 工業(yè)控制計算機, 2017,30(1);112-113.

[9] 張琨,楊會菊,宋繼紅,等. 基于遺傳算法的自動組卷系統(tǒng)的設(shè)計與實現(xiàn)[J]. 計算機工程與科學(xué), 2012,34(5):178-183.

[10] 馮阿芳. 基于遺傳算法的自動組卷策略[J]. 哈爾濱師范大學(xué)自然科學(xué)學(xué)報, 2008,24(4):27-30.

[11] 吳飛. 自適應(yīng)遺傳算法解決組卷問題的探討[J]. 重慶科技學(xué)院學(xué)報(自然科學(xué)版), 2007,9(2):132-135.

[12] 許永達. 基于改進遺傳算法的智能組卷研究[J]. 計算機與數(shù)字工程, 2013,41(2):176-178.

[13] 薛方,蘇虞磊. 基于改進遺傳算法的試卷生成算法研究[J]. 現(xiàn)代電子技術(shù), 2010,33(6):143-144.

[14] 賀榮,陳爽. 在線組卷策略的研究與設(shè)計[J]. 計算機工程與設(shè)計, 2011,32(6):2183-2186.

[15] 周艷聰,劉艷柳. 遺傳模擬退火智能組卷策略研究[J]]. 計算機工程與設(shè)計, 2011,32(3):1066-1069.

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

[17] 王曉東. 算法設(shè)計與分析[M]. 北京:清華大學(xué)出版社， 2010:195-273.

[18] 余穎,李曉昀,左貴啟,等. 基于自適應(yīng)遺傳算法的自動組卷策略研究[J]. 南華大學(xué)學(xué)報(自然科學(xué)版), 2016,30(3):61-65.

[19] 顧瑋. 遺傳算法在試題自動組卷中的應(yīng)用[J]. 辦公自動化, 2016,21(18)：57-58.