劉 鋒 郭維威 田鐵剛

(雞西大學，黑龍江 雞西 158100)

試題組卷算法有很多種，到目前為止還沒有一個令人滿意的解決方案，組卷算法一直是我們需要探討的問題。試題庫系統(tǒng)中對試題的質(zhì)量要求很高，自動組卷的速度與組卷的質(zhì)量取決于組卷算法的優(yōu)劣。如何才能設(shè)計一個合理、高效的算法以便從試題庫中組合成最符合要求的試卷，對此，我們根據(jù)遺傳算法原理進行了研究。

1 遺傳算法原理

1.1 編碼

在遺傳算法中參數(shù)不能直接處理，它只能處理個體，因此必須把參數(shù)形式的問題解轉(zhuǎn)化成為遺傳空間的染色體或者是個體，這個轉(zhuǎn)化過程叫做編碼。近年來所使用的編碼過程形式是多種多樣的，有進制編碼(最常用的編碼方式)、多字符及實數(shù)編碼、樹編碼和自適應(yīng)編碼。其中自適應(yīng)編碼方法的思想就是利用遺傳算法在解決問題時，讓它同時也能夠調(diào)整編碼，以便讓遺傳算法更好地利用它。

1.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)將直接影響遺傳算法的收斂速度及能否找到最優(yōu)解。在遺傳算法中，它的搜索過程不是利用外部信息，而僅把適應(yīng)度函數(shù)作為依據(jù)，然后再利用個體的適應(yīng)度進行搜索。遺傳算法基本的要求是用戶針對輸入可以計算出能夠用以比較的非負數(shù)結(jié)果，就是這個特點使得遺傳算法具有了廣泛的適用性。

1.3 遺傳操作

我們通過編碼過程組成初始群體之后，遺傳操作能夠?qū)Τ跏既后w中的個體按照它對環(huán)境的適應(yīng)程度來加以運行，從而實現(xiàn)優(yōu)勝劣汰的進化過程。通過這個過程，遺傳操作可以把問題解進一步地優(yōu)化，進而接近最優(yōu)解。遺傳操作包括三個基本算子。

2 組卷算法設(shè)計與實現(xiàn)

2.1 編碼初始化

初始染色體群體中染色體的長度為n，大小為m。如果m很小，很難求得最優(yōu)解，過大反而會增長收斂時間。群體大小一般按經(jīng)驗或試驗給出m=30～160的范圍。例如在“Visual Basic程序設(shè)計”這門課程中，要求試卷總分值為100分，程序閱讀(30%)、選擇題(30%)、編程題(40%)。在試題庫中，程序閱讀的分值有兩種6分、10分、20分，選擇題的分值有10分和20分的，編程題有10分和20分的，那么可以看出程序閱讀題占10個基因(5個6分，3個10分，1個10分與1個20分)，選擇題占6個基因，編程題占13個基因，那么染色體總長度為29。

2.2 適應(yīng)度函數(shù)

一般情況下，適應(yīng)度函數(shù)由目標函數(shù)轉(zhuǎn)換而成，其適應(yīng)值越大個體就越好，適應(yīng)值越小則個體越差。本文采用的方法將目標函數(shù)f轉(zhuǎn)換為適應(yīng)度函數(shù)F′，當f<100時，F(xiàn)′=100-f，當f為其他值時，F(xiàn)′=0。指數(shù)的比例可以提高個體之間的相互競爭，所以對F′采取指數(shù)比例變換的這種方法可以轉(zhuǎn)換為適應(yīng)度函數(shù)，則f=exp(-βF′)，β的值為-0.03。

2.3 遺傳算子設(shè)計

在選擇算子的設(shè)計中，為了保留遺傳操作中較優(yōu)的個體，保持群體的大小不變，可以刪除適應(yīng)度隊列后面的2個個體，再隨機抽取隊列最前面的m-2個個體p(p≤m-2)進行交叉與變異操作。在交叉算子設(shè)計中，遺傳操作利用了分段思想，交叉時按照題型段進行交叉，因此不存在試題重復(fù)的問題。每種題型的題量也不會發(fā)生變化，交叉概率pc按照經(jīng)驗值應(yīng)該在0.4～0.6之間。變異算子設(shè)計過程中，變異在題型段內(nèi)進行，變異概率pm一般按照經(jīng)驗值控制在0.01～0.2之間。

3 組卷結(jié)果測試與分析

為了驗證算法的可行性與有效性，我們以“Visual Basic程序設(shè)計”這門課程為例，以雞西大學計算機軟件技術(shù)專業(yè)學生Visual Basic程序設(shè)計建立試卷模板。在這次試驗中，試題庫中共有600道題，分別為判斷、單選、簡答、填空和應(yīng)用共5種類型題，這5種試題的數(shù)分別為100,150,150,100，100；各種題型的分數(shù)比例為2∶3∶6∶8∶20。系統(tǒng)組卷要求為100滿分,難度系數(shù)0.75(即期望平均得分為75分)。利用遺傳算法設(shè)計的系統(tǒng)在抽題時，變異概率pm和交叉概率pc的確定非常重要。pc過小會使抽取的試題過程緩慢，過大將會破壞高適應(yīng)值的試題模型，按照經(jīng)驗值控制在0.4左右。pm過小不會產(chǎn)生新的試題模型，過大則產(chǎn)生的試題模型過多，最好控制在0.1左右。試驗表明，參數(shù)的選擇是非常重要的，即交叉概率在0.6～1.0之間，變異概率應(yīng)該在0.001～0.01之間，群體規(guī)模控制在50～80時，利用試題庫系統(tǒng)可以有效地解決組卷問題，很快地組合成用戶滿意的試卷。

目前，試題庫建立與試卷生成系統(tǒng)已應(yīng)用在黑龍江技師學院的考務(wù)管理中，在雞西大學的“Visual Basic程序設(shè)計”和“操作系統(tǒng)”等課程中也得到了具體的應(yīng)用。經(jīng)過一年的應(yīng)用，結(jié)果表明：該系統(tǒng)是合理有效的，具有較高的研究價值和市場應(yīng)用價值。

參考文獻：

[1]劉鋒.試題組卷算法的研究與應(yīng)用[J].雞西大學學報，2008，(12).

[2]殷霖.遺傳算法在自動組卷中的應(yīng)用[J].廊坊師范學院學報，2011，(3).

[3]趙永虹.組卷算法研究與實現(xiàn)[J].現(xiàn)代電子技術(shù)，2011，(4).