改進的人工魚群算法在試題庫構建中的應用*

李曉靜，李 攀

（1.濟源職業(yè)技術學院藝術設計系，河南 濟源459000;2.濟源職業(yè)技術學院信息工程系，河南 濟源459000）

引言

隨著計算機和現(xiàn)代教育理念的蓬勃發(fā)展，基于Web 的信息系統(tǒng)應用越來越廣泛，利用網(wǎng)絡考試系統(tǒng)取代紙質考試是近幾年來的一個研究領域.在高等院校中，作為檢驗學生知識和技能掌握情況的主要考核方式之一的紙質考試，由于其過程復雜、效率低下并且較易出錯，漸漸地不能適應高等院校發(fā)展的需要，而基于Web 的網(wǎng)絡考試系統(tǒng)具有方便、靈活、節(jié)省成本、高效率等優(yōu)勢，使其在高等院校的應用中顯得越來越普遍.

使用網(wǎng)絡考試系統(tǒng)，教師平時可以有效地收集試題并保存到試題庫中，考試時的出卷將變得較為輕松，甚至可以完全由計算機自動進行;利用計算機能科學的分析學生的成績情況和教學中的不足環(huán)節(jié).利用試題庫技術可以充分地實現(xiàn)考教分離，提高辦學效益.

1 試題庫組卷策略

試題庫屬性參數(shù)的設置與自動組卷策略是網(wǎng)絡在線考試系統(tǒng)建設中最關鍵的兩個環(huán)節(jié).要完成組卷過程，就要求系統(tǒng)根據(jù)組卷策略輸入的屬性和參數(shù)設置抽取出所要求的試題［1］.在構建組卷策略時，要考慮三方面的內容，即試題屬性項目的定義、試題組卷參數(shù)的定義和試題變換算法的說明，其中要充分考慮試題查詢參數(shù)的定義和對所定義的參數(shù)使用的算法等.

試題庫自動組卷需要設置試題的一些屬性，如:難度系數(shù)、區(qū)分度、題目分值等，根據(jù)屬性和組卷策略自動生成試卷.具體步驟如圖1 所示.

2 人工魚群算法描述

通過對魚群集體合作尋食行為的分析，李曉磊等人于2002年提出了一種新型的尋優(yōu)算法，即人工魚 群 算 法 （Antificial Fish Swarm Algorithm，AFSA）［2］，該算法模擬出魚群之間相互協(xié)作提高群體效益的方法.

AFSA 算法中有多條“人工魚”共同存在，集體合作尋優(yōu)，這種行為類似于魚群尋找食物，其中一條“人工魚”代表了AFSA 中的一個備選解.設定有一個包含n 條人工魚的群體所構成的目標搜索空間中，定義向量為第i 條人工魚的狀態(tài)，那么每條人工魚的狀態(tài)就是該目標搜索空間的一個潛在解，即欲尋優(yōu)的變量，記作:Xi=（xi1，xi2，…，xin）（i =1，2，…n）.Xi值優(yōu)劣的衡量取決于函數(shù)值的大小，該函數(shù)值的計算可通過將所得到的潛在解Xi帶入被優(yōu)化的函數(shù)，以所得到的最小值為最優(yōu)值.簡而言之，就是將一群人工魚（隨機解）作為AFSA 的初始化狀態(tài)，這些人工魚通過覓食行為、聚群行為、追尾行為在迭代優(yōu)化函數(shù)過程中，逐步更新自己，生成新魚群，從而實現(xiàn)全局最優(yōu).

以上所描述的人工魚群算法模型中，每條人工魚為了從覓食、聚群和追尾中選擇一種行為實際執(zhí)行，就要探索它當前所處的環(huán)境和伙伴的狀況，當尋找到最優(yōu)的解時，人工魚將會集結在幾個局部極值周圍.在通常情況下，求最優(yōu)解時，為了更方便獲取全局極值域，會將適應值較大的人工魚集結于值較大的極值區(qū)域周圍.作為一種新型的高效尋優(yōu)算法，該算法的收斂速度不但快，而且還可以有效地解決實時性問題;特別是在精度要求不太高的情況下，使用該算法可以更快地找到解決方法.該算法模型如下所示:

3 試題抽取算法中對人工魚群算法的約定

3.1 試題樣本空間及個體距離的約定

在網(wǎng)絡在線考試系統(tǒng)中，將要抽取的試題方案表示為魚群的單個個體.假如在考試系統(tǒng)中有四道題，分別為:第一題、第二題、第三題和第四題，那么在抽取題目的過程中，搜索空間中的狀態(tài)1100 表示抽取第一題和第二題，而不是抽取第三題和第四題;在搜索空間中，每個狀態(tài)都能表示一個個體，每兩個個體之間的距離就是這兩個狀態(tài)之間差異的程度，比如一個個體狀態(tài)是0101，另一個個體狀態(tài)是0011，那么這兩個狀態(tài)之間共有2 位不同，也就是說它們之間的距離是2.

3.2 人工魚食物濃度的計算

任一狀態(tài)的食物濃度計算公式如下:

在該公式中，將需覆蓋而未覆蓋的葉子知識點數(shù)量記為UC;將考試范圍內葉子知識點總量記為NC;并依據(jù)試題的難易程度（困難、較困難、普通、較簡單、簡單）將分值依次記為L1 至L5;依據(jù)教師規(guī)定題目的難易程度（困難、較困難、普通、較簡單、簡單）將分值記為NL1 至NL5;則有L =L1 +L2 +L3+L4 +L5;NL=NL1 +NL2 +NL3 +NL4 +NL5;D 表示該試題的區(qū)分度;W1、W2、W3和W4 分別表示在搜索過程中知識點覆蓋率、難度差異、總分差異和區(qū)分度的重要程度，默認比例是1∶ 1∶ 1∶ 1.由上式不難看出在這里適應度函數(shù)值是越小越好［3］.

3.3 人工魚行為約定

當人工魚搜索行為開始后，首先在其視野內隨機選擇一個狀態(tài)，產(chǎn)生一個魚群，魚群中的個體隨機產(chǎn)生.種群數(shù)量確定后，進行追尾行動，每條魚Xi能查看到距離小于Visual（Visual為可視域）的其他魚（可根據(jù)搜索空間指定），在這里將最小適應函數(shù)值記為Xj，將適應度函數(shù)值記為Yj，并用nf表示最小適應函數(shù)值Xj可視區(qū)域內的人工魚數(shù)量，當Yj·nf＜δ·Yi（δ 表示擁擠度因子，此處取1）時，表示當前最小適應函數(shù)值周圍“食物”較多且不太擁擠，這時就要對比Xi、Xj的值，并對不相同的位重新取值（比如Xi是1010，Xj是0011，則要對Xi的第1 位和第4位重新隨機取值），從而使Xi的值趨向于Xj［4］.在追尾行為不成功的情況下，就要重新執(zhí)行聚群活動，為了重新形成一個魚群，每條人工魚都要在可視區(qū)域內找到其它魚，并且確定魚群的中心點，方法是:假如魚群中有一半的魚第i 位值為1，那么魚群中心點的第i 位值也為1，否則就為0，接著再次進行追尾活動，采用前面的方法檢測中心點周圍的“食物”數(shù)量和擁擠程度，并據(jù)此決定是否進行聚群行為［5］.假如不能進行聚群行為，則要重新進行覓食行為，“人工魚”隨機選取自身的Visual 個位，通過隨機變換得到一個新的狀態(tài)，假如所得到的新狀態(tài)比原狀態(tài)優(yōu)越，則趨向于新狀態(tài)，否則就要再次進行覓食行為，如果重復覓食行為m 次后仍然沒有找到更好的狀態(tài)，“人工魚”就要進行隨機運動（m 值由搜索空間決定）［6］.

4 海量試題抽取的算法改進，基于AFCM 的試題抽取

運用上面所述的人工魚群算法進行試題抽取，在試題庫的題量較少的情況下效率較高，但在海量題庫的情況下性能就明顯降低了.為了解決這個問題，我們嘗試引入基于人工魚群的模糊C 均值（Fuzzy C－means，F(xiàn)CM）的改進算法（AFCM）.其基本思想如下:

將題庫中所有試題作為AFCM 的樣本空間，首先對所有試題按要求進行歸類（尋找聚類中心），歸類的原則可以是試題難度、知識點分布、區(qū)分度等，也可以是幾者的結合.經(jīng)過歸類，可以將試題按預設規(guī)則劃分成不同的子集，然后在已經(jīng)優(yōu)化的局部試題集的基礎上再一次執(zhí)行人工魚群抽取算法.這樣可以將全局的試題抽取轉化為局部的最優(yōu)抽取，可以有效地提高海量試題抽取的效率.

5 結論

根據(jù)試題庫建模理論，結合對各種試題抽取算法的實踐與研究，通過使用AFCM和人工魚群算法相結合的方法，對海量試題抽取時的效率進行了改進，取得了很好的效果.在實踐中，運用軟件工程的思想，采用微軟.NET 平臺的C#語言和ASP.NET 技術，實現(xiàn)了基于WEB 的在線綜合考試系統(tǒng)，整個系統(tǒng)采用三層B/S 架構實現(xiàn)，后臺數(shù)據(jù)庫端采用了SQL 分布式視圖的技術以提高數(shù)據(jù)訪問的性能，前臺采用基于JQUERY和WEB 服務的AJAX 技術提供無刷新界面以提高用戶體驗.同時，我們模擬構造了大試題量的試題庫，經(jīng)過運行實驗，在WEB 環(huán)境下對試題的抽取性能有很大的提高，基本上達到了我們的目的.目前，我們正在對基于人工魚群的FCM 算法和人工魚群算法進行深層結合，使之在大批量試題的抽取上性能更加提高，更具應用價值.

［1］肖洋，王強，劉鳳新.在線考試組卷算法研究［J］.北京化工大學學報，2006，33（4）:44－47.

［2］李曉磊.一種新型的智能優(yōu)化方法—人工魚群算法［D］.杭州:浙江大學，2003.

［3］陳磊，姜薇.通用考試系統(tǒng)的設計與實現(xiàn)［J］.計算機工程與設計，2007，28 （17）:4285－4288.

［4］歐麗輝.基于遠程教育的網(wǎng)絡考試的設計與構想［J］.中小企業(yè)管理與科技，2011，（7）:279－280.

［5］李曉磊，路飛，田國會.組合優(yōu)化問題的人工魚群算法應用［J］.山東大學學報:工學版，2004，34（5）:64－67.

［6］高尚，楊靜宇.群智能算法及其應用［M］.北京:中國水利水電出版社，2006.