李可欣

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

關(guān)鍵詞：智能組卷；遺傳算法；小生境

1 引言

目前，教育也面臨著現(xiàn)代化和智能化[1]?；诰W(wǎng)絡(luò)的考試充分利用了網(wǎng)絡(luò)無限廣闊的空間，可以隨時隨地對學(xué)生進(jìn)行考試，試卷由系統(tǒng)從題庫中隨機(jī)抽取產(chǎn)生，因而有效的避免了考試作弊和試題泄露等問題的發(fā)生，保障了考試的公平性和安全性[2]。因此，智能組卷系統(tǒng)研究是一項具有非常重要意義的實際課題。

2 研究現(xiàn)狀

隨著計算機(jī)軟硬件技術(shù)的飛速發(fā)展，特別是計算機(jī)網(wǎng)絡(luò)技術(shù)的日新月異，信息處理技術(shù)和數(shù)據(jù)庫系統(tǒng)等新技術(shù)為考試系統(tǒng)的發(fā)展提供了新動力。

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

3 優(yōu)化的組卷算法

3.1 算法描述

優(yōu)化的混合遺傳算法是在遺傳算法的基礎(chǔ)上，引入了小生境算法的思想，改進(jìn)了自適應(yīng)交叉和變異算子。算法步驟如下：

Step1 隨機(jī)產(chǎn)生N個個體組成初始種群，設(shè)置進(jìn)化代數(shù)計數(shù)器t=1，求出每個個體的適應(yīng)度 。

Step2 按照個體適應(yīng)度值進(jìn)行排序，并計算出各個個體的被選概率 。

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

Step4 交叉。用自適應(yīng)交叉運算對種群 進(jìn)行操作，得到 。

Step5 變異。用自適應(yīng)變異運算對種群 進(jìn)行操作，得到 。

Step6 對新一代種群適應(yīng)度值 進(jìn)行計算。

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

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

3.2 優(yōu)化選擇算子

設(shè)父代種群 個體的適應(yīng)度為 ，子代群體初始為 ，則具體選擇算子的過程為：

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

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

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

⑷對所有被選擇的個體進(jìn)行存儲。然后返回。

4 實驗結(jié)果

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

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

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

5 結(jié)束語

智能組卷系統(tǒng)涉及到合理的軟件架構(gòu)、綜合全面的組卷規(guī)則和強(qiáng)大的組卷算法，本考試系統(tǒng)在湖南工學(xué)院試運行的過程中，為計算機(jī)基礎(chǔ)課相關(guān)內(nèi)容的的練習(xí)和考試都帶來了很多便利之處，取得了良好的效果，并且大幅度提高了學(xué)生計算機(jī)等級考試的過級率。

[參考文獻(xiàn)]

[1]陳磊.通用考試系統(tǒng)的設(shè)計與實現(xiàn).計算機(jī)工程，2007，17（2）：140～143.

[2]楊永斌.網(wǎng)絡(luò)智能試題庫系統(tǒng)建設(shè)研究.計算機(jī)科學(xué)，2007，12（8）：296～298.

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

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