劉召華?李建良

摘 要：隨著計(jì)算機(jī)技術(shù)的發(fā)展，利用計(jì)算機(jī)存儲(chǔ)大量的試題信息并結(jié)合數(shù)據(jù)庫(kù)技術(shù)實(shí)現(xiàn)試題的自動(dòng)組卷功能已成為一項(xiàng)實(shí)際可行且應(yīng)用性廣泛的課題。本文就試題組卷遺傳算法進(jìn)行了論述和總結(jié)。

關(guān)鍵詞：自動(dòng)組卷；遺傳算法；試題庫(kù)

隨著信息技術(shù)不斷發(fā)展，傳統(tǒng)考試方式已經(jīng)不能適應(yīng)現(xiàn)代化考試需求，設(shè)計(jì)開(kāi)發(fā)和應(yīng)用計(jì)算機(jī)考試管理系統(tǒng)成為現(xiàn)代教育教學(xué)改革的一項(xiàng)重要任務(wù)。計(jì)算機(jī)技術(shù)不斷發(fā)展，并結(jié)合現(xiàn)有成熟的數(shù)據(jù)庫(kù)技術(shù)，為計(jì)算機(jī)考試管理系統(tǒng)開(kāi)發(fā)提供了可靠保證?？荚嚬芾硐到y(tǒng)設(shè)計(jì)中，建立一個(gè)好的試題庫(kù)尤為重要，而良好的組卷方法卻是核心。如何保證生成的試卷能最大程度地滿(mǎn)足用戶(hù)的不同需求，并具有隨機(jī)性、科學(xué)性、合理性；尤其在交互環(huán)境下，對(duì)組卷速度要求較高，而一個(gè)在理論上能搜索到全局最優(yōu)的算法可能會(huì)以犧牲時(shí)間為代價(jià)，往往達(dá)不到預(yù)期的效果。因此，選擇一個(gè)高效、科學(xué)的算法是自動(dòng)組卷的關(guān)鍵。以往具有自動(dòng)組卷功能的考試系統(tǒng)大多采用隨機(jī)選取法和回溯試探法。在限制條件狀態(tài)空間的控制下，隨機(jī)選取法有時(shí)能夠抽取出一組令用戶(hù)滿(mǎn)意的試題，但由于它隨機(jī)選取試題的范圍太大，有可能在無(wú)法抽取合適試題的區(qū)域內(nèi)反復(fù)選題，進(jìn)入死循環(huán)，最終導(dǎo)致組卷失敗?；厮菰囂椒ńM卷成功率高，卻以犧牲大量的時(shí)間為代價(jià)。遺傳算法（Genetic Algorithms）以其全局尋優(yōu)和智能搜索技術(shù)，及收斂性好的特性能很好地滿(mǎn)足自動(dòng)組卷的要求。

1. 遺傳算法原理

遺傳算法（Genetic Algorithm，GA）是模擬自然界自然選擇遺傳機(jī)制進(jìn)行搜索尋優(yōu)的方法，通過(guò)模擬生物在染色體層面的各種遺傳優(yōu)化作用而設(shè)計(jì)人工尋優(yōu)方法，GA本質(zhì)上是一個(gè)群體迭代過(guò)程，從一個(gè)隨機(jī)的初始群體出發(fā)，依據(jù)優(yōu)勝劣汰原則.通過(guò)競(jìng)爭(zhēng)、選擇、繁衍、變異等遺傳操作，產(chǎn)生性能更優(yōu)的下一代群體。直到滿(mǎn)足環(huán)境約束的優(yōu)良體或合乎具體的應(yīng)用準(zhǔn)則為止。遺傳算法的這種特點(diǎn)使其很適合解決多重條件最優(yōu)解的問(wèn)題。

2. 組卷問(wèn)題的數(shù)學(xué)模型建立

通過(guò)實(shí)際組卷分析，組卷約束條件主要有知識(shí)點(diǎn)，題型，章節(jié)，認(rèn)知層次，題量，分值，答題時(shí)間，難度，區(qū)分度，曝光度等10個(gè)方面。根據(jù)對(duì)上述組卷約束條件的分析，可以構(gòu)建組卷問(wèn)題的數(shù)學(xué)模型。由于一張?jiān)嚲泶嬖?0個(gè)約束變量，所以針對(duì)于整個(gè)試卷所有的題目構(gòu)成了一個(gè)10維度變量的空間：知識(shí)點(diǎn)，題型，章節(jié)，認(rèn)知層次，題量，分值，答題時(shí)間，難度，區(qū)分度，曝光度。為了減小組卷算法的復(fù)雜度，提高組卷算法的效率，需要對(duì)這個(gè)10維空間進(jìn)行化簡(jiǎn)處理。一般而言，要出一份試卷，我們總是先確定試題難度、試卷的滿(mǎn)分值和所用的題型以及各種題型的題目和分?jǐn)?shù)以及知識(shí)點(diǎn)分布，而且對(duì)一種考試而言，這種難度分布常保持相對(duì)穩(wěn)定。不同難度試題的分?jǐn)?shù)分布通常成正態(tài)分布，我們可以根據(jù)難度系數(shù)、各知識(shí)點(diǎn)分?jǐn)?shù)、各題型分?jǐn)?shù)來(lái)約束將要被選中的試題個(gè)數(shù)以及試題難度分布，計(jì)算出不同難度級(jí)別的題目在試卷中所占的比例。再結(jié)合各知識(shí)點(diǎn)、各題型的分?jǐn)?shù)在試卷中所占的比例，可將10維空間簡(jiǎn)化為一個(gè)5維的空間——試卷（知識(shí)點(diǎn)，章節(jié)，題型，分值，難度），在這個(gè)5維空間里對(duì)試題進(jìn)行操作來(lái)完成組卷。不同的計(jì)算機(jī)系統(tǒng)通常采用不同的二進(jìn)制文件格式。

3. 遺傳算法在自動(dòng)組卷中的應(yīng)用

遺傳算法模擬達(dá)爾文的自然界遺傳學(xué)：繼承（基因遺傳）、進(jìn)化（基因突變）和優(yōu)勝劣汰（優(yōu)的基因大量被遺傳復(fù)制，劣的基因較少被遺傳復(fù)制）。其實(shí)質(zhì)就是一種把自然界有機(jī)體優(yōu)勝劣汰的自然選擇、適者生存的進(jìn)化機(jī)制與同一群體中個(gè)體與個(gè)體間的隨機(jī)信息交換機(jī)制相結(jié)合的搜索算法。運(yùn)用遺傳算法求解問(wèn)題，首先需將所要求解的問(wèn)題表示成二進(jìn)制編碼，然后根據(jù)環(huán)境循環(huán)進(jìn)行基本的操作：selection（選擇）、crossover（交叉）、mutation（變異），最后收斂到一個(gè)最適應(yīng)環(huán)境條件的個(gè)體上，得到問(wèn)題的最優(yōu)解。算法步驟如下：

（1）染色體的編碼：假設(shè)試題庫(kù)中有m道題，可用一個(gè)m位的二進(jìn)制串來(lái)表示，形式為：a1，a2，a3 ，...am，，其中若ai為1，則表示該題被選中；若ai 為0，則表示該題未被選中，即ai=1，第i道題被選中；ai=0，第i道題未被選中。

（2）初始化群體：通過(guò)隨機(jī)的方法生成初始化的串群體，在串群體中，串的長(zhǎng)度是相同的，群體的大小按需要根據(jù)經(jīng)驗(yàn)或?qū)嶒?yàn)給出。

（3）計(jì)算當(dāng)前種群每個(gè)個(gè)體的目標(biāo)函數(shù)：本問(wèn)題的目標(biāo)函數(shù)可定義為

F=

Fi表示第i個(gè)屬性指標(biāo)與用戶(hù)要求的誤差的絕對(duì)值，Wi表示第i個(gè)指標(biāo)對(duì)組卷重要程度的權(quán)值，F(xiàn)是所有指標(biāo)與用戶(hù)要求的誤差絕對(duì)值之和。該目標(biāo)函數(shù)越大，則適應(yīng)度越小，被淘汰的概率越大。

（4）選擇：按照一定的選擇概率對(duì)種群進(jìn)行復(fù)制，選擇較好的串生成下一代（個(gè)體的適應(yīng)度函數(shù)值越大，該串的性能越好，選擇概率越大），去掉較差的串。

（5）交叉：交叉是兩個(gè)串按照一定的概率（交叉概率P ），從某一位開(kāi)始逐位互換。首先，對(duì)每個(gè)二進(jìn)制串產(chǎn)生一個(gè)0～1范圍內(nèi)的隨機(jī)數(shù)；若該數(shù)小于P ，則選擇該串進(jìn)行交叉，否則不予選擇。然后隨機(jī)地對(duì)被選擇的二進(jìn)制串進(jìn)行配對(duì)，并根據(jù)二進(jìn)制串的長(zhǎng)度 ，隨機(jī)產(chǎn)生交叉位置i，i為[1，n-1]上的一個(gè)整數(shù)。

（6）變異：變異是二進(jìn)制串的某一位按照一定的概率（突變概率Pm）發(fā)生反轉(zhuǎn)，1變?yōu)?，0變?yōu)?。這里Pm 較小，Pm 可小于0.001。但在實(shí)踐中發(fā)現(xiàn)，在有些遺傳算子中，Pm為0.1時(shí)更好。

（7）終止：記錄進(jìn)化的代數(shù)，并判斷是否滿(mǎn)足終止條件。若滿(mǎn)足，則輸出結(jié)果，否則轉(zhuǎn)向步驟3繼續(xù)執(zhí)行。終止條件如下：（a）出現(xiàn)種群滿(mǎn)足F=0；（b）某個(gè)個(gè)體目標(biāo)函數(shù)值（個(gè)體適應(yīng)度值）達(dá)到指定要求；（c）達(dá)到指定的進(jìn)化代數(shù)；（d）當(dāng)前種群中最大目標(biāo)函數(shù)值與以前各代中最大目標(biāo)函數(shù)值相差不大，進(jìn)化效果不顯著。

遺傳算法在試題組卷中的應(yīng)用可以將教師從繁重的考試出卷等工作中解放出來(lái)，最大限度地減少人為因素在組卷過(guò)程中的影響，最大程度地實(shí)現(xiàn)了組卷的自動(dòng)化，有效提高試卷的質(zhì)量。我們也可以對(duì)簡(jiǎn)單遺傳算法改進(jìn)，利用組卷過(guò)程中的誤差對(duì)遺傳算法中的隨機(jī)性選擇進(jìn)行誘導(dǎo)，保證產(chǎn)生的新個(gè)體的誤差相比對(duì)于同一個(gè)體的其他信息位的變異所產(chǎn)生的新個(gè)體而言，產(chǎn)生的誤差最小。理論分析與實(shí)驗(yàn)結(jié)果表明，基于遺傳算法的試題組卷算法具有較好的智能組卷性能。

參考文獻(xiàn)

1.王小平.《遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)》西安交通大學(xué)出版社，2002

2.張文修，梁怡.《遺傳算法的數(shù)學(xué)基礎(chǔ)》西安交通大學(xué)出版社，2003

3.樂(lè)光學(xué)，彭小寧，曾志峰.試題庫(kù)自動(dòng)組卷系統(tǒng)的算法與實(shí)現(xiàn)，計(jì)算機(jī)應(yīng)用，2001；21（8）：198-200

4.孫勇，柏云.基于遺傳算法的試題組卷策略.淄博學(xué)院學(xué)報(bào)（自然科學(xué)版），2002；（3）：27—28

5.劉彬，李勇，糜長(zhǎng)軍.智能組卷系統(tǒng)中專(zhuān)家知識(shí)的表示與實(shí)現(xiàn).計(jì)算機(jī)工程與應(yīng)用，2002；38（17）：229— 231

6.王慧，劉寶坤，曹明，等.一種改進(jìn)遺傳算法及應(yīng)用.天津理工學(xué)院學(xué)報(bào)，1998；14（4）：62—65