一種基于策略集的概率縮域算法對多目標(biāo)隨機組卷問題的解決方案

周華君,丁愛芬,呂小俊

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

0 引 言

隨著高校信息化教學(xué)的推進，電子考試系統(tǒng)在高校教考過程的展開，自動組卷是電子考試系統(tǒng)中一個非常重要的組成部分，保證自動組卷的科學(xué)性、隨機性和高效性是自動組卷算法研究的一個難點[1-2]。當(dāng)前自動組卷算法在研究組卷的隨機性上基本采用隨機洗牌算法[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!)，算法難度大，適合小題量的組卷?？梢钥闯鰡我坏慕M卷算法在保證組卷的科學(xué)性、隨機性和高效性上都難以做到均衡。

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

本文提出一種基于策略集的概率縮域算法，實現(xiàn)對多目標(biāo)隨機組卷問題的解決。首先通過對同組試題數(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)成分?jǐn)?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為題型分?jǐn)?shù)txScore。

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

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

7)當(dāng)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)當(dāng)前的剩余試題集不滿足分布需求抽取要求。

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

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

2)當(dāng)前策略集和已經(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)當(dāng)T.tmSize

3)開始合并,當(dāng)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。所以，基于策略集的概率縮域算法在解決多目標(biāo)隨機組卷問題上是可行的，能夠同時滿足時效性、均衡性要求。

4 結(jié)束語

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

實驗結(jié)果表明算法效率與組卷份數(shù)呈現(xiàn)二次函數(shù)的變化趨勢,算法效率隨題庫題目數(shù)量的變化較小。即算法對組卷份數(shù)的時間復(fù)雜程度為O(n2);題庫題目數(shù)量對組卷效率影響較小，算法適合較大題目量的組卷應(yīng)用。由于算法的解決問題情景同樣也可以應(yīng)用于多目標(biāo)的整數(shù)規(guī)劃，研究多目標(biāo)整數(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.