智能組卷系統的研究

李可欣

摘 要：本文研究智能組卷系統，針對傳統遺傳算法極易未成熟收斂和后期搜索效率低的情況，引入小生境技術，提出優化的混合遺傳算法，改進了組卷策略等關鍵技術，實驗結果表明，新算法在全局搜索性能和收斂速度上有顯著提高。

關鍵詞：智能組卷；遺傳算法；小生境

1 引言

目前，教育也面臨著現代化和智能化[1]。基于網絡的考試充分利用了網絡無限廣闊的空間，可以隨時隨地對學生進行考試，試卷由系統從題庫中隨機抽取產生，因而有效的避免了考試作弊和試題泄露等問題的發生，保障了考試的公平性和安全性[2]。因此，智能組卷系統研究是一項具有非常重要意義的實際課題。

2 研究現狀

隨著計算機軟硬件技術的飛速發展，特別是計算機網絡技術的日新月異，信息處理技術和數據庫系統等新技術為考試系統的發展提供了新動力。

然而，現有組卷系統常采用隨機選取法、回溯試探法和遺傳算法等[3]。前兩者耗時長，組卷成功率低；而遺傳算法GA（Genetic Algorithms）[4]雖然是一種全局優化搜索算法，但容易陷入局部最優，產生早熟現象。遠遠無法滿足智能考試取代傳統筆試的要求。

3 優化的組卷算法

3.1 算法描述

優化的混合遺傳算法是在遺傳算法的基礎上，引入了小生境算法的思想，改進了自適應交叉和變異算子。算法步驟如下：

Step1 隨機產生N個個體組成初始種群，設置進化代數計數器t=1，求出每個個體的適應度 。

Step2 按照個體適應度值進行排序，并計算出各個個體的被選概率 。

Step3 選擇。選擇N個子個體的種群 。

Step4 交叉。用自適應交叉運算對種群 進行操作，得到 。

Step5 變異。用自適應變異運算對種群 進行操作，得到 。

Step6 對新一代種群適應度值 進行計算。

Step7 進行小生境淘汰運算。求出 中每兩個個體bi和bj之間的海明距離，得種群 。

Step8 終止條件判斷。如果現階段不滿足終止條件，將 作為新的一代群體 ，轉Step3；若滿足終止條件，則輸出結果，算法結束。

3.2 優化選擇算子

設父代種群 個體的適應度為 ，子代群體初始為 ，則具體選擇算子的過程為：

⑴將父代群體X中所有個體的適應度的總和計算出來。

⑵計算出所有個體的被選概率。

⑶采用多輪輪盤賭選擇種群。

⑷對所有被選擇的個體進行存儲。然后返回。

4 實驗結果

為了驗證改進的混合遺傳算法的可行性和有效性，以《大學計算機基礎》為例，針對計算機基礎課題庫，按照上述思想用就java語言編制了程序，進行組卷試驗。

我們將遺傳算法和優化的混合遺傳算法通過進化相同代數，比較兩種算法產生的最優解的適應度值。取進化代數為10、20、50、100、200，小生境半徑取0.5，運行后，如下表1所示：

由上表對比可看出：傳統的遺傳算法，在早期便可獲得次優解，在后代中存在大量的局部最優的近親子孫，很難有有意義的新個體產生。而優化的混合遺傳算法采用了自適應調整交叉和變異算子技術后，函數的收斂速度明顯加快，獲得的解更優。

5 結束語

智能組卷系統涉及到合理的軟件架構、綜合全面的組卷規則和強大的組卷算法，本考試系統在湖南工學院試運行的過程中，為計算機基礎課相關內容的的練習和考試都帶來了很多便利之處，取得了良好的效果，并且大幅度提高了學生計算機等級考試的過級率。

[參考文獻]

[1]陳磊.通用考試系統的設計與實現.計算機工程，2007，17（2）：140～143.

[2]楊永斌.網絡智能試題庫系統建設研究.計算機科學，2007，12（8）：296～298.

[3]陳友文.一種改進選擇算子和基于小生境的算法.計算機與數字工程， 2009，6（236）：21～24.

[4]Dirk Krafzig，Karl Banke.Enterprise SOA：Service-Oriented Architecture Best Practices.Prentice Hall PTR，2004：21～23.