基于蟻群算法在建模中的應用與發(fā)展

王 棟，邊 超

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

0 引言

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

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

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

1 試卷質量評價的指標體系構建

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

1）試卷的平均難度。試卷難度是指測試的全體學生在該試卷上的失分率，用符號D表示。試卷難度的計算公式為：

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

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

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

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

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

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

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

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

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

目標矩陣應滿足如下的約束條件：

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

3）總時間。設考試的總時間為T0，完成試卷X估計需要時間為T(X)，檢查時間預設為βT(X)，那么實際完成試卷X花費的時間為：

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

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

5）知識點分數(shù)約束。設重點和次重點知識點集合分別為I1和I2，其對應分數(shù)范圍分別為[L1,U1]和 [L2, U2]，則：

6）知識點覆蓋面約束。用符號R表示，其定義如下：

一般情況下，為了保證試卷的知識點覆蓋面，r大于80%。

2.2 自動組卷問題的目標函數(shù)

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

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

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

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

3 蟻群算法的自動組卷問題求解

3.1 蟻群算法原理

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

3.2 自動組卷問題的蟻群算法設計

3.2.1 試卷編碼方式

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

圖1 試卷的編碼方式

其中，

3.2.2 適應度函數(shù)設計

適應度函數(shù)是用來評價個體優(yōu)劣程度的指標，對于自動組卷問題來說，就是對試卷的質量的評價，結合式（11）組卷問題具體目標函數(shù)，本文就是要求其的值最小，因此蟻群算法的適應度函數(shù)為：

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

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

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

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

那么，螞蟻在運動過程中，其轉移概率為：

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

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

3.3 蟻群算法的自動組卷過程

1）設置試卷的組卷要求。

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

3）將所有螞蟻從試題庫隨機選擇一個試題編號放入相對應的禁忌列表中，令螞蟻的禁忌表的索引號為1。

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

5）螞蟻個體根據(jù)狀態(tài)轉移概率公式來來選擇下一步應該選擇的試題編號。

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

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

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

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

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

4 仿真試驗

4.1 組卷要求

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

圖2 基于蟻群算法的自動組卷過程

表1 題型的設定

表2 試題難度一分數(shù)分布

表3 章節(jié)分數(shù)

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

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

4.3 組卷效率比較

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

圖3 幾種組卷算法的組卷效率對比

4.4 組卷成功率比較

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

圖4 幾種組卷算法的組卷成功率對比

5 結束語

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

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

[2] 池撫新, 沈麗, 孫桂蘭. 計算機隨機抽題組卷算法與應用[J]. 撫順石油學院學報, 1999, 19(2): 45-47.

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

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