基于二元蟻群算法求解組卷問題
2008-12-31 00:00:00程美英熊偉清魏平
計算機應用研究 2008年9期
摘 要：通過分析組卷的數學模型及目標函數，抽象出組卷模型實質是一個多目標線性規劃模型，并將二元蟻群算法用于求解組卷問題。由于采用二進制編碼，任意時刻每只螞蟻只需根據其面前兩條路徑上的信息素強度決定該題選或不選，這對單個螞蟻的智能行為要求非常低，而且存儲空間也相對減少。實驗結果表明，該算法能快速有效地完成組卷過程，具有較強的實用性。
關鍵詞：二元蟻群算法；多目標線性規劃模型；試題組卷；進化計算
中圖分類號：TP301.6 文獻標志碼：A
文章編號：1001-3695(2008)09-2637-03
Composing test paper based on binary ant colony algorithm
CHENG Meiying，XIONG Weiqing，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 abstracted that the composing test paper model was really a multiobjective 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; multiobjective linear programming model; test paper; evolutionary computation
0 引言
目前網絡上的智能組卷系統為數不少，但用戶真正青睞的卻不多。其原因是多方面的，如組建題庫的困難太大、題型比較單一、生成試卷時間過長、誤差太大等，但最主要的是組卷策略問題。智能組卷系統是一種設計型的專家系統，它是指計算機根據出卷人指定的組卷參數，如題目類型數、難度系數、區分度、知識點范圍、完成試題時間等，從題庫中抽取滿足以上組卷約束條件的試題組成試卷。如何保證生成的試卷能最大限度地滿足用戶的不同需要，并具有隨機性、科學性、合理性，一直是眾人思考和追求的目標，而這又完全取決于抽題算法的設計。如何設計一個算法從題庫中既快又好地抽出一組最優解或抽出一組非常接近最優解的實體，涉及到一個全局最優解和收斂速度快慢的問題。以往的組卷算法大多采用隨機抽題法、回溯試探法以及各種改進的遺傳算法。本文將根據實踐提出一種全新的快速而有效的智能組卷算法——基于二元蟻群算法的試題組卷算法。
近年來，集群智能一直是眾多學者研究的熱點之一，如飛鳥如何聚集成群、昆蟲如何集體飛行，螞蟻如何聰明地找到把食物搬運回家的最短路程，并還能形成等級森嚴的社會體系……人類通常的思維習慣是把自然界的某種智慧行為歸功于比這種行為更聰明的造物者的設計。實際上，近年來的人工生命科學研究的結果是，復雜的智能是可以通過簡單的交互作用涌現的。蟻群算法(ant colony optimization， ACO)作為一種新型的模擬進化算法，是由意大利學者Marco Dorigo等人根據螞蟻尋找食物的群體行為提出的[1，2]。其先后在TSP、二次分配、車間調度、圖著色等經典的組合優化問題中得到廣泛的應用。受DNA雙螺旋結構[3]以及遺傳算法的啟發，文獻[4]將其與蟻群算法結合，提出了一種有別于傳統蟻群算法的二元蟻群算法。由于其特殊的隨機二進制鏈式結構，使得該算法在求解連續函數優化以及離散的組合優化（如NP難的整數規劃問題、0/1背包問題）問題[4]時，都取得了非常好的效果。本文將從求解組卷問題的目標函數出發，抽象出了組卷的多目標線性規劃模型，并將該算法應用于求解組卷問題，取得了滿意的效果。
1 組卷問題的數學模型[5]描述
計算機自動組卷過程是在一定題量的試題庫中搜索滿足組卷目標要求的一組試題。組卷中決定一道試題，就要決定n項指標，這里考慮n維向量（題型a1，題分a2，
目標矩陣應滿足如下約束條件：
K為教學要求，即教學約束。教學要求k取值為識記、理解、綜合、應用等具體種類，所占分數由用戶給定。
同理，知識單元、全卷估時、題型、區分度、期望值等約束條件與上面類似，可以由用戶在組卷時給出。
根據組卷的數學模型知道，組卷問題作為典型的多目標優化問題，往往需要同時考慮k個目標，且要求所有目標函數在滿足約束的條件下越小越好。但問題所包含的不同目標往往又存在著一定的沖突，也就是說，多目標優化中多個目標幾乎不可能在同一解上達到最優。在所有的優化問題求解中，必須對解的質量進行評價。最常用的方法是將多個目標根據某種效用函數合成單一的目標，利用單目標函數的優化方法去求解，如目標加權法。其基本思想是賦予問題中的每一個目標一個權重，將所有的目標分量乘上各自相應的權重系數后加起來構成一個新的目標函數。
針對本組卷問題，設計其目標函數為
為第i組卷因素對組卷目標的誤差；f越小，選出的試卷就越滿足用戶的要求。根據用戶輸入具體的組卷要求，可以得出目標函數中變量的約束集。這樣就把組卷問題——一個典型的多目標優化問題抽象成為典型的線性規劃問題。2 二元蟻群算法基本模型描述點狀態之間連接的網絡如圖1所示。其中：n表示二進制編碼的長度。
擇1的能見度。由于是二進制編碼，螞蟻無須像傳統蟻群算法那樣采用禁忌表來記錄已經遍歷過的節點，只需根據面前兩條路徑上信息素的大小來進行選擇。此外，隨著時間的推移，信息素會逐漸揮發，ρ是信息素的殘留因子，1-ρ是信息素的揮發因子。經過m時刻，即螞蟻完成一次遍歷后，路徑上的信息素按式（4）（5）進行更新調整。同時為了提高算法的效率，在信息素更新過程中引入maxmin原則，即每一次迭代之后，只有在本次迭代中取得最優的那條路徑上的信息素進行更新。
其蟻群算法以概率1收斂。
3 組卷的二元蟻群算法設計
二元蟻群算法因其特殊的隨機二進制鏈式結構，使得螞蟻每一時刻只需從0和1中進行選擇，而1和0恰好對應著題庫中該題“出”與“不出”，這就使得該算法特別適合于求解組卷問題。算法設計如下：
a）編碼方式。通常情況下，二進制表示法是最有效和最經濟的數據表示法，是自然界中最容易模擬和實現的二值邏輯，這也是二元蟻群算法不同于傳統蟻群算法之處。在實際組卷中每種題型的數目是固定的，且相同題型的分數和答題時間是相同的。這樣就可以將整個二進制碼串按照題型劃分為不同的功能塊；每個功能塊對應一種特定的題型。在本文中，總的編
b）適應度函數的設計。適應度函數是用來評價個體優劣程度的指標，它要求應能滿足待求解問題的特征。二元蟻群算法利用適應度這一信息來指導搜索方向，而不需要適應度函數連續或可導。在本算法中，結合上文所抽象出來的組卷的多目標線性規劃模型，參考式（1）
考慮n個約束條件。其中：wi可以根據用戶對不同組卷約束條件的重視程度而分為強約束、一般約束或弱約束等，并相應取不同的權值，這里取相同的值，即w1=w難度、時間）；ei對應為第i組卷因素對組卷目標的誤差。f越小，選出的試卷就越符合用戶的組卷要求。
c）路徑選擇。各個螞蟻根據圖1進行路徑選擇。由于是二進制編碼，螞蟻無須具有記憶功能，僅根據面前兩條邊的信息素大小進行選題。信息素濃度越大，該題被選擇的概率就越大。d）信息素更新。為了描述信息素的更新過程，首先引入一個二元組（A，T）。其中：A為頂點集，定義為A={a1，a2，…，aLC×VN}；T為信息素軌跡的集合，定義為T={τ(ai，c)|τ(ai，c)∈R，1≤i≤LC×VN，c∈{0，1}}。那么信息素軌跡集合T即可表示成一個2×L的矩陣且T(i，c)=τ(ai，c)。在本算法中，信息素的更新分為兩個步驟：(a)信息素的揮發，用公式表示為τ(ai，c)(t+1)=ρ×τ(ai，c)；(b)根據maxmin規則，即信息素只釋放在具有最優解的螞蟻遍歷過的路徑上，即Δτ×bestij=1/f(sbest)。其中:f(sbest)為每一次迭代的最優解或是全局最優解。
e）非法個體的修正。在本算法中，因標準化試卷每種題型要求的個數是固定的，而螞蟻在遍歷的過程中不可避免地會產生一些非法個體，為了保持種群中個體的合法性就必須對非法個體進行修正。采用的方法如下：在螞蟻完成一次遍歷后，判斷各題型所在的編碼段中1的個數是否滿足各題型要求的出題個數；若不滿足，則在各題型所在的編碼段中隨機產生t位（其中t為該題型要求的個數），選取t個1，然后將多余的1全部置0。這樣經過螞蟻的多代搜索，必然能得到滿足用戶要求的試卷。
f）迭代終止判據。當出現滿足組卷要求（即適應度值達到預先的設定值），或達到最大的迭代次數時，算法終止。
下面本文具體給出二元蟻群算法在試題組卷中應用的偽代碼描述。
input:An objective function f(x)= ni=1wiei
/*f(x)組卷的目標函數*/
initialize pheromone distribution T;
/*初始化路徑上的信息素*/
while (stop condition not met) do
for i=1 to m do/*m為種群中螞蟻的個數*/
vi←empty binary string
/*vi用來存放螞蟻遍歷的二進制碼串*/
for j=1 to LC*VN do
/*螞蟻遍歷二進制鏈的過程，LC*VN 為題庫中總的試題個數*/
choose a value c∈{0，1} for aj
/*螞蟻根據路徑上的信息素大小在{0，1}進行選擇，aj為二進制碼串中的第j位*/
append aj=c to vi
end for
end for
encode and evaluate all the colony size solution
vi，i∈{1…m}
/*將每個螞蟻所抽出的試題與用戶輸入的要求進行對比*/
perform local pheromone update
/*信息更新（揮發）*/
vI best←iteration best solution
VGbest←best of vI best and previous global best vGbest
perform global pheromone update
/*全局信息素更新*/
end while
output: Best solution found vGbest.
/*輸出最佳試卷*/
4 實例分析
在二元蟻群算法用于求解組卷問題中，軌跡的相對重要性α、能見度的相對重要性β、信息素殘留因子ρ、群體規模m及信息素強度Δτ等參數的選取方法和選取原則直接影響到組卷過程的全局收斂性和求解效率。因為在二元蟻群算法中，螞蟻在隨機二進制鏈上只需根據面前兩條邊上的信息素大小進行0、1選擇，所以在本算法中信息素殘留因子ρ和群體規模m及信息素強度Δτ對組卷過程有著非常重要的影響。信息素揮發因子（1-ρ）直接關系到螞蟻的全局搜索能力以及組卷的速度，權衡兩者，取ρ=0.95。二元蟻群算法作為一種并行的隨機搜索算法，螞蟻在搜索過程中表現出來的信息交流與相互協作對組卷也會產生非常大的影響。螞蟻數目多可以提高全局搜索能力及算法的穩定性，但收斂速度會減慢，并影響到算法的時間性能；而螞蟻數目少雖然會提高收斂速度，但會使得全局搜索的隨機性減弱，穩定性差。鑒于本算法的題庫規模較大，取m=40。信息素強度Δτ為螞蟻在每一次迭代結束后釋放的信息素，在本算法中為螞蟻在本代經歷的最優路徑上釋放的信息素量。因螞蟻每次只在兩條路徑中進行選擇；Δτ太大，螞蟻則會更多趨向于上次遍歷過的最優路徑，使得該路徑上的信息素濃度迅速增大，極易陷于局部最優；Δτ太小，則正反饋作用不明顯。所以本算法采用maxmin規則來限制每條邊上信息素的濃度。
現在采用C語言程序設計課程進行實驗。將1 000道題按要求存于試題庫中，題型要求為選擇題、填空題、編程題、改錯題、判斷題，并且每種題型各200道。為了使試題的各種屬性（如難度、教學要求、知識單元等）分布合理，試題的該種屬性值用隨機函數產生，并給出目標試卷的要求。算法中，wi=1(i=1，2，3，4，5)，考慮五項約束指標。教學要求分為識記、理解、綜合、應用（分別用數字1~4表示），并給出相應的分數比例（表1）。知識單元根據文獻[6]的章節進行劃分，分10個章節（分別用數字1~10表示）并給出各章節的分數比例（表2）。總分100分，時間100 min，難度系數為0.6。
表1 教學要求分值分布
教學要求分值
表2 各知識單元分值分布
運行350代后，產生的標準化試卷如表3所示，基本上能滿足用戶的組卷要求。
表3 生成試卷
題號題型題分難度系數知識單元教學要求估時
注：本試卷總試題數為32。其中選擇題（x）10道，填空題（t）10道，編程題（b）2道，問答題（w）5道，改錯題（g）5道。
生成試卷教學要求分值分布（表4）和知識單元分值分布（表5）與樣本值進行對照。
表4 生成試卷教學要求分值分布
教學要求分值
表5 生成試卷各知識單元分布值分布
章節分值章節分值
實驗結果表明，用二元蟻群算法產生的試卷總體誤差約為14，比用傳統的隨機抽題法（如螞蟻運行第一代時產生的試卷總體誤差為130.138）產生的試卷效果要好得多。當然，增大題庫規模時，該算法還是會得到滿意的結果，并不會受到題庫規模的限制，只不過運行的時間會稍微長些。
5 結束語
二元蟻群算法作為一種新型的人工生命模型，其單個螞蟻是簡單的、短視的、具有非常有限的感知能力，并且只會進行簡單的推理，而整個蟻群群體卻能夠涌現出智慧性、靈活的自適應性和自組織特性。本文成功地為組卷問題提供了一種新的高效而實用的方法，該算法適用于各門課程。結果表明：用該算法生成的試卷較好地滿足了各個控制指標的分布要求，效果明顯優于傳統的試題組卷算法（如隨機抽題法等），并且若與遺傳算法相結合，效果將會更加突出。
參考文獻：
［1］DORIGO M，CARO G D.Ant colony optimization:a new metaheuristic[C]//Proc of the Congress on Evolutionary Computation. Washington DC:[s.n.]，1999:14701477.
[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]魏平，熊偉清，王小權.DNA計算求解連續空間優化問題[J].計算機應用研究，2006，23(1):151153.
[4]熊偉清，魏平.二進制蟻群進化算法[J].自動化學報，2007，33(3): 259-264.
[5]魏平，熊偉清.用遺傳算法解組卷問題的設計與實現[J].微電子學與計算機，2002，19(4)：48-50.
[6]譚浩強.C語言程序設計教程[M].北京:高等教育出版社，1998.
