高校試題庫(kù)組卷算法的研究與實(shí)踐

劉 鋒 郭維威 田鐵剛

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

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

1 遺傳算法原理

1.1 編碼

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

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

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

1.3 遺傳操作

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

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

2.1 編碼初始化

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

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

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

2.3 遺傳算子設(shè)計(jì)

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

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

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

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

參考文獻(xiàn)：

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

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

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