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

李曉靜，李 攀

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

引言

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

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

1 試題庫組卷策略

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

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

2 人工魚群算法描述

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

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

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

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

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

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

3.2 人工魚食物濃度的計算

任一狀態的食物濃度計算公式如下:

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

3.3 人工魚行為約定

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

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

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

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

5 結論

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

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

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

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

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

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

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