王 棟，邊 超

（1. 甘肅聯(lián)合大學(xué) 電子信息工程學(xué)院，蘭州 730000；2. 中國(guó)礦業(yè)大學(xué) 銀川學(xué)院，銀川 750011）

0 引言

隨著人工智能技術(shù)發(fā)展和教學(xué)改革不斷深入，智能組卷系統(tǒng)越來越受到眾多學(xué)者的關(guān)注。在計(jì)算機(jī)輔助教學(xué)中，計(jì)算機(jī)輔助測(cè)驗(yàn)（CAT）是其中一個(gè)重要組成部分，CAT集組卷、評(píng)卷和題庫管理于一體。而計(jì)算機(jī)自動(dòng)組卷是CAT最為重要的部分，因此設(shè)計(jì)出合理的組卷算法是計(jì)算機(jī)自動(dòng)組卷系統(tǒng)研究的難點(diǎn)和熱點(diǎn)[1]。

計(jì)算機(jī)自動(dòng)組卷是由計(jì)算機(jī)自動(dòng)從試題庫中抽取試題，組成一份符合題型、知識(shí)點(diǎn)、難度和分?jǐn)?shù)分布等要求的試卷。隨機(jī)算法抽取試題常不能滿足試題要求，易產(chǎn)生無效試卷，因此組卷成功率比較低。而回溯試探法組卷算法，該算法當(dāng)試題庫比較大時(shí)，回溯的次數(shù)比較多且組卷時(shí)間較長(zhǎng)[5]。遺傳算法具有全局尋優(yōu)和收斂速度快的特點(diǎn)，但對(duì)不同要求試題要設(shè)置不同的遺傳算法，實(shí)現(xiàn)比較復(fù)雜。因此，開發(fā)出一套通用、高效且生成試卷質(zhì)量高的自動(dòng)組卷算法對(duì)計(jì)算機(jī)輔助測(cè)驗(yàn)具有很大的實(shí)用價(jià)值。

蟻群算法(ant colony optimization，ACO)作為一種新仿生類模擬進(jìn)化算法，其模擬自然界蟻群覓食行為，具有全局搜索和群體智能搜索等優(yōu)點(diǎn)。將蟻群算法引入到計(jì)算機(jī)自動(dòng)組卷中，并通過具體實(shí)例對(duì)該算法有效性進(jìn)行預(yù)測(cè)表明，相對(duì)于其他幾種常用的自卷組卷算法，蟻群算法的自動(dòng)組卷系統(tǒng)提高了組卷成功率，加快了組卷的速度，基本上能夠適應(yīng)自動(dòng)組卷高成功率、實(shí)時(shí)性要求。

1 試卷質(zhì)量評(píng)價(jià)的指標(biāo)體系構(gòu)建

試卷指標(biāo)體系是指試卷一些重要參數(shù)，是對(duì)試卷的特征和功能進(jìn)行定性的或定量的描述，因此試卷的指標(biāo)系統(tǒng)是實(shí)現(xiàn)計(jì)算機(jī)自動(dòng)組卷的關(guān)鍵。

1）試卷的平均難度。試卷難度是指測(cè)試的全體學(xué)生在該試卷上的失分率，用符號(hào)D表示。試卷難度的計(jì)算公式為：

式中，ki表示第i題的分值，Pi表示第i道試題的難題，m表示試卷的總題量。

2）試卷區(qū)分度。試卷分度稱之為試卷鑒別力，用來衡量試卷對(duì)參加測(cè)試的不同能力水平學(xué)生的區(qū)分程度，用符號(hào)P表示，其計(jì)算公式如下：

式中，PH表示考生的高分得分率，PL表示考生低分得分率，P越大表示該試卷區(qū)分能力越強(qiáng)。

3）試卷的信度。試卷信度指測(cè)試結(jié)論與數(shù)據(jù)的可靠性程度，是衡量試卷質(zhì)量穩(wěn)定性和可靠性的重要指標(biāo)，采用如下的估計(jì)方法：

式中，n表示題總數(shù)，S2表示考試總分的方差，pi表示題目i的通過率，r表示信度系統(tǒng)。

2 自動(dòng)組卷系統(tǒng)的數(shù)學(xué)模型

2.1 自動(dòng)組卷系統(tǒng)的數(shù)學(xué)模型描述

自動(dòng)組卷是指計(jì)算機(jī)從題庫中選取一定數(shù)量的試題組成試卷，使試卷既能滿足考查要求又能滿足用戶要求。

設(shè)一份試卷所含的試題數(shù)為m，每一道試題有n個(gè)屬性指標(biāo)，則一份試卷就是一個(gè)m×n矩陣，即：

目標(biāo)矩陣應(yīng)滿足如下的約束條件：

2）試卷題型及分?jǐn)?shù)約束。Q表示第t題型分?jǐn)?shù)，t表示題型號(hào)，C為選擇、判斷、填空、簡(jiǎn)答、計(jì)算題等，具體題目類型和和各題分?jǐn)?shù)比例由用戶給定，則有：

3）總時(shí)間。設(shè)考試的總時(shí)間為T0，完成試卷X估計(jì)需要時(shí)間為T(X)，檢查時(shí)間預(yù)設(shè)為βT(X)，那么實(shí)際完成試卷X花費(fèi)的時(shí)間為：

4）試題難度分布采用PSt表示，則試題難度可以定義為：

如果ai3在第i個(gè)難度等級(jí)范圍內(nèi)，那么C1i就等1，否則等于0。

5）知識(shí)點(diǎn)分?jǐn)?shù)約束。設(shè)重點(diǎn)和次重點(diǎn)知識(shí)點(diǎn)集合分別為I1和I2，其對(duì)應(yīng)分?jǐn)?shù)范圍分別為[L1,U1]和 [L2, U2]，則：

6）知識(shí)點(diǎn)覆蓋面約束。用符號(hào)R表示，其定義如下：

一般情況下，為了保證試卷的知識(shí)點(diǎn)覆蓋面，r大于80%。

2.2 自動(dòng)組卷問題的目標(biāo)函數(shù)

根據(jù)計(jì)算機(jī)組卷的數(shù)學(xué)模型可知，自動(dòng)組卷問題是一個(gè)典型的多目標(biāo)優(yōu)化問題，其通過利用單目標(biāo)函數(shù)的優(yōu)化方法對(duì)其求解。本文采用目標(biāo)加權(quán)法來對(duì)自動(dòng)組卷進(jìn)行建模，其基本思想是給每一個(gè)目標(biāo)一個(gè)權(quán)重，將所有的目標(biāo)分量乘上各自相應(yīng)的權(quán)重系數(shù)，然后再加起來構(gòu)成一個(gè)新的目標(biāo)函數(shù)，具體為：

最后得到組卷問題的具體目標(biāo)函數(shù)為：

其中，wi表示權(quán)重系數(shù)。

這樣通過變換，將計(jì)算機(jī)自組卷這樣一多約束條件的優(yōu)化問題轉(zhuǎn)為一個(gè)典型線性規(guī)劃問題。

3 蟻群算法的自動(dòng)組卷問題求解

3.1 蟻群算法原理

蟻群算法是由意大利人Doringo等人提出的，是一種對(duì)螞蟻的群體覓食行為的模擬而得出的仿生優(yōu)化算法。螞蟻在蟻群覓食過程中，總能找到一條從食物到蟻巢最優(yōu)路徑。主要是因?yàn)槲浵佋谝捠尺^程中，在所經(jīng)過的路徑上釋放出信息素，其它螞蟻根據(jù)路徑上的信息素選擇下一條路徑。若一條路徑上的信息素越高，表明該路徑上爬行的螞蟻數(shù)越多，即該條路徑的性能就更優(yōu)，這樣后續(xù)螞蟻選擇該路徑的概率就越大，由此形成一個(gè)學(xué)習(xí)信息的正反饋機(jī)制，從而找到所求問題的最優(yōu)解。

3.2 自動(dòng)組卷問題的蟻群算法設(shè)計(jì)

3.2.1 試卷編碼方式

試題庫的每一個(gè)試題都有“選中”和“不選中”兩種狀態(tài)，因此蟻群算法可以采用二進(jìn)制編碼表示。本文采用分塊式的二進(jìn)制編碼方式，每一塊表示一種題型。設(shè)試題庫中其有L種題型，每種題型有K個(gè)題數(shù)，那么每一個(gè)螞蟻的編碼長(zhǎng)度為：L×K。因此，試卷的具體編碼形式如圖1所示：

圖1 試卷的編碼方式

其中，

3.2.2 適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù)是用來評(píng)價(jià)個(gè)體優(yōu)劣程度的指標(biāo)，對(duì)于自動(dòng)組卷問題來說，就是對(duì)試卷的質(zhì)量的評(píng)價(jià)，結(jié)合式（11）組卷問題具體目標(biāo)函數(shù)，本文就是要求其的值最小，因此蟻群算法的適應(yīng)度函數(shù)為：

3.2.3 信息素更新規(guī)則

要從試題庫中選取規(guī)定數(shù)量的試題，組成一份符合用戶要求和組卷?xiàng)l件的試卷，首先對(duì)每一個(gè)試題的信息素濃度進(jìn)行初始化，并對(duì)揮發(fā)值進(jìn)行計(jì)算。開始將螞蟻置于試題庫的任一題上，螞蟻在移動(dòng)過程中根據(jù)信息素的濃度和揮發(fā)函數(shù)計(jì)算出其偏好量，然后根據(jù)偏好量選擇下一個(gè)移動(dòng)方向，將螞蟻選過的試題存入一段記憶體的空間中，當(dāng)全部螞蟻都選擇初解后，對(duì)螞蟻所找的解進(jìn)行檢查，看其是否滿足自動(dòng)組卷全部限制條件，若出現(xiàn)不滿足解，那么就對(duì)其進(jìn)行修正，使符合所有限制條件，然后采用區(qū)域搜尋法對(duì)解進(jìn)行進(jìn)一步改善，使其更加接近最優(yōu)解，找出本輪目標(biāo)函數(shù)最好的試卷，稱之為本輪迭代最優(yōu)解，若本輪最優(yōu)解好于全局最優(yōu)解，那么本輪最優(yōu)解替代全局最優(yōu)解，并對(duì)信息素進(jìn)行更新。

3.2.4 狀態(tài)轉(zhuǎn)移概率

初始時(shí)刻，每一個(gè)試題的信息素濃度相等，螞蟻在運(yùn)動(dòng)過程中，根據(jù)信息素濃度和揮發(fā)值來選擇一個(gè)試題，題目被選中的概率從信息素的強(qiáng)度上反應(yīng)出來，如果試題的信息素越高表示該試題會(huì)經(jīng)常被螞蟻選到，這樣螞蟻對(duì)該試題信息素濃度累積就越多。第i題的揮發(fā)值用hi表示，其計(jì)算公式為：

那么，螞蟻在運(yùn)動(dòng)過程中，其轉(zhuǎn)移概率為：

其中，hij表示由試題i轉(zhuǎn)移到試題j的局部揮發(fā)值；allowedk表示下一步允許訪問的試題；α和β分別表示權(quán)重參數(shù)，用來協(xié)調(diào)路徑上的信息素、局部啟發(fā)信息的啟發(fā)信息因子。

通過禁忌表來記錄每一只螞蟻目前已經(jīng)選擇試題，在搜索過程中不斷的更新，表示螞蟻k在t時(shí)刻從試題i轉(zhuǎn)向試題j的狀態(tài)轉(zhuǎn)移概率。

3.3 蟻群算法的自動(dòng)組卷過程

1）設(shè)置試卷的組卷要求。

2）蟻群和路徑的初始化。所有試題路徑上的初始信息素為0；初始時(shí)間t＝0。

3）將所有螞蟻從試題庫隨機(jī)選擇一個(gè)試題編號(hào)放入相對(duì)應(yīng)的禁忌列表中，令螞蟻的禁忌表的索引號(hào)為1。

4）循環(huán)次數(shù)加1。

5）螞蟻個(gè)體根據(jù)狀態(tài)轉(zhuǎn)移概率公式來來選擇下一步應(yīng)該選擇的試題編號(hào)。

6）將選擇好之后的螞蟻移到新試題上，并將該試題編號(hào)插入到禁忌表中，并修改禁忌表的索引號(hào)。

7）將每個(gè)螞蟻所抽出的試題與用戶輸入的要求進(jìn)行對(duì)比，如果滿足要求，得到一套試卷。

8）如果該套試卷比全局最優(yōu)試卷要好，則代替全局最優(yōu)試卷。

9）信息素局部和全部更新。

10）結(jié)束條件判斷，如果滿足結(jié)束條件，則輸入最優(yōu)試卷，否則跳轉(zhuǎn)到步驟3），繼續(xù)組卷。組卷的具體流程如圖2所示。

4 仿真試驗(yàn)

4.1 組卷要求

為了研究算法的有效性，對(duì)辦公自動(dòng)化這門課程進(jìn)行自動(dòng)組卷，該試卷其有選擇題、判斷題、填空題、簡(jiǎn)答題和分析題5種類型。該試卷的各種設(shè)置見表1～表3。

圖2 基于蟻群算法的自動(dòng)組卷過程

表1 題型的設(shè)定

表2 試題難度一分?jǐn)?shù)分布

表3 章節(jié)分?jǐn)?shù)

4.2 蟻群算法參數(shù)設(shè)定

設(shè)蟻群算法的螞蟻數(shù)為10，α＝1，β＝2，最大迭代數(shù)為100；實(shí)驗(yàn)時(shí)硬件環(huán)境：CPU 3.0GHz，內(nèi)存容量2G，軟件環(huán)境為MATLAB2008和VC++ 6.0；對(duì)比模型為隨機(jī)變量算法、回溯試探法和遺傳算法。

4.3 組卷效率比較

幾種算法的組卷率對(duì)比結(jié)果如圖3所示。從圖3可知，本文的蟻群算法的組卷效率是所有算法最高的，是由于蟻群算法是一群體智能搜索算法，全局尋優(yōu)能力強(qiáng)，具有并行性。

圖3 幾種組卷算法的組卷效率對(duì)比

4.4 組卷成功率比較

圖4表示幾種算法組卷成功率的對(duì)比結(jié)果。從圖4可知，在所有的組卷算法中，本文的蟻群算法組卷成功率最高，達(dá)到100%，全部組卷成功，且速度快，能夠滿足了組卷的實(shí)用性要求，為計(jì)算機(jī)自動(dòng)組提供了一種新的工具。

圖4 幾種組卷算法的組卷成功率對(duì)比

5 結(jié)束語

目前，雖然有各種各樣的自動(dòng)組卷系統(tǒng)，但這些系統(tǒng)都存在一定缺陷。本文在對(duì)國(guó)內(nèi)外相關(guān)研究進(jìn)行分析的基礎(chǔ)上，針對(duì)組卷實(shí)際特點(diǎn)，提出了基于蟻群算法的自動(dòng)組卷算法。通過對(duì)比實(shí)驗(yàn)表明，基于蟻群算法的自動(dòng)組卷系統(tǒng)提高了組卷的效率和成功率，具有很強(qiáng)的實(shí)用性，在計(jì)算機(jī)計(jì)算機(jī)輔助考試中有著廣泛的應(yīng)用前景。

[1] 陳華光, 周鐵山, 張曉清. 通用試題庫系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 湖南工程學(xué)院學(xué)報(bào)(自然科學(xué)版), 2002, 12(3): 32-34.

[2] 池?fù)嵝? 沈麗, 孫桂蘭. 計(jì)算機(jī)隨機(jī)抽題組卷算法與應(yīng)用[J]. 撫順石油學(xué)院學(xué)報(bào), 1999, 19(2): 45-47.

[3] 麗雯, 陳渝光, 劉巍. 一種有效的試題庫框架設(shè)計(jì)算法[J]. 計(jì)算機(jī)應(yīng)用, 2000, (1): 60-61.

[4] 華如海, 王俊普, 鄭全, 等. 基于約束滿足的智能組卷方法的研究與實(shí)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用研究.