李可欣

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

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

1 引言

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

2 研究現(xiàn)狀

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

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

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

3.1 算法描述

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

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

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

Step3 選擇。選擇N個(gè)子個(gè)體的種群 。

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

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

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

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

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

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

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

⑴將父代群體X中所有個(gè)體的適應(yīng)度的總和計(jì)算出來(lái)。

⑵計(jì)算出所有個(gè)體的被選概率。

⑶采用多輪輪盤(pán)賭選擇種群。

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

4 實(shí)驗(yàn)結(jié)果

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

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

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

5 結(jié)束語(yǔ)

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

[參考文獻(xiàn)]

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

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

[3]陳友文.一種改進(jìn)選擇算子和基于小生境的算法.計(jì)算機(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.