基于二元蟻群算法求解組卷問題

摘 要：通過分析組卷的數(shù)學(xué)模型及目標(biāo)函數(shù)，抽象出組卷模型實質(zhì)是一個多目標(biāo)線性規(guī)劃模型，并將二元蟻群算法用于求解組卷問題。由于采用二進(jìn)制編碼，任意時刻每只螞蟻只需根據(jù)其面前兩條路徑上的信息素強(qiáng)度決定該題選或不選，這對單個螞蟻的智能行為要求非常低，而且存儲空間也相對減少。實驗結(jié)果表明，該算法能快速有效地完成組卷過程，具有較強(qiáng)的實用性。

關(guān)鍵詞：二元蟻群算法；多目標(biāo)線性規(guī)劃模型；試題組卷；進(jìn)化計算

中圖分類號：TP301.6 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)09-2637-03

Composing test paper based on binary ant colony algorithm

CHENG Meiying，XIONG Weiqing，WEI Ping

 (Institute of Computer Science Technology， Ningbo University， NingboZhejiang 315211， China)

Abstract:Through analyzing the mathematical model and objective function of the composing test paper， this article abstracted that the composing test paper model was really a multiobjective linear programming model， and introduced the binary ant colony algorithm to solve the problem. Owning to the adoption of the binary coding， each ant chose the subject or not only need to according to the strength of the pheromone on every edge， and the requirement for the behavior of every single ant was lower， so the corresponding memory was relatively less. Experiment results show that the algorithm can solve the test paper composition problem quickly and effectively， and also has more capability and utility.

Key words:binary ant colony algorithm; multiobjective linear programming model; test paper; evolutionary computation

0 引言

目前網(wǎng)絡(luò)上的智能組卷系統(tǒng)為數(shù)不少，但用戶真正青睞的卻不多。其原因是多方面的，如組建題庫的困難太大、題型比較單一、生成試卷時間過長、誤差太大等，但最主要的是組卷策略問題。智能組卷系統(tǒng)是一種設(shè)計型的專家系統(tǒng)，它是指計算機(jī)根據(jù)出卷人指定的組卷參數(shù)，如題目類型數(shù)、難度系數(shù)、區(qū)分度、知識點范圍、完成試題時間等，從題庫中抽取滿足以上組卷約束條件的試題組成試卷。如何保證生成的試卷能最大限度地滿足用戶的不同需要，并具有隨機(jī)性、科學(xué)性、合理性，一直是眾人思考和追求的目標(biāo)，而這又完全取決于抽題算法的設(shè)計。如何設(shè)計一個算法從題庫中既快又好地抽出一組最優(yōu)解或抽出一組非常接近最優(yōu)解的實體，涉及到一個全局最優(yōu)解和收斂速度快慢的問題。以往的組卷算法大多采用隨機(jī)抽題法、回溯試探法以及各種改進(jìn)的遺傳算法。本文將根據(jù)實踐提出一種全新的快速而有效的智能組卷算法——基于二元蟻群算法的試題組卷算法。

近年來，集群智能一直是眾多學(xué)者研究的熱點之一，如飛鳥如何聚集成群、昆蟲如何集體飛行，螞蟻如何聰明地找到把食物搬運回家的最短路程，并還能形成等級森嚴(yán)的社會體系……人類通常的思維習(xí)慣是把自然界的某種智慧行為歸功于比這種行為更聰明的造物者的設(shè)計。實際上，近年來的人工生命科學(xué)研究的結(jié)果是，復(fù)雜的智能是可以通過簡單的交互作用涌現(xiàn)的。蟻群算法(ant colony optimization， ACO)作為一種新型的模擬進(jìn)化算法，是由意大利學(xué)者M(jìn)arco Dorigo等人根據(jù)螞蟻尋找食物的群體行為提出的^[1，2]。其先后在TSP、二次分配、車間調(diào)度、圖著色等經(jīng)典的組合優(yōu)化問題中得到廣泛的應(yīng)用。受DNA雙螺旋結(jié)構(gòu)^[3]以及遺傳算法的啟發(fā)，文獻(xiàn)[4]將其與蟻群算法結(jié)合，提出了一種有別于傳統(tǒng)蟻群算法的二元蟻群算法。由于其特殊的隨機(jī)二進(jìn)制鏈?zhǔn)浇Y(jié)構(gòu)，使得該算法在求解連續(xù)函數(shù)優(yōu)化以及離散的組合優(yōu)化（如NP難的整數(shù)規(guī)劃問題、0/1背包問題）問題^[4]時，都取得了非常好的效果。本文將從求解組卷問題的目標(biāo)函數(shù)出發(fā)，抽象出了組卷的多目標(biāo)線性規(guī)劃模型，并將該算法應(yīng)用于求解組卷問題，取得了滿意的效果。

1 組卷問題的數(shù)學(xué)模型^[5]描述

計算機(jī)自動組卷過程是在一定題量的試題庫中搜索滿足組卷目標(biāo)要求的一組試題。組卷中決定一道試題，就要決定n項指標(biāo)，這里考慮n維向量（題型a1，題分a2，

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

K為教學(xué)要求，即教學(xué)約束。教學(xué)要求k取值為識記、理解、綜合、應(yīng)用等具體種類，所占分?jǐn)?shù)由用戶給定。

同理，知識單元、全卷估時、題型、區(qū)分度、期望值等約束條件與上面類似，可以由用戶在組卷時給出。

根據(jù)組卷的數(shù)學(xué)模型知道，組卷問題作為典型的多目標(biāo)優(yōu)化問題，往往需要同時考慮k個目標(biāo)，且要求所有目標(biāo)函數(shù)在滿足約束的條件下越小越好。但問題所包含的不同目標(biāo)往往又存在著一定的沖突，也就是說，多目標(biāo)優(yōu)化中多個目標(biāo)幾乎不可能在同一解上達(dá)到最優(yōu)。在所有的優(yōu)化問題求解中，必須對解的質(zhì)量進(jìn)行評價。最常用的方法是將多個目標(biāo)根據(jù)某種效用函數(shù)合成單一的目標(biāo)，利用單目標(biāo)函數(shù)的優(yōu)化方法去求解，如目標(biāo)加權(quán)法。其基本思想是賦予問題中的每一個目標(biāo)一個權(quán)重，將所有的目標(biāo)分量乘上各自相應(yīng)的權(quán)重系數(shù)后加起來構(gòu)成一個新的目標(biāo)函數(shù)。

針對本組卷問題，設(shè)計其目標(biāo)函數(shù)為

為第i組卷因素對組卷目標(biāo)的誤差；f越小，選出的試卷就越滿足用戶的要求。根據(jù)用戶輸入具體的組卷要求，可以得出目標(biāo)函數(shù)中變量的約束集。這樣就把組卷問題——一個典型的多目標(biāo)優(yōu)化問題抽象成為典型的線性規(guī)劃問題。2 二元蟻群算法基本模型描述點狀態(tài)之間連接的網(wǎng)絡(luò)如圖1所示。其中：n表示二進(jìn)制編碼的長度。

擇1的能見度。由于是二進(jìn)制編碼，螞蟻無須像傳統(tǒng)蟻群算法那樣采用禁忌表來記錄已經(jīng)遍歷過的節(jié)點，只需根據(jù)面前兩條路徑上信息素的大小來進(jìn)行選擇。此外，隨著時間的推移，信息素會逐漸揮發(fā)，ρ是信息素的殘留因子，1-ρ是信息素的揮發(fā)因子。經(jīng)過m時刻，即螞蟻完成一次遍歷后，路徑上的信息素按式（4）（5）進(jìn)行更新調(diào)整。同時為了提高算法的效率，在信息素更新過程中引入maxmin原則，即每一次迭代之后，只有在本次迭代中取得最優(yōu)的那條路徑上的信息素進(jìn)行更新。

其蟻群算法以概率1收斂。

3 組卷的二元蟻群算法設(shè)計

二元蟻群算法因其特殊的隨機(jī)二進(jìn)制鏈?zhǔn)浇Y(jié)構(gòu)，使得螞蟻每一時刻只需從0和1中進(jìn)行選擇，而1和0恰好對應(yīng)著題庫中該題“出”與“不出”，這就使得該算法特別適合于求解組卷問題。算法設(shè)計如下：

a）編碼方式。通常情況下，二進(jìn)制表示法是最有效和最經(jīng)濟(jì)的數(shù)據(jù)表示法，是自然界中最容易模擬和實現(xiàn)的二值邏輯，這也是二元蟻群算法不同于傳統(tǒng)蟻群算法之處。在實際組卷中每種題型的數(shù)目是固定的，且相同題型的分?jǐn)?shù)和答題時間是相同的。這樣就可以將整個二進(jìn)制碼串按照題型劃分為不同的功能塊；每個功能塊對應(yīng)一種特定的題型。在本文中，總的編

b）適應(yīng)度函數(shù)的設(shè)計。適應(yīng)度函數(shù)是用來評價個體優(yōu)劣程度的指標(biāo)，它要求應(yīng)能滿足待求解問題的特征。二元蟻群算法利用適應(yīng)度這一信息來指導(dǎo)搜索方向，而不需要適應(yīng)度函數(shù)連續(xù)或可導(dǎo)。在本算法中，結(jié)合上文所抽象出來的組卷的多目標(biāo)線性規(guī)劃模型，參考式（1）

考慮n個約束條件。其中：wi可以根據(jù)用戶對不同組卷約束條件的重視程度而分為強(qiáng)約束、一般約束或弱約束等，并相應(yīng)取不同的權(quán)值，這里取相同的值，即w1=w難度、時間）；ei對應(yīng)為第i組卷因素對組卷目標(biāo)的誤差。f越小，選出的試卷就越符合用戶的組卷要求。

c）路徑選擇。各個螞蟻根據(jù)圖1進(jìn)行路徑選擇。由于是二進(jìn)制編碼，螞蟻無須具有記憶功能，僅根據(jù)面前兩條邊的信息素大小進(jìn)行選題。信息素濃度越大，該題被選擇的概率就越大。d）信息素更新。為了描述信息素的更新過程，首先引入一個二元組（A，T）。其中：A為頂點集，定義為A={a1，a2，…，aLC×VN}；T為信息素軌跡的集合，定義為T={τ(ai，c)|τ(ai，c)∈R，1≤i≤LC×VN，c∈{0，1}}。那么信息素軌跡集合T即可表示成一個2×L的矩陣且T(i，c)=τ(ai，c)。在本算法中，信息素的更新分為兩個步驟：(a)信息素的揮發(fā)，用公式表示為τ(ai，c)(t+1)=ρ×τ(ai，c)；(b)根據(jù)maxmin規(guī)則，即信息素只釋放在具有最優(yōu)解的螞蟻遍歷過的路徑上，即Δτ×bestij=1/f(sbest)。其中:f(sbest)為每一次迭代的最優(yōu)解或是全局最優(yōu)解。

e）非法個體的修正。在本算法中，因標(biāo)準(zhǔn)化試卷每種題型要求的個數(shù)是固定的，而螞蟻在遍歷的過程中不可避免地會產(chǎn)生一些非法個體，為了保持種群中個體的合法性就必須對非法個體進(jìn)行修正。采用的方法如下：在螞蟻完成一次遍歷后，判斷各題型所在的編碼段中1的個數(shù)是否滿足各題型要求的出題個數(shù)；若不滿足，則在各題型所在的編碼段中隨機(jī)產(chǎn)生t位（其中t為該題型要求的個數(shù)），選取t個1，然后將多余的1全部置0。這樣經(jīng)過螞蟻的多代搜索，必然能得到滿足用戶要求的試卷。

f）迭代終止判據(jù)。當(dāng)出現(xiàn)滿足組卷要求（即適應(yīng)度值達(dá)到預(yù)先的設(shè)定值），或達(dá)到最大的迭代次數(shù)時，算法終止。

下面本文具體給出二元蟻群算法在試題組卷中應(yīng)用的偽代碼描述。

input:An objective function f(x)= ni=1wiei

/*f(x)組卷的目標(biāo)函數(shù)*/

initialize pheromone distribution T;

/*初始化路徑上的信息素*/

while (stop condition not met) do

for i=1 to m do/*m為種群中螞蟻的個數(shù)*/

vi←empty binary string 

/*vi用來存放螞蟻遍歷的二進(jìn)制碼串*/

for j=1 to LC*VN do 

/*螞蟻遍歷二進(jìn)制鏈的過程，LC*VN 為題庫中總的試題個數(shù)*/

choose a value c∈{0，1} for aj

/*螞蟻根據(jù)路徑上的信息素大小在{0，1}進(jìn)行選擇，aj為二進(jìn)制碼串中的第j位*/

append aj=c to vi

end for

end for

encode and evaluate all the colony size solution

vi，i∈{1…m}

/*將每個螞蟻所抽出的試題與用戶輸入的要求進(jìn)行對比*/

perform local pheromone update

/*信息更新（揮發(fā)）*/

vI best←iteration best solution

VGbest←best of vI best and previous global best vGbest

perform global pheromone update

/*全局信息素更新*/

end while

output: Best solution found vGbest. 

/*輸出最佳試卷*/

4 實例分析

在二元蟻群算法用于求解組卷問題中，軌跡的相對重要性α、能見度的相對重要性β、信息素殘留因子ρ、群體規(guī)模m及信息素強(qiáng)度Δτ等參數(shù)的選取方法和選取原則直接影響到組卷過程的全局收斂性和求解效率。因為在二元蟻群算法中，螞蟻在隨機(jī)二進(jìn)制鏈上只需根據(jù)面前兩條邊上的信息素大小進(jìn)行0、1選擇，所以在本算法中信息素殘留因子ρ和群體規(guī)模m及信息素強(qiáng)度Δτ對組卷過程有著非常重要的影響。信息素?fù)]發(fā)因子（1-ρ）直接關(guān)系到螞蟻的全局搜索能力以及組卷的速度，權(quán)衡兩者，取ρ=0.95。二元蟻群算法作為一種并行的隨機(jī)搜索算法，螞蟻在搜索過程中表現(xiàn)出來的信息交流與相互協(xié)作對組卷也會產(chǎn)生非常大的影響。螞蟻數(shù)目多可以提高全局搜索能力及算法的穩(wěn)定性，但收斂速度會減慢，并影響到算法的時間性能；而螞蟻數(shù)目少雖然會提高收斂速度，但會使得全局搜索的隨機(jī)性減弱，穩(wěn)定性差。鑒于本算法的題庫規(guī)模較大，取m=40。信息素強(qiáng)度Δτ為螞蟻在每一次迭代結(jié)束后釋放的信息素，在本算法中為螞蟻在本代經(jīng)歷的最優(yōu)路徑上釋放的信息素量。因螞蟻每次只在兩條路徑中進(jìn)行選擇；Δτ太大，螞蟻則會更多趨向于上次遍歷過的最優(yōu)路徑，使得該路徑上的信息素濃度迅速增大，極易陷于局部最優(yōu)；Δτ太小，則正反饋作用不明顯。所以本算法采用maxmin規(guī)則來限制每條邊上信息素的濃度。

現(xiàn)在采用C語言程序設(shè)計課程進(jìn)行實驗。將1 000道題按要求存于試題庫中，題型要求為選擇題、填空題、編程題、改錯題、判斷題，并且每種題型各200道。為了使試題的各種屬性（如難度、教學(xué)要求、知識單元等）分布合理，試題的該種屬性值用隨機(jī)函數(shù)產(chǎn)生，并給出目標(biāo)試卷的要求。算法中，wi=1(i=1，2，3，4，5)，考慮五項約束指標(biāo)。教學(xué)要求分為識記、理解、綜合、應(yīng)用（分別用數(shù)字1~4表示），并給出相應(yīng)的分?jǐn)?shù)比例（表1）。知識單元根據(jù)文獻(xiàn)[6]的章節(jié)進(jìn)行劃分，分10個章節(jié)（分別用數(shù)字1~10表示）并給出各章節(jié)的分?jǐn)?shù)比例（表2）。總分100分，時間100 min，難度系數(shù)為0.6。

表1 教學(xué)要求分值分布

教學(xué)要求分值

表2 各知識單元分值分布

運行350代后，產(chǎn)生的標(biāo)準(zhǔn)化試卷如表3所示，基本上能滿足用戶的組卷要求。

表3 生成試卷

題號題型題分難度系數(shù)知識單元教學(xué)要求估時

注：本試卷總試題數(shù)為32。其中選擇題（x）10道，填空題（t）10道，編程題（b）2道，問答題（w）5道，改錯題（g）5道。

生成試卷教學(xué)要求分值分布（表4）和知識單元分值分布（表5）與樣本值進(jìn)行對照。

表4 生成試卷教學(xué)要求分值分布

教學(xué)要求分值

表5 生成試卷各知識單元分布值分布

章節(jié)分值章節(jié)分值

實驗結(jié)果表明，用二元蟻群算法產(chǎn)生的試卷總體誤差約為14，比用傳統(tǒng)的隨機(jī)抽題法（如螞蟻運行第一代時產(chǎn)生的試卷總體誤差為130.138）產(chǎn)生的試卷效果要好得多。當(dāng)然，增大題庫規(guī)模時，該算法還是會得到滿意的結(jié)果，并不會受到題庫規(guī)模的限制，只不過運行的時間會稍微長些。

5 結(jié)束語 

二元蟻群算法作為一種新型的人工生命模型，其單個螞蟻是簡單的、短視的、具有非常有限的感知能力，并且只會進(jìn)行簡單的推理，而整個蟻群群體卻能夠涌現(xiàn)出智慧性、靈活的自適應(yīng)性和自組織特性。本文成功地為組卷問題提供了一種新的高效而實用的方法，該算法適用于各門課程。結(jié)果表明：用該算法生成的試卷較好地滿足了各個控制指標(biāo)的分布要求，效果明顯優(yōu)于傳統(tǒng)的試題組卷算法（如隨機(jī)抽題法等），并且若與遺傳算法相結(jié)合，效果將會更加突出。

參考文獻(xiàn)：

［1］DORIGO M，CARO G D.Ant colony optimization:a new metaheuristic[C]//Proc of the Congress on Evolutionary Computation. Washington DC:[s.n.]，1999:14701477.

[2]DORIGO M，GAMBARDELLAL M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Trans on Evolutionary Computation，1997，1(1):53-66.

[3]魏平，熊偉清，王小權(quán).DNA計算求解連續(xù)空間優(yōu)化問題[J].計算機(jī)應(yīng)用研究，2006，23(1):151153.

[4]熊偉清，魏平.二進(jìn)制蟻群進(jìn)化算法[J].自動化學(xué)報，2007，33(3): 259-264.

[5]魏平，熊偉清.用遺傳算法解組卷問題的設(shè)計與實現(xiàn)[J].微電子學(xué)與計算機(jī)，2002，19(4)：48-50. 

[6]譚浩強(qiáng).C語言程序設(shè)計教程[M].北京:高等教育出版社，1998.