智能組卷策略的研究

王 穎，劉志丹

（1.商丘職業(yè)技術(shù)學(xué)院，河南 商丘 476000；2.河南大學(xué) 軟件學(xué)院，河南 鄭州 475001）

在線考試系統(tǒng)研發(fā)過程中［1］39，實(shí)現(xiàn)系統(tǒng)自動(dòng)化的關(guān)鍵問題就是智能組卷.智能組卷是計(jì)算機(jī)自動(dòng)隨機(jī)地從試題庫中抽取出與約束條件相對(duì)應(yīng)數(shù)量和質(zhì)量的試題，從而組成一份滿足組卷要求的試卷，同時(shí)滿足用戶的組卷約束條件.通常為了方便組卷，需要給每道試題設(shè)置一系列參數(shù)，這些參數(shù)要反映試題情況，例如，出題日期、試題題型、所屬章節(jié)、知識(shí)點(diǎn)、分值、題目?jī)?nèi)容、使用次數(shù)等等.智能組卷就是依據(jù)上述試題的屬性去匹配相關(guān)的用戶要求，通過組卷算法抽題并組卷的.

1 組卷的約束條件

計(jì)算機(jī)組卷的約束條件是由用戶對(duì)試卷的細(xì)節(jié)要求所構(gòu)成的.計(jì)算機(jī)根據(jù)這些用戶需求循環(huán)抽取每一道試題，最終生成整張?jiān)嚲?因此，組卷問題的求解過程可以看成是尋找滿足條件的最優(yōu)組合，而這些約束條件則影響著試卷的質(zhì)量.

一般來說，這些條件可以包括對(duì)試題題型、所屬章節(jié)、知識(shí)點(diǎn)、難度、分值、估時(shí)、抽取次數(shù)等試題的屬性.如果把對(duì)所有題目的每一項(xiàng)條件都看成是局部的約束，那么所有條件就組成了整個(gè)試卷的全局性的約束條件.為了讓整個(gè)試卷滿足各項(xiàng)指標(biāo)之間的平衡，就需要協(xié)調(diào)局部與全局約束，從而，判斷哪些試題可以被選用.這就是智能組卷.

而根據(jù)考試學(xué)理論［2］131，通常評(píng)價(jià)試卷的質(zhì)量要遵循以下規(guī)律：1）試卷中設(shè)計(jì)的考點(diǎn)內(nèi)容是否合理、科學(xué)；2）試卷中設(shè)計(jì)的考點(diǎn)廣度是否符合大綱要求；3）整個(gè)試卷的難度分配、考查的深度是否合理；4）試卷中的試題類型是否豐富，各類題型所占試卷比例是否合適；5）試卷是否具備良好的優(yōu)劣區(qū)分度.

依據(jù)以上目標(biāo)，在線考試系統(tǒng)采取下列步驟進(jìn)行組卷.首先，在建設(shè)試題庫系統(tǒng)時(shí)，細(xì)化試題的屬性包括難度、區(qū)分度、效率度、信用度，對(duì)組卷的約束條件進(jìn)行預(yù)先設(shè)計(jì)，一般先確定章節(jié)和考點(diǎn)的覆蓋面、試題的類型、用時(shí)、試卷難度；然后，采用合理的組卷算法［3］214自動(dòng)也更高效地從試題庫中抽取一定的試題，確定并合理調(diào)整各試題所占分值，最后合理完成排版.

2 組卷算法

在線考試系統(tǒng)所采用的組卷算法一直是近年來研究的熱點(diǎn)，國(guó)內(nèi)外有很多學(xué)術(shù)機(jī)構(gòu)都在研究.相對(duì)成熟的算法有隨機(jī)法、回溯法、粒子群算法和遺傳算法，筆者在此介紹一下上述4種組卷算法，并簡(jiǎn)單分析它們各自的優(yōu)缺點(diǎn)以及適用性.

2.1 隨機(jī)法

隨機(jī)法在組卷中很常見，即根據(jù)試題庫中的試題屬性和數(shù)量，計(jì)算機(jī)調(diào)用隨機(jī)函數(shù)從試題庫中抽取每一道符合要求的試題，然后加入試卷，循環(huán)進(jìn)行直到組卷完成作為結(jié)束.這是最常用的一種組卷算法.由于要考慮的組卷約束條件較多，算法還需要使用到大量的附加函數(shù)，用來區(qū)分試題的難度、知識(shí)點(diǎn)等屬性.

顯然，該算法結(jié)構(gòu)簡(jiǎn)單易行，對(duì)于單次試題的抽取，算法運(yùn)行速度較快.這正是隨機(jī)抽題法的優(yōu)點(diǎn).但是，基于隨機(jī)函數(shù)的算法抽題的特點(diǎn)是隨意和不確定，試卷的質(zhì)量把握不具有整體性.隨著題庫規(guī)模變大，隨機(jī)法的效率就會(huì)降低，組卷過程就會(huì)變長(zhǎng).隨機(jī)抽題法還需要協(xié)調(diào)局部和全局的約束條件，但這些相互制約的約束條件有時(shí)會(huì)造成組卷失敗.

2.2 回溯法

回溯法（探索與回溯法）是對(duì)隨機(jī)法的改進(jìn)，屬于深度優(yōu)先算法，也是一種選優(yōu)搜索法.按選優(yōu)條件向前搜索以達(dá)到目標(biāo).回溯法的算法原理為：先使用隨機(jī)法進(jìn)行深度優(yōu)先搜索，記錄下沿路產(chǎn)生的狀態(tài)，一旦某次搜索失敗，就出棧返回到上次記錄的狀態(tài)，以此為起點(diǎn)重新探索試探.通過這樣循環(huán)反復(fù)的回溯以及試探，直到成功組成一份完整的試卷.

2.3 粒子群算法（PSO）

粒子群優(yōu)化算法［4］86（Particle Swarm optimization，PSO）又稱為微粒群優(yōu)化算法、微粒群算法或粒子群算法，是由Kennedy博士和Eberhart博士發(fā)明.該算法的應(yīng)用領(lǐng)域很廣，通常用于組合優(yōu)化問題的解決，也可以解決連續(xù)優(yōu)化的問題.該算法模擬鳥群的捕食行為.

一群鳥在某個(gè)區(qū)域隨機(jī)搜尋一塊食物，而食物在哪里對(duì)于所有的鳥都是未知的.已知的是每只鳥的位置和食物之間的距離.那么怎么樣更快地通過鳥兒們尋找到食物呢？最快的辦法就是先找到所有鳥中誰距離食物是最近的，然后搜尋這只鳥的周圍即可.粒子群算法先抽象每個(gè)優(yōu)化問題的解，即粒子.每個(gè)粒子都有決定其運(yùn)動(dòng)方向和距離的速度值，以及由優(yōu)化函數(shù)決定的適應(yīng)值，最優(yōu)粒子將成為粒子們所追隨搜索的目標(biāo).

該算法簡(jiǎn)潔易實(shí)現(xiàn)，它的優(yōu)點(diǎn)是參數(shù)少，收斂速度特別快，特別是在運(yùn)行的初期.而粒子群算法的缺點(diǎn)是容易發(fā)散且精度低，在某些條件下造成算法不收斂，使得算法結(jié)果無法獲取最優(yōu)解；而在某些條件下，粒子趨向同一化，精度較低.

2.4 遺傳算法（GA）

遺傳算法［5］61于1975年由美國(guó)密西根大學(xué)JoHolland教授首先提出，通過對(duì)生物進(jìn)化論中的自然選擇和遺傳學(xué)機(jī)理的模擬，建立計(jì)算模型，搜索最優(yōu)解的方法.遺傳算法利用"優(yōu)勝劣汰"的原理，從群體中選擇出更優(yōu)的個(gè)體為主要目標(biāo)，借助選擇、交叉以及變異操作將個(gè)體靠近最優(yōu)解，最終逐步搜索到問題的最優(yōu)解.遺傳算法廣泛應(yīng)用于很多學(xué)科，為了反映各種復(fù)雜的結(jié)構(gòu)，算法采用簡(jiǎn)單編碼的技術(shù).當(dāng)遺傳算法應(yīng)用于智能化組卷時(shí)，算法中的基因問題由每一題試題代入并進(jìn)行編碼.為了簡(jiǎn)化基因編碼的復(fù)雜度，遺傳算法常用的簡(jiǎn)單的編碼方式比如二進(jìn)制編碼、實(shí)數(shù)編碼和自然數(shù)編碼.例如二進(jìn)制編碼，依據(jù)算法產(chǎn)生初始種群之后，按照"優(yōu)勝劣汰"的原理，將初始種群逐代演化，得到越來越好的近似解，然后從每一代選擇適應(yīng)度大小合適的個(gè)體，再采用遺傳算子進(jìn)行交叉、變異，得出的種群代表了新的解集，這個(gè)結(jié)果作為問題近似最優(yōu)解.

3 結(jié)論

通過討論組卷約束條件和常見的組卷策略，綜合比較各種算法的優(yōu)缺點(diǎn)，根據(jù)不同用戶的需求合理地選取組卷算法.可以看出，隨機(jī)搜索法和回溯法都簡(jiǎn)單易于實(shí)現(xiàn)，但不太適合計(jì)算量較大的情況.粒子群算法和遺傳算法兩者都是對(duì)初始化的種群隨機(jī)化，都通過使用適應(yīng)值來對(duì)系統(tǒng)進(jìn)行評(píng)價(jià)，并依據(jù)適應(yīng)值進(jìn)行隨機(jī)的搜索.在求解方面，兩個(gè)系統(tǒng)都不保證一定能找到最優(yōu)化的解.可以說，粒子群算法和遺傳算法其實(shí)有很多共同之處.

［1］劉志丹，王 穎.基于ASP的網(wǎng)絡(luò)試題庫系統(tǒng)的研究［J］.商丘職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2013（2）.

［2］劉新平，劉存?zhèn)b.教育統(tǒng)計(jì)與測(cè)評(píng)導(dǎo)論［M］.北京：科學(xué)出版社，2003.

［3］雷英杰.MATLAB遺傳算法工具箱及應(yīng)用［M］.西安：西安電子科技大學(xué)出版社，2005.

［4］馮 雪，裴志松.粒子群優(yōu)化算法的研究與應(yīng)用［J］.吉林建筑工程學(xué)院學(xué)報(bào)，2011（03）.

［5］關(guān)凇元，劉大有，金 弟，王新華，蘇 奎.基于局部搜索的遺傳算法求解自動(dòng)組卷問題［J］.吉林大學(xué)學(xué)報(bào)（理學(xué)版），2009（05）.